Binary Search

문제 https://school.programmers.co.kr/learn/courses/30/lessons/64062 풀이 처음 문제를 읽어보고 바이너리 서치를 이용해야겠다고 생각했다. 결정해야 할 값을 건널 수 있는 최대 인원수로 맞춰놓고 바이너리 서치를 이용하여 찾으면 되기 때문이다. 바이너리 서치를 이용한 알고리즘은 다음과 같다. 바이너리 서치를 통해 찾고 싶은 값은 징검다리를 건널 수 있는 최대 인원 수이다. 징검다리 하나의 내구도가 최대 2억이므로 1에서 2억까지의 범위 내에서 인원 수의 최대값을 찾는다 값이 유효한지 체크하는 방법은 징검다리에서 현재 인원 수가 밟은 수를 뺀 다음 0 이하의 징검다리 돌들이 연속되는 경우가 k개 이하면 통과, 초과면 통과시키지 않는다. 바이너리 서치 결과를 리턴한다. 이 코드의 시간 복잡도는 $N$이 stones 배열의 크기, $M$이 돌 내구도의 최대값이라 했을 때 $O(N \log M)$이다. 돌 내구도의 최대값은 2억이고, 2의 30제곱이 약 10억이므로 30번 이내에 찾을 수 있다. 최대 20만 크기의 배열을 30번 정도 반복한다고 생각하면 충분히 시간 복잡도가 나온다. ...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/72412 풀이 많이 해맨 문제다. 처음에는 다음과 같이 알고리즘을 생각했다. 일단 쿼리의 개수와 info 배열의 크기를 생각해보면 filter를 사용하는 문제는 아님 바이너리 서치, Upper bound와 Lower bound의 차이가 해당하는 원소의 개수가 같음 info 배열을 잘 정렬해서 바이너리 서치만 하면 쉽게 해결될 문제 하지만 조금만 생각해보면 이러한 방식의 알고리즘은 문제를 절대로 해결할 수 없다. 우선 쿼리의 조건들이 독립적이다. 정렬 기준에 따라서 포함되어야 할 값이 포함되지 않게 된다. 그렇다고 바이너리 서치 -> 다시 정렬을 반복하기엔 차라리 filter를 쓰는게 더 시간 복잡도가 더 좋다. 다음에 생각한 방식은 트리를 이용하는 방식이었다. ...

문제 https://www.acmicpc.net/problem/1939 풀이 섬(노드)들과 다리(엣지)로 이루어진 그래프가 주어지고, 그 다리들 사이를 지나 목표 노드에 도착해야 한다. 다리에 웨이트가 존재하지 않고 (중량 제한은 엣지가 유효한지 판단하는 기준일 뿐 엣지의 웨이트랑 관련 없다) 최단 거리를 구하는 문제도 아니므로, 다익스트라 알고리즘이 아닌 BFS를 이용해 탐색할 수 있다. 중량이 늘어날수록 건널 수 있는 다리가 적어진다(엣지가 비활성화 된다). 우리는 이 때 주어진 두 섬 중 하나의 섬에서 다른 하나의 섬으로 갈 수 있는 최대의 중량을 구하면 된다. 리니어 서치로도 결과를 구할 수야 있겠지만 현실적으로 1 - 1,000,000,000 값을 다 탐색하는건 너무 비효율적이기 때문에 바이너리 서치를 하면 된다. ...