오늘은 이분 탐색에 대해서 공부했었다. 이분탐색을 왜 써야하는지 사실 처음에 이해가 되지 않았다. 하지만 이분탐색을 사용하지 않으면 시간초과로 문제가 풀리지 않았다.
백준 문제: 1920번 / 수 찾기
GitHub: 코드보기
그래서 먼저 이분 탐색이 무엇인지 먼저 찾아보았다. 정리는 아래 블로그에 정리했다.
블로그 : 이분탐색이란?
이분탐색을 재귀함수로 만들어 놓으면, 나중에 다른 문제를 풀 때 편할 것 같았다. 그래서 start index
와 end index
를 넣고, 찾기를 희망하는 target
값을 매개변수로 넣어놓으면, 이분탐색을 통해서 재귀하면서 target
과 동일한 값의 위치를 리턴해주는 함수를 만들었다.
이분탐색을 계속해서 재귀하게 되면 start
와 end
가 결국에는 겹치는 형태이기 때문에 이를 잘 이해하고 사용해야 할 것 같다.
알고리즘을 조금씩 알아가면서 느끼는 점은 이제 문제를 보면 어느 유형의 문제인지 어느 정도 유추를 할 수 있을 것 같았다. 알고리즘 주차가 끝나더라도 계속 꾸준하게 백준 문제를 풀어봐야겠다.