이 레슨과 관련된 학습 키워드
컴퓨터 과학 & 프로그래밍 — 문제 해결의 도구 → 알고리즘 — 문제 해결의 체계적 접근 → 알고리즘 — 문제 해결의 체계적 접근 → 고급 알고리즘
Learn dynamic programming fundamentals: memoization, tabulation, knapsack, coin change, LIS, grid paths, house robber, and Kadane algorithm.
fib(5) = fib(4) + fib(3)여러분, 오늘은 알고리즘에서 가장 강력한 기법인 DP를 배워볼게요.
DP는 코딩 면접에서 가장 많이 출제되는 유형이기도 해요.
그런데 DP가 왜 필요한 걸까요?
그림 왼쪽을 보세요. 피보나치 재귀 호출 트리가 있어요.
fib 다섯을 구하면 fib 넷과 fib 셋을 호출하죠.
fib 넷은 또 fib 셋과 fib 둘을 호출해요.
보이시죠? fib 셋이 두 번이나 중복 계산돼요.
fib 둘은 무려 세 번이나 반복됩니다.
n이 사십이면 십일억 번 이상 연산해야 해요.
시간 복잡도가 O 이의 n승이라 실용적이지 않죠.
이제 오른쪽을 보세요. DP로 해결한 모습이에요.
핵심 아이디어는 "같은 문제를 두 번 풀지 않는다"예요.
한 번 계산한 값을 테이블에 저장하고 재사용하는 거죠.
dp 영에서 dp 다섯까지 각 값을 한 번씩만 계산해요.
n이 사십이어도 연산은 딱 사십 번이면 충분해요.
십일억 대 사십이라니 엄청난 차이죠?
그런데 모든 문제에 DP를 쓸 수 있는 건 아니에요.
그림 아래쪽 주황 상자를 보세요. 두 가지 조건이 필요해요.
첫째, 최적 부분 구조예요. 전체 최적이 부분 최적으로 구성되어야 해요.
둘째, 중복 부분 문제예요. 같은 하위 문제가 반복 등장해야 해요.
이 두 조건을 만족하면 DP로 지수 시간을 다항 시간으로 줄일 수 있어요.
이번 레슨에서 이 패턴들을 하나씩 익혀볼게요.
선생님: DP가 왜 필요한지 한 문장으로 설명해볼래요?
학생: 재귀로 풀면 같은 하위 문제를 여러 번 반복 계산하니까, 저장해서 재사용하려는 거 아닌가요?
선생님: 맞아요! 그게 DP의 본질이에요. 그럼 모든 재귀 문제에 DP를 쓸 수 있을까요?
학생: 아니요, 최적 부분 구조랑 중복 부분 문제 두 조건이 필요해요.
선생님: 정확해요. 이진 탐색은 중복 부분 문제가 없어서 DP가 아닌 분할 정복이에요.
학생: 그러면 피보나치처럼 같은 하위 문제가 반복될 때만 DP가 효과적인 거군요!