기술사 학습노트 | imt-log

기술사 학습노트› 알고리즘› 동적계획법(DP)

Algorithm · 한장정리

[기술사토픽] 동적계획법(DP) 완벽 정리 - 한장정리

동적계획법의 최적성 원리, 메모이제이션, 피보나치 예제, 그리디·분할정복 비교까지 기술사 핵심 학습노트

동적계획법DynamicProgrammingDP알고리즘점화식최적성원리상향식접근피보나치수열메모이제이션정보관리기술사알고리즘

Ⅰ.개요

동적계획법(Dynamic Programming, DP)은 복잡한 문제를 작은 부분 문제로 분해하고, 각 부분 문제의 해를 저장하여 재활용함으로써 중복 계산을 제거하는 알고리즘 설계 기법이다. 1950년대 벨만(R. Bellman)이 최적 제어 이론에서 처음 제안하였다.

적용 조건

① 최적 부분 구조(Optimal Substructure): 전체 문제의 최적해가 부분 문제의 최적해로 구성됨
② 중복 부분 문제(Overlapping Subproblems): 동일한 부분 문제가 여러 번 반복 호출됨

Ⅱ.동작 방식 및 절차

DP는 부분 문제를 푸는 순서에 따라 하향식(Top-Down)과 상향식(Bottom-Up) 두 방식으로 구현한다.

방식	명칭	구현	특징
Top-Down	하향식(메모이제이션)	재귀 + 캐시 테이블	직관적, 스택 오버플로 위험
Bottom-Up	상향식(타뷸레이션)	반복문 + DP 테이블	스택 사용 없음, 공간 효율 가능

DP 적용 절차

단계	내용
① 부분 문제 정의	전체 문제를 겹치는 소문제로 분해
② 점화식 수립	부분 문제 간의 관계식(점화식) 도출
③ 초기값 설정	가장 작은 부분 문제의 해(기저 조건) 정의
④ 테이블 채우기	작은 문제부터 순서대로 계산하여 저장
⑤ 해 추출	전체 문제에 해당하는 테이블 값 반환

Ⅲ.피보나치 수열 예제

피보나치 수열은 DP 적용의 대표 예제이다. 단순 재귀는 O(2ⁿ)이지만 DP 적용 시 O(n)으로 줄어든다.

점화식: F(n) = F(n-1) + F(n-2), F(0)=0, F(1)=1
단순 재귀: F(5) 계산 시 F(3)이 2번, F(2)가 3번 중복 호출 → O(2ⁿ)
DP(메모이제이션): 각 F(i)를 한 번만 계산하고 저장 → O(n)
DP(상향식): dp[0]=0, dp[1]=1, dp[i]=dp[i-1]+dp[i-2] 순서대로 채움 → O(n), O(n) 또는 O(1) 공간

시험 포인트

메모이제이션(Memoization)은 하향식 DP에서 계산 결과를 캐시에 저장하여 재활용하는 기법. 타뷸레이션(Tabulation)은 상향식 DP로 반복문을 사용해 테이블을 채운다. 시험에서 둘의 차이를 묻는 문제가 자주 출제된다.

Ⅳ.그리디 · 분할정복 비교

구분	동적계획법(DP)	그리디(Greedy)	분할정복(D&C)
접근 방법	부분 문제 저장·재활용	현재 최선 선택	독립 부분 문제 재귀 분할
부분 문제	중복 발생	단방향 선택	독립적(중복 없음)
최적해 보장	조건 만족 시 항상 보장	조건 만족 시 보장	항상 보장
대표 예시	배낭 문제, LCS, 편집거리	허프만 코딩, MST	퀵정렬, 합병정렬
시간복잡도	문제마다 다름(보통 다항식)	보통 O(n log n)	T(n)=2T(n/2)+O(n)

Ⅴ.결론

Conclusion

동적계획법은 최적 부분 구조와 중복 부분 문제가 존재하는 최적화 문제에서 강력한 알고리즘 설계 기법이다. 메모이제이션(하향식)과 타뷸레이션(상향식) 두 구현 방식을 상황에 맞게 선택해야 한다. DP는 그리디보다 적용 범위가 넓고 최적해를 보장하지만, 부분 문제 저장을 위한 추가 메모리가 필요하다는 트레이드오프가 있다.

블로그: 기술사 학습노트 · imt-log.tistory.com

← 알고리즘 목록