동적 프로그래밍(Dynamic Programming)

동적 프로그래밍(Dynamic Programming) 제대로 이해하기

문제를 쪼개고, 기억하고, 다시 쓰는 사고 방식

1. 동적 프로그래밍은 알고리즘이 아니다

동적 프로그래밍(Dynamic Programming, 이하 DP)은
특정 문제를 푸는 하나의 알고리즘이 아니다.

DP는 문제를 해결하는 사고 방식이자 설계 전략이다.

 

같은 계산을 여러 번 반복하게 되는 문제를
“작은 문제로 나누고, 그 결과를 저장하여 재사용”함으로써
전체 문제를 효율적으로 해결하는 접근 방식이 바로 동적 프로그래밍이다.

 

2. 왜 동적 프로그래밍이 필요한가

다음과 같은 문제를 생각해보자.

• 피보나치 수열을 재귀로 구현
• 계단을 오르는 경우의 수를 단순 재귀로 계산

이 방식의 공통점은 다음과 같다.

• 동일한 하위 문제가 여러 번 계산됨
• 호출 횟수가 기하급수적으로 증가
• 입력 크기가 조금만 커져도 시간 초과 발생

동적 프로그래밍은
이 중복 계산 문제를 제거하기 위해 등장했다.

 

3. 동적 프로그래밍이 적용 가능한 조건

모든 문제에 DP를 적용할 수는 없다.
다음 두 조건을 반드시 만족해야 한다.

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

• 문제를 작은 문제로 나누었을 때
• 동일한 작은 문제가 여러 번 등장하는 경우

이때 결과를 저장해두면
다음 계산에서 그대로 사용할 수 있다.

 

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

• 큰 문제의 최적해가
• 작은 문제들의 최적해로부터 구성되는 경우

예를 들어,
“전체 최소 비용”이
“부분 최소 비용”의 조합으로 만들어질 수 있어야 한다.

이 두 조건이 동시에 만족될 때만
동적 프로그래밍을 적용할 수 있다.

 

4. 동적 프로그래밍의 두 가지 구현 방식

DP는 구현 방식에 따라 두 가지로 나뉜다.

메모이제이션 (Top-Down 방식)

• 재귀 기반
• 계산한 결과를 배열이나 맵에 저장
• 필요한 순간에만 계산 수행

특징:

• 구현이 직관적
• 기존 재귀 코드에 쉽게 적용 가능
• 재귀 깊이가 깊으면 스택 오버플로우 위험 존재

 

테이블링 (Bottom-Up 방식)

• 반복문 기반
• 가장 작은 문제부터 순차적으로 계산
• 테이블을 채워가며 결과 도출

특징:

• 스택 오버플로우 위험 없음
• 실행 흐름이 명확
• 계산 순서를 직접 설계해야 함

중요한 점은
두 방식은 개념의 차이가 아니라 구현 방식의 차이라는 것이다.

 

5. 동적 프로그래밍 문제 접근 공식

DP 문제를 처음 마주했을 때
다음 절차를 따르면 안정적으로 접근할 수 있다.

1단계: 상태(State) 정의

• 어떤 값을 저장할 것인가
• 배열의 인덱스가 무엇을 의미하는가

2단계: 점화식 도출

• 현재 상태가 이전 상태들로부터 어떻게 계산되는가

3단계: 초기값 설정

• 가장 작은 문제의 답은 무엇인가

4단계: 계산 순서 결정

• 작은 문제부터 큰 문제로 계산 가능한가

5단계: 정답 추출

• 최종적으로 어떤 상태가 문제의 답인가

이 다섯 단계는
모든 DP 문제에 공통적으로 적용된다.

 

6. 대표적인 동적 프로그래밍 문제 유형

1차원 DP

• 피보나치 수열
• 계단 오르기
• 최대 연속 부분 합

특징:

• 상태가 하나의 인덱스로 표현됨
• 입문 단계에서 가장 많이 접함

 

2차원 DP

• 최장 공통 부분 수열(LCS)
• 편집 거리(Edit Distance)
• 격자 경로 문제

특징:

• 두 가지 기준을 동시에 고려
• 상태 정의가 핵심

 

배낭 문제(Knapsack Problem)

• 제한된 자원 내에서 최대 가치 선택
• 상태 정의와 점화식 설계 능력이 중요

DP 사고력이 본격적으로 요구되는 유형이다.

 

7. 다른 알고리즘 기법과의 비교

동적 프로그래밍은 다른 기법과 다음과 같이 구분된다.

• 그리디 알고리즘
  매 순간의 선택이 항상 최적일 때 사용
• 분할 정복
  부분 문제가 서로 독립적일 때 사용
• 동적 프로그래밍
  부분 문제가 서로 겹칠 때 사용

문제의 성격을 먼저 파악하는 것이
알고리즘 선택의 출발점이다.

 

8. 자주 발생하는 오해

• 모든 최적화 문제는 DP로 풀 수 있다
  → 아니다. 조건을 만족해야 한다.
• DP는 반드시 배열을 사용해야 한다
  → 아니다. 맵이나 캐시 구조도 가능하다.
• 점화식 없이 DP를 구현할 수 있다
  → 불가능하다. 점화식은 DP의 핵심이다.

 

9. 정리

동적 프로그래밍은
문제를 푸는 기술이 아니라 문제를 설계하는 방식이다.

• 상태를 어떻게 정의하는가
• 중복 계산을 어떻게 제거하는가
• 작은 문제를 어떻게 쌓아 올리는가

이 세 가지를 명확히 할 수 있다면
동적 프로그래밍은 더 이상 어렵지 않다.