분할 정복

개념

분할 정복은 “큰 문제를 작은 문제 단위로 쪼개면서 해결해나가는 방식"이다. 미국 수학자 폰노이만이 1945년에 개발한 알고리즘이다. 퀵소트, 병합 정렬이 분할 정복 방법을 통해 구현한다.

예전엔 테이프를 이용해 데이터를 저장했다. 테이프 드라이브에 저장된 데이터는 항상 처음부터 순차적으로 읽어야 하기 때문에 데이터를 정렬하기 어려웠다. 이런 테이프 드라이브의 문제점을 극복하기 위해 병합 정렬 알고리즘이 탄생했다

1. 분할 : 문제를 더 이상 분할할 수 없을 때까지 동일 유형의 여러 하위 문제로 나눈다
2. 정복 : 가장 작은 단위의 하위 문제를 해결하며 정복한다
3. 조합 : 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합한다

예시

분할 정복은 구조는 동일하지만 더 작은 문제를 해결하는 방식이 반복되는 재귀라고 볼 수 있다. 5의 계승(5!)을 재귀로 계산하는 factorial 함수가 전형적인 분할 정복의 예다. 5의 계승은 5 * 4 * 3 * 2 * 1의 결과이므로 5부터 -1씩 문제를 쪼깬 후(분할), 가장 작은 단위의 하위 문제인 2 * 1 부터 문제를 해결하며(정복/조합) 결과를 도출한다.

• $5 \times (4 \times 3 \times 2 \times 1) = 5 \times \text{fact}(5-1) = (5 \times 24)$
• $4 \times (3 \times 2 \times 1) = 4 \times \text{fact}(4-1) = (4 \times 6)$
• $3 \times (2 \times 1) = 3 \times \text{fact}(3-1) = (3 \times 2)$
• $2 \times 1 = 2 \times \text{fact}(2-1) = (2 \times 1)$
• $1\,\text{(Base Case)}$

function fac(n) {
  // Base Case 재귀가 멈추는 조건
  if (n === 1) return 1;

  // Recursive Case
  return n * fac(n - 1);
}

fac(5); // 120

병합 정렬

알고리즘 개념

➊, ➋ 같은 원형 번호는 진행 순서 / 파란색 블록은 주어진 데이터들이 정렬된 상태

병합 정렬은 1개 배열을 ➊2개의 작은 배열로 분할하여 ➋각 배열을 정렬(정복)한 후 ➌다시 병합(결합)하는 과정을 반복하며 정렬하는 알고리즘이다

1. 분할 : 입력 받은 배열을 동일 길이의 2개 배열로 분할
2. 정복 : 분할한 배열 정렬. 분할한 배열 길이가 2 이상이면 재귀 호출로 분할 정복 다시 적용