코드를 읽고 설명하면, 합격합니다
이 레슨과 관련된 학습 키워드
알고리즘 — 문제 해결의 체계적 접근 → 고급 알고리즘
동적 프로그래밍(Dynamic Programming, DP)은 알고리즘의 가장 강력하고 가장 많이 출제되는 기법입니다.
DP가 필요한 이유:
재귀로 피보나치를 구하면:fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2)
fib(3) = fib(2) + fib(1) ← 중복!
fib(3)을 2번, fib(2)를 3번 계산합니다. n이 커지면 O(2ⁿ)!
DP의 핵심 아이디어:
"같은 문제를 두 번 풀지 않는다" — 한 번 구한 답을 저장하고 재사용합니다.
DP가 적용되는 조건:
1. 최적 부분 구조(Optimal Substructure): 전체 최적이 부분 최적으로 구성
2. 중복 부분 문제(Overlapping Subproblems): 같은 부분 문제가 반복 등장
면접에서의 DP:
여러분, 오늘은 알고리즘에서 가장 강력한 기법인 DP를 배워볼게요.
DP는 코딩 면접에서 가장 많이 출제되는 유형이기도 해요.
그런데 DP가 왜 필요한 걸까요?
그림 왼쪽을 보세요. 피보나치 재귀 호출 트리가 있어요.
fib 다섯을 구하면 fib 넷과 fib 셋을 호출하죠.
fib 넷은 또 fib 셋과 fib 둘을 호출해요.
보이시죠? fib 셋이 두 번이나 중복 계산돼요.
fib 둘은 무려 세 번이나 반복됩니다.
n이 사십이면 십일억 번 이상 연산해야 해요.
시간 복잡도가 O 이의 n승이라 실용적이지 않죠.
이제 오른쪽을 보세요. DP로 해결한 모습이에요.
핵심 아이디어는 "같은 문제를 두 번 풀지 않는다"예요.
한 번 계산한 값을 테이블에 저장하고 재사용하는 거죠.
dp 영에서 dp 다섯까지 각 값을 한 번씩만 계산해요.
n이 사십이어도 연산은 딱 사십 번이면 충분해요.
십일억 대 사십이라니 엄청난 차이죠?
그런데 모든 문제에 DP를 쓸 수 있는 건 아니에요.
그림 아래쪽 주황 상자를 보세요. 두 가지 조건이 필요해요.
첫째, 최적 부분 구조예요. 전체 최적이 부분 최적으로 구성되어야 해요.
둘째, 중복 부분 문제예요. 같은 하위 문제가 반복 등장해야 해요.
이 두 조건을 만족하면 DP로 지수 시간을 다항 시간으로 줄일 수 있어요.
이번 레슨에서 이 패턴들을 하나씩 익혀볼게요.