구르는 돌에는 이끼가 끼지 않는다

동적계획법

책 [코딩인터뷰 완전분석]에서는 알고리즘 문제를 보았을때 재귀로 풀기 적당한 문제인지 파악하는 문장 키워드는 다음 3가지를 예시로 들었다.

• "n번째 ... 를 계산하는 알고리즘을 설계하라"
• "첫 n개를 나열하는 코드를 작성하라"
• "모든 ... 를 계산하는 메서드를 구현하라"

위와 같은 문장이 100프로 재귀 문제가 아닐 수도 있겠지만 괸장히 도움이 되는 팁이기도 하다.

상향식 접근법

bottom-up approach, 가장 직관적인 경우가 많음

간단한 경우들에 대한 풀이법을 발견하는 것부터 시작

하향식 접근법

top-down approach, 덜 명확해서 복잡해 질 수 있음

문제에 대해 생각하기에 가장 좋은 방법

반반 접근법

상향식, 하향식 접근법 외에 데이터를 절반으로 나누는 방법

예를 들어 이진 탐색이 반반 접근법을 이용한 탐색임

병렬 정렬 또한 반반 접근법을 이용한 정렬임

재귀적 해법의 단점

재귀적 알고리즘은 공간 효율성이 나빠질 수 있음

재귀가 한번 발생할 때 마다 스택에 새로운 층이 추가됨

이는 재귀의 깊이가 n일 때 O(n) 만큼의 메모리를 사용하게 된다는 것을 의미

모든 재귀적 알고리즘은 순환적으로 구현될 수 있지만, 순환적으로 구현된 코드는 때로 훨신 더 복잡할 수 있음

동적계획법&메모이제이션

동적 프로그램은 거의 대부분 재귀적 알고리즘과 반복적으로 호출되는 부분문제를 찾아내는 것이 관건

이를 찾은 뒤 나중을 위해 현재 결과를 캐시에 저장

어떤 사람은 하향식 동적 프로그래밍을 메모이제이션(memoization)이라 부르고 오직 상향식 접근법만 '동적 프로그래밍'으로 부리기도함

동적프로그램 적용 예

하향식 동적 프로그래밍

• 피보나치 수열int fibonacci(int i){ if(i == 0) return 0; if(i == 1) return 1; return fibonacci(i-1) + fibonacci(i-2); }

위 식을 트리 형태로 표시를 해보면 각 노드는 두개의 자식 노드를 갖음

각 노드는 두 경우로 분기됨

따라서 수행 시간은 대충 O(2^n)이 됨

재귀 트리를 보면 fib(3)은 두번 호출, fib(2)는 세번 호출 됨

많은 노드들이 중복되어 호출됨

이러한 노드의 중복을 캐시에 저장하고 나중에 저장된 값을 사용하면 효율적이 됨

이를 메모이제이션(memoization)이라고 함

다음 코드는 메모이제이션을 적용하여 fibonacci(i)의 결과를 캐시에 저장하는 부분임

int fibonacci(int n){ 
	return fibonacci(n, new int[n+1]); 
} 

int fibonacci(int i, int[] memo){ 
	if(i == 0 || i == 1) return i; 
    if(memo[i] == 0) { 
    	memo[i] = fibonnacci(i-1, memo) + fibonacci(i-2, memo); 
    } return memo[i]; 
}

위와 같이 코드 수정시 O(N) 시간으로 돌아가게됨

상향식 동적 프로그래밍

위 하향식 프로그래밍으로 푼 문제를 상향식으로 변경이 가능함

int fibonacci(int n){ 
	if(n == 0) return 0; 
    else if(n == 1) return 1; 
    int[] memo = new 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] + memo[n-2]; 
 }

위 코드에서 memo[i]는 memo[i+1]과 memo[i+2]를 계산할 때만 사용 될 분 그 뒤에는 전혀 사용 되지 않음

그래서 이름 memo테이블 말고 변수 몇 개를 사용해서 풀수도 있음

int fibonacci(int n) { 
	if(n == 0) return 0; 
    int a = 0; 
    int b = 1; 
    for(int i = 2; i < n; i++){ 
    	int c= a+b; a=b; b=c; 
    } 
    return a+b; 
}

(feat. 예전에 프로그래머스 문제중에 피보나치를 재귀로 풀었다가 똑같은 overflow가 발생하여 위와 같이 반복문 형태로 풀었던 기억이 있었다. 결국 이와 같이 푸는 방식도 일종으 동적계획법이라는 것을 알수 있었다. 상향식 동적 프로그래밍이 단순하게 생각하여 적용해 볼 수 있는 방식이라는 것을 이해할 수 있었다.)

http://www.yes24.com/Product/Goods/44305533