징검다리 건너기

프로그래머스 2019 카카오 개발자 겨울 인턴십 문제이다.

처음 이 문제를 접했을 당시에만 해도 혹시 DFS 유형의 문제인가...혹은 DP 형식의 문제인가 하면서 왼쪽에서 오른쪽으로 접근하는 방법만 여러번 생각하였고 구현했던 결과 전부 효율성 테스트를 통과하지 못해서 절망했던 문제였다. 결국 이것저것 검색한 끝에 이 문제의 유형은 이진탐색 이란걸 알게되었을때 대체 어떻게 이게 이진탐색류의 문제지? 하면서 혼란스러워 했던거같다.

내가 생각하는 이진탐색이란 기본적으로 벡터가 정렬이 되어있어야하고 특정으로 타겟이 되어있는 숫자를 찾는다던지 항상 탐색에 중점을 두었다 생각했기때문에 문제가 원하는 최대 인원을 구한다는 답에 적합하지 않는다 생각해서 아예 배제하고 있었다. 그러나 이 문제를 통해 이진탐색에 색다로운 접근법을 배웠다.

이진탐색을 할때 가장 중요한거는 무엇을 찾는지를 아는것과 무엇을 비교하는지를 알아야지 범위를 좁혀가면서 탐색할수 있다. 이것만 알게되면 문제를 푸는데 훨씬 도움이 많이 될거고 이해하기 쉬울것이다. 가장 먼저 start 지점을 0으로 지정하고 징검다리에서 가장 큰 값을 end 로 지정했다. 최소값과 최대값의 중간점을 시작으로 해서 징검다리를 건너는게 가능하다면 조금 더 많은 인원을 추가하고 만약에 임의의 값에서 징검다리를 건너는게 불가능하다면 end의 범위를 줄여주면 된다.

배운점:
1. 이진탐색의 활용도는 높다
2. 항상 비교하는 값을 잘 생각하고 활용해보자