Dev Club 알고리즘 스터디, 이진 탐색
이번 포스팅에선 Dev Club 에서 참여한 알고리즘 스터디에서 함께 공부 했던 알고리즘 중, 이진 탐색에 대한 내용을 설명한다.
이 스터디는 코딩 테스트에서 일가견이 있으신 Jason 멘토님과 함께 했다.
멘토님께선 초등학교 때부터 알고리즘 문제를 취미로 푸셨고, 커리어에서 많은 코딩 테스트 경험, 라이브 코딩 테스트 경험을 가지고 계신 분이시다. 이 글의 내용은 멘토님이 나눠주신 인사이트임을 밝힌다.
Dev Club은 F-Lab에서 주최하는 개발자들을 위한 커뮤니티로, 다양한 주제로 세미나와 네트워킹 행사를 열고 있다. 월 회비를 크게 할인하고 있어, 부담없이 참여해볼 수 있다.
1. 어떤 문제가 이진 탐색을 써야하는 문제일까?
‘이진 탐색은 어떤 상황에서 사용해야 합니까?’ 라고 질문 받는다면, 뭐라고 대답해야 할까?
‘값이 고유한 데이터들이 정렬되어 있고, 값의 크기에 따라 조건이 만족하거나 불만족하는데 만족하는 값의 최솟값을 찾아야 할 때요.’
와 같이 대답할 수 있을 것 같다. 그런데 알고리즘 문제의 설명 내용 중 어떤 키워드, 혹은 늬앙스가 이진 탐색의 트리거가 되는지는 대답하지 못할 것 같다.
그에 대한 답은 아래와 같다.
- “최솟값과 최댓값이 정해져 있고 그 사이에서 그 조건을 만족하는 가장 작은 값을 찾아라.”
- “어느 순간부터 true가 되고 그 이후는 모두 true다.”
- ~한 값들 중에 최소값을 찾아라.
위와 같은 메세지가 있다면 그것은 이진 탐색을 써야하는 문제이다. 이런 메세지가 있으면 왜 이진 탐색을 써야할까?
실제 문제를 살펴보며 이해해보자.
2. 이론 사용해보기
LeetCode 278 문제에 우리가 배운 이론을 사용해보자.
2.1 문제의 설명
당신은 팀은 새로운 프로젝트를 개발하도록 이끌어 가고 있는 PM이다. 그런데 안타깝게도, 당신의 프로젝트의 마지막 버전은 품질 검사 중 불합격 판정을 받았다. 프로젝트의 각 버전은 이전 버전을 기반으로 개발되었기 때문에 bad version의 이후 모든 버전은 bad version 이다.
당신은 n개의 버전([1, 2, …, n])을 가지고 있는데, 첫 번째 나쁜 버전이 몇 버전인지 찾으려고 한다.
당신은 버전이 나쁜지 여부를 반환하는 API bool isBadVersion(version)을 가지고 있다. 이 API를 이용해 첫 번째 bad version 을 찾는 함수를 구현하라.
2.2 문제를 파악하고 풀이 논리 세우기
문제 속에서 우리가 개발 중인 프로젝트의 각 버전은 이전 버전을 베이스로 만들어지기 때문에, 한 번 bad 버전이 출연하면 이후의 버전은 모두 bad임을 설명하고있다.
’~ 한 조건’을 만족하는 값들 중 최소값을 찾으라는게 요구사항인 문제에서, 조건을 만족하지 않는 값과 만족하는 값이 나뉘어지는 상황이다.
이 상황에서는 어느 순간부터 bad version 이 되고 그 이후는 모두 bad version 이기 때문에, 특정 버전을 확인했을 때 bad version이 아니라면 그 이전 버전들은 확인할 필요가 없다.
따라서, 이진 탐색을 사용하기가 적합하다. 인덱스의 중앙을 확인하고, bad version이 아니라면 확인한 버전의 오른쪽 버전들만 확인하면 된다.
중앙을 확인했을 때 bad version 이라면, 확인한 버전의 왼쪽에 있는 버전(이전 버전) 중에 bad version이 있는지만 확인하면 된다.
가운데를 찍어서 f일 때 왼쪽 값들은 볼 필요가 없게 되는, 효율적인 탐색을 할 수 있는 것이다.
2.3 구현 요령
while(l <= r)과 while(l < r) 와 같은 조건문을 사용해서 이진 탐색을 진행한다고 생각하면 쉽다.
전자는 m = l = r 인 경우도 확인해봐야 할 때 필요한 조건문이다. 이진탐색을 다음 단계로 넘어갈 때 t로 바뀌는게 명확하다면 l <= r 조건을 사용해도 되지만 아니라면 무한 루프에 빠질 위험이 있다.
우리가 1절에서 살펴본 이진 탐색의 냄새가 이제 당신에게 나는가? 그렇다.. 우리는 모두 느끼고 있다.
2.4 문제 풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
int l = 1, r = n;
while (l < r) {
int m = l + (r - l) / 2;
if (isBadVersion(m)) {
r = m;
} else {
l = m + 1;
}
}
return l;
}
}