이분탐색(binary search)

알고리즘 책이나 강의를 보면 항상 초반에 한 가지 탐색 방법이 소개 됩니다. 이분탐색(binary search)라는 이름을 가지고 있는 이 알고리즘은 보통 책이나 강좌의 앞쪽에 소개 되는데다 그 개념 자체가 이해하기 어렵지 않기 때문에 배울 때는 큰 어려움이 없지만, 의외로 코딩테스트의 문제로 만나게 되면 문제를 쉽게 풀 수 없게 만드는 복병이 되기도 합니다.

 

오늘은 이 이분 탐색에 대해 간단히 알아보고 실제 코딩 테스트에서 어떻게 활용할 수 있는지에 대해 생각해 보도록 하겠습니다.

 

사실 이분탐색의 개념은 매우 간단하고 직관적입니다. 이를 설명하기 위해 스무고개 놀이를 한 번 해 보도록 하겠습니다. 1부터 100사이에 있는 숫자를 하나 생각하고 가능한 적은 횟수의 추측으로 이 숫자를 알아내는 방법을 생각해 봅시다. 

 

가장 쉬운 방법은 1, 2, 3, 4 순서대로 추측하고 질문하는 것입니다. 만약 '그 숫자가 1인가요?' 라고 물으면 상대방은 '예' 또는 '아니오' 라고 대답하겠죠. '예'라는 답이 나올 때 까지 숫자를 1씩 더해가면서 질문을 이어가면 됩니다. 이런 방법을 단순 탐색(simple search)라고 하는데요. 이 방법으로 질문 하면 한 번 질문할 때 마다 답이 아니라는 사실만을 알게 될 뿐입니다. 만약 답이 22이었다면 정답을 맞추기 전에 스무번의 질문 기회를 모두 다 써버리게 되겠죠.

 

이분탐색(binary search)

---

당연히 더 좋은 방법이 있습니다. 질문의 방법을 바꾸는 것이죠. 이제는 질문 할 때 마다 그 숫자가 내가 추측한 숫자보다 크거나 같은지를 물어봅니다. 그런데 이렇게 숫자를 1부터 추측해 나가면 모든 숫자는 1보다 크거나 같은 것이 당연하기 떄문에 의미가 없겠죠? 그래서 이번에는 중간 숫자인 50부터 질문을 시작해 나갑니다.

 

만약 '그 숫자가 50보다 큰가요?' 라고 물었을때 대답이 '아니오' 라면 다음 질문은 1부터 49사이의 숫자 중 하나를 골라 질문할 수 있겠죠. 이 때 역시 1부터 49 까지의 숫자 중 중간 숫자에 해당하는 것을 질문하는 것이 가장 효율적일 것입니다. 그러면 다음 질문으로 '그 숫자가 25보다 크거나 같은가요?' 라고 물으면 되겠죠? 이런 질문을 반복해 나가면 금방 정답을 찾을 수 있습니다. 정답이 32라고 정해 놓고 실제로 스무고개를 한 번 해 보도록 하겠습니다.

 

1. 문 : 그 숫자가 50보다 크거나 같은가요?  답 : 아니오
2. 문 : 그 숫자가 25보다 크거나 같은가요?  답 : 예
3. 문 : 그 숫자가 37보다 크거나 같은가요?  답 : 아니오
4. 문 : 그 숫자가 32보다 크거나 같은가요?  답 : 예
5. 문 : 그 숫자가 34보다 크거나 같은가요?  답 : 아니오
6. 문 : 그 숫자가 33 보다 크거나 같은가요? 답 : 아니오
7. 그 숫자는 32 입니다.

결국 우리는 이 방법을 통해 딱 6번의 질문만에 정답을 찾아 냈습니다. 만약 첫번째 방법으로 32라는 숫자를 찾아내려고 했다면 최소한 32번의 질문이 필요했을 것입니다. 

 

이렇게 무엇이든 절반씩 나누어서 탐색하기 때문에 이분 탐색이라는 이름을 가지게 되었다는 것을 쉽게 유추할 수 있겠죠? 그리고 다들 눈치 채셨겠지만 이 방법은 먼저 '정렬된' 원소들에 대해서만 사용할 수 있습니다. 하지만 정렬된 자료에서는 어떤 경우에도 O(log n) 시간 안에 정답을 찾아낼 수 있죠.

 

코드

---

이분 탐색을 코드로 구현하면 다음과 같습니다.(JAVA입니다)

while (start <= end) {
    mid = (start + end) / 2;
    
    ...
    
    if (condition) {
        start = mid + 1;
    } else {
        end = mid - 1
    }
}

 

정렬된 데이터에서 필요한 값을 찾거나, 혹은 필요한 숫자를 찾을 때 이 코드를 사용할 수 있습니다. 개념 자체가 명확하고 직관적인 만큼 코드도 간단합니다. 그러나 우리가 어떤 문제를 풀 때, 이분탐색으로 풀 수 있는 문제인지 무진장 헷갈립니다. 

 

중요한 것은 '무엇을 이분탐색으로 찾을 것인가?' 라는 질문에 들어맞는 답이 존재 해야 한다는 것입니다. 말로 하면 어려우니까 실제 예제 문제를 풀어 보면서 설명해 보도록 하겠습니다.

 

프로그래머스 - 입국심사 문제

---

예제는 프로그래머스에서 제공하는 입국심사라는 문제를 사용하겠습니다. 문제를 보시려면 이 링크를 확인해 주시기 바랍니다.

 

이 문제에서 '무엇을 이분탐색을 찾을 것인가?' 라는 질문에 해당하는 답은 무엇일까요? 제 생각에 그 답은 '심사관들에게 주어지는 시간'입니다. 어떤 시간이 주어졌을 때 심사관들이 몇 명을 심사할 수 있는지를 계산할 수 있기 때문에 몇 명을 심사할 수 있는 지를 주어진 n 비교해 n 보다 크면 시간을 줄이고, n보다 작으면 시간을 늘이는 식으로 필요한 시간을 찾아갈 수 있을 것입니다. 이 때 당연히 이 시간을 찾는 방법은 이분탐색이 되겠죠.

 

말로 하는 것 보다 코드를 한 번 보는 것이 더 빠를테니 코드를 보도록 하겠습니다.

    public long solution(int n, int[] times) {
    	long answer = 0;
        long start = 0;
        long end = Long.MAX_VALUE / 2;
        
        while (start <= end) {
        	long mid = (start + end) / 2;
        	long people = n;
        	for (int time : times) {
    			people -= (long) mid / time;
                if (people < 0) break;
    		}
        	if (people > 0) {
        		start = mid + 1;
        	} else {
        		end = mid - 1;
        		answer = mid;
        	}
        }
        return answer;
    }

 

아직까지 감이 쉽게 잡히지 않으니 예제를 하나 더 풀어 보도록 하겠습니다.

 

프로그래머스 - 징검다리 문제

---

이번 예제 역시 프로그래머스에서 제공하는 징검다리라는 문제를 사용하도록 하겠습니다. 문제를 보시려면 이 링크로 들어가서 확인해 주세요.

 

이번에도 역시 '무엇을 이분탐색으로 찾을것인가'의 답을 생각 해야 합니다. 이전 문제에 비해서 그 답을 찾기가 조금 어렵지만 저는 '바위 사이의 최소 거리' 라고 생각했습니다.

 

바위 사이의 최소거리를 정해놓고 그 최소거리보다 작은 바위들을 다 제거 하는 것이죠. 만약 그 제거하는 바위의 갯수가 주어진 n보다 크다면 거리를 좁혀야 할 것이고, n보다 작다면 거리를 늘여야 합니다. 이 때, 이 최소 거리를 찾는 방법은 당연히 이분탐색이 될 것입니다.

 

백문이불여일코드일테니 코드를 보도록 하겠습니다.

  public int solution(int distance, int[] rocks, int n) {
    
    Arrays.sort(rocks);

    int answer = 1;
    int start = 1;
    int end = distance;
    
    while (start <= end) {
      int mid = (start + end) / 2;
      
      int cnt = 0;
      int last = 0;
      for (int i = 0; i < rocks.length + 1; i++) {
        int gap = i != rocks.length ? rocks[i] - last : distance - rocks[i-1];
        if (gap < mid) {
          cnt++;
        } else if(i != rocks.length) {
          last = rocks[i];
        }
      }
      
      if (cnt > n) {
        end = mid - 1;
      } else {
        start = mid + 1;
        answer = mid;
      }
    }
    
    return answer;
  }

 

거듭 말씀 드리지만 이분탐색은 정렬된 자료에 대해서만 적용가능합니다. 정렬되지 않은 자료에 대해서는 먼저 정렬을 해 주고 사용을 해야 합니다.

 

자, 이렇게 어떤 경우에도 O(log n) 시간안에 답을 구할 수 있는 아주 빠른 알고리즘인 이분탐색의 개념과 실제 코딩테스트에서 나오는 문제 유형을 어떻게 대처하는지 까지 알아 봤습니다. 이분 탐색을 활용해서 풀 수 있는 문제는 아주 많고 다양하지만 오늘은 이 쯤에서 마치도록 하겠습니다.

 

감사합니다.