동적 계획법(Dynamic Programming)이란?
동적 계획법(다이내믹 프로그래밍, Dynamic Programming)은 다양한 알고리즘 설계 기법 중 하나로, 복잡한 문제를 여러 개의 작은 부분 문제(sub-problem)로 나누어 해결하는 방식입니다. 핵심 아이디어는 한 번 계산한 부분 문제의 결과를 저장해 두었다가, 이후 동일한 부분 문제가 다시 필요할 때 재계산하지 않고 저장된 값을 그대로 활용하는 것입니다. 이를 통해 불필요한 중복 연산을 제거하고 전체 계산 시간을 크게 단축할 수 있습니다.
예를 들어 피보나치 수열을 단순 재귀로 구현하면 지수 시간이 걸리지만, 동적 계획법을 적용하면 선형 시간에 해결할 수 있습니다. 이처럼 DP는 성능 최적화에 매우 효과적인 기법입니다.
동적 계획법이 적용되는 두 가지 핵심 조건
- 중복되는 부분 문제(Overlapping Subproblem): 문제를 나누었을 때 동일한 부분 문제가 반복적으로 등장해야 합니다. 결과를 메모리에 저장(메모이제이션)함으로써 중복 계산을 피할 수 있습니다.
- 최적 부분 구조(Optimal Substructure): 전체 문제의 최적해가 부분 문제들의 최적해로부터 구성될 수 있어야 합니다. 즉, 작은 문제의 답을 조합하여 큰 문제의 정답을 얻을 수 있는 구조여야 합니다.
구현 방식: 메모이제이션 vs 타뷸레이션
동적 계획법은 일반적으로 두 가지 방식으로 구현합니다.
- 메모이제이션(Memoization): 재귀 호출 기반으로, 필요할 때 부분 문제를 계산하고 그 결과를 배열이나 해시맵에 캐싱하는 하향식(Top-down) 접근입니다.
- 타뷸레이션(Tabulation): 반복문을 사용해 가장 작은 부분 문제부터 차례로 테이블을 채워 올라가는 상향식(Bottom-up) 접근입니다.
동적 계획법으로 풀 수 있는 대표 문제 총정리
아래는 동적 계획법 학습에 필수적인 대표 문제들을 주제별로 정리한 목록입니다.
1. 기초 · 수열 문제
- 피보나치 수열 생성
- 못생긴 수(Ugly Numbers)
- 1부터 n까지 모든 숫자의 자릿수 합 계산
- 자릿수의 합이 특정 값과 같은 숫자 찾기
- N자리 수에서 자릿값이 감소하지 않는 수의 총 개수
- 숫자를 세 번 나누어 얻을 수 있는 최대 합
2. 계단 · 경로 · 격자 문제
- n번째 계단에 도달하는 방법의 수
- 목적지에 도달하는 최소 비용
- 행렬에서 목적지까지의 최소 비용 경로 찾기
- 두 번의 이동으로 격자에서 최대 점수 수집하기
- 행렬에서 직사각형 영역의 최대 합
- 모든 원소가 1인 최대 크기 정사각형 부분 행렬
- 도달 가능한 최소 점프 횟수
- 목적지에 도달하기 위한 최소 토큰 수
3. 문자열 · 부분 수열 문제
- 편집 거리(Edit Distance)
- 최장 공통 부분 수열(Longest Common Subsequence)
- 최장 증가 부분 수열(Longest Increasing Subsequence)
- 최대 합 증가 부분 수열
- 최장 바이토닉(Bitonic) 부분 수열
- 최장 회문 부분 수열의 길이
- 최장 회문 부분 문자열
- 연속된 1이 없는 이진 문자열의 개수 세기
- 주어진 시작 문자로부터의 최장 연속 경로
- 최대 합 연속 부분 배열
- 와일드카드 패턴 매칭 문제
- 최단 공통 초수열(Shortest Common Super-sequence)
4. 배낭 · 분할 · 조합 문제
- 부분 집합 합(Subset Sum) 문제
- 같은 합을 가진 두 집합으로 분할 가능 여부 검사
- 최소 동전 교환(Coin Change) 문제
- 막대 자르기(Rod Cutting) 문제
- 친구 짝 짓기 문제
- 게임에서 주어진 점수에 도달하는 방법의 수
- 건물을 건설할 수 있는 경우의 수 세기
- 쌍 체인(pair-chain)의 최대 길이
- 휴대폰 숫자 키패드 문제
5. 행렬 · 그래프 · 최적화 문제
- 행렬 체인 곱셈(Matrix Chain Multiplication)
- 최적 이진 탐색 트리(Optimal BST)의 비용
- 플로이드-워셜(Floyd-Warshall) 알고리즘
- 다각형 삼각형 분할의 최소 비용
- 상자 쌓기(Box Stacking) 문제
- 계란 낙하(Egg Dropping) 퍼즐
- 가중 작업 스케줄링 문제
- 주식을 두 번 사고팔아 얻는 최대 이익
- 네 개의 키로 출력할 수 있는 최대 'A' 개수
- 특정 값에 도달하기 위한 최소 완전제곱수의 합
- 회문 분할(Palindrome Partitioning) 알고리즘
- 단어 줄바꿈(Word Wrap) 문제
- 최대 독립 집합(Largest Independent Set) 문제
- 정점 커버(Vertex Cover) 문제
마무리
동적 계획법은 처음에는 어렵게 느껴질 수 있지만, 위와 같은 대표 문제들을 유형별로 차근차근 연습하면 점화식을 세우는 감각이 길러집니다. 각 문제를 풀 때 ① 부분 문제 정의 → ② 점화식 도출 → ③ 메모이제이션 또는 타뷸레이션 구현의 순서로 접근하면 체계적으로 실력을 향상시킬 수 있습니다.