java
-
BOJ) 회의실배정알고리즘/백준 2020. 7. 11. 20:43
회의실배정 1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 풀이 포스팅하기에는 조금 민망한 코드지만, 정답률이 높지 않아서 포스팅하게 됐다. 회의가 시작시간과 끝나는 시간이 담겨있는 여러 회의에 대해 요청받는다. 이 때, 고르게 분포해서 최대한 많은 팀이 회의를 할 수 있게 만들어야한다. 그래서 처음에는 회의 시간이 가장 짧은 순으로 정렬을 했었다. 하지만, 반례가 존재했고 다시 고민했다. 회의가 끝나는 시간을 기준으로 시작시간이 가장 빠른 순서로 정렬하기로 했다. 회의가 끝나는 시간이 빠른 회의들 중 가장 회의 시간이 짧은 회의들을 채택하는 방법이다. 이후, 정렬된 배열을 돌면서 앞선 회의의 끝나는 시간과 같거나 이후인 회의..
-
BOJ) 로프알고리즘/백준 2020. 7. 11. 20:36
로프 2217번: 로프 N(1≤N≤100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하지만 www.acmicpc.net 풀이 냉정하게 판단하자면 아주 간단한 문제다. 병렬로 로프를 연결하면, 각 로프에 가해지는 무게를 똑같은 무게로 나누어 가질 수 있다는 조건이 있다. 그리고, 각 로프가 최대 견딜 수 있는 하중이 주어진다. 1 2 3 4 5 라는 각각 하중을 버틸 수 있는 로프가 주어진다면, 5 하나만 쓰는 것이 가장 무거운 무게를 들 수 있는지, 5 4를 합쳐서 드는 것이 합리적인지 따져가면 되는것이다. 그래서 우선 입력받은 로프를 정렬해주었다. 자바의 Arrays..
-
BOJ) 30 (자바, JAVA)알고리즘/백준 2020. 7. 11. 20:30
30 10610번: 30 문제 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶� www.acmicpc.net 풀이 N을 입력받는다. N는 최대 10^5개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다. 문제에서 주어진 이 조건을 N의 최대값이 10^5로 읽어서 처음에는 DFS로 시도했다. 하지만, 최대 10^5개의 숫자니까 100000 개의 숫자로 이루어져 있다는 거니까 DFS는 어마어마한 요청이 들어가고 stack over flow가 뜬다.. 런타임 에러가 뜨자마자 왜지?하고 봤더니 10^5가 숫자의 갯수였다. 그래서 로직을 찾아봤다. 30으로 나눠지는 숫자..
-
BOJ) 리모컨알고리즘/백준 2020. 7. 11. 20:22
리모컨 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼�� www.acmicpc.net 풀이 리모콘이 고장나면 고치거나 바꿔야하는데, 그대로 써서 골치아프게한 문제다. 우선, 1~9 버튼과 채널 위아래 이동 + - 버튼 11개가 있는 리모컨이다. 그리고, 입력에서 버튼이 고장난 갯수와 버튼의 위치를 알려주는데, 여기서 런타임에러가 한번 떴다. 처음에는 if(n !=ZERO)를 해주지 않아서, n이 0인 경우 ( 고장난 버튼이 없는 경우 ) 에 입력을 받고 저장하려고 시도해서 에러가 났다. 그래서 if문을 통해 걸러줬다. ..
-
BOJ) 카드 구매하기알고리즘/백준 2020. 7. 8. 20:07
카드 구매하기 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 풀이 갑자기 dp문제를 풀고싶어서 이 문제를 풀었다. 이 문제는 한번에 정답을 맞추지 못했다. 총 세번을 제출했는데, 첫번째는, 에라토스테네스의 체를 이용해서 소수를 판별하는 것처럼, 특정 인덱스 i 에서 n까지 i 씩 증가하면서 초기에 저장된 가격과 i를 여러번 곱한 값 중 더 큰 값을 저장해주었다. for(int i=1; i
-
BOJ) 유기농 배추알고리즘/백준 2020. 7. 8. 19:53
유기농 배추 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 � www.acmicpc.net 풀이 이 문제도 grouping 문제여서, find-union을 써볼까 했지만, 크게 효율적일 것 같다는 느낌이 없었고, 이 문제에 적용하기에는 조금 복잡해질 것 같다고 생각했다. 그래서 그냥 BFS로 풀었다.. ㅎㅎㅎ 총 세번을 제출했고, BFS, BFS, DFS 순으로 제출했다. 첫번째는 평소에 풀던 것 처럼 grouping을 해주면서, gourping이 끝난 이후 저장된 groupIdx를 출력해줬다. 하지만, group을 지어서 값을 변경하거나 이용하지..
-
BOJ) 파이프 옮기기 1알고리즘/백준 2020. 7. 8. 19:37
파이프 옮기기 1 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 풀이 옮길 수 있는 모든 경우의 수를 찾는 문제기 때문에 브루트포스 문제다. 직접 다 돌리는데는 BFS나 DFS만큼 편한게 없다고(?) 생각해서 DFS로 풀었다. 문제를 풀면서 막혔던 부분은 첫째로, 문제 조건을 잘못 이해했다는 것이다. 파이프의 한쪽 끝을 (N, N)로 이동시키는 방법의 개수 이 문구에서 N,N을 보지 않고 N,y or x,N으로 이동한 파이프들을 구해줬었다... 두번째로는 실수라기 보다는 기둥의 시작점..
-
BOJ) 인구 이동알고리즘/백준 2020. 7. 7. 20:28
인구 이동 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모�� www.acmicpc.net 풀이 인접해있는 땅과 인구의 차이가 주어진 L과 R 사이에 존재하면 평균을 내면서, L과 R 사이에 존재하지 않을 때 까지 묶어주는 문제다. 처음 제출하자마자 맞았지만, 효율성이 조금 떨어진다고 생각해서 코드를 수정했다. 얼마 전 포스팅했던 성곽 문제랑 푸는 방법이 비슷하다. grouping을 해주고 각 group의 평균 값을 HashMap에 저장한다. 전체 grouping이 끝나면, 각 gourp마다 평균 값을 넣어주면서 조건에 부합..