다이나믹 프로그래밍(Dynamic Programming)

다이나믹 프로그래밍은 동적계획법이라고도 불리며 짧게 DP라고 많이 사용합니다.

DP의 중점은 "작은 문제를 해결하고 이를 이용해 큰 문제를 해결하자 / 큰 문제를 작은 문제로 쪼개서 해결하자."입니다.

---

DP를 배우지는 않으셨더라도 피보나치 수를 재귀로 구하는 방법은 한번쯤 들어보셨을 거라 생각합니다.

이를 DP를 사용하는 방법으로 한 번 바꿔보겠습니다.

int fibo(int n){ 
	if(n==1 || n==0) return n; 
    return fibo(n-1) + fibo(n-2); 
}

 

일단 기존 방법의 재귀 소스코드는 위와 같습니다.

 

4번째 피보나치 수를 구하려면 위와 같이 함수를 호출하게 되는데 2번째 피보나치 수를 구하는 함수를 중복해서 호출하게 됩니다. 2번째 피보나치 수는 상황에 따라서 변하는 값이 아니므로 두 번 구할 필요가 없는데 불필요하게 두 번이나 구하는 절차를 하게 되는 것입니다.

지금은 별로 중복되는게 없어보여도 큰 수인 피보나치 수를 구하게 된다면 중복되는 수도 증가하게 되고 시간도 훨씬 오래 걸리게 될 것입니다.

따라서 사실 위 그림에서 빗금친 부분은 구할 필요가 없습니다. 이전 단계에서 FIBO(2)에 해당하는 값을 구했기 때문입니다.

그럼 이전 단계에서 구한 FIBO(2)에 해당하는 값을 재활용 해야 되므로 구한 값을 미리 저장을 해야합니다. 이때 배열(메모리)을 사용합니다.

 

이렇게 이전에 계산한 값을 메모리에 저장하여 반복 작업을 제거하는 것을 메모이제이션(memoization)이라고 합니다.

---

배열을 왜 사용하는지는 알았으니 배열을 만들기는 해야 하는데 인덱스와 해당 배열 안에 무엇을 넣어야 할지 고민됩니다.

이럴 때는 변하는 것(조건)과 구해야 하는 것을 한 번 찾아보면 좋습니다.

예를 들어 피보나치 수에서는 변하는 것(조건)은 몇 번째 피보나치 수를 구하는지 입니다. 그리고 구하고자 하는 것은 그때의 피보나치 수입니다.

따라서, 몇 번째인지는 배열의 인덱스로 넣어주고 그 때의 피보나치 수는 배열 값으로 넣어줍니다.

dp[n] = n번째 피보나치 수. 이렇게 저장을 합니다.

배열 이름은 임의로 dp라고 하였습니다.

---

이제 점화식을 세워야 합니다.

우리는 이미 피보나치 수에 대한 점화식을 알고 있습니다.

n번째 피보나치 수 = n-1번째 피보나치 수 + n-2번째 피보나치 수.

이를 사용해서 배열로 적절히 치환해보면

dp[n] = dp[n-1] + dp[n-2];

 

가 됩니다.

---

이제 설계까지 모두 끝났으니 구현을 할 차례입니다.

int fibo(int n){ 
	if(n==1 || n==0) return n; 
    return fibo(n-1) + fibo(n-2); 
}

 

처음에 소개했던 피보나치 수 구하기 재귀함수 입니다.

이를 배열을 사용하는 DP로 바꿔보겠습니다.

int fibo(int n){ 
	if(n==1 || n==0) return n; 
    if(dp[n] != -1) return dp[n]; //이미 구한 값이면 그 값 반환 
    
    dp[n] = fibo(n-1) + fibo(n-2); 
    return dp[n]; 
}

 

앞에서 말했던 것과 같이 이미 구한 수라면 그 값을 사용하면 되므로 그 값을 구하기 위해 따로 함수를 호출할 필요는 없습니다.

따라서 종료 조건에 이를 한 줄 추가해줍니다. 위 소스코드에서는 3번째 줄이 이에 해당됩니다.

왜 dp[n]을 -1과 비교했냐면 -1은 어떠한 피보나치 수도 될 수 없는 값입니다. (피보나치 수는 0이상)

따라서 해당 배열을 모두 -1로 초기화 시켜주고 사용합니다.

만약 dp[n]이 -1이라면 아직 구하지 않은 값이므로 fibo(n-1) + fibo(n-2)를 호출해서 배열을 갱신해야 할 것이고 -1이 아니라면 이미 구한 값이므로 별도의 처리없이 dp[n]을 반환하면 됩니다.

 

이제 피보나치 수의 재귀함수에 대해서 DP로 바꾸는 작업이 모두 끝났습니다.

이때까지 알아본 방법은TOP-DOWN방법입니다.

이렇게 끝내기는 아쉬우니 BOTTOM-UP도 알아보겠습니다.

---

BOTTOM-UP방법은 작은 수의 피보나치 수부터 구해가면서 N번째 피보나치 수를 구하는 것입니다.

먼저 DP 소스코드를 보겠습니다.

int fibo(int n) { 
	int dp[N+1]; 
    dp[0] = 0; 
    dp[1] = 1; 
    for(int i=2; i <= N; i++) 
    	dp[i] = dp[i-1] + dp[i-2]; 
    return dp[N]; 
}

0번째와 1번째 피보나치 수는 미리 갱신해두고 이를 이용하여 그 다음 피보나치 수를 dp 배열에 저장해갑니다.

dp[n]이 n번째 피보나치 수에 해당하므로 dp[n]까지 채우고 이를 반환하면 BOTTOM-UP 방식의 DP 피보나치 코드가 됩니다.

---

다이나믹 프로그래밍이 무엇이고 어떻게 하는지에 대해서 알아보았습니다.

 

피보나치 수를 구하는 재귀함수의 시간복잡도는 O(2N)이고 DP를 사용하면 O(N)이 됩니다.

시간복잡도가 현저히 줄어드는 것을 알 수 있습니다.

DP를 사용하면 중복 작업이 제거되므로 이처럼 시간복잡도는 감소하지만 메모리를 사용하므로 메모리 용량에 대한 이슈가 생깁니다.

메모리 크기를 줄일 수 없을 때도 있지만 공간 국부화(spatial localization)로 줄일 수 있을 때도 있으므로 알고리즘 문제에서 메모리 제한을 보고 줄여야 할 때는 줄여줘야 합니다.

 

예를 들면 위에서 BOTTOM-UP방식으로 구현했을 때 사실상 접근하는 배열의 인덱스는 현재(i)보다 1, 2작은 경우만 접근하게 됩니다. 그래서 모든 경우의 피보나치 수를 N의 크기를 가지는 배열에 저장하지 않고 2의 크기를 가지는(i-1, i-2 번째만 알면 되므로) 배열로만으로도 이를 구현할 수 있습니다.

 

'2의 크기만 가지는 배열이라면 변수 2개만으로도 풀 수 있지 않느냐' 라는 생각을 하실 수도 있겠습니다.

네, 맞습니다.

int fibo(int n) { 
	int sum; 
    F1 = 0; 
    F2 = 1; 
    for(int i=2; i <= N; i++) { 
    	sum = F1 + F2; 
        F1 = F2; 
        F2 = sum; 
    } 
    return sum; 
}

 

위 소스코드가 배열 안 사용하는 방법으로 BOTTOM-UP 코드를 수정한 코드인데 기존에 알고 있던 피보나치 수를 구하는 반복문 방법과 같습니다.

이 포스팅에서는 BOTTOM-UP으로는 DP를 어떻게 짜는지 보여주기 위해서 다소 비효율적으로(메모리를 추가해서) 구현해보았습니다.

---

이 포스팅에서는 DP가 무엇인지 왜 이렇게 사용하는지에 대한 내용을 중점적으로 적었습니다.

DP의 대표 문제는 배낭문제가 있습니다. 이는 다른 포스팅에서 상세히 설명해두었으므로 그 포스팅을 참고해주세요. (링크)

이렇게 다양한 문제 유형에 대해서도 설명이 필요할 것 같긴한데 그러면 포스팅 자체가 너무 길어져서 알고리즘 문제 풀이 카테고리에서 DP태그에 해당하는 문제들을 보시면 될 것 같습니다.

추후에 그래도 필요할 것 같다 싶으면 다른 포스팅으로 작성하겠습니다.

---

+ 잡담

백준 문제분류에서 가장 많은 문제수를 가지고 있는 것은 위 그림과 같이 다이나믹 프로그래밍입니다.

개인적으로 무엇인지에 대해서 알아도 어려운 것이 DP라고 생각합니다.

배열을 어떻게 만들것인지, 점화식을 어떻게 세울것인지가 중요한데 이게 정말 어렵거든요.

이에 따라 문제 유형도 매우 다양하므로 DP가 무엇인지 알아도 풀기 어려운 문제가 많습니다.

다른 알고리즘 문제도 그렇겠지만 DP 또한 많이 풀어보고 직접 점화식을 세우는 연습을 해야 합니다.

 

제가 처음으로 알고리즘에 흥미를 느낀게 친구가 기숙사에서 재밌는 것을 알아왔다고 배낭문제를 알려줬을 때입니다. 공책에 예를 들어가며 배열을 채우면서 설명을 열심히 해줬었는데 사실 그 당시에는 이해를 못했었습니다. DP를 처음 접하는 제게는 너무 생소하고 어려웠거든요.

하지만 하나하나 적으면서 규칙을 찾고 배열을 만들고 점화식을 세워서 문제를 푸니까 그게 너무 재밌어서 알고리즘에 점점 빠졌습니다.

 

문제를 보고 점화식을 못세운다고 너무 자책하지 마세요. 어려울수록 돌아가라고 그럴때는 직접 하나하나 배열을 채워가면서 규칙을 먼저 찾아보는 것을 추천합니다. 제가 자주 사용하는 방법인데 DP를 풀때는 펜과 종이를 앞에 두고 풀는것이 좋습니다. (다른 문제를 풀 때도 똑같습니다.)

 

DP 문제를 풀어보고 싶으시다면 백준-문제분류에서 다이나믹 프로그래밍 들어가시면 500개 이상의 문제가 있으니 정답률이 높은 것부터 하나씩 풀어보세요. 제 블로그 태그에서 #DP 를 찾아서 풀어보는 것도 좋을 것 같아요.