2026-02-03 | 5 min read | 137 | 동적 프로그래밍 DP 알고리즘

5-1. 동적 프로그래밍 (DP) 소개

1. 동적 프로그래밍(DP)의 이해

동적 프로그래밍(Dynamic Programming, DP)은 복잡한 문제를 작은 부분 문제(subproblem)로 나누어 해결하고, 이 부분 문제들의 해결 결과를 재사용하여 전체 문제를 해결하는 알고리즘 설계 기법입니다. 핵심은 "분할 정복(Divide and Conquer)"과 비슷하지만, 부분 문제의 중복을 해결하여 효율성을 높이는 것입니다. 간단하게 말해, "문제를 쪼개서 풀고, 풀었던 것을 기억해두었다가 다시 써먹는" 방법이라고 할 수 있습니다.

1) 왜 동적 프로그래밍인가?

복잡한 문제는 종종 동일한 부분 문제를 여러 번 반복해서 풀어야 하는 경우가 있습니다. 이때, 각 부분 문제를 매번 처음부터 다시 계산하는 것은 비효율적입니다. DP는 이러한 중복 계산을 피하기 위해 부분 문제의 해답을 저장해두고, 필요할 때마다 참조하여 전체 문제 해결 시간을 단축합니다. DP는 효율적인 문제 해결을 위한 강력한 도구이며, 특히 최적화 문제(optimization problems)에 유용합니다.

2) 동적 프로그래밍과 분할 정복의 비교

두 기법 모두 문제를 작은 단위로 쪼개어 해결한다는 공통점을 가지고 있지만, 중요한 차이점이 있습니다.

특징	분할 정복 (Divide and Conquer)	동적 프로그래밍 (Dynamic Programming)
부분 문제	독립적 (서로 영향을 주지 않음)	중첩될 수 있음 (부분 문제가 다른 부분 문제에 영향을 줄 수 있음, 중복 문제)
해결 방식	부분 문제 해결 → 전체 문제 해결	부분 문제 해결 및 저장 → (중복 문제 해결) → 전체 문제 해결
메모이제이션	X (부분 문제 해결 결과를 저장하지 않음)	O (부분 문제 해결 결과를 저장하여 재사용)
적용 예시	퀵 정렬, 병합 정렬, 이진 탐색	피보나치 수열, 최장 공통 부분 수열, 배낭 문제
시간 복잡도	부분 문제의 크기에 따라 달라짐	부분 문제의 중복 여부 및 메모이제이션 활용에 따라 달라짐 (일반적으로 시간 절약 가능)

분할 정복은 문제를 독립적인 부분 문제로 분할하기 때문에, 부분 문제 간의 의존성이 없는 문제에 적합합니다. 반면, 동적 프로그래밍은 부분 문제 간의 의존성이 있는, 즉, 부분 문제가 중복되는 문제에 효율적입니다.

2. 동적 프로그래밍의 적용 조건

DP를 적용하기 위해서는 두 가지 주요 조건을 만족해야 합니다.

1) 최적 부분 구조 (Optimal Substructure)

전체 문제의 최적 해가 부분 문제들의 최적 해로부터 구성될 수 있어야 합니다. 즉, 전체 문제의 최적 해를 구하기 위해 부분 문제들을 해결하고, 그 해결 결과들을 조합하여 전체 문제의 최적 해를 구성할 수 있어야 합니다. 최적 부분 구조는 DP가 적용될 수 있는 기본적인 조건입니다.

예를 들어, 최단 경로 문제에서 A 지점에서 B 지점까지의 최단 경로는, A 지점에서 중간 지점 X까지의 최단 경로와 X 지점에서 B 지점까지의 최단 경로를 결합하여 구할 수 있습니다.

2) 중복되는 부분 문제 (Overlapping Subproblems)

동일한 부분 문제가 반복적으로 나타나야 합니다. DP는 이 중복되는 부분 문제들의 해결 결과를 저장해두고 재사용함으로써 효율성을 극대화합니다. 만약 부분 문제들이 서로 겹치지 않고 독립적이라면, DP를 사용할 필요가 없으며 분할 정복을 사용하는 것이 더 효율적일 수 있습니다.

3. 동적 프로그래밍 접근 방식

DP는 크게 두 가지 접근 방식으로 구현할 수 있습니다.

1) 탑다운(Top-down) 방식 (Memoization)

탑다운 방식은 재귀 함수를 사용하여 문제를 해결합니다. 재귀 호출 과정에서 부분 문제의 해결 결과를 저장하고, 이미 해결된 부분 문제에 대한 호출이 다시 발생하면 저장된 결과를 반환합니다. 메모이제이션(memoization)은 탑다운 방식의 핵심 기법입니다. 메모이제이션은 중복 계산을 피하고 시간 복잡도를 줄이는 데 기여합니다.

탑다운 방식 설명 뒤

2) 바텀업(Bottom-up) 방식 (Tabulation)

바텀업 방식은 반복문을 사용하여 문제를 해결합니다. 가장 작은 부분 문제부터 해결하고, 그 결과를 이용하여 더 큰 부분 문제를 해결해 나갑니다. 테이블(table)을 사용하여 부분 문제의 해결 결과를 저장하고, 이 테이블을 채워나가는 방식으로 문제를 해결합니다. 탭ulated 방식은 일반적으로 탑다운 방식보다 더 효율적일 수 있습니다.

바텀업 방식 설명 뒤

4. 동적 프로그래밍 예시: 피보나치 수열

피보나치 수열은 DP의 대표적인 예시입니다. 피보나치 수열은 다음과 같이 정의됩니다.

$F(0) = 0$
$F(1) = 1$
$F(n) = F(n-1) + F(n-2)$, for $n \ge 2$

1) 재귀를 이용한 피보나치 수열 (Top-down, Memoization)

def fibonacci_recursive(n, memo={}):
  if n in memo:
    return memo[n]
  if n <= 1:
    return n
  memo[n] = fibonacci_recursive(n-1, memo) + fibonacci_recursive(n-2, memo)
  return memo[n]

위 코드는 메모이제이션을 사용하여 피보나치 수열을 계산합니다. memo 딕셔너리를 사용하여 이미 계산된 결과를 저장하고, 중복 계산을 방지합니다.

2) 반복문을 이용한 피보나치 수열 (Bottom-up, Tabulation)

def fibonacci_iterative(n):
  if n <= 1:
    return n
  fib_table = [0, 1]
  for i in range(2, n + 1):
    fib_table.append(fib_table[i-1] + fib_table[i-2])
  return fib_table[n]

위 코드는 탭ulated 방식을 사용하여 피보나치 수열을 계산합니다. fib_table 리스트에 부분 문제의 해결 결과를 저장하고, 반복문을 통해 테이블을 채워나갑니다.

3) 성능 비교

재귀 방식(메모이제이션)과 반복 방식(탭ulated) 모두 피보나치 수열을 효율적으로 계산하지만, 일반적으로 탭ulated 방식이 재귀 방식보다 더 빠릅니다. 재귀 방식은 함수 호출 오버헤드가 발생할 수 있지만, 탭ulated 방식은 반복문을 사용하므로 오버헤드가 적습니다. 피보나치 수열의 경우, 시간 복잡도는 $O(n)$으로 동일하지만, 실제 실행 시간은 탭ulated 방식이 더 빠릅니다.

5. 동적 프로그래밍 활용 사례

DP는 다양한 분야에서 활용됩니다.

1) 최적화 문제

배낭 문제 (Knapsack Problem): 주어진 가치와 무게를 가진 물건들을 배낭의 용량 제한 내에서 가장 가치 있는 조합을 찾는 문제입니다.
최장 공통 부분 수열 (Longest Common Subsequence, LCS): 두 문자열의 부분 수열 중 가장 긴 공통 부분 수열을 찾는 문제입니다.
최단 경로 문제 (Shortest Path Problems): 그래프에서 두 노드 사이의 최단 경로를 찾는 문제입니다 (예: 다익스트라 알고리즘, 벨만-포드 알고리즘).

2) 게임 이론

게임의 최적 전략 계산: 게임의 각 상태에서 최적의 선택을 계산하여 승리 전략을 수립합니다.
미니맥스 알고리즘 (Minimax Algorithm): 두 명의 플레이어가 번갈아 가며 수를 두는 게임에서 최적의 수를 찾는 알고리즘입니다.

3) 컴퓨터 과학

문자열 편집 거리 (Edit Distance): 두 문자열을 동일하게 만들기 위해 필요한 최소한의 연산 횟수(삽입, 삭제, 변경)를 계산합니다.
컴파일러 최적화: 코드 최적화에 사용됩니다.

6. 주의사항 및 트러블 슈팅

1) 문제 정의의 명확성

DP를 적용하기 전에, 문제를 정확하게 정의하고 부분 문제로 어떻게 나눌 수 있는지 명확하게 파악해야 합니다. 잘못된 문제 정의는 잘못된 DP 설계를 초래할 수 있습니다.

2) 점화식의 설계

DP의 핵심은 점화식(recurrence relation)을 설계하는 것입니다. 점화식은 부분 문제 간의 관계를 정의하며, 전체 문제를 해결하기 위한 중요한 단서입니다. 점화식 설계 시, 부분 문제의 정의, 부분 문제 간의 관계, 기저 사례(base case) 등을 신중하게 고려해야 합니다.

3) 메모리 사용량

DP는 부분 문제의 해결 결과를 저장하기 때문에, 메모리 사용량이 증가할 수 있습니다. 메모리 제한이 있는 경우, 메모리 사용량을 최소화할 수 있는 방법을 고려해야 합니다. 예를 들어, 1차원 DP 테이블을 사용하는 경우, 이전 단계의 결과만 저장하여 메모리 사용량을 줄일 수 있습니다.

4) 시간 복잡도 분석

DP의 시간 복잡도를 분석하여 효율성을 확인해야 합니다. DP의 시간 복잡도는 부분 문제의 수와 각 부분 문제를 해결하는 데 걸리는 시간에 따라 결정됩니다. 시간 복잡도가 너무 높은 경우, DP 설계를 다시 고려해야 할 수도 있습니다.

7. 결론

동적 프로그래밍은 복잡한 문제를 효율적으로 해결하기 위한 강력한 알고리즘 설계 기법입니다. 최적 부분 구조와 중복되는 부분 문제라는 두 가지 조건을 만족하는 문제에 적용할 수 있으며, 탑다운(메모이제이션) 방식과 바텀업(탭ulated) 방식의 두 가지 접근 방식을 통해 구현할 수 있습니다. 피보나치 수열과 같은 간단한 예시부터 최적화 문제, 게임 이론, 컴퓨터 과학 등 다양한 분야에서 활용되며, 문제 해결 능력을 향상시키는 데 기여합니다. DP는 알고리즘 학습의 중요한 부분이며, 꾸준한 연습을 통해 숙달할 수 있습니다.