DP 개념 정리

동적 프로그래밍 (DP, Dynamic Programming)

- 통산적으로 메모리를 더 사용하여 시간 복잡도 개선할 때 많이 사용됨

- DP로 문제를 해결하기 위해 '점화식'을 찾는 것이 핵심 과정

 

동적 프로그래밍은 아래의 두 조건을 만족할 때 사용가능하다

1. 최적 부분 구조(optimal substructure) 
 큰 문제를 유사한 형태의 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아 큰 문제를 해결한다.

2. 반복되는 부분 문제(overlapping sub-problem) 
 동일한 작은 문제를 반복적으로 해결해야 한다. 

 

점화식 

- 인접한 항으로 현재 값을 결정하는 관계식을 의미함 

- 점화식은 "재귀 함수"로 표현가능 

예) 파보나치 수열 점화식  
An = (An-1) + (An-2)  
(이때 초기값 a1 = 1, a2 = 1)

 

점화식의 기본 구성 요소는 다음과 같다

 

1. 초기항 : 종료 조건 역할을 함

2.인접한 항과의 관계  

 

DP 문제 해결 접근 순서/방식 

문제 이해 -> 점화식 찾기* -> 상향식/하향식 구현 방식 결정 -> 점화식을 실제 코드로 구현

(1) 상향식 (bottom-up) : 반복문을 이용해 초기 항부터 차근차근 계산한다. 

(2) 하향식 (top-down) 

- 재귀 함수로 구현 ('큰 문제를 해결하기 위해 작은 문제를 호출 후 해결하여 결과 찾는 방식')

- 이미 구한 함수 값을 담는 테이블을 흔히 'DP 테이블/캐쉬 테이블/memoization' 이라 함 

- 하향식의 단점으로 스택 오버플로우가 발생 가능

---

대표적인 동적 프로그래밍 문제

1) 피보나치 수열 

 

하향식 

// 한번 계산된 결과를 Memoization하기 위한 배열 초기화
const arr = new Array(100).fill(0);

function fibo(x) {
    // 종료 조건
    if(x === 1 || x === 2) return 1;
    
    // 이미 계산한 적있는 문제인 경우 
    if(arr[x] !== 0) return arr[x];
    
    // 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
    arr[x] = fibo(x - 1) + fibo(x - 2);
    return arr[x];
}

console.log(fibo(99));

 

상향식

// 한번 계산된 결과를 Memoization하기 위한 배열 초기화
const arr = new Array(100).fill(0);

arr[1] = 1;
arr[2] = 1;
const n = 99;

// 피보나치 함수(Fibonacci Function)을 반복문으로 구현(bottom-up 방식)
for(let i = 3; i <= n; i++) {
    arr[i] = arr[i - 1] + arr[i - 2];  
}

console.log(arr[n]);

 

2) 1로 만들기(실버3) 

X를 1로 만들 때 최소 연산 횟수 구하는 문제 (이때 X는 1 이상 10^6 이하)

- 3으로 나누는 경우

- 2로 나누는 경우

- 1을 빼는 경우

 

상향식

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

const n = Number(file[0]);

const dp = new Array(1000001).fill(0);

// bottom-up, 상향식
for(let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + 1;
    
    if(i % 2 === 0) {
        dp[i] = Math.min(dp[i], dp[i / 2] + 1);
    }
    
    if(i % 3 === 0) {
        dp[i] = Math.min(dp[i], dp[i / 3] + 1);
    }
}

console.log(dp[n]);