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번 정도 반복한다고 생각하면 충분히 시간 복잡도가 나온다. ...

소개 수열의 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크면서, 가장 긴 길이를 가지는 부분 수열을 찾는 알고리즘 DP 방식과 Binary Search를 쓰는 Greedy 방식 두 가지가 있으며, 별개의 방식이 아닌 두 방식이 밀접하게 연관되어 있다. 아이디어 LIS는 현재까지 구한 부분 수열의 결과를 이용해 더 긴 부분 수열을 만들어 나가는 문제이다. DP는 이전 계산 결과를 이용해 현재 상태를 구하며, Binary Search를 이용한 방식은 같은 아이디어를 유지하면서 탐색 과정을 최적화한 것이다. ...

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

off by one error 바이너리 서치를 할 때, 경계나 중간 값을 처리하면서 인덱스가 하나 어긋나는 에러 주요 원인은 바이너리 서치에 대한 이해 부족 인덱스 레인지, high / low 갱신 방식, 중간값 계산 방식, 값 리턴 방식을 다양하게 생각해야 함 Binary Search 테크닉 else보다는 else if를 사용하여 조건을 명확하게 표현하기 오버플로우 방지를 위해서는 mid를 계산할 때, (low + high) / 2보다 low + (high - low) / 2를 사용하기 바이너리 서치는 단순히 정렬된 배열에서 값을 찾는 알고리즘이 아니다. 바이너리 서치를 이용하여, 정확한 값을 찾는 경우보다 조건을 만족하는 첫 번째 또는 마지막 위치를 찾는 경우가 더 많다. ...

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