동적 계획법 / 다이나믹 프로그래밍 Dynamic Programming

https://school.programmers.co.kr/learn/courses/30/lessons/12914

프로그래머스

 

위 문제는 "합이 n이 되는 1과 2의 조합 개수" 로 핵심을 추려볼 수 있고,

이러한 문제는 대표적인 동적 계획법 (Dynamic Programming, DP) 문제라 할 수 있다.

동적 계획법 / "기억하며 풀기"

DP의 핵심은

1. 문제를 작은 범위로 나누기

2. 특정 범위에 대한 답을 구하기 위해 다른 부분에서 구한 답을 기억 및 활용

하는 방식으로 알고리즘을 설계하는 기법이다.

 

어떻게 보면 분할 정복/재귀와 비슷하다고 볼 수 있는데 가장 큰 차이는 아래와 같다.

DP	- 상향식(bottom-up) : 작은 범위의 문제에 대한 해부터 시작해 결과를 저장 및 활용하며 점진적으로 상위 문제에 대한 해를 구한다. - 메모이제이션 (Memoization) 활용 : 이전 계산된 값을 저장하고 다음 계산에서 활용함으로써 이미 계산된 값을 다시 계산하지 않도록 최적화한다. - 부분 문제들이 중복된다.
분할 정복	- 하향식(top-down) : 주어진 범위의 문제를 나누어 각각의 해를 구하며 다시 합병함으로써 처음 문제의 해를 구한다. - 재귀 함수 활용 - 부분 문제들이 중복되지 않는다.

 

 

문제에 적용

n = 1 인 경우, 1 (1개)

n = 2 인 경우, 1+1, 2+0 (2개)

n = 3 인 경우, 2+1, 1+2, 1+1+1 (3개)

=> 2+(n = 1인 경우) 와 1+(n = 2인 경우)

n = 4 인 경우, 2+2, 2+1+1, 1+2+1, 1+1+2, 1+1+1+1 (5개)

=> 2+(n = 2인 경우) 와 1+(n = 3인 경우)

 

즉 f(i) = f(i-1) + f(i-2) 로 생각해볼 수 있으며, 이는 피보나치 수열 문제와 동일하다.

 

DP 를 활용해 메모이제이션을 동반한 상향식으로 알고리즘을 설계한다면,

1. f(2) = f(1) + f(0) 부터 시작하여 f(n) = f(n-1) + f(n-2) 까지 루프

2. 각 단계의 f(i-1) 과 f(i-2) 을 기록 및 업데이트

 

따라서 아래와 같이 반복문을 통해 점진적으로 상위 문제를 해결함으로써 f(n) 을 구할 수 있다.

// base case
if (n <= 1) return 1;

long long MinusOne = 1;
long long MinusTwo = 1;

for (int i = 2; i <= n; i++)
{
	long long current = (MinusOne + MinusTwo) % 1234567;
    MinusTwo = MinusOne;
    MinusOne = Current;
}

// 루프를 빠져나올 때 current 가 MinusOne 에 대입된 상태이므로 MinusOne 반환
return MinusOne;