Algorithm
-
-
BOJ) 자동차경주대회알고리즘/백준 2020. 6. 18. 15:05
자동차경주대회 2651번: 자동차경주대회 첫째 줄에 정비소에서 정비하는데 걸리는 총 정비 시간을 출력한다. 둘째 줄에 방문하는 정비소의 개수를 출력한다. 셋째 줄에는 방문하는 정비소의 번호를 한 줄에 차례로 출력하며 정비소 번� www.acmicpc.net 풀이 이 문제는 DP를 활용해서 풀었다. 정비소의 위치와 걸리는 시간을 담을 배열을 각각 선언해서 값을 저장해줬다. 이 때, 출발 지점인 0과 도착 지점인 마지막 위치도 같은 배열에 저장해서 도로의 출발점과 도착점까지 탐색하도록 설정했다. 각 정비소를 들르면서, 이전까지 최대 이동거리인 maxDist안에 있는 정비소를 찾아 걸리는 시간의 최소값을 구했다. 해당 정비소가 최소 시간을 만족하기 때문에, 걸리는 시간을 더해주면서 마지막 도착지점까지 시간이 ..
-
BOJ) 다음수알고리즘/백준 2020. 6. 13. 20:28
다음수 4880번: 다음수 문제 등차수열(AP)은 인접한 두 수의 차이(공차)가 일정한 수열이다. 예를 들어, 3, 5, 7, 9, 11, 13, ...은 차이가 2로 일정한 등차수열이다. 이 문제에서 등차수열의 공차는 항상 0이 아닌 정수이다. 등 www.acmicpc.net 풀이 이 문제도 복잡하게 생각할 것 없이 간단하게 풀었다. 주어진 숫자들이 등차수열인지 등비수열인지 판별하고, 그 다음 수를 AP num 또는 GP num으로 출력을 해주는 것이기 때문에 판별 메소드를 구해야하나 생각했었다. 하지만, 주어진 숫자의 범위가 |numbers| < 10000 로 매우 협소하고, 다음 숫자를 구해야 하기 때문에 그냥 둘 다 돌리기로 선택했다. 등차수열인지 판별하고 맞다면 다음 수를 담아서 출력하는 isA..
-
BOJ) 빗물알고리즘/백준 2020. 6. 13. 20:22
빗물 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치� www.acmicpc.net 풀이 문제를 처음 맞이했을 때 생각한 것 보다는 꽤나 신경을 써야하는 문제였다. 먼저, 배열을 사용하지 않고 입력받은 값에 대해 구간의 max값을 구해줘서 답을 내주려고 했었다. 0으로 시작하는 구간이나 마지막 값이 0이면 빗물이 생성되지 않는다는 조건 때문에 포기했다. 그래서 배열을 만들고 위의 로직을 시도해볼까 했는데, 너무 복잡해지는 것 같아서 포기했다. 마지막으로 떠올린 것은, 한 구간에 대해 양 옆에 제일 높은 기둥 두개를 찾는 ..
-
BOJ) 조약돌 꺼내기알고리즘/백준 2020. 6. 13. 20:15
조약돌 꺼내기 13251번: 조약돌 꺼내기 첫째 줄에 뽑은 조약돌이 모두 같은 색일 확률을 출력한다. 정답과의 절대/상대 오차는 10-9까지 허용한다. www.acmicpc.net 풀이 단순한 확률 계산 문제였다. 복잡한 수식이 들어가지도 않았고, 예외 처리에 크게 신경써야하는 문제도 아니었기 때문에 간단하게 요약하겠다. 입력 값을 int형 배열에 담으면서, 전체 갯수를 세준다. 이후, 저장된 배열을 돌면서 k개를 뽑을 수 있을만큼 충분하다면, 확률을 구해 답에 더해준다. 12개에서 5개를 연속으로 뽑는다면, 그 확률은 5/12 * 4/11 * 3/10 * 2/9 *1/8 이 된다. 연속으로 뽑는 확률을 모두 더해 답을 리턴한다. 코드 import java.io.BufferedReader; import ..
-
-
BOJ) 백조의 호수알고리즘/백준 2020. 6. 12. 23:29
백조의 호수 3197번: 백조의 호수 문제 두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다. 호수는 가로로 R, 세로로 C만큼의 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있� www.acmicpc.net 풀이 처음 코테를 준비할 때 풀다가 실패한 문제였다. 그게 벌써 1년은 더 지난 것 같다. 1년간 매일같이 코테 연습을 하지는 않았지만, 실력이 많이 늘었을 거란 생각에 다시 도전했다. 하지만, 처참히 깨졌다... 처음으로 짰던 코드는, 가지치기 없이 BFS를 날마다 돌리면서 답을 찾는 것이었다. 6%에서 시간초과가 떴고, 시간 초과를 회피할 오랫동안 생각하다가 떠오르지 않아서 여러 블로그를 참고했다. Union-Find로 문제를 해결한 분들도 계셨..
-
BOJ) 연속합알고리즘/백준 2020. 6. 12. 23:21
연속합 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 오늘 어려운 문제에 여러개 도전하다가 실패해서 그런지 머리가 잘 돌아가지 않았다. 그래서, 예전에 풀었던 기억이 있어서 참고해서 풀었다. 우선, 막혔던 부분은 partialSum을 저장하는 부분이었다. Math.max(0,partialSum)을 통해 해당 번호에서 다시 시작하는게 좋은지, 지금까지 더해왔던 수를 계속 이용하는게 좋은지 판별해주는 부분이 놓친 부분이었다. 이전까지의 합이 양수면, 거기에 더해주는게 더 합리적이기 때문에.. 또한, 0과 비교하는 이..