개념

• 하나의 큰 문제를 여러 개의 작은 문제로 나눈 뒤
• 그 결과를 저장하여 더 큰 문제를 해결하는 것
  • 분할(divide) + 캐싱(caching)

사용하는 이유

• 재귀(Recursion)와 유사
• 재귀를 단순 사용하면 동일한 작은 문제들이 여러 번 반복되는 비효율성 증가

예: 단순 재귀 + 피보나치 수열

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 ...

• 재귀로 함수를 구성하면 return f(n) = f(n-1) + f(n-2)
• f(n-1)에서 한 번 구한 값을 f(n-2)에서 또 구하는 과정 반복
• 피보나치 항이 100번 째만 되어도 함수 호출 횟수가 기하급수적으로 증가
  • 약 7해, #,###경 #,###조 => 컴퓨터 사망

해결

• 한 번 구한 값의 결과를 저장해두고 재사용
  => 100번째를 구해도 약 200회 이내에 계산이 가능해짐
  
• 시간 복잡도로 따지면 O(n^2) → O(f(n))로 개선 (문제에 따라 다를 수 있음)

사용 조건

동적 계획법 적용을 위해 만족해야 할 조건 2가지

2. Overlapping Subproblems

• 하위 문제가 겹쳐야 함
• 동적 계획법을 쓰려면 연산 간 겹치는 부분이 있어야 함
• 연산 간에 특정 부분이 반복적으로 쓰이지 않는다면 앞 부분 결과를 저장해두어도 의미가 없으므로 동적 계획법 사용 불가

Optimal Substructure

• 부분 문제의 최적 값으로 전체 문제의 최적 결과를 낼 수 있는 경우
  • 예: A-B 사이의 가장 짧은 경로 찾기

• 위 그림에서 A-X 사이의 최단 거리는 AX2이고 X-B는 BX2이다.
  => 전체 최단 경로는 AX2-BX2

• 다른 경로를 택한다고 해서 전체 최단 경로가 변할 수는 없음

• 부분 문제에서 구한 최적의 결과가 전체 문제에서도 동일하게 적용되어 결과가 변하지 않을 때

  • 예: 피보나치 수열도 해당
  • 동일하게 이전의 계산 값을 그대로 사용하여 전체 답을 구할 수 있음

문제 풀이 과정

1. DP로 풀 수 있는 문제인지 확인

• 위의 두 조건에 해당하는지 확인한다.

DP로 풀 수 있는 문제 예시

• 특정 데이터 내 최대화/최소화 계산
• 특정 조건 내 데이터 카운팅(갯수/횟수 세기)
• 확률 계산

2. 문제에서 변하는 값인 변수 파악

• DP는 현재 변수에 따라 그 결과 값을 찾고 그것을 전달하여 재사용하는 과정
• 즉, 문제 내 변수의 개수를 알아내야 함 (= "state" 결정)
• 예: 피보나치 수열
  • n번째 숫자를 구해야 하므로 n이 변수
• 예: 문자열 간 차이 구하기
  • 문자열의 길이, Edit 거리로 2가지 변수 (문제 몰라도 됨)
• 예: 유명한 Knapsack 문제
  • index, 무게로 2가지 변수 필요

3. 변수 간 관계식 만들기 (= 점화식)

• DP: 변수들에 의해 결과 값이 달라지고, 동일한 변수의 경우 결과 값이 동일하며, 그 결과 값을 그대로 이용
  => 이를 구조적으로 표현하는 관계식을 생성한다.
• 예: 피보나치 수열의 점화식: f(n) = f(n-1) + f(n-2)

4. 메모하기 (memoization)

• 변수 값에 따른 결과 값을 저장 (= 메모)
• 방법
  • 변수 값에 따른 결과를 저장할 배열 등을 미리 생성
  • 결과가 나올 때마다 배열 내에 저장
  • 이후 배열에 저장된 값 재사용

5. 기저 상태(= 초기 상태) 파악하기

• 가장 작은 문제의 상태(state)를 알아내는 것
• 보통 몇 가지 예시를 직접 손으로 테스트하여 파악
• 예: 피보나치 수열의 기저 상태
  • f(0) = 0와 f(1) = 1
  • 다음 연산이 반복되어도 가장 작은 문제(변수)는 이 2개
• 해당 초기 문제의 결과 값을 파악한 후 배열 등에 저장하여 재활용

6. 구현하기

• 실제로 DP로 구현하는 법은 2가지

1. Bottom-Up: 반복문 사용 (Tabulation 방식)

• 아래에서부터 계산을 수행하고 누적시켜서 전체 큰 문제를 해결하는 것
• 예: 메모를 위해서 dp 배열 생성
  • 이것이 1차원이라 가정했을 때, dp[0]가 기저 상태이고 dp[n]은 목표 상태
  • dp[0]부터 시작하여 반복문을 통해 점화식으로 결과를 내고 dp[n]까지 그 값을 재활용

Tabulation의 의미?

• 반복을 통해 dp[0]부터 하나 하나씩 채우는 과정을 "table-filling"이라고 함
• 이 Table에 저장된 값에 직접 접근하여 재활용하는 것을 가리켜 Tabulation이라는 명칭이 붙음
• 결과 값을 기억하고 재활용한다는 측면에서 근본 개념은 Memoization과 유사

2. Top-Down: 재귀 사용 (Memoization 방식)

• 위에서부터 호출을 시작하여 dp[0]의 상태까지 내려간 다음 해당 결과 값을 재귀를 통해 전이시켜 재활용
• 예: 피보나치 수열
  • f(n) = f(n-2) + f(n-1)의 과정에서 n=5일 때 f(3), f(2)의 동일한 계산이 반복적으로 나오게 됨
  • 이 때 이미 이전에 계산을 완료한 경우 단순히 메모리에 저장되어 있는 내역을 꺼내서 활용
    => 가장 최근의 상태 값을 메모해 두었다고 하여 Memoization

번외: Divide and Conquer(분할 정복)와 차이점은?

공통점

• 주어진 문제를 작게 쪼개서 하위 문제로 해결하고
• 이후 연계적으로 큰 문제를 해결한다는 점

차이점

• 분할 정복
  • 분할된 하위 문제가 동일하게 중복이 일어나지 않는 경우
• 동적 프로그래밍
  • 연산 간 동일한 중복이 발생하는 경우

참고자료

알고리즘 - Dynamic Programming(동적 계획법) - by jjong1991