이 레슨과 관련된 학습 키워드
컴퓨터 과학 & 프로그래밍 — 문제 해결의 도구 → 알고리즘 — 문제 해결의 체계적 접근 → 알고리즘 — 문제 해결의 체계적 접근 → 고급 알고리즘
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로 지수 시간을 다항 시간으로 줄일 수 있어요.
이번 레슨에서 이 패턴들을 하나씩 익혀볼게요.