[알고리즘]자바에서의 동적 계획법(Dynamic Programming - DP)

동적 계획법(Dynamic Programming) 과 분할 정복(Divide and Conquer)

* 동적 계획법(DP)

- 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서 보다 큰 크기의 부분 문제를 해결, 최종적으로 전체 문제를 해결하는 알고리즘 이다.

- 상향식 접근법으로, 가장 최하위 해답을 구한 후 이를 저장하고, 해당 결과값을 이용해서 상위 문제를 풀어가는 방식이다.

- Memoization(메모이제이션) 기법을 사용한다.

    - 프로그램 실행 시 이전에 계산한 값을 저장해서 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술이다.

    - 잘개 쪼개진 작은 부분 문제들을 한번씩만 풀기 위해서 사용한다.

    - 예시 : 피보나치 수열

    - 말이 어려울 뿐이지 사실 한번 계산해서 얻은 결과를 배열과 같은 자료구조에 저장해서 추후에 필요할 경우 배열 인덱스 서칭을 통해 데이터를 가져오는 것이다. 

 

 

* 분할 정복

- 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘 이다.

- 하향식 접근법으로, 상위의 해답을 구하기 위해 아래로 내려가면서 하위의 해답을 구하는 방식이다.

    - 일반적으로 재귀 함수로 구현한다.

- 문제를 잘개 쪼갤 때, 부분 문제는 서로 중복되지 않는다.

    - 예시 : 병합 정렬, 퀵 정렬 등

- 분할 정복에 대한 이해는 이후에 병합 정렬, 퀵 정렬에 대한 수업을 들으면서 이해해보자.

 

DP 와 DAQ 의 공통점과 차이점

* 공통점

- 문제를 잘개 쪼개서 가장 작은 단위로 분할한다.

* 차이점

- 동적 계획법(DP)

    - 부분 문제는 중복되어 상위 문제 해결 시 재활용된다.

    - Memoization 기법을 사용한다.(부분 문제의 해답을 저장해서 재활용하는 최적화 기법으로 사용)

- 분할 정복(DAQ)

    - 부분 문제는 서로 중복되지 않는다.

    - Memoization 기법을 사용하지 않는다.

 

DP 에 대한 이해

- 피보나치 수열 문제 : 피보나치 수열 n 을 입력받아서 다음과 같이 계산한다.

 

여기서 피보나치 수열을 일반 재귀 호출 형식으로 작성할 경우 아래와 같이 문제가 발생할 수 있다.

- fibo(4) 의 값을 구하려면 fibo(3) 과 fibo(2) 의 값이 필요하고, fibo(3) 의 값을 구하려면 fibo(2), fibo(1) 의 값이 필요하며, fibo(2) 의 값을 구하려면 fibo(1), fibo(0) 의 값이 필요하다.

- 이를 보면 알 수 있듯이 동적 계획법을 사용하지 않고 일반 재귀 호출로 문제를 해결하게 되면 fibo(2), fibo(1), fibo(0) 과 같이 중복되는 문제의 경우, 이미 앞서 답을 구했음에도 불구하고 똑같은 문제를 중복해서 다시 해결하게 된다.

- 동적 계획법을 활용하면 Memoization 기법을 활용하기 때문에 똑같은 중복 문제를 다시 풀지 않고 전체 문제를 해결할 수 있게된다.

 

동적 계획법(DP) 문제의 풀이법

- 적용될 수 있는 점화식을 찾아내는 것이 중요하다.

- 점화식이란 이웃하는 두 개의 항 사이에 성립하는 관계를 나타낸 관계식이다.

- 예시 : dp[n] = dp[n - 1] + dp[n - 2]

 

피보나치 수열을 동적 계획법으로 작성하는 방식으로 풀 수 있는 문제를 백준에서 다음과 같이 찾아서 해결 해보았다.

https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

 

- Main.java

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.math.BigInteger;


public class Main {
	
	static BigInteger[] tile = null;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int n = Integer.parseInt(br.readLine());
		tile = new BigInteger[n];
		if(n == 1)
			tile[0] = BigInteger.valueOf(1);
		else{
			tile[0] = BigInteger.valueOf(1);
			tile[1] = BigInteger.valueOf(2);
		}
		
		
		bw.write(tiling(n) + "\n");
		bw.flush();
		bw.close();
	}

	private static BigInteger tiling(int n) {
		if(n == 1 || n == 2)
			return tile[n-1];
		else {
			for(int i = 2; i < n; i++) {
				tile[i] = tile[i-1].add(tile[i-2]);
			}
		}
		return tile[n-1].remainder(BigInteger.valueOf(10007));
	}
}

- 입력 숫자가 1,2 와 같이 작은 문제에 해당하는 부분은 따로 값을 찾아서 선언해놓은 배열에 적재해 주었다.

- 입력 숫자가 3이 넘어갈 때 부터는 피보나치 수열의 점화식 대로 n-1 번째 인덱스와 n-2 번째 인덱스 값의 합을 배열의 적절한 인덱스에 적재해주었다.

- 위와 같이 계산한 값을 배열에 적재해 주는것을 Memoization 기법 이라고 한다.