2.4Divide and Conquer

Divide and Conquer

Divide and Conquer(분할 정복) 패턴은 문제를 더 작고 동일한 구조의 문제로 분할(divide)하고, 그 각각을 재귀적 또는 반복적으로 해결(conquer)하여 전체 문제를 푸는 전략이다.

이 패턴은 정렬이나 탐색처럼 대규모 데이터를 효율적으로 처리할 때 매우 유용하며, 대표적인 예로 Binary Search, Merge Sort, Quick Sort 등이 있다.

예시 1:

정렬된 정수 배열이 주어졌을 때, 특정 값이 존재하는 인덱스를 반환하는 함수를 작성하라.

javascript
search([1, 2, 3, 4, 5, 6], 4) //3

비효율적인 풀이는 아래와 같다. Linear Search라고 하는 방식으로, 단순히 for 루프로 처음부터 끝까지 찾는 방식이다. O(n)의 시간 복잡도를 가진다.

javascript
function search(arr, val){
  for(let i = 0; i < arr.length; i++){
    if(arr[i] === val){
      return i;
    }
  }
  return -1;
}

다음은 효율적인 방식으로, Binary Search라고도 한다. 배열이 정렬된 것을 이용하는 방법으로, 중앙 값을 기준으로 좌우를 나눠가며 탐색을 반복한다. 시간 복잡도가 O(log n)으로 줄어든다.

javascript
function search(array, val){
  let min = 0;
  let max = array.length -1;

  while(min <= max){
    let middle = Math.floor((min + max) / 2);
    let currentElement = array[middle];

    if(array[middle] < val){
      min = middle + 1;
    } else if (array[middle] > val){
      max = middle -1 ;
    } else {
      return middle;
    }
  }
  return -1;
}

Divide and Conquer는 특히 탐색, 정렬에 많이 쓰이는 패턴으로 앞으로도 많이 볼 수 있을 것이다.

---

🤠 문제 풀이

강의에선 Divide and Conquer를 활용한 문제를 몇가지 제시한다.

1. countZeros

1과 0으로 구성되어 있고, [1, 1, 1, ... 0, 0, ...0] 형태로 1이 쭉 붙어있다가 0으로 이어지는 배열이 주어질 때 0의 개수를 세는 함수 countZeroes를 작성하라. 단, 시간 제한은 O(log N)이다.

filter나 for를 쓰면 O(N)이 되므로 binary search를 써야 한다. 기본적으로 본문에서 본 search와 같은 로직이고, 첫번째로 0이 나오는 인덱스를 찾아 배열의 전체 길이에서 해당 인덱스를 빼면 된다.

javascript
function countZeroes(arr){
  let left = 0;
  let right = arr.length - 1;
  let firstZero = arr.length; // 기본값은 0이 없으면 length로

  while(left <= right){
    let mid = Math.floor((left + right) / 2);

    if(arr[mid] === 0){
      firstZero = mid;
      right = mid - 1; // 왼쪽에 0이 더 있을 수 있음
    } else {
      left = mid + 1; // 오른쪽 부분 탐색
    }
  }

  return arr.length - firstZero;
}

2. sortedFrequency

정렬된 숫자들의 배열과 n이 주어지면, 해당 숫자의 빈도를 반환하는 sortedFrequency 함수를 작성하라.

역시 배열이 정렬되어 있으므로 이진 탐색으로 해당 숫자가 첫번째로 등장하는 인덱스와 마지막으로 등장하는 인덱스를 찾을 수 있다. 이렇게 찾은 인덱스들을 이용해 빈도를 계산한다.

javascript
function sortedFrequency(arr, num){
  function findFirst(){
    let left = 0, right = arr.length - 1, first = -1;
    while(left <= right){
      let mid = Math.floor((left + right) / 2);
      if(arr[mid] === num){
        first = mid;
        right = mid - 1; // 더 왼쪽에 같은 값이 있을 수 있음
      } else if (arr[mid] < num){
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    return first;
  }


  function findLast(){
    let left = 0, right = arr.length - 1, last = -1;
    while(left <= right){
      let mid = Math.floor((left + right) / 2);
      if(arr[mid] === num){
        last = mid;
        left = mid + 1; // 더 오른쪽에 같은 값이 있을 수 있음
      } else if(arr[mid] < num){
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    return last;
  }
  const first = findFirst();
  if(first === -1) return -1;
  const last = findLast();

  return last - first + 1;
}

3. findRotatedIndex

정렬되어 있는 숫자의 배열이지만 rotate된(오름차순 방향은 일정하지만 처음부터 시작하는것이 아니라, 중간부터 시작해서 끝나면 다시 처음으로 돌아오는) 배열과 특정 숫자가 주어지면 해당 숫자의 인덱스를 구하는 findRotatedIndex 함수를 작성하라.

배열이 [정렬된 큰 값들] + [정렬된 작은 값들] 구조인데, 이진 탐색처럼 mid를 잡고 양 끝 쪽과 비교해보자.

예를 들어, [6, 7, 8, 9, 1, 2, 3, 4]가 있을 때 mid는 4이고 여기에 있는 수는 1이다. 1이 6보다 큰지 작은지를 비교함으로 mid를 포함해 왼쪽이 정렬이 되어있는지, 오른쪽이 정렬이 되어있는지 확인할 수 있다. 이 경우는 1이 6보다 작으므로 오른쪽이 정렬된 것이다.

만약 8을 찾는다고 할 때, 왼쪽은 정렬이 안되어 있으므로 right에 mid - 1을 할당해서 다시 루프를 본다. 이 때 mid는 1이되고, 여기에 있는 수는 7이다. 7과 left(6), right(9)를 비교하면 7이 더 크므로 왼쪽이 정렬되어 있다. target 8은 7보다 크므로 left에 mid + 1을 할당한다. 이런 작업을 반복한다.

위의 내용을 코드로 작성하면 아래와 같다.

javascript
function findRotatedIndex(arr, target){
  let left = 0, right = arr.length - 1;

  while(left <= right){
    let mid = Math.floor((left + right) / 2);
    if(arr[mid] === target) return mid;

    // 왼쪽이 돌아오는 구간 없이 완벽히 정렬되어 있음
    // 배열의 가운데보다 왼쪽이 더 크면 한번 꺾여있다는 얘기
    if(arr[left] <= arr[mid]){
      if(target >= arr[left] && target < arr[mid]){
        right = mid - 1; // target은 왼쪽에 있음
      } else{
        left = mid + 1; // target은 오른쪽에 있음
      }
    }
    // 오른쪽이 돌아오는 구간 없이 완벽히 정렬되어 있음
    else{
      if(target > arr[mid] && target <= arr[right]){
        left = mid + 1; // target은 오른쪽에 있음
      } else {
        right = mid - 1; // target은 왼쪽에 있음
      }
    }
  }
  return -1;
}

console.log(findRotatedIndex([6,7,8,9,1,2,3,4],8)); // 2
console.log(findRotatedIndex([6,7,8,9,1,2,3,4],3)); // 6