Dynamic Programming

1. 조건

- Overlapping Subproblem: 문제를 작은 문제로 쪼갤 수 있고, 큰 문제와 작은 문제를 같은 방법으로 풀 수 있다.

- Optimal Substructure: 문제의 정답을 작은 문제의 정답에서 구할 수 있기 때문에, 같은 문제는 구할 때마다 정답이 같다. 또한 작은 문제를 구했으면 어딘가에 메모를 해놓아야 한다.

 

2. 구현 방법

- Top-down

- Bottom-up

 

2.1 Top-down

- 재귀를 이용해서 푸는 방법이다.

- 풀이 과정 예시

① fibonacci(n)

② 문제를 작은 문제로 나눈다. fibonacci(n) = fibonacci(n-1)+fibonacci(n-2)

③ 작은 문제를 푼다.

④ 작은 문제의 정답을 통해 큰 문제를 푼다.

public static int[] memo = new int[n+1];

public static int fibonacci(int n) {
	if(n<=1) { return 1; }
	else {
		if(memo[n]>0) { return memo[n]; }
        
		memo[n] = fibonacci(n-1)+fibonacci(n-2);

		return memo[n];
	}
}

 

2.2 Bottom-up

- 반복문을 이용해서 푸는 방법이다.

- 풀이 과정 예시

① 크기가 작은 문제부터 차례대로 푼다.

② 반복을 통해 큰 문제를 푼다.

public static int[] memo = new int[n+1];

public static int fibonacci(int n) {
	memo[0] = 0; memo[1] = 1;

	for(int i=2; i<=n; i++) { memo[i] = memo[i-1]+memo[i-2]; }

	return memo[n];
}

 

참고

- 『알고리즘 기초 1/2』