프로그래밍/알고리즘(Algorithm)

[알고리즘][Java] 동적 계획법(Dynamic Programming)

거북고래 2023. 7. 11. 12:56
반응형

[알고리즘] 동적 계획법(Dynamic Programming)

□  1. 개 요

동적 계획법(Dynamic Programming, 이하 DP)은 알고리즘 보다는 하나의 문제해결 페러다임으로서 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 기본적인 아이디어에서 출발한다.

 

특히 큰 문제를 동일한 작은 문제들이 여러 번 반복되는 경우에 그 답을 저장해두고 재활용하게 되며, 혹자는 '기억하며 풀기' 라고 부른다.

 

이름의 기원은 Richard Bellman이 1950년대에 사용한 단어로 현재까지 이어져 온 것으로 특별한 의미는 없다.

□ 2. DP를 사용하는 이유

DP는 일반적인 재귀 방식(Naive Recursion) 방식과 뿌리는 같으나 일반 재귀에서의 문제점을 해결하기 위해 등장했다. 일반 재귀의 가장 큰 문제점은 단순히 사용할 경우 동일한 작은 문제들이 여러 번 반복되어 비효율적인 계산이 될 수 있다는 것이다.

 

예를 들어 일반 재귀를 이용한 피보나치 수열을 살펴보자. 이는 아래와 같다.

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

이를 점화식으로 나타내면 이와 같다. f(n) = f(n-1) + f(n-2)

 

간단하게 5까지의 피보나치 수열을 구한다고 할 때 그에 따른 피보나치 수열 함수 호출 트리는 아래와 같다.

아래 예시에서도 볼 수 있듯이 f(n-1)에서 한 번 구한 값을 f(n-2)에서 또 다시 같은 값을 구하는 과정을 반복하게 되며 100번째 피보나치 수를 구할 때 호출되는 함수의 횟수는 기하급수적으로 증가한다.

 

그러나 한 번 구한 작은 문제의 결과 값을 저장해두고 재사용한다면 앞에서 계산된 값을 다시 반복가 없어 매우 효율적으로 문제를 해결할 수 있게 되며, 문제마다 다르나 시작복잡도를 아래와 같이 개선할 수 있다.

O(n^2) → O(f(n))으로 개선(다항식 수준으로, 문제에 따라 다름.)

피보나치 수열 함수 호출 트리

□ 3. DP 사용 조건

DP가 적용되기 위해서는 2가지 조건을 만족해야 한다.

 

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

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

 

○ Overlapping Subproblems(겹치는 부분 문제)

 DP는 동일한 작은 문제들이 반복하여 나타나는 경우에 한해 사용이 가능하다. 부분 문제의 결과를 저장하여 재활용할 수 있어야 하는 기본 아이디어이기에 부분 문제가 반복적으로 나타나지 않는다면 재사용이 불가능하기에 사용할 수 없다.

○ Optimal Substrucrue(최적 부분 구조)

 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우를 의미한다. 단순히 말해서 부분문제의 결과값을 저장하였는데 이를 재사용할 때 전체 문제에서도 동일하게 유의미할 때 사용가능하다.

□ 3. DP 사용 조건

일반적으로 DP를 사용하기 전에는 아래의 과정을 거쳐 진행할 수 있다.

 

1. DP로 해결할 수 있는 문제인지 확인

2. 문제의 변수 파악

3. 변수 간 관계식 만들기(점화식)

4. 메모하기(memoization or tabulation)

5. 기저 상태 파악하기

6. 구현하기

 

① DP로 해결할 수 있는 문제인지 확인

위에서 언급한 DP 사용 조건이 충족되는 문제인지를 체크한다. 보통 특정 데이터 내 최대화/최소화 계산을 하거나 특정 조건 내 데이터를 세야 한다거나 확률 등의 계산의 경우에 DP로 풀 수 있는 경우가 많다.

② 문제의 변수 파악

DP는 현재 변수에 따라 그 결과 값을 찾고 그것을 전달하여 재사용하는 것을 거친다. 즉 문제 내 변수의 개수를 알아내야 한다. 이것을 영어로 'state'를 결정한다고 한다.

③ 변수 간 관계식 만들기

변수에 따라 결과값이 달라지지만 동일한 변수값인 경우, 결과는 동일하다. 또한 우리는 그 결과값을 저장하여 이용할 것이기에 그 관계식인 점화식을 만들어낼 수 있어야 한다.

④ 메모하기

변수간 관계식까지 정상적으로 생성되었다면 변수의 값에 따른 결과를 저장해야 한다. 이것을 메모한다고 하여 Memorization 이라고 부른다.

 

변수 값에 따른 결과를 저장할 배열 등을 미리 만들고, 그 결과를 나올 때마다 배열 내에 저장하고 그 저장된 값을 재사용하는 방식으로 문제를 해결해 나간다.

 

이 결과값을 저장할 때는 보통 배열을 사용하며 변수의 개수에 따라 배열의 차원이 1 ~ 3차원 등 다양할 수 있다.

⑤ 기저 상태 파악하기

가장 작은 문제의 상태를 파악해야한다. 보통 몇 가지 예시를 직접 손으로 테스트하여 구성하는 경우가 많다. 해당 기저 문제에 대해 파악 후 그 결과값을 미리 배열 등에 저장해두면 된다.

⑥ 구현하기

DP는 2가지 방식으로 구현할 수 있다.

 

1. Bottom-Up (Tabulation 방식) - 반복문 사용

2. Top-Down (Memorization 방식) - 재귀 사용

 

① Bottom-Up 방식

메모를 위해서 만든 배열 등에 기저 상태를 입력하고 반복문을 통해 점화식으로 결과를 도출하여 아래에서 부터 채워나가는 방식이다. 

 

② Top-Down 방식

Top-Down 방식은 아래 순서를 따른다.

  •  기저값일 경우, 해당 값 반환
  • 주어진 n의 결과가 저장되어 있을 경우, 해당 값을 배열에서 꺼내 반환
  • 없다면 해당 값을 계산하여 배열에 저장하고 그 값을 반환

□ 4. 구현하기

아래 코드는 백준 1003번 피보나치 함수를 풀며 작성한 코드로 Top-Down과 Bottom-Up 두 가지 방법을 모두 작성하였다.

추가로 두 가지 방식을 모두 작용하여 작성한 문제 풀이들을 첨부하니 참고하기 바란다.

package baekjoon;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
	
public class B1003 {
	
	static int[][] topDownMemo;
	static int[][] bottomUpMemo;
	static final int MAXTESTCOUNT = 40;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int numberOfTests = Integer.parseInt(br.readLine());
		
		for(int i = 0; i < numberOfTests; i++) {
			
			topDownMemo = new int[MAXTESTCOUNT + 1][2]; 
			bottomUpMemo = new int[MAXTESTCOUNT + 1][2]; 

			int givenNum = Integer.parseInt(br.readLine());
			int[] answer = topDownFibonacci(givenNum);
//			int[] answer = bottomUpFibonacci(givenNum);
			
			bw.write(String.valueOf(answer[0]) + " ");
			bw.write(String.valueOf(answer[1]) + "\n");			
		}
		bw.flush();
		bw.close();
		br.close();
	}
	
	// DP Top-Down을 사용
	static int[] topDownFibonacci(int givenNum) {
		// 기저 상태 사전 저장
		topDownMemo[0][0] = 1;
		topDownMemo[0][1] = 0;
		topDownMemo[1][0] = 0;
		topDownMemo[1][1] = 1;
		
		if(givenNum < 2) {
			// 기저값 도달시, 사전값 반환
			return topDownMemo[givenNum];
		} else if(topDownMemo[givenNum][0] > 0 && topDownMemo[givenNum][1] > 0) {
			// 메모에 계산된 값이 있으면 바로 반환
			return topDownMemo[givenNum];
		}
		
		// 재귀를 사용
		topDownMemo[givenNum][0] = topDownFibonacci(givenNum - 1)[0] + topDownFibonacci(givenNum - 2)[0];
		topDownMemo[givenNum][1] = topDownFibonacci(givenNum - 1)[1] + topDownFibonacci(givenNum - 2)[1];
		
		return topDownMemo[givenNum];
	}
	
	// DP Bottom-Up을 사용
	static int[] bottomUpFibonacci(int givenNum) {
		// 기저 상태 사전 저장
		bottomUpMemo[0][0] = 1;
		bottomUpMemo[0][1] = 0;
		bottomUpMemo[1][0] = 0;
		bottomUpMemo[1][1] = 1;
		
		// 반복문을 통해 table을 채워나감
		for(int i = 2; i <= givenNum; i++) {
			bottomUpMemo[i][0] = bottomUpMemo[i - 1][0] + bottomUpMemo[i - 2][0];
			bottomUpMemo[i][1] = bottomUpMemo[i - 1][1] + bottomUpMemo[i - 2][1];
		}
		
		return bottomUpMemo[givenNum];
	}
}

 

□ 참고 자료

https://hongjw1938.tistory.com/47

 

 

반응형