재귀와 분할 정복

문제를 자기 자신의 작은 버전으로 쪼개는 사고법.

개념

재귀는 거울 속의 거울 같아요. 마주 본 두 거울 사이에 서면 똑같은 방이 점점 작게 끝없이 비치죠. 재귀도 같은 문제의 더 작은 버전을 자기 안에 계속 담아요. 여러분이 할 일은 그 작은 문제로 미뤄 두는 것뿐이에요. 분할 정복은 여기에 한 가지를 더해요 — 문제를 반으로 쪼개 각각 풀고, 그 답들을 다시 합쳐요.재귀는 '같은 문제의 더 작은 버전을 풀 수 있다고 가정하고, 그걸 이용해 지금 문제를 푸는' 방식이에요. 중요한 건 작은 문제가 어떻게 풀리는지 따라 내려가지 않는 것이에요. 그건 컴퓨터가 해요.재귀 함수를 쓸 때 정할 것은 두 가지뿐이에요. 더 이상 쪼갤 수 없는 기저 조건과, 작은 답으로 큰 답을 만드는 결합 규칙이에요.

기저 조건 — 언제 쪼개기를 멈추는가 (빈 배열, 노드 없음, n이 0 또는 1)
쪼개기 — 문제를 어떻게 더 작게 만드는가
결합 — 작은 답들을 어떻게 합쳐 지금의 답으로 만드는가

분할 정복

재귀 중에서도 문제를 절반씩 쪼개는 형태를 분할 정복이라고 해요. 절반씩 줄어드니 깊이가 log n이고, 각 깊이에서 O(n)의 일을 하면 전체가 O(n log n)이 돼요. 병합 정렬이 정확히 그 구조예요.

알고리즘	쪼개기	결합	복잡도
병합 정렬	반으로 나눔	정렬된 둘을 합침 `O(n)`	`O(n log n)`
퀵 정렬	기준값 기준 분할 `O(n)`	결합 불필요	평균 `O(n log n)`
거듭제곱	지수를 반으로	제곱 한 번 `O(1)`	`O(log n)`

거듭제곱이 좋은 예예요. a^n을 n번 곱하면 O(n)이지만, a^n = (a^(n/2))²라는 관계를 쓰면 O(log n)이에요. 지수가 홀수면 a를 한 번 더 곱해 주면 돼요.병합 정렬 [3, 1, 2]을 손으로 돌려 볼게요. 내려갈 땐 반씩 쪼개기만, 올라올 땐 정렬된 둘을 합치기만 해요. 들여쓰기가 깊어질수록 더 작은 문제라고 보면 돼요.

[3,1,2] 병합 정렬 — 내려가며 쪼개고, 올라오며 합치기
쪼개기 (내려가는 길)
  sort [3,1,2]
    sort [3]        -> [3]
    sort [1,2]
      sort [1]      -> [1]
      sort [2]      -> [2]
합치기 (올라오는 길)
      merge [1] [2] -> [1,2]
    sort [1,2]      -> [1,2]
  merge [3] [1,2]
      3 vs 1 -> 1,   3 vs 2 -> 2,   남은 3
                  -> [1,2,3]
  sort [3,1,2]      -> [1,2,3]

쪼개기는 그냥 절반으로 나눌 뿐 정렬은 안 해요. 진짜 정렬은 전부 합치기에서 일어나요. merge [3] [1,2]처럼, 이미 정렬된 두 조각의 앞에서부터 작은 값을 하나씩 뽑아 붙이는 거죠. 이 한 번의 합치기가 O(n)이고, 쪼개기 깊이가 log n이라 전체가 O(n log n)이에요.

재귀와 반복

모든 재귀는 스택을 직접 관리하면 반복문으로 바꿀 수 있어요. 10주차에서 스택을 배운 뒤에 재귀를 배우는 이유예요. 깊이가 깊어 스택 오버플로가 걱정될 때 이 변환을 써요.

패턴 코드

메모이제이션으로 중복 계산 없애기

javascript
Copy code
const memo = new Map();
function fib(n) {
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n);
  const value = fib(n - 1) + fib(n - 2);
  memo.set(n, value);
  return value;
}

병합 정렬

javascript
Copy code
function mergeSort(a) {
  if (a.length <= 1) return a;
  const mid = a.length >> 1;
  const left = mergeSort(a.slice(0, mid));
  const right = mergeSort(a.slice(mid));
  const out = [];
  let i = 0;
  let j = 0;
  while (i < left.length && j < right.length) {
    out.push(left[i] <= right[j] ? left[i++] : right[j++]);
  }
  return out.concat(left.slice(i), right.slice(j));
}

빠른 거듭제곱

javascript
Copy code
function power(a, n) {
  if (n === 0) return 1;
  const half = power(a, Math.floor(n / 2));
  return n % 2 === 0 ? half * half : half * half * a;
}

이번 주 문제

이번 주 진행0 / 4

주차 진행률

이번 주 주제로 골라둔 문제예요. 채점은 프로그래머스에서 하고, 풀고 나면 여기에 체크해 두세요. 난이도 순으로 보여줘요.

프로그래머스 진행률

쿼드압축 후 개수 세기 푼 문제로 표시
쿼드압축 후 개수 세기
Lv. 2풀기

셀프 체크

다음 주로 넘어가기 전에 소리 내어 답해 보세요. 막히면 그 부분이 아직 덜 익은 개념이에요.

재귀 함수를 쓸 때 반드시 정해야 하는 두 가지는?
재귀 피보나치가 느린 이유와, 고치는 방법은?
분할 정복이 O(n log n)이 되는 이유를 '깊이 × 각 깊이의 일'로 설명할 수 있는가?

← 12주차 · 체크포인트 2 14주차 · 트리와 이진 트리 →