동적계획법(Dynamic Programming) / Memoization

-동적계획법 (dynamic programming)

복잡한 문제를 간단한 여러개의 문제로 나누어서 푸는 방법.

부분문제반복과 최적부분구조를 가지고있는 알고리즘을 일반적인 방법보다 더 적은 시간내에 풀 때 사용.

 

문제를 여러개의 하위 문제(subproblem)로 나누어 품.

이 하위문제들을 결합하여 최종적인 문제에 도달하는 것.

 

메모이제이션(memoization)

컴퓨터 프로그램이 동일한 계산을 반복할 때, 이전에 계산한 값은 메모리에 저장해서 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술.

동적 계획법의 핵심 기술.

 

처음 방문하는 재귀문제면 계산을 통해 얻은 값을 메모리에 저장,

이 후 재방문을 하면 계산하지 않고 저장 된 값 사용.

ex)

import java.util.Scanner;

public class Main {
	static int array[][][] = new int[51][51][51];
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int a=0, b=0, c=0;
		while(true){
			a = scan.nextInt();
			b = scan.nextInt();
			c = scan.nextInt();
			if(a==-1 && b==-1 && c==-1) break;
			System.out.printf("w(%d, %d, %d) = %d\n",a,b,c,w(a,b,c));
			
		}

	}
	
	static int w(int a, int b, int c) {
		if(a<=0 || b<=0 || c<=0)
			return 1;
		else if(array[a][b][c] != 0)
			return array[a][b][c];
		else if(a>20 || b>20 || c>20)
			return array[a][b][c] = w(20,20,20);
		else if(a<b && b<c)
			return array[a][b][c] = w(a,b, c-1) + w(a, b-1, c-1) - w(a, b-1, c);
		else
			return array[a][b][c] = w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1);
	}

}

 

이전에 계산한 값들을 배열에다 저장시키고, 이전에 계산한값이 있으면 계산을 하지않고 바로 저장된 값을 return하여 프로그램 속도 개선을 할 수 있음.