동적 계획법(Dynamic Programming)

학부시절 알고리즘에서 제일 어려웠던 것으로 기억하는 알고리즘이다

지금도 알고리즘 문제를 보면 수많은 문제들이 있으며 여러 방법으로 응용이 가능한 방식이다.

 

1. 개요

Dynamic Programming (DP)

 

복잡한 문제를 간단하게 여러개의 문제로 나누어 이를 점화식으로 만들어 재귀구조로 문제를 해결하는 방식을 말한다.

주로 최적값 문제를 해결할 때에 사용한다. 가장 대표적인 문제를 뽑자면, 피보나치 수와 최단경로, 행렬 곱셉들이 있다.

 

문제를 여러게로 나누어 풀기 때문에 분할 정복과 비슷하지만 문제를 나누는 방식에서 그 차이가 들어난다.

분할정복의 경우 각 문제의 중복이 없게 분할한다. 즉, 각 문제들이 독립적으로 분리되어 있다.

하지만 동적 계획법의 경우는 문제 분할 시 중복이 존재하며, 이를 위해 이전의 결과를 저장하고 이를 재활용한다.

 

 

 

2. 조건

자 그렇다면 이제 햇갈리기 시작한다.

그렇다면 어떤 문제에는 DP를 사용하고 어떤 문제에는 분할 정복으로 풀어야 하는가?

 

DP의 경우에는 2개의 속성을 만족해야 문제를 풀 수 있다.

1. 겹치는 부분 문제 (Overlapping Subproblem)

2. 메모이제이션 (Memorizaton)

 

 

 

2.1.1 Overlapping Subproblem

겹치는 부분 문제는 분할 정복과 DP를 나누는 특성이다.

두 방식 모두 문제를 분할한다는(Subproblem) 점은 동일하다. 하지만 DP의 경우는 분할된 문제가 반복적으로(Overlapping) 사용되는 경우에 분할 정복보다 유리하게 적용된다. 이는 대표적으로 피보나치 수열 문제가 있다.

 

 

6번째 피보나치 수의 분할 정복 호출 함수

 

피보나치 수 공식

 

피보나치 수는 초기값과 점화식으로 정의되는 수열이다. 

여기서 식을 보면 F(n) 을 구하려면 이전에 구했던 F(n-1) 과 F(n-2) 가 필요하다.

만약 F(6) 분할 정복으로 풀게 된다면 위의 첫 번째 그림과 같이 이전해 사용한 중복 문제를 지속적으로 재 풀이하며

n이 50 이상만 넘어가도 알고리즘 시험에서 시간초과로 탈락하게 된다.

 

이와 같이 분할한 문제들이 중복되는 문제에서는 분할-정복보다는 DP를 사용하며 이는 메모이제이션 (Memorizaton) 으로 해결이 가능하다.

 

2.1.2 Optimal Substructure

최적 부분구조(Optimal substructure)는 그리디 알고리즘과 DP를 나누는 특성이다.

어떤 문제의 최적의 해결책이 그 부분 문제의 최적의 해결책으로부터 설계될 수 있는 경우를 말한다.

이는 대표적으로 배낭문제인 Knapsack Problem 에서 확인할 수 있다.

 

 

W = 5 배낭에 들어갈 짐 

 

 Knapsack Problem는 쪼갤수 없는 짐을 무게 제한이 있는 가방에 가치가 최대가 되도록 넣는 문제이다.

그리디 알고리즘으로 이 문제에 접근하는 경우 무게당 가치가 가장 높은 물건 순으로 선택하여 배낭에 넣을 것이다.

그렇게 되면 1번째(2.6v/w)와 4번째(6v/w)의 아이템이 선택되어 총 14의 결과가 나오게 된다.

하지만 실제로는 3번째와 4번째을 선택하여 15의 결과가 정답이다.

 

해당 문제에서 그리디의 문제점이 나타난다.

그리디는 그 순간의 최선의 선택을 하지만 해당 선택이 항성 최적은 아니라는 문제점이 있다.

이와 같이 최적의 수를 구할려면 모든 경우를 확인해야 하는 경우가 존재하는데 이때 DP가 활용되게 된다.

 

2.2 Memorizatoin

위의 Overlapping Subproblem에서 제시되듯 일부 문제는 분할 정복을 활용할 시 중복문제 계산이 발생한다.

대신 재계산한 결과는 항상 같다. 그래서 DP는 이를 해결하기 위해 이전 계산의 결과들을 저장한다. 이를 메모이제이션이라 한다.

 

 

 

 

저장할 결과값(퍼런샥)과 이로 인해 호출이 제외되는 함수들(빨간색)

위의 피보나치 수를 보자.

피보나치 수열을 계산했을때 n=0 일때부터 계산을 했다면, F(n)를 구할 때면 이미 F(n-1)의 계산을 한번 완료했을 것이다.

즉 이미 이전에 계산한 피보나치 수를 저장하고, 이를 다음 수의 계산에 활용하여 이전에 계산했던 문제들을 재호출 하는 행동을 방지할 수 있다. 해당 방식을 적용하면 기존에 F(6)를 계산하기 위한 함수 호출이 절반 이상으로 줄어든게 된다.

 

이를 사용하면 피보나치수의 시간복잡도는 O(n)으로 줄어들게 된다.

 

 

 

3 . 구현 방식

구현방식은 아래와 같이 2개의 방식이 존재한다.

1. Top - Down

2. Bottom-Up

 

 

3.1 Top-Down

Top -Down의 경우는 분할 정복처럼 재귀방식으로 구하려는 값(Top)에서 아래로(Down) 값을 찾아가는 방식이다.

메모이제이션을 활용하여 이미 계산한 결과가 있다면 저장한 결과를 활용하게 함으로서 중복 호출을 방지한다.

 

int fibo(int n) {
	// 초기값
	if(n==1 || n==2) 
    	return 1;
    
    // 종복계산
    if(dp[n]>0)      
    	return dp[n];
    
    //재귀 호출
    dp[n] = fibo(n-1) + fibo(n-2);
    return dp[n];
}

 

3.2 Bottom-up

Bottom-Up의 경우는 재귀가 아닌 반복문으로 처음부터(Bottom) 값을 구하는 방식이다(Up)

메모이제이션으로 재귀가 아닌 반복문으로 해결이 가능하다.

 

int fibo(int n) {
	
    dp[0] = 0;
    dp[1] = 1;
    
    for(int i = 2; i <= n; i++)
    	dp[i] = fibo(i-1) + fibo(i-2);
    
    return dp[n];
}

 

 

4.여담

DP는 가장 기억에 남던 내용 중 하나다.

배우기는 쉽지만 실제로 응용하기가 까다롭고, 까딱하면 런타임 에러가 발생하는 문제이기 때문이다.

특히나 학부시절에 수기로 경우의 수 트리를 적어서 10페이지가 넘게 과제로 제출했기 때문에 기억에 안남을 수가 없던 녀석이다.

실제 알고리즘 문제에서도 높은 난이도 문제로 출제되기 때문에 자주 풀어보자.

 

 

5.연관된 문제들

2020/10/25 - [분류 전체보기] - 백준 No.2748) 피보나치 수2

백준 No.2748) 피보나치 수2

 

추가예정