정보관리기술사 학습 노트
← 목록으로
컴퓨팅·임베디드
#동적계획법#최적부분구조#중복부분문제#메모이제이션#점화식
최종 업데이트 · 2026-11-03

동적 계획법(Dynamic Programming)

1. 개요

가. 정의

동적 계획법(Dynamic Programming, DP) 은 하나의 큰 문제를 서로 겹치는 작은 하위 문제로 분해하고, 각 하위 문제의 해를 한 번만 계산해 저장(기억)한 뒤 재사용함으로써 지수적 탐색을 다항 시간으로 끌어내리는 최적화 알고리즘 설계 기법이다.

동적 계획법은 1950년대 리처드 벨만(Richard Bellman)이 다단계 의사결정 문제를 풀기 위해 정립한 기법으로, 이름의 'dynamic'은 시간에 따른 다단계 결정을, 'programming'은 수학적 최적화(계획법)를 뜻한다. 오늘날 DP는 알고리즘 설계의 3대 패러다임(분할정복·탐욕·동적계획법) 중 하나로, "같은 하위 문제를 여러 번 반복해 푸는" 비효율을 제거하는 핵심 도구로 자리 잡았다.

나. 등장 배경과 필요성

많은 최적화 문제는 단순한 재귀(완전 탐색)로 정의하면 동일한 하위 문제를 지수적으로 중복 계산한다. 가장 흔한 예가 피보나치 수열이다. fib(n) = fib(n-1) + fib(n-2)를 그대로 재귀 호출하면 fib(n-2)가 두 번, fib(n-3)은 세 번 계산되며, 전체 호출 수는 황금비에 비례해 약 O(1.618ⁿ)으로 폭증한다. n=50만 되어도 호출이 수억 번에 달해 실용 시간 안에 끝나지 않는다. 문제의 '해'는 분명히 다항 개수인데, 탐색 방식이 지수적이라는 모순이 바로 DP가 해결하려는 지점이다.

동적 계획법은 이 중복을 "한 번 계산한 답을 저장하고, 다시 필요하면 꺼내 쓴다"는 단순하지만 강력한 원리로 제거한다. 피보나치의 서로 다른 하위 문제는 fib(0)~fib(n)의 n+1개뿐이므로, 각각을 한 번씩만 계산하면 전체는 O(n)에 끝난다. 즉 DP의 본질은 시간을 메모리와 교환(공간-시간 트레이드오프) 하여, 중복 계산이라는 지수적 낭비를 다항 저장 공간으로 흡수하는 것이다. 이 교환이 성립하려면 문제가 두 가지 조건을 만족해야 한다.

DP의 필요성은 '다항 개수의 해를 지수적으로 탐색하는' 모든 최적화 문제에서 반복적으로 나타난다. 경로 탐색, 자원 배분, 문자열 정렬, 일정 수립 등 서로 무관해 보이는 문제들이 사실은 "작은 결정이 누적되어 최적의 전체 결정을 이룬다"는 공통 구조를 가지며, 완전 탐색으로는 결정의 조합이 지수적으로 폭증한다. DP는 이 폭증을 '상태'라는 중간 요약으로 접어 넣어, 같은 상태에 도달하는 수많은 경로를 하나의 저장된 값으로 대표시킨다. 따라서 DP를 익히는 것은 개별 문제의 풀이를 외우는 일이 아니라, 이 공통 구조를 알아보고 상태로 추상화하는 안목을 기르는 일이다.

다. DP가 성립하는 두 가지 조건

DP를 아무 문제에나 적용할 수 있는 것은 아니다. 적용 가능성은 최적 부분구조(Optimal Substructure) 와 중복 부분문제(Overlapping Subproblems) 라는 두 조건으로 판별한다. 전자는 "큰 문제의 최적해가 작은 문제의 최적해로 구성된다"는 성질이고, 후자는 "같은 작은 문제가 반복해서 등장한다"는 성질이다. 두 조건은 독립적이어서, 둘 다 만족하면 DP가, 최적 부분구조만 있고 중복이 없으면 분할정복이, 여기에 지역 최적이 전역 최적을 보장하면 탐욕법이 적합하다. 이 판별은 뒤의 비교 절에서 상세히 다룬다.

두 조건은 DP의 '적용 여부'뿐 아니라 '효율'까지 함께 설명한다. 최적 부분구조가 점화식의 '정확성'(부분해를 결합해 올바른 전체해가 나오는가)을 보장한다면, 중복 부분문제는 DP의 '이득'(저장·재사용으로 얼마나 아끼는가)을 결정한다. 중복이 거의 없으면 저장 비용만 늘 뿐 이득이 없어 사실상 분할정복과 다르지 않고, 중복이 많을수록 지수에서 다항으로의 절감 폭이 커진다. 따라서 문제를 받으면 두 조건을 각각 명시적으로 확인하는 습관이, 잘못된 적용과 불필요한 적용을 모두 걸러내는 첫 관문이 된다.

2. 동적 계획법의 원리와 구조

동적 계획법의 전체 구조는 '문제 분해 → 상태 정의 → 점화식 → 저장·재사용 → 해 복원'의 흐름으로 이해할 수 있다. 아래 구조도는 완전 탐색(중복 계산)과 DP(저장·재사용)의 차이를 한눈에 보여준다.

flowchart TB
  P["원 문제"] --> SUB["하위 문제로 분해"]
  SUB --> CHK{"이미 계산한<br/>하위 문제인가?"}
  CHK -->|"예(중복)"| MEM["저장소에서 조회(O(1))"]
  CHK -->|"아니오(최초)"| CALC["점화식으로 계산"]
  CALC --> STORE["저장소에 기록(메모)"]
  STORE --> COMB["상위 문제의 해로 결합"]
  MEM --> COMB
  COMB --> ANS["원 문제의 최적해"]

가. 최적 부분구조(Optimal Substructure)

최적 부분구조란 전체 문제의 최적해가 그 하위 문제들의 최적해만으로 구성된다는 성질이다. 예컨대 서울→부산 최단 경로가 서울→대전→부산을 지난다면, 그 경로에 포함된 서울→대전 구간 역시 서울→대전의 최단 경로여야 한다. 만약 더 짧은 서울→대전 경로가 있다면 전체 경로도 더 짧아질 수 있어 "최적"이라는 가정에 모순되기 때문이다. 이 성질 덕분에 큰 문제를 작은 문제의 답으로 '점화식(recurrence relation)' 형태로 표현할 수 있다.

최적 부분구조가 중요한 이유는, 이것이 없으면 작은 문제의 답을 아무리 저장해도 큰 문제를 구성할 수 없기 때문이다. 예를 들어 '최장 단순 경로(longest simple path)' 문제는 최적 부분구조가 성립하지 않는다. 두 부분 경로를 이으면 정점이 중복되어 '단순 경로'라는 제약이 깨질 수 있어, 부분 최적해의 결합이 전체 최적해를 보장하지 못한다. 이처럼 DP 적용 전에는 반드시 "부분해의 결합이 전체해를 이루는가"를 먼저 검증해야 한다.

나. 중복 부분문제(Overlapping Subproblems)

중복 부분문제란 재귀적으로 문제를 풀 때 동일한 하위 문제가 여러 번 반복해 호출되는 성질이다. 피보나치에서 fib(3)이 수차례 재계산되는 것이 전형적 예다. 이 중복이 많을수록 DP의 이득이 커진다. 반대로 병합 정렬처럼 하위 문제가 서로 겹치지 않고 매번 새로운 입력을 다루면, 저장해 재사용할 것이 없으므로 DP가 아니라 분할정복이 맞다.

중복 부분문제는 '서로 다른 하위 문제의 총개수'로 정량화된다. 피보나치는 n+1개, 0/1 배낭 문제는 (물건 수)×(용량) 개, 최장 공통 부분수열(LCS)은 (문자열1 길이)×(문자열2 길이) 개의 서로 다른 하위 문제를 갖는다. DP의 시간 복잡도는 대체로 '서로 다른 하위 문제 수 × 하위 문제 1개를 푸는 비용'으로 계산되므로, 상태 공간의 크기를 정확히 파악하는 것이 성능 분석의 출발점이다.

이 정량화는 실무에서 "DP가 과연 돌아갈 것인가"를 코딩 전에 판단하는 근거가 된다. 예를 들어 상태가 (물건 1,000개)×(용량 100만)이면 상태 수가 10억에 이르러 메모리·시간 모두 한계를 넘으므로, DP를 그대로 적용하기 전에 상태 축소나 근사 알고리즘을 고려해야 한다는 신호가 된다. 반대로 상태 수가 수백만 이내면 안심하고 DP를 설계할 수 있다. 이처럼 '상태 공간 크기 추정'은 DP 적용의 타당성을 선행 검증하는 실무적 체크포인트다.

다. 두 가지 구현 방식 — 메모이제이션과 타뷸레이션

DP는 구현 방식에 따라 하향식(Top-Down) 메모이제이션 과 상향식(Bottom-Up) 타뷸레이션 으로 나뉜다. 메모이제이션은 재귀 호출을 유지하되 계산 결과를 캐시(배열·해시맵)에 저장해 같은 호출이 오면 즉시 반환한다. 코드가 원래의 점화식과 거의 같아 직관적이고, 실제로 필요한 하위 문제만 계산하는 장점이 있으나 재귀 호출 스택의 깊이 제한과 함수 호출 오버헤드가 단점이다.

타뷸레이션은 가장 작은 하위 문제부터 표(table)를 채워 올라가며 큰 문제로 전진한다. 재귀가 없어 스택 오버플로가 없고 반복문 기반이라 상수 계수가 작아 대체로 더 빠르지만, 모든 하위 문제를 빠짐없이 계산하므로 일부가 불필요할 수 있고 계산 순서를 직접 설계해야 한다. 아래 표는 두 방식의 선택 기준을 정리한 것이며, 그 차이는 단순 취향이 아니라 "불필요한 상태가 많은가, 재귀 깊이가 깊은가"라는 문제 특성에서 비롯된다.

두 방식의 선택은 실무에서 구체적 제약으로 갈린다. 예컨대 n이 10만을 넘어 재귀 깊이가 기본 스택 한계(파이썬 1,000, 다수 언어 수만 수준)를 초과할 위험이 크면, 재귀 기반 메모이제이션은 스택 오버플로로 죽을 수 있어 타뷸레이션이 강제된다. 반대로 상태 공간이 이론상으로는 거대하지만 실제로 방문하는 상태는 극히 일부인 '희소(sparse)' 문제에서는, 필요한 상태만 계산하는 메모이제이션이 메모리·시간 모두에서 유리하다. 즉 선택의 근거는 코드 취향이 아니라 상태 공간의 밀도와 재귀 깊이라는 정량적 특성이다.

구분 메모이제이션(Top-Down) 타뷸레이션(Bottom-Up)
방향 큰 문제 → 작은 문제(재귀) 작은 문제 → 큰 문제(반복)
계산 범위 필요한 하위 문제만 모든 하위 문제
장점 직관적, 희소 상태에 유리 스택 안전, 상수 계수 작음, 공간 최적화 용이
단점 재귀 오버헤드·스택 한계 계산 순서 설계 필요, 불필요 계산 가능
적합 상황 상태 공간이 크고 희소 상태 공간이 조밀하고 전부 필요

3. 동적 계획법 설계 절차

실무에서 DP 문제를 푸는 과정은 아래와 같은 5단계 절차로 정형화할 수 있다. 이 절차의 핵심은 코딩이 아니라 '상태(state) 정의와 점화식 수립'이라는 모델링 단계에 있다.

flowchart LR
  S1["1.상태 정의<br/>(무엇을 저장할지)"] --> S2["2.점화식 수립<br/>(상태 간 관계)"]
  S2 --> S3["3.기저 조건<br/>(초기값)"]
  S3 --> S4["4.계산 순서<br/>(의존성 위상정렬)"]
  S4 --> S5["5.해 복원<br/>(역추적)"]

1단계 상태 정의 는 "하위 문제를 유일하게 식별하는 변수"를 정하는 일이다. 예를 들어 배낭 문제는 dp[i][w]를 "앞의 i개 물건만 고려하고 용량이 w일 때의 최대 가치"로 정의한다. 상태를 잘못 잡으면 점화식이 성립하지 않으므로, 이 단계가 전체 설계의 성패를 가른다. 2단계 점화식 은 상태 간 의존 관계를 수식으로 표현한다. 3단계 기저 조건 은 재귀가 멈추는 최소 상태의 값을 명시한다(예: dp[0][*]=0). 4단계 계산 순서 는 어떤 상태를 먼저 채워야 하는지를 의존성에 따라 위상정렬하는 것으로, 타뷸레이션에서 특히 중요하다. 5단계 해 복원 은 최적값뿐 아니라 "그 값을 만든 선택(어떤 물건을 담았는가)"을 역추적해 복원하는 단계로, 저장해 둔 결정 경로를 거슬러 올라간다.

이 절차에서 초심자가 가장 자주 실패하는 지점은 1~2단계다. 상태를 너무 좁게 잡으면(필요한 정보를 상태에 담지 못하면) 점화식이 과거 선택에 의존해 성립하지 않고, 너무 넓게 잡으면 상태 공간이 폭발해 복잡도가 비현실적으로 커진다. 따라서 "현재 결정을 내리는 데 필요한 최소한의 정보가 무엇인가"를 묻는 것이 상태 정의의 핵심 질문이다. 점화식 역시 '현재 상태를 어떤 더 작은 상태들의 조합으로 표현할 수 있는가'라는 한 문장으로 환원되며, 이 모델링이 서면으로 명확히 정리되면 구현은 기계적 작업에 가깝다. 기술사 답안에서도 코드가 아니라 바로 이 상태·점화식·기저조건의 삼위일체를 수식으로 제시하는 것이 평가의 중심이 된다.

4. 대표 사례

대표 사례에 들어가기 전에, 가장 단순한 피보나치로 DP의 효과를 수치로 확인해 두면 이후 사례가 명료해진다. fib(50)을 단순 재귀로 풀면 약 2×10¹⁰회의 함수 호출이 발생해 보통의 PC에서 수십 초가 걸리지만, dp[0]=0, dp[1]=1, dp[i]=dp[i-1]+dp[i-2]를 상향식으로 채우면 51번의 덧셈으로 즉시 끝난다. 더구나 피보나치는 바로 앞 두 값에만 의존하므로 배열 전체를 둘 필요 없이 변수 두 개(O(1) 공간)만으로도 계산된다. 이 한 예가 DP의 세 가지 핵심 — 중복 제거, 공간-시간 교환, 상태 공간 최적화 — 을 모두 압축해 보여준다.

가. 0/1 배낭 문제(0/1 Knapsack)

0/1 배낭 문제는 용량 W의 배낭에 무게·가치가 주어진 물건들을 담아 가치 합을 최대화하되, 각 물건은 담거나 담지 않거나(0 또는 1) 둘 중 하나만 선택하는 문제다. 완전 탐색은 물건 n개의 모든 부분집합 2ⁿ을 검사해 지수적이지만, DP는 dp[i][w] = max(dp[i-1][w], dp[i-1][w-무게ᵢ] + 가치ᵢ) 라는 점화식으로 n×W 개의 상태만 채워 O(nW)에 푼다. 예를 들어 n=100, W=1000이면 완전 탐색은 2¹⁰⁰(약 10³⁰)회이지만 DP는 10만 회로 끝나, 실용성의 경계를 완전히 넘나든다.

주의할 점은 이 O(nW)가 '의사 다항(pseudo-polynomial)'이라는 것이다. W는 입력의 '값'이지 '크기(비트 수)'가 아니므로, W가 매우 크면 여전히 비현실적이다. 0/1 배낭이 NP-난해로 분류되면서도 DP로 풀리는 이유가 여기에 있다. 이 사례는 "DP의 복잡도는 상태 공간의 크기에 비례한다"는 원리와, 그 상태 공간이 입력 값에 의존할 때의 함정을 동시에 보여준다.

나. 최장 공통 부분수열(LCS)과 편집 거리

LCS는 두 문자열에서 순서를 유지하며 공통으로 뽑을 수 있는 가장 긴 부분수열을 찾는 문제로, dp[i][j]를 "문자열1의 앞 i글자와 문자열2의 앞 j글자의 LCS 길이"로 정의한다. 글자가 같으면 dp[i-1][j-1]+1, 다르면 max(dp[i-1][j], dp[i][j-1])로 채워 O(mn)에 푼다. 편집 거리(Levenshtein Distance)도 삽입·삭제·교체 세 연산의 최소 횟수를 같은 2차원 DP로 구한다.

이 두 사례는 산업적으로 매우 널리 쓰인다. LCS는 git diff·버전 관리의 차이 비교, DNA 서열 정렬(bioinformatics)의 기반이며, 편집 거리는 맞춤법 교정·검색어 오타 보정·DNA 유사도 측정에 쓰인다. 예컨대 검색 엔진이 "안녕하세요"의 오타 "안뇽하세요"를 교정 제안할 때, 두 단어의 편집 거리가 작다는 사실을 DP로 계산해 활용한다. 생성형 AI의 출력 평가 지표 중 하나인 문자열 유사도 역시 이 계열의 DP에 뿌리를 둔다.

다. 플로이드-워셜(모든 쌍 최단 경로)

플로이드-워셜(Floyd-Warshall)은 그래프의 모든 정점 쌍 사이 최단 경로를 구하는 DP 알고리즘이다. dp[k][i][j]를 "정점 1~k만 경유지로 허용할 때 i→j 최단 거리"로 정의하고, 경유지 k를 하나씩 늘려가며 dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])로 갱신한다. 세 중첩 반복으로 O(V³)에 모든 쌍을 구하는 이 알고리즘은 라우팅 테이블 계산, 네트워크 지연 분석, 교통망 거리표 산출 등에 쓰인다. 다익스트라를 모든 정점에서 반복하는 것보다 구현이 간결하고 음의 가중치(음의 사이클 제외)도 다룰 수 있다는 장점이 있다.

플로이드-워셜의 교훈은 '상태에 경유지 차원을 추가'하는 발상이다. 최단 경로를 거리만으로 정의하면 점화식이 순환해 성립하지 않지만, "경유 가능한 정점 집합"을 단계 변수 k로 두면 k가 단조 증가하는 무순환 구조가 되어 DP가 가능해진다. 이처럼 상태를 어떻게 정의하느냐에 따라 같은 문제가 풀리기도 하고 풀리지 않기도 한다는 점이, DP에서 상태 설계가 왜 핵심인지를 단적으로 보여준다.

라. 최장 증가 부분수열(LIS)

최장 증가 부분수열(Longest Increasing Subsequence)은 수열에서 순서를 유지하며 뽑을 수 있는 가장 긴 '증가하는' 부분수열의 길이를 구하는 문제다. 기본 DP는 dp[i]를 "i번째 원소로 끝나는 LIS 길이"로 정의하고, dp[i] = max(dp[j]) + 1 (단, j<i이고 원소ⱼ<원소ᵢ)로 채워 O(n²)에 푼다. 예컨대 [10, 9, 2, 5, 3, 7, 101, 18]의 LIS는 [2, 3, 7, 18]로 길이 4이며, 각 위치에서 자신보다 작은 앞선 원소들의 dp값 중 최대를 이어받는 방식으로 구한다.

LIS가 교육적으로 중요한 이유는 DP를 다른 자료구조와 결합해 더 빠르게 만드는 전형 이기 때문이다. 이분 탐색을 접목하면 각 원소를 '증가 수열의 꼬리 배열'에 끼워 넣는 위치를 O(log n)에 찾아 전체를 O(n log n)으로 개선할 수 있다. 이는 "DP 점화식 자체는 O(n²)이지만, 전이(transition) 비용을 자료구조로 줄여 전체 복잡도를 낮춘다"는 상급 설계 패턴으로, 세그먼트 트리·펜윅 트리를 결합한 DP 최적화의 출발점이 된다. 실무에서는 작업 스케줄링, 버전 호환 경로 탐색, 주가 추세 분석 등에 변형 형태로 쓰인다.

5. 분할정복·탐욕법과의 비교

세 패러다임은 모두 "문제를 작게 나눈다"는 공통점이 있으나, 하위 문제의 중복 여부와 선택 전략에서 갈린다. 아래 표는 그 차이를 요약하되, 차이가 생기는 '이유'까지 함께 본다.

구분 동적 계획법 분할정복 탐욕법
하위 문제 중복 있음(저장·재사용) 없음(독립) 없음
전개 방향 상향/하향 모두 하향(재귀) 순차적 결정
선택 방식 모든 경우 비교 후 최적 분할 후 병합 매 단계 지역 최적
최적성 보장 항상(조건 충족 시) 분할 기준에 의존 탐욕 선택 속성 필요
대표 예 배낭·LCS·플로이드 병합정렬·이진탐색 거스름돈·MST·허프만

분할정복과 DP의 결정적 차이는 하위 문제의 중복 여부 다. 병합 정렬은 배열을 반으로 나누지만 두 절반은 완전히 독립적이어서 재사용할 것이 없다. 반면 피보나치는 fib(n-1)과 fib(n-2)가 fib(n-2)를 공유하므로 저장이 이득이 된다. 즉 "나눈 조각들이 서로 겹치는가"가 DP를 쓸지 분할정복을 쓸지를 가른다.

탐욕법과 DP의 차이는 선택의 재고 가능성 에 있다. 탐욕법은 매 단계 가장 좋아 보이는 선택을 하고 되돌아보지 않는다. 이것이 전역 최적을 보장하려면 '탐욕 선택 속성'이 증명되어야 한다. 예를 들어 분할 가능한(fractional) 배낭은 단위 무게당 가치가 높은 순으로 담는 탐욕법이 최적이지만, 0/1 배낭은 그렇지 않아 반드시 DP로 모든 경우를 비교해야 한다. 실무적 함의는 분명하다 — 탐욕법이 맞으면 DP보다 빠르고 간단하지만, 탐욕 선택 속성 증명에 실패하면 DP로 안전하게 전환해야 한다. 성급한 탐욕 적용은 "대부분 맞지만 가끔 틀리는" 가장 위험한 버그를 낳는다.

실제로 세 패러다임은 배타적이기보다 연속선 위에 있다. 탐욕법은 "각 단계에서 하나의 선택만 남기는 특수한 DP"로 볼 수 있고, 분할정복은 "하위 문제가 겹치지 않는 특수한 DP"로 볼 수 있다. 이 관점에서 보면, 어떤 문제를 만났을 때 ① 하위 문제가 겹치는지(겹치지 않으면 분할정복), ② 겹친다면 매 단계 하나의 선택으로 충분한지(충분하면 탐욕, 아니면 일반 DP)를 순서대로 점검하는 의사결정 흐름이 자연스럽게 도출된다. 기술사 수준에서는 개별 알고리즘 암기를 넘어 이 판별 흐름 자체를 설계 지식으로 체화하고, 주어진 업무 문제에 어떤 패러다임이 적합한지를 근거와 함께 제시할 수 있어야 한다.

6. 심화: 상태 공간 최적화와 최신 활용

DP의 실무 난제는 상태 공간이 메모리를 초과하는 경우다. 대표적 해법이 슬라이딩 윈도(rolling array) 기법 으로, 점화식이 바로 이전 행(dp[i-1])에만 의존하면 2차원 배열을 1차원으로 압축해 공간을 O(nW)에서 O(W)로 줄인다. 배낭 문제에서 용량을 역순으로 순회하면 1차원 배열만으로 정확히 같은 답을 얻는 것이 그 예다. 또한 상태를 비트마스크로 인코딩하는 비트마스킹 DP(bitmask DP) 는 외판원 문제(TSP) 등 집합을 상태로 삼는 문제를 O(2ⁿ·n²)에 푸는데, 이는 완전 탐색의 O(n!)보다 획기적으로 빠르다. n=15면 15!(약 1.3조)와 2¹⁵·15²(약 740만)의 차이로, DP의 위력을 다시 보여준다.

산업 현장의 또 다른 대표 사례는 금융공학의 옵션 가격결정이다. 미국형 옵션(만기 전 조기 행사 가능)의 가치를 구하는 이항 트리 모형은, 만기 시점의 가치에서 거꾸로 각 시점·가격 노드의 가치를 max(즉시 행사 가치, 보유 가치의 할인 기댓값)로 역산하는데, 이는 전형적인 상향식 DP다. 또한 데이터베이스 질의 최적화기(optimizer)는 여러 테이블의 조인 순서를 정할 때, 부분 집합별 최소 비용 조인 계획을 비트마스킹 DP로 탐색해 O(3ⁿ)에 최적 순서를 찾는다(System R 이래의 고전 기법). 통신 분야의 비터비 복호도 합성곱 부호의 최우 경로를 DP로 찾는 것으로, DP가 알고리즘 교과서를 넘어 금융·DB·통신 전반의 핵심 엔진임을 보여준다.

최신 동향으로는 DP가 전통적 알고리즘을 넘어 기계학습·자연어 처리에 깊이 스며들어 있다는 점을 들 수 있다. 음성 인식·필기 인식의 핵심인 은닉 마르코프 모델(HMM) 디코딩은 비터비(Viterbi) 알고리즘이라는 DP로 최적 상태열을 찾고, DNA·단백질 서열 정렬의 Needleman-Wunsch·Smith-Waterman 알고리즘도 편집 거리 계열 DP다. 강화학습의 벨만 방정식(Bellman Equation)은 동적 계획법의 창시자 이름을 그대로 딴 것으로, 가치 반복(Value Iteration)·정책 반복(Policy Iteration)이 모두 DP의 직접적 응용이다. 정보관리기술사 관점에서 DP는 단순한 코딩 기법이 아니라, 최적 의사결정을 다단계로 분해하는 범용 사고 틀로 이해해야 한다.

예상 출제 방향으로는 ① 특정 문제(배낭·LCS·최장 증가 부분수열 등)의 점화식·복잡도 유도, ② 분할정복·탐욕법과의 비교 및 적용 조건 판별, ③ 메모이제이션/타뷸레이션 선택 근거, ④ 의사 다항 복잡도와 NP-난해의 관계 등이 유력하다. 답안 작성 시에는 점화식을 반드시 명시하고, 상태 공간 크기로 복잡도를 유도하며, "왜 탐욕/분할정복이 아닌 DP인가"의 근거(최적 부분구조·중복 부분문제)를 함께 서술하는 것이 고득점 전략이다.

구체적 답안 구성 전략을 예시하면, 1교시 단답형이라도 "정의 → 성립 조건 두 가지 → 대표 점화식 한 개(예: 배낭) → 복잡도 → 타 기법과의 한 줄 비교"의 골격을 갖추면 깊이가 드러난다. 2·3교시 논술형이라면 여기에 ⓐ 개념도(완전 탐색 대 DP의 차이), ⓑ 설계 5단계 절차, ⓒ 2개 이상의 사례별 점화식과 복잡도 유도, ⓓ 상태 공간 최적화(슬라이딩 윈도·비트마스킹) 기법, ⓔ 기술사 관점의 적용 판단(의사 다항의 함정, 패러다임 선택 흐름)을 층층이 쌓는다. 특히 채점자는 "점화식을 세울 줄 아는가"와 "적용 조건을 판별할 줄 아는가"를 핵심 변별점으로 보므로, 암기한 결과가 아니라 상태 정의에서 점화식에 이르는 사고 과정을 서술로 드러내는 것이 결정적이다.

7. 고려사항 및 시사점

  1. 적용 조건의 사전 검증(정확성): DP는 만능이 아니다. 최적 부분구조와 중복 부분문제가 모두 성립하는지를 먼저 검증해야 하며, 최장 단순 경로처럼 부분해 결합이 전체해를 보장하지 못하는 문제에 DP를 적용하면 틀린 답을 낸다. 설계 전 "부분해를 결합해 전체해가 되는가"를 반드시 증명한다.
  2. 공간-시간 트레이드오프의 관리(자원 효율): DP는 시간을 메모리와 교환한다. 상태 공간이 메모리 한계를 넘으면 슬라이딩 윈도·상태 압축·희소 저장(해시맵) 등으로 공간을 줄이는 설계가 필수다. 임베디드·대용량 환경에서는 이 최적화 여부가 적용 가능성을 좌우한다.
  3. 의사 다항 복잡도의 함정(성능 판단): 배낭 문제의 O(nW)처럼 복잡도가 입력 '값'에 비례하면, 값이 클 때 사실상 지수적으로 느려진다. NP-난해 문제가 DP로 풀린다고 해서 모든 규모에서 실용적인 것은 아니므로, 입력 범위를 근거로 적용 타당성을 판단한다.
  4. 패러다임 선택의 전략(설계 판단): 탐욕법이 성립하면 DP보다 빠르고 간단하므로 우선 검토하되, 탐욕 선택 속성 증명에 실패하면 DP로 전환한다. 하위 문제가 독립이면 분할정복이 맞다. 세 패러다임을 배타적으로 보지 말고, 문제 특성에 따라 선택·결합하는 안목이 기술사의 역량이다.
  5. 범용 사고 틀로의 확장(전망·연계 기술): DP는 강화학습(벨만 방정식), 서열 정렬(바이오인포매틱스), 음성·필기 인식(비터비) 등으로 확장되는 범용 최적화 틀이다. 전통 알고리즘을 넘어 AI·데이터 분야의 기반 기술로 연계해 이해하면 응용 범위가 크게 넓어진다.

참고자료

  • Cormen et al., "Introduction to Algorithms", MIT Press (동적 계획법·최적 부분구조)
  • R. Bellman, "Dynamic Programming", Princeton University Press, 1957
  • cp-algorithms, Dynamic Programming: https://cp-algorithms.com/dynamic_programming/

한 줄 요약: 동적 계획법은 최적 부분구조와 중복 부분문제 가 성립하는 문제를 하위 문제로 나눠 그 해를 저장·재사용함으로써 지수적 탐색을 다항 시간으로 줄이는 기법으로, 메모이제이션/타뷸레이션으로 구현하며 탐욕·분할정복과 달리 "모든 경우를 비교하되 중복은 한 번만 계산"하는 설계 판단이 핵심이다.