30초 답변

분할 정복은 큰 문제를 같은 구조의 독립된 부분 문제로 나누어 해결한 뒤 결과를 합치는 방식입니다. 재귀로 구현하며, merge sort와 quick sort가 대표적인 예입니다.

꼬리질문

조금 더 깊게 물어본다면

답변 뒤에 이어질 수 있는 질문들을 하나씩 열어볼 수 있어요.

1

2

3

4

DP와 분할 정복의 차이는?

둘 다 문제를 작은 부분 문제로 나눕니다. 분할 정복은 부분 문제가 겹치지 않아 결과를 저장하지 않고, DP는 겹치는 부분 문제를 저장해 중복 계산을 줄입니다.

이전 질문다음 꼬리질문

부가 설명

분할, 정복, 합병의 세 단계로 이루어집니다. 배열을 정렬한다면 절반으로 나누고, 각 절반을 독립적으로 정렬한 뒤, 정렬된 두 배열을 병합합니다. 이게 merge sort의 흐름입니다.

DP와의 차이는 부분 문제가 겹치는지 여부입니다. DP는 같은 부분 문제가 반복 등장해 결과를 저장해 재사용하는 반면, 분할 정복의 부분 문제들은 서로 독립적이라 저장이 필요 없습니다. 병합 정렬에서 왼쪽 절반 정렬과 오른쪽 절반 정렬은 완전히 분리되어 있습니다.

시간복잡도는 마스터 정리로 분석합니다. 문제를 a개로 나누고 크기를 b분의 1로 줄이며 각 단계 비용이 O(n^d)라면, T(n) = a·T(n/b) + O(n^d)로 표현됩니다. Merge sort는 a=2, b=2, d=1이므로 O(n log n)입니다.

한 줄 정리

분할 정복은 겹치지 않는 독립 부분 문제로 나누어 재귀로 해결하고 합치는 방식입니다.