이분탐색 고득점 kit 풀이 완료, 후기

이분탐색 알고리즘은 두 가지 선택지(true/false) 중에서 하나를 판단하고 범위를 좁혀 나가서 효율적으로 정답을 찾는 알고리즘이다.

이 알고리즘의 응용으로 1부터 10억까지 숫자중 상대방이 고른 숫자를 yes or no 문답 식으로 약 30번의 질문안으로 맞힐 수도 있을 정도로 매우 효율적인 알고리즘이다.

이분탐색 알고리즘을 프로그래머즈에서 처음 접해봐서 그런지 2개의 문제들은 모두 쉽지 않았다.

접근법을 떠올리는건 동적계획법, 그리디 알고리즘보다 다소 어려웠지만 매우 재미있는 알고리즘인 것 같다. 

이 문제들을 풀면서 이분탐색 기법으로 어떻게 접근하는지 충분히 감을 익힐 수 있었다.

 

제일 먼저 할 일은 정답이라고 가정할 적당한 값을 세우는 것인데, 보통 정답이 될 수 있는 범위의 중간값으로 세우게 된다.

그 후에는 이 값을 정답이라고 가정하고 문제를 검산하면 되는데, 문제에서 정해진 조건 혹은 변수가 검산 했을 때 나온 것와 일치 하는지 확인하는 작업이라고 할 수 있다. 일치 하지 않다면 이들의 대소관계를 비교하여 범위를 어떻게 좁힐지 판단하고, 좁혀진 범위의 중간값을 다시 정답이라고 가정 한뒤 문제를 검산 하는 작업을 반복하면 된다.

보통 이분탐색 문제에서는 궁극적으로 모든 경우들의 최솟값 혹은 최댓값을 물어보므로, 문제에서 정해진 조건 혹은 변수가 검산 결과와 일치 하더라도 정답의 범위의 크기가 1이 될 때 까지 이분 탐색을 계속 해줘야 정확한 정답을 구할 수 있다.

이분탐색은 위와 같은 흐름으로 이루어 지게 된다.

 

모든 문제

[난이도 중] 입국심사 kimcoder.tistory.com/147

[난이도 상] 징검다리 kimcoder.tistory.com/173