이진 탐색
-
BOJ) 선분 위의 점알고리즘/백준 2020. 8. 28. 02:01
선분 위의 점 11663번: 선분 위의 점 첫째 줄에 점의 개수 N과 선분의 개수 M이 주어진다. (1 ≤ N, M ≤ 100,000) 둘째 줄에는 점의 좌표가 주어진다. 두 점이 같은 좌표를 가지는 경우는 없다. 셋째 줄부터 M개의 줄에는 선분의 시작점과 www.acmicpc.net 풀이 2달 전에 이 문제를 풀다가 계속 시간초과랑 오답이 번갈아 뜨면서 포기했던 문제였다. 오늘도 풀면서 3번이나 틀렸지만 결국 풀어냈다..!! 우선, 문제의 조건에 따라 각 점들은 int형으로 주어지고, 선분의 left, right 범위는 long 타입으로 주어진다. 그리고 완전탐색을 하게되면 가지치기를 엄청나게 잘하지 않는 이상은 시간초과가 뜬다고 생각했다. 그래서 binary search를 이용했다. 점들의 배열을 오..
-
BOJ) 수 찾기알고리즘/백준 2020. 8. 26. 15:31
수 찾기 1920번: 수 찾기 첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안�� www.acmicpc.net 풀이 binary search인 것을 몰랐으면, 아마 시간 초과가 뜨고 나서야 시도했을 것 같다. 하지만, binary search라는 것을 알고 문제를 풀 때는 어렵지 않은 문제다. binary search에서 가장 중요한 것은 여러번 언급했듯, 기준점이다. 이 문제에서는 기준점이 명확하게 특정 숫자다. 특정 숫자를 담고있는 배열의 index를 찾는 문제라고 생각하면되겠다. 기준이 되는 배열은 Arrays...
-
BOJ) 달팽이는 올라가고 싶다알고리즘/백준 2020. 7. 26. 17:27
달팽이는 올라가고 싶다 2869번: 달팽이는 올라가고 싶다 문제 땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다. 달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 �� www.acmicpc.net 풀이 달팽이가 막대의 높이 V까지 올라가는 데, 걸리는 날을 구하는 문제다. A는 달팽이가 낮에 올라갈 수 있는 높이이고, B는 밤에 잠을 자는 동안 아래로 미끄러지는 높이다. 정상에 올라간 후에는 미끄러지지 않는다. 위의 조건으로 미루어 봤을 때, 막대까지 오르는 날 * A 만큼 위로 올라가고, (막대까지 오르는 날 -1) * B 만큼 아래로 미끄러진다. 잠을 자는 동안만 미끄러지고, 높이까지 올랐을 때는 미끄러지지 ..