이진 검색 ) 10억번의 시행 횟수를 단 30번의 시행으로

작성일 In Views: Disqus:

코딩테스트 문제에서 주어진 데이터들을 순회할 때, 답을 찾기 위해 직접적으로 순회하면 시간 조건을 초과하는 경우가 있습니다. 이 때 시간 복잡도를 줄이기 위해 투 포인터와 이진 검색을 고려합니다. 두 개의 포인터로 정답 도출이 가능할 것 같을 때에 투 포인터 알고리즘을 적용하고, 불가능 할 때에는 이진 검색을 적용합니다.

▪︎ 이진 검색

이진 검색은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘입니다. 탐색 범위를 절반씩 줄여나가면서 값을 찾기 때문에 빠른 속도를 보장합니다.

Untitled

위 배열에서 121이라는 숫자가 몇 번째 index에 있는지를 도출해야한다고 생각해봅시다. index 0부터 순회하며 121을 찾을 수 있지만 배열의 범위를 보면 121이 아닌 더 큰 값이 입력으로 들어왔을 경우 최악의 경우 10^9 번의 동작을 순회해야 합니다. 완전 탐색 포스팅에서 확인했듯이 코딩 테스트에서 우리는 10^8 안으로 시행 횟수를 기준으로 생각하기 때문에 이 방법은 불가능 합니다.

그러면 이진 검색을 활용하면 어떨까요? 최악의 경우에도 30번의 시행만으로 답을 찾아낼 수 있습니다.

▫︎ 이진 검색 구현

  1. 인덱스의 최소값 / 최대값을 변수로 선언합니다.
  2. 범위 내 중간값을 지닌 인덱스에 위치한 요소를 판단하여 121보다 크다면 최대값을 줄여 범위를 좁히고, 작다면 최소값을 높여 범위를 좁힙니다.
  3. 121을 도출할 때까지 2번의 과정을 반복합니다.
1
2
3
4
5
6
7
8
9
10
11
12
let start = 0;
let end = 1000000000;
let answer;

while (start <= end) {
  let mid = Math.floor((start + end) / 2);

  if (array[mid] <= 121) {
    answer = mid;
    start = mid + 1;
  } else end = mid - 1;
}

기본적인 구현 방법은 위와 같고, 도출할 값의 특성에 따라 조금씩 바뀔 수 있습니다. 예를 들어 어떠한 조건에 맞는 최소값을 찾아야 한다면 도출되는 값은 여러개가 될 것이므로 계속 해서 답을 업데이트해야 합니다. 이 때 어떠한 조건문에 답을 업데이트 하는 로직을 추가할지 잘 생각해야 합니다. 위 이진 검색의 구현 코드는 ‘기본적으로 이렇게 작성된다’라고 생각하며 넘어가고 실제 문제 풀이를 통해 어떤식으로 코드가 작성되고 진행되는지 살펴보겠습니다.

▫︎ 최소 / 최대값 도출하기

때때로 코딩테스트에서 범위에 속하는 값들 중 최소 / 최대값을 찾아야하는 경우도 있습니다. 이 경우 위 코드를 조금 변형하여 풀어낼 수 있습니다. 이 때 answer에 mid값을 할당하는 코드의 위치가 중요합니다. 최소값을 구할 때는 end값을 조정할 때 answer값을 재할당 해야하고, 최대값을 구할 때는 start값을 조정할 때 answer를 재할당 해야합니다. 밑에 작성할 문제 풀이를 통해 확인해봅시다.

▪︎ Example of Apply

Untitled

모든 문제에서 처음 완전 탐색이 가능한지부터 생각합니다. 위 문제에서는 N 과 M에 따라 데이터를 몇번이나 순회할지 결정되어집니다. 입력 설명을 볼 때 N의 범위가 1000보다 작습니다. M에 따라 최악의 경우 1000개를 순회하면서 각 요소들을 어떤 DVD에 넣을지를 분기한다면, 시행 횟수는 2^8을 가볍게 넘을 것입니다. 따라서 이진 검색을 통해 나올 수 있는 정답의 범위를 정하고 조건에 부합하는 값 중 최소값을 찾아보겠습니다.

▫︎ 문제 접근

  1. 한 노래를 쪼개서 두 개의 DVD에 녹화할 수 없기 때문에, 용량 크기는 최소한 주어진 배열의 요소 중 최대값보다는 커야한다.
  2. 모두 한 DVD에 넣는 경우보다 용량이 커질 경우는 없다. 따라서 곡의 길이를 전부 합한 값이 최대값이다.
  3. 이진 검색을 통해 조건을 판별한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function solution(m, arr) {
  let answer = 0;
  let start = Math.max(...arr);
  let end = arr.reduce((acc, cur) => acc + cur);

  while (start <= end) {
    let mid = Math.ceil((start + end) / 2);
    let sum = 0;
    let count = 1;

    for (let x of arr) {
      if (sum + x <= mid) sum += x;
      else if (sum + x > mid) {
        count++;
        sum = x;
      }
    }

    if (count <= m) {
      end = mid - 1;
      answer = mid;
    } else if (count > m) start = mid + 1;
  }
  return answer;
}