알고리즘 개념 - 동적 계획법(DP)

DP Algorithm

"동적계획법(Dynamic Programming)이란 큰 문제를 작은 문제로 나누어 푸는 알고리즘이다."

하나의 문제를 여러개의 작은 문제로 나누어 그결과를 저장(메모이제이션)하여 다시 큰문제를 해결할때 사용하는 것이다. Dynamic Programming 이라는이름이 뭔가 동적으로 프로그래밍을 해야하나? 생각할수있는데 전혀아니다. 그냥 큰문제를 작은문제로 쪼개서 그답을 저장해두고 활용한다는것에 집중하면될것이다. (기억하며풀기 알고리즘)

 

이러한 DP는 분할정복 알고리즘과도 닮은 부분이 있다. 하지만 분할정복에서는 부분문제의 계산결과를 저장하는 메모이제이션을 활용하지 않는다. 이것이 DP와 분할정복의 차이이고, 계산결과를 저장해두고 활용하기 때문에 시간복잡도 면에서 DP가 유리하다.

 

DP 사용이유

DP를 사용하는 이유는 뭘까? 재귀(Recursion)이 DP와 매우 유사하게 동작한다. 하지만 둘의 차이점이 있다. 일반적으로 재귀를 단순하게 사용하면 동일한 작은 문제들이 여러번 반복되어 비효율적인 계산이 될수도 있다는 점이다. 

 

예를들어 피보나치 수열을 살펴보면

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ...

 

피보나치수를 구하고 싶을때 재귀로 함수를 구성하면

return f(n) = f(n-1) + f(n-2) (n > 2)

 

이때, f(n-1), f(n-2)에서 함수를 1번씩 호출하면, 동일한 값을 2번씩 구하게 된다. 예를들어 100번째 피보나치수를 구하게 된다면... 기하급수적인 함수의 호출이 일어난다.

자 그럼 여기서 DP의 효율성을 볼수있다. 위의 그림을 보면 작은 문제의 결과가 중복되는것을 볼수있고, 이를 저장해놓고 재사용한다면 앞에서 계산한 값을 반복할필요가 없어, 훨씬 적은 함수 호출로 계산이 가능해진다.

 

매우 효율적으로 문제를 해결할수있는데, 시간복잡도를 기준으로 보면 

O(n^2) > O(f(n)) 으로 개선 (다항식 수준, 문제에 따라 다르다.) 가능하다.

 

DP의 사용조건

• Overlapping Subproblems(겹치는 부분문제)
• Optimal Substructure(최적 부분구조)

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

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

 

다시말해서 DP는 부분 문제의 결과를 저장하여 재 계산하지 않아야 하는데, 부분문제가 반복적으로 나타나지않으면 재사용이 불가능하여 부분문제가 중복되지 않는경우에는 사용할수가 없다.

 

예를들어 이진탐색과 피보나치수열을 비교해보자.

 

이진탐색의 경우는 특정 데이터를 정렬된 배열안에서 위치를 찾기때문에 위치를 찾은후 반환할뿐, 재사용하는 과정을 거치지 않는다. 하지만 피보나치수열은 아래와 같이 트리구조로 함수가 호출된다.

그림에서 보다시피 f(3), f(2), f(1), f(0) 처럼 동일한 부분문제가 중복된다. 이렇게 1회만 계산한뒤 그뒤로는 저장하여 값을 재활용 하는것이다.

 

 

 

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

부분문제의 최적 결과값을 사용해 전체문제의 최적결과를 나타낼수있는 경우를 의미한다.이렇게 되면 특정 문제의 정답은 문제의 크기와 상관없이 동일하다.

 

A - B 까지의 최단 경로를 찾는 문제가 있고, 중간에 X가 있다. 일단 그림을 살펴보자.

그림에서 A-X / X-B 가 많은 경로중에 가장 짧은 경로라면 전체 최적의 경로도 A - X - B 가 된다.

 

다시말해서, 그림에서 볼때 A -X 사이의 최단경로는 AX2 이고, B - X 사이의 최단경로는 BX2 이다. 만약 다른 경로를 택해도 A - X - B 라는 최단경로는 변하지 않는다. 이처럼 부분문제에서 구한 최적의 결과가 전체 문제에서도 동일하게 적용되어 결과가 변하지 않을때 DP를 사용할수있다.

 

DP 사용 과정

DP는 다양한 문제해결에 사용될수있다. 즉, 적용할수있는 문제인지 판별하는 것이 중요하고 그방법은 아래와 같다.

 

• DP로 풀 수 있는 문제인지 확인한다. - 조건이 충족되는지 확인
• 문제간의 변수를 파악한다. 
• 변수간 관계식을 만든다.(점화식) - 피보나치에서 f(n) = f(n-1) + f(n-2) 처럼...!
• 메모한다.(momoization or tabulation) - 변수의 값에 따른 결과를 저장하는 것
• 기저 상태를 파악한다. - 가장작은 문제의 상태를 파악, 피보나치에서 f(0) = 0, f(1) = 1 처럼...
• 구현한다. - Buttom-up(반복문) , Top-down(재귀)

 

구현방법

1. Bottom-Up 방식(Tabulation)

이름처럼 아래에서부터 계산을 수행하고 누적시켜 전체의 큰문제를 해결하는 방식이다. 메모를 위해서 dp라는 배열을 만들고 이것을 1차원이라고 가정했을때, dp[0]가 기저상태이고, dp[n]을 목표상태로 보자. Buttom-up 방식은 dp[0]부터 시작하여 반복문을 통해 점화식을 도출하고, 결과를 내어 dp[n]까지 값을 재활용하여 문제를 푸는 방식이다. 보통 반복문을 사용하여 문제를 풀고, 재귀를 사용하는 경우도 있다.

	public static int bottomUp(int num) { //bottom-up dp
    	
        //기저상태를 사전에 미리 저장
		dp[0] = 0;
		dp[1] = 1;
        
        //반복문을 사용하여 테이블을 채워간다.
		for( int i = 2 ; i <= num ; i++) {
			dp[i] = dp[i-1] + dp[i-2];
		}
        
		return dp[num];
	}

여기서의 tabulation은 메모이제이션과 같다. 메모를 위한 저장값인데 반복문을 돌면서 dp[0]부터 하나씩 채우는 과정을 table-filling 이라고 하고 이 Table에 저장된 값에 직접 접근하여 활용하므로 Tabulation 이라는 명칭이 붙었다고 한다.

 

 

2. Top-down 방식(Memoization)

dp[0]의 기저상태에서 출발하지 않고, dp[n]의 값을 찾기위해 위에서 부터 바로 호출을 시작하여, dp[0]까지 내려간 다음 해당 결과값을 재귀를 통해 전이시켜 재활용하는 방식이다.

 

피보나치의 예시에서의 트리에서 봤듯이, n=5일때 f(3), f(2) ... 가 반복적으로 나오게 된다. 이때 이미 계산이 완료된 부분문제의 경우 다시 문제를 푸는게 아니라 메모리에 저장된 내역을 꺼내서 활용하는 것이다. 코드를 보고 이해해보자.

public static int topDown(int num) {
		
        //기저 상태 도달시 0,1로 초기화
        if( num <= 0 )return 0;
	else if ( num ==1) return 1;
        
       //메모에 계산된 값이 있으면 바로 반환
	if(memo[num]!=0) {
		return memo[num];
	}
        
       //재귀를 사용
	memo[num] = topDown(num-1) + topDown(num-2);
       
	return memo[num];
}

 

 

 

Ref.

[겐지충프로그래머 블로그]

[sukong.log velog]

[Libre]