알고리즘 설계 기법: 동적 계획법(DP)과 분할 정복

복잡한 문제를 효율적으로 해결하기 위한 두 가지 핵심 패러다임인 동적 계획법과 분할 정복의 차이점과 대표 사례들을 정리합니다.

1. 동적 계획법 (Dynamic Programming)

DP의 핵심은 **"기억하며 풀기"**입니다. 작은 문제들이 반복해서 나타날 때, 그 결과를 저장(Memoization)해 두었다가 재사용하여 중복 계산을 획기적으로 줄입니다.

• 성립 조건: 최적 부분 구조(작은 문제의 답으로 큰 문제의 답을 구함)와 중복되는 부분 문제(같은 작은 문제가 반복됨)가 있어야 합니다.
• 대표 예시: 피보나치 수열, 배낭 문제(Knapsack), 최장 공통 부분 수열(LCS)

2. 분할 정복 (Divide and Conquer)

분할 정복의 핵심은 **"쪼개서 각각 해결하기"**입니다. 문제를 독립적인 부분 문제로 나누고, 각각을 해결한 뒤 다시 합칩니다. DP와 달리 부분 문제들이 서로 겹치지 않습니다.

• 대표 예시: 퀵 정렬, 병합 정렬, 이진 탐색

3. 한눈에 비교하기

구분	동적 계획법 (DP)	분할 정복
핵심 아이디어	부분 문제의 해를 저장 및 재활용	독립적인 부분 문제로 분할 후 결합
중복성	부분 문제가 반복적으로 발생함	부분 문제가 중복되지 않음
방식	주로 상향식(Bottom-up)	주로 하향식(Top-down, 재귀)