[알고리즘 | JS] 분할과 정복 패턴( Divide and Conquer)

🍕분할과 정복 패턴(Divide and Conquer)이란? 

이 알고리즘은 주로 배열이나 문자열같은 큰 규모의 데이터셋을 처리한다.
(This pattern involves dividing a data set into samller chunks and then repeating a process with a subset of data )
해당 패턴은 시간 복잡도를 엄청나게 줄일 수 있다.
(This pattern can tremendously decrease time complexity.)

- 퀵 정렬, 병합 정렬, 이진탐색은 분할 정복 알고리즘의 예시이다. 

- 분할정복 알고리즘은 정렬이나 탐색 알고리즘(e.g.이진 탐색 트리)으로 넘어가기 전에 살펴봐야 하는 개념이다. 

 

🍕분할정복 과정

1. Divide -> 기존 문제를 작은 부분 문제들로 나눔 
   • 여기서는 2가지로 분류: Base case / Recursive case (뒤의 재귀함수에서 다시 나오는 개념입니다.)
   • Base case: 이미 문제가 충분히 작아서, 더 작은 문제로 나누지 않아도 바로 답을 알 수 있는 경우
   • Recursive case : 문제가 커서 바로 답을 알 수 없어서, 같은 형태의 부분 문제들로 쪼개서 풀어야 하는 경우
2. Conquer -> 각 부분 문제를 해결(정복) 
   • 해당 단계에서 다시 divide, conquer, combine 으로 쪼개질 수 있다.(재귀적으로 진행되는 경우 많음)
3. Combine -> 부분 문제들의 솔루션을 통해 기존 문제를 해결

 

---

예시를 통해 알아봅시다. 

 

탐색 알고리즘 예시

• 배열은 오름차순으로 정렬되고 정수로 구성된 배열(sorted array needed)이어야 한다. 
• search라는 함수를 만들고 해당 함수는 정렬된 배열과 찾고자하는 value를 인수로 받는다.

예상 결과▼

search([1,2,3,4,5,6],4) // 3 (index:3(인덱스의 위치를 반환한다.) there's number 4)
search([1,2,3,4,5,6],6) // 5
search([1,2,3,4,5,6],11) // -1 (not found)

▶a naive solution 

• 시간 복잡도 : O(n) -> 그래서 해당 구조를 '선형(linear) 탐색'이라고 부른다. 
• 선형 탐색은 n만큼 즉, 요소 하나하나를 일직선으로 탐색하는 것이라고 생각하면 된다. 

//단순하게 for문을 통해 n을 하나하나 체크
function search(arr, value) {
  for (let i = 0; i < array.length; i++) {
    if (arr[i] == value) {
      return i;
    }
  }
  return -1;
}

▶refactored code 

• 시간 복잡도 O(log n)
• '이진 탐색'이라고 부르며 분할 정복 알고리즘이 적용됐다.
• 이진 탐색 원리: 정렬된 배열의 중간값을 선택
  배열의 중간 값을 대충 골라서 해당 값이 찾고자하는 값보다 작은지 확인 작다면 왼쪽에 있는 값들은 무시
  오른쪽에 남은 배열의 부분에서 또 중간지점을 선택 찾고자하는 값보다 작다면 왼쪽값 무시 반복
• 결국 배열을 중간으로 자꾸 나누면서 범위를 좁혀가는 것 이렇게되면 연산이 선형 탐색보다 훨씬 빨라진다.

//이진 탐색이라고 부르며 분할 정복 알고리즘이 적용됐다
//middle 이 해당 array요소의 중간값을 나타낸다. 
function search(array, val) {
  let min = 0;
  let max = array.lengh - 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;
}

결론: 분할정복은 더 큰 데이터셋을 취해 작은 하위셋으로 분할하고 다른 부분은 무시하는 개념이다.
병합 정렬이나 퀵 정렬의 경우, 요소들을 다시 병합 즉, 작은 조각들에서 한 번에 하나씩 병합하는 형태