DP

  동적 프로그래밍은 Dynamic Programming이며 짧게 DP라고 줄여서 부릅니다. 이름 자체가 "동적" " 역동성" 이어서 난이도가 높아보이고 용어가 어려워 보이지만 그렇게 무서워할만한 파트는 아닙니다. 오히려 한번 감을 잡으면 아주 쉽게 풀 수 있습니다.(?)

 

  동적 프로그래밍은 재귀적 알고리즘과 반복적으로 호출되는 부분으로 찾아내는 것이 관건입니다. 이를 찾은 뒤에 나중을 위해서 현재 결과를 캐쉬에 저장하면 됩니다. 캐쉬라는 것은 별 것 아니고 쉽게 말해 배열에 현재 결과 값을 저장하고 다음에 해당 값이 필요해지면 바로 꺼내 쓰기 위한 것입니다. 가장 흔한 예시로는 피보나치 수열이 있는데 아래 사진을 보면서 DP의 위력을 비교해보겠습니다.

 

문제를 해결할 때 N부터 시작하여 하위로 내려가는 방식을 전문적인 용어로 하향식 프로그래밍(Top-Down) 방식이라고 불립니다. 아래 예시는 하향식 에 대해 설명합니다.

DP에서는 상향식 프로그래밍(Bottom-Up)방식도 존재하며 이는 미리 N=0,N=1에서의 풀이법을 찾고 이전 사례를 확장해서 전체를 해결하는 방법입니다. 

사실 하향식 상향식은 중요하지 않습니다. 대신 '캐쉬를 이용하여 DP에서 문제를 해결하는 것을 메모이제이션(Memoization)이라고 한다.'라는 것만 기억하세요.

 

(위) 재귀 (아래) DP

 

public int fibonacci(int n){
    if(n==0) return 0;
    if(n==1) return 1;
    return fibonacci(n-1) + fibonacci(n-2);
}

  위의 사진이 일반적으로 재귀로 문제를 해결하는 경우입니다. n=5라는 상황은 충분히 모두 확인할만큼 작은 수이긴 하지만 만약 숫자가 크다면 어떻할까요? 같은 연산은 무수히 반복해야하겠지요. 그렇다면 예시의 계산 흐름을 살펴볼까요? 함수를 살펴보면 피보나치 return 문의 앞에 있는 fibonacci(n-1)을 계속 실행하면서 순차적으로 f(5) -> f(4) -> f(3) -> f(2)를 먼저 계산함을 알 수 있습니다. 그리고 이후에 오른쪽 자손의 f(3) f(2)도 계산을 끝까지 하고 있습니다. 눈치가 빠르신 분들은 알겠지만 f(3), f(2)는 중복되는 계산 값이기에 이 귀찮은 반복을 줄여보고자 캐쉬를 사용게 됐습니다.

 

이 값들을 캐쉬(배열)에 저장하면 빨간 박스 부분을 계산하지 않고 아래 그림처럼 단순한 모양의 트리를 만들 수 있습니다. 따라서 캐쉬를 한 번 추가해볼까요? 캐쉬라고 어려워하지마세요~! 단지 현재 결과값을 저장하는 배열을 만드는 것 뿐입니다.

 

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

 

시간복잡도가 O(2^N)의 시간에서 O(N) 으로 줄었습니다! 더이상 설명으로 알려드리기 보다 이해가 안가시면 직접 손으로 그리면서 해보시길 추천합니다. n=5를 넣어보세요!

 

* DP vs Divde And Conquer vs Greedy

  최적의 값을 구하기 위해 문제를 작게 쪼개는 의미에서 Divide and Conquer와 비슷하지만 문제 간의 관계가 다릅니다. 동적 프로그래밍은 하위 문제가 서로 종속성을 가지기 때문에 서로 영향을 미칩니다. 쉽게 말해서 지금 내가 구한 최선의 결과가 다음 단계의 문제를 푸는데 꼭 필요하다는 의미입니다. 모든 하위 문제를 풀되 그 결과를 저장하고 다음 단계의 문제를 푸는데 사용됩니다.

 

Dvide and Conquer의 경우에도 무수히 많은 경우의 수 중에서 최선의 경우를 찾기 위해 쓰는 전략입니다. 대신 DP와 다른 점은 쪼개진 문제들이 독립적으로 각각의 경우에서 최선의 결과를 만든 뒤 다시 결과들을 모아서 가장 최선의 결과를 도출합니다.

 

 현재의 선택지 중에 최선의 선택을 해나가며 문제 간에 관계가 종속적이다는 의미에서 Greedy와 비슷하지만 사용하는 목적이 다릅니다. 매 순간 최선의 선택을 한다고 해서 그것이 곧 최적의 결론에 도달하지 않습니다. 우리가 차를 타고 아무리 지름길로 간다고 해도 사고 때문에 몇시간을 기다렸다가 가야한다면(Greedy), 멀리 돌아가서 경로가 좀 길어지더라도 목적지에 빨리 도착하면 그것이 결론적으로 최적의 알고리즘 인 것입니다(DP). 따라서 Greedy는 정확한 결과값보다는 근사값을 확인 할 때 사용하지만 시간복잡도는 DP보다 빠릅니다.

 

가능한 해답이 무수히 존재하는 상황에서
각각의 해답은 숫자 등의 크기를 가질 때
가장 크거나 작은 최적의 값을 가지는 해답을 찾는 문제에서 사용한다.