동적계획법(DP, Dynamic Programming)

*️⃣ 개념

• 복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법
• 큰 문제를 작은 문제로 나눈 뒤, 기억하여 푸는 기법(시간 복잡도↓ 공간복잡도↑)

1. 알고리즘 기법
문제를 해결하기 위해 사용되는 절차적인 방법 또는 계획
(EX, 정렬 알고리즘, 검색 알고리즘, 그래프 탐색 알고리즘 등)

2. 알고리즘 설계 기법
문제 해결을 위해 알고리즘을 설계하는 방법이나 접근 방식. 설계 기법은 알고리즘을 개발하고 구현하는 데 사용되는 전략이나 원칙들을 포함한다.
(EX, 분할 정복, 동적 계획법, 탐욕적 알고리즘, 백트래킹 등)

 

*️⃣ DP과 재귀적 호출의 차이점

1. 하향식(Top-down) vs 상향식(Bottom-up) 접근

재귀적 호출은 주로 하향식(top-down) 접근 방식을 사용한다. 큰 문제를 작은 하위 문제로 나누어 해결하는 방식이다.

동적 계획법은 주로 상향식(bottom-up) 접근 방식을 사용한다. 작은 하위 문제들부터 시작하여 그 결과를 저장하고, 이를 이용하여 점진적으로 큰 문제의 해를 구해나간다.

 

2. 메모이제이션(Memoization)

DP는 중복되는 계산 결과를 저장하는 메모리 기법인 메모이제이션을 사용한다. 이를 통해 이전에 계산한 값을 캐시하고, 다시 필요할 때 해당 값을 가져와 재사용한다. 이는 재귀적 호출에서의 중복 계산을 방지하고 계산 속도를 향상시킨다.

 

 

*️⃣ DP 기법을 적용시킬 수 있는 조건

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

DP는 기본적으로 문제를 나누고 그 문제의 결과 값을 재활용해서 전체 답을 구한다. 그래서 동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능하다.

 

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

부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우 사용이 가능하다.

 

 

*️⃣ DP 문제 해결 방식

• 메모하기
  변수 값에 따른 결과를 저장할 배열 등을 미리 만들고 그 결과를 나올 때마다 배열 내에 저장하고 그 저장된 값을 재사용하는 방식으로 문제를 해결해 나간다.
• 변수 간 관계식(점화식) 만들기
  예를 들어 피보나치 수열의 f(n) = f(n-1) + f(n-2) 라는 식

 

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

• 작은 부분 문제부터 차례대로 해결하여 전체 문제를 해결하는 방식
• 반복문을 사용하여 반복적으로 부분 문제들을 해결하고, 결과를 배열 등에 저장
• 일반적으로 더 직관적이고 이해하기 쉽다. 또한, 모든 작은 부분 문제를 해결하므로 최적 부분 구조를 보장

 

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

• 큰 문제를 작은 부분 문제로 나누어 해결하는 방식
• 재귀 함수를 사용하여 문제를 작은 부분 문제들로 쪼개고, 중복 계산을 피하기 위해 이전에 계산한 값을 저장하는 Memoization(캐싱을 통해 이전 계산 결과를 저장하여 중복 계산을 피하는 것)을 활용
• 필요한 부분 문제만 해결하므로 계산 시간을 절약할 수 있다. 하지만 재귀 호출의 오버헤드가 발생할 수 있으며, 모든 작은 부분 문제를 해결하지 않을 경우 최적 부분 구조를 보장하지 않을 수 있다.

 

 

*️⃣ 대표적인 DP 문제들

1. 피보나치 수열 > Top-Down 방식

피보나치 수열은 이전 두 항의 합으로 이루어지는 수열이다. 동적 계획법을 사용하여 피보나치 수열을 구할 수 있다. 작은 문제부터 시작하여 계산 결과를 저장하고 이를 이용하여 큰 문제의 해를 구한다.

// 백준 9461
// https://www.acmicpc.net/problem/9461

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

function solution(arr) {
  const N = +arr[0];
  const result = [];

  for(let i = 1; i <= N; i++) {
    result[i-1] = pado(+arr[i]);
  }

  return result.join('\n');
}

function pado(n) {
  const dp = new Array(n + 1);

  dp[0] = 0;
  dp[1] = 1;
  dp[2] = 1;

  // 점화식
  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 2] + dp[i - 3];
  }

  return dp[n];
}


console.log(solution(input));

 

2.  배낭 문제(Knapsack Problem) > Bottom-Up 방식

주어진 가방의 용량에 최대한 가치가 높은 물건을 넣는 문제이다. 각 물건은 가치와 무게를 가지고 있으며, 동적 계획법을 사용하여 가방의 용량에 따른 최대 가치를 구할 수 있다.

 

3. 최장 증가 부분 수열(Longest Increasing Subsequence) > Bottom-Up 방식

주어진 수열에서 순서를 유지하면서 가장 긴 부분 수열을 찾는 문제이다. 동적 계획법을 사용하여 각 원소를 마지막으로 하는 부분 수열의 길이를 저장하고, 이를 이용하여 전체 최장 증가 부분 수열의 길이를 구할 수 있다.

 

4. 최단 경로 문제(Shortest Path Problem) > Bottom-Up 방식

주어진 그래프에서 시작 노드부터 도착 노드까지의 최단 경로를 찾는 문제이다. 동적 계획법을 사용하여 각 노드까지의 최단 거리를 저장하고, 이를 이용하여 최단 경로를 찾을 수 있다.

 

5. 문자열 편집 거리 문제(Edit Distance Problem) > Bottom-Up 방식

두 문자열 사이의 최소 편집 거리를 찾는 문제이다. 편집 연산은 문자 삽입, 삭제, 대체 등이 있으며, 동적 계획법을 사용하여 각 문자열의 부분 문자열까지의 최소 편집 거리를 저장하고, 이를 이용하여 전체 편집 거리를 구할 수 있다.

 

참고  https://velog.io/@boyeon_jeong/%EB%8F%99%EC%A0%81%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming

백준 https://www.acmicpc.net/problemset?sort=ac_desc&algo=25

 

 

+) Tree DP

• TreeDP는 Tree구조에서 서브트리(부분 문제)의 해를 가지고 전체 해를 구하는 방식이다.
• DP에 서브트리의 어떠한 것(서브트리의 노드 개수, 서브트리의 간선 개수 등등)을 저장하고, 보통 DFS를 통해 탐색하면서 서브트리의 해를 구해나간다.
• 정점을 기준으로 탐색해나간다면, 보통 O(N)만에 풀린다.

참고 및 관련 문제 ➔ https://cano721.tistory.com/175