동적 계획법, 그리고 알고리즘

1. 동적 계획법(Dynamic Programming, DP)

  - 특별한 속성을 가진 복잡한 문제를 푸는 방법

  - 단순한 하위 문제를 나눠서 푼다.

  Ex) 배낭 문제

  - 물품 하나가 추가될 때마다 경우의 수가 2배씩 늘어난다.

  - 시간복잡도: O(2^n)

 

2. 메모이제이션(memoization)

  - 계산 결과를 캐시에 저장해둔 뒤, 나중에 재사용하는 기법

    -> 처음 계산할 때, 그 결과를 캐시에 저장한다. 

  - 메모이제이션에 "배열"이 가장 적합하다.

    -> 배열은 매개변수에 대해 값을 저장할 수 있다.

  Ex) 메모이제이션을 사용한 피보나치 함수

<hide/>
public static int fibonacciRecursive(int number, int [] cache) {
		
		if(number <= 1) {
			return number;
		}
		
		if(cache[number] != 0) {
			return cache[number];
		}
		
		int ret = fibonacciRecursive(number - 2, cache) + fibonacciRecursive(number - 1, cache);
		cache[number] = ret;
		
		return ret;	
}

 

3. 동적 계획법과 메모이제이션의 차이점

  - 메모이제이션: 실행된 결과를 기억해뒀다가 재사용하는 최적화 기법

  - 동적 계획법: 복잡한 문제를 하위 문제로 쪼개서 재귀적으로 푸는 방법

    -> 동적 계획에서 메모이제이션이 자주 쓰인다.

 

4. top-down 동적 계획법

  - 최종적으로 풀려고 하는  복잡한 문제(루트)에서 시작한다.