DP(다이나믹 프로그래밍)

동적 계획법

하나의 큰 문제를 작은 문제로 나누어 푸는 알고리즘
중복되는 부분 문제를 memorization함으로써 반복 계산을 피해 효율성을 높임

 

재귀 vs DP

• 재귀는 함수가 자기 자신을 호출하여 문제를 푸는 방식, 중복된 계산 발생 가능
• DP 구현 방법 중 재귀 포함 (Top-Down 방식)
• DP는 재귀와 유사하지만, 결과를 저장하고 재활용함으로써 기하급수적인 함수 호출을 막음
• memorization 차이 !

 

 

분할 정복 vs DP

• 분할 정복은 문제를 작고 독립적인 하위 문제로 나누고, 각 문제를 독립적으로 해결
  중복된 계산이 없으며, 한 번 계산된 값은 재사용되지 않음.
• DP는 부분 문제들이 동일하며, 중복된 부분 문제들을 memorization하고 재사용함
  중복된 계산을 피하고, 동일한 하위 문제를 여러 번 풀지 않음
• 즉, 분할 정복은 하위 문제들이 독립적이고 중복되지 않지만 DP는 동일한 하위 문제들이 반복되므로 그 계산 결과를 저장하고 재사용하는 방식 !

 

 

DP 사용 조건

 

1. 겹치는 부분 문제

• 동일한 작은 문제들이 반복해서 나타나는 경우
• 이진탐색의 경우, 위치를 찾으면 바로 반환 ≫ 재사용하지 않으므로 DP 사용 X
• 피보나치 수열의 경우, 같은 연산이 계속 호출됨 ≫ 재사용함으로써 반복 연산 방지 ≫ DP

2. 최적 부분 구조

• 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우
• 전체 문제에 부분 문제에서 구한 최적 결과가 그대로 쓰여짐
• 예) A → B → C 에서 최단 경로는 (A → B의 최단 경로) + (B → C의 최단경로)
  A → B에서의 최적의 결과(최단 경로)가 전체 최단 경로에 동일하게 적용됨

 

 

DP 사용 절차

 

1. 문제를 분할, 부분 문제 정의

 

2. 문제의 변수 파악

• N 구하기
• 예) 피보나치 수열의 N번째 숫자 구하기
• N이 변수가 되고, 점화식에서의 N번째 결과값이 답이 됨

3. 점화식 만들기

• 반복 / 재귀를 통해 문제가 자동으로 해결되도록 하는 관계식
• 특정 상태의 값을 결정할 때 이전 상태의 값을 어떻게 활용할 수 있을지 생각하기

4. memorization

• 결과를 저장할 배열 등을 만들고 결과가 나올 때마다 배열에 저장 → 이후에 재사용

5. 기저 상태 파악

• 가장 작은 문제의 상태를 파악
• 모르겠을 땐 몇 가지 예시를 직접 테스트하여 구성하기

6. 구현

• Bottom-Up 방식 : 반복문을 통해 idx 값에 대해 이전 배열값을 재사용하여 점화식을 통해 dp[idx] 설정
• Top-Down 방식 : dp[n]의 값을 찾기 위해 idx가 n일 때부터 바로 호출을 시작, 기저 상태까지 내려간 후 재귀를 통해 값 재활용 ≫ 이미 이전에 계산을 완료한 경우에는 단순히 dp[idx] 값을 return

 

 

DP 사용하는 대표적인 문제 유형

 

1. 배낭 문제 (Knapsack Problem)

 

2. 최장 공통 부분 수열 (LCS, Longest Common Subsequence)

 

3. 최소 편집 거리 (Edit Distance)

 

4. 가장 긴 증가하는 부분 수열 (LIS, Longest Increasing Subsequence)

 

5. 피보나치 수열

 

6. 다익스트라 알고리즘 (Dijkstra)