[알고리즘] 다이나믹 프로그래밍 (DP)

 

큰 문제를 작은 문제로 나눠서 푸는 알고리즘

 

이름에 의미부여 하지 말자.... 다이나믹 = 아무 의미 없음

 

 

목차

• 다이나믹 프로그래밍을 이용해 풀 수 있는 문제의 특징
• 다이나믹 프로그래밍 구현 방법
• 다이나믹 프로그래밍 문제 풀이법
• 다이나믹 프로그래밍 문제 유형

 

▶ 다이나믹 프로그래밍을 이용해 풀 수 있는 문제의 특징

 

1. 중복되는 부분 문제

→ 동일한 작은 문제를 반복적으로 해결해야함

 

ex) 피보나치 수

F0 = 0

F1 = 1

Fn(큰문제) = Fn-1(작은문제)  +  Fn-2(작은문제) // 점화식을 반복적으로 해결해야 함

 

 

2. 최적 부분 구조
→ 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다

ex) 피보나치 수

F0 = 0

F1 = 1

Fn(큰문제) = Fn-1(작은문제)  +  Fn-2(작은문제) 

 

 

★ 다이나믹 프로그래밍과 분할 정복의 차이점은 부분 문제의 중복이다! 

DP는 각 부분 문제들이 서로에게 영향을 미치며 부분 문제가 중복된다
(EX. 피보나치 수에서 F4는 F5를 구할때도 F6을 구할때도 쓰임)
BUT! 분할정복은 동일한 부분 문제가 반복적으로 계산되지 않는다 

 

 

▶ 다이나믹 프로그래밍 구현 방법

 

1. Top-down (재귀)

ex) 위에서 구현한 피보나치

 

2. Bottom-up (반복문)

ex) 반복문을 이용한 피보나치

int d[100];
int fibonacci(int n) {
    d[0] =0;
    d[1] =1;
    for(int i=2; i<=n; i++) 
    {
        d[i] = d[i-1] + d[i-2];
    }
    return d[n];
}

 

질문 사항

• top-down 보다 bottom-up이 더 시간 복잡도가 더 빠른가? --> 알수 없음!
• top-down이나 bottom-up 중에 하나만 써야하는 경우가 있나? --> 있긴한데 어려운 경우 (cpp, java인 경우 둘다 사용하고 python인 경우는 bottom-up을 사용하자)

★ 이미 계산된 결과(작은 문제)는 별도의 메모리 영역(배열)에 저장한다 -> memoization 이용!

->top-down 방식에서 주로 이용

ex) memoization 사용 안한 피보나치 vs 사용한 피보나치

 

memoization 사용 안한 피보나치 : 시간복잡도 O(2^n)

int fibonacci(int n) 
{
	if (n <= 1) 
	{
		return n;
	} 
	else
	{
		return fibonacci(n-1) + fibonacci(n-2);
	}
}

 

 

 

memoization 사용한 피보나치 : 시간복잡도 O(N)

int memo[100];
int fibonacci(int n) 
{
    if (n <= 1) 
    {
		return n;
    } 
    else 
    {
    	if(memo[n] > 0) return memo[n];
        memo[n] = fibonacci(n-1) + fibonacci(n-2);
        return memo[n];
    }
}

 

 

▶ 다이나믹 프로그래밍 문제 풀이법

1. 점화식의 정의를 세운다

ex) 1로 만들기에서 점화식 -> D[N] = N을 1로 만드는 최소 연산 횟수 

ex) 2 * N 타일링에서 점화식 -> D[N] = 2 * N을 채우는 방법의 수

 

2. 큰 문제를 작은 문제로 나눌때는 문제의 단계 하나와 나머지 전체 단계로 나눈다

ex) 1로 만들기에서 N을 N/3 하는 단계 1개(문제의 단계 하나)와 N/3에서 1까지 가는 나머지 전체 단계

-> D[N] = 1 + D[N/3]

ex) 2 * N 타일링에서 가장 오른쪽에 타일을 놓을수 있는 방법은 가로, 세로이다(문제의 단계 하나) 

-> D[N] = D[N-1](세로타일 놓았을 경우) + D[N-2](가로타일 놓았을 경우)

 

3. 별도의 메모리 영역에 점화식의 결과를 저장하자

ex) 점화식의 결과 D[0], D[1], D[2].....배열로 쭉 저장!

 

4. 예외로 생기는 상황을 따로 처리하자

ex) 피보나치에서의 F0 = 0, F1 = 1과 같은것은 따로 정의

 

5. 어떤 문제를 풀때 알수없는 정보가 있으면 하나하나 해서 점화식을 찾자

ex) 카드 구매하기 문제에서 마지막에 산 카드팩 안에 카드가 몇개가 들어있는지는 "알수 없다" 

-> 그러므로 카드팩 안에 카드가 1개인 경우 2개인경우,,,n개인 경우를 모두 해보자

 

6. 문제를 풀이 함에 있어서 경우의 수 분할이 필요하다면 메모리 공간을 2차원 배열로 만들어서 각 경우의 수를 분리하자 → 차원이라는것은 문제에서 구해야하는 값에 들어있는 변수

ex) 1,2,3 더하기 5 문제에서 마지막에 더한 수가 1인경우, 2인경우, 3인경우를 나눈다

ex) 쉬운 계단 수 문제에서 마지막에 있는 수가 0, 9인경우 vs 1,2,3,4,5,6,7,8인 경우를 나눈다

ex) 이친수에서 점화식 D[N][L] = N자리 이친수 마지막 수 L

 

7. 다이나믹 문제에선 문제에 나와있는 상황을 반대로 해서 품

ex) 2*n타일링 문제에서 타일을 놓을건데 마지막 타일이 빠지면 무슨일이 일어나나

ex) 정수 삼각형 문제에서 특정 정수는 어떤 정수에 의해서 선택 되어 지는가

 

 

문제풀이팁

 

※ 연속, 증가, 감소 같은 조건은 인접한 2개로 나눌수 있다 (ex.1,2,3 더하기, 쉬운 계단 수, 이친수->마지막에 어떤게 오는지를 2차원 배열로 케이스 나눔)

 

 

▶ 다이나믹 프로그래밍 문제 유형

 

1. 기본 유형 (점화식의 마지막이 구하는 답이고 1차원 배열로 풀리는 문제)

◆ d[i] = ??? 의 형태로 점화식이 나오는 다이나믹 

ex) 1로 만들기

◆ d[i] = ??? 부분에 합이 들어가는 다이나믹

ex) 2*n 타일링

 

 

2. 2차원 배열 유형 (값을 저장할때 조건이 있어서 케이스를 분류해서 저장해야하는 문제)

◆ d[i][j] = ??? 의 형태로 점화식이 나오는 다이나믹

ex) 1,2,3 더하기 5(조건 : 같은 수를 두번이상 못 사용하는 경우), 쉬운 계단 수(조건 : 0,9로 끝나는 경우와 나머지)

 

 

3. 저장된 값중에서 마지막이 답이 아닌경우 + 점화식이 문제에서 대놓고 나와있지 않은경우 (입력받는 배열과 저장하는 배열을 만들어서 입력받는 배열을 확인하면서 저장하는 배열에 값을 계속 넣음)

◆ d[i] = ??? 의 형태로 점화식이 나오는 다이나믹, ??? 부분에 min이나 max가 들어가는 다이나믹

◆ d[i] = ??? 의 형태로 점화식이 나오지만, 정답이 d[n]에 없는 다이나믹

◆ 다이나믹에서 역추적(ex. 가장 긴 증가하는 부분 수열)

ex) 가장 긴 증가하는 부분 수열(중간에 최댓값이 있음), 연속합

=> max값을 구해야 할땐 조건으로 max값을 구해서 1차원 배열에 저장하는것도 생각하자 (ex.포도주 시식)

cout<<*max_element(result+1, result+n+1)<<'\n';

-> 이런식을 최댓값 찾으면 됨