[c++] 알고리즘 개념공부 :: 재귀호출 (동적 계획법)

🍑동적 프로그래밍

동적 프로그래밍은 Dynamic Programming 즉, DP라고 불리는 알고리즘 기법이다.

복잡한 문제를 점화식으로 만들어 분할 정복할 때, 반복문 또는 재귀를 사용할 수 있는데 이 과정에서 계산의 결과 값을 저장해두어 중복되는 계산을 하지 않도록 만들어준다. 이는 점화식 이렇게 결과 값을 저장해두는 것을 메모이제이션이라고 하는데, 보통 배열의 형태로 수행된다.

DP 과정

1. 전체 문제를 부분 문제로 단순화한다.
2. 1번의 과정에서 점화식을 도출한다.
3. 점화식을 이용하여 배열로 간단히 해결할 수 있는지 생각한다.
   1. bottom-up
   2. top-down
4. 없다면 재귀함수를 만들고 메모이제이션한다.
5. 메모이제이션 방식은 보통 배열이다.
6. 전체 문제를 해결한다.

 

대표 문제

1. 피보나치 수열 구하기

피보나치 수열을 구하기 위해서 재귀 호출로 완전탐색의 방법을 쓴다면 그 과정 중에 한 번 호출했던 재귀함수를 또 호출하는 경우가 발생한다.

피보나치 4를 그림으로 표현해보자.

 

 

다음과 같이 중복되는 fibo(2)나 fibo(1), fibo(0)이 계속 등장한다. DP를 사용하면 fibo(4)에서 호출되는 함수는 4회 뿐일 것이다.

• 전체 문제를 부분 문제로 단순화한다.
• 재귀적인 구조를 가지는 점화식을 만든다.

fibo(i) = fibo(i-1) + fibo(i-2)

• 작은 문제를 해결하며 답을 저장하는 것을 반복한다.

파란색 상자를 채우기 위해 앞의 연두색 상자 2개가 필요함을 알 수 있다.

 

2. 배열 곱의 계산 순서를 정하는 문제

배열의 곱은 계산 순서에 상관없이 언제나 값이 같다. 하지만 순서에 따라 컴퓨터에서의 시간복잡도는 달라진다. 따라서 가장 효율적으로 배열의 곱을 구하려면 어떻게 계산해야할지를 DP로 구해보자.

 

이렇게 3가지의 A, B, C 행렬이 있을 때 세 행렬의 곱을 구하려 한다.

 

위와 같은 3가지 방식으로 구했을 때 총 연산의 횟수가 다르다. 두 행렬을 곱할 때는 앞 행렬의 행과 뒷 행렬의 열을 곱하면서 각 요소를 앞 행렬의 열, 즉 뒷 행렬의 행만큼 곱하므로 세가지 수를 곱해주면 된다. ABC 순서로 곱셈 연산을 했을 때는 AB를 먼저 곱한 후 나온 {(2, 4) => 행이 2, 열이 4인 행렬}과 C를 곱하게 된다.

 

해당 문제는 모든 연산을 수행해보는 완전탐색의 방법을 사용해도 되지만, 몇가지 경우의 수가 겹쳐보인다. 예를들어 A,B,C,D 4개의 행렬이 있을 때 (AB)(CD)와 A(BCD) 연산 중 CD는 이미 해둔 연산이므로 다시 할 필요가 없다. 따라서 DP를 사용해보기로 하자.

• 전체 문제를 부분 문제로 단순화한다.
• 행렬의 곱에 대한 연산 수라는 전체 문제를 어떻게 부분 문제로 나눌 수 있을까? 전체 행렬의 곱이 있을 때, 2개의 부분으로 나누면 두 행렬을 만드는 데에 드는 연산의 수 + 두 행렬의 곱에 드는 연산의 수 로 점화식을 세울 수 있다.

위와 같은 (행,열)을 가진 행렬들이 있을 때, 빨간 색 바를 기준으로 나누면 앞쪽 행렬의 결과는 (2,2) 행렬이고 뒤쪽 행렬의 결과는 (2,4) 행렬이다. 각각의 행렬이 몇 번의 연산을 거쳐 만들어졌는지는 모르겠지만, 이 두 행렬은 2*2*4번의 연산으로 계산 가능하다는 것을 안다. 그렇다면 재귀적으로 앞의 (2,2)행렬이 최소 몇 번의 연산으로 만들어질 수 있는지 나타낼 수 있다.

 

• 재귀적인 구조를 가지는 점화식을 만든다.

// 정의
A(i) = d(i-1)*d(i)
M(i,j) = A(i)*A(i+1)*...*A(j)의 최소 연산 수

// 점화식
M(i,j) = min ( M(i,k) + M(k+1,j) + d(i-1)d(k)d(j) )
// k는 1 ~ (j-1) 까지
// M(i,k) : k가 빨간 막대이고, 앞의 행렬 곱 연산 수를 뜻함
// M(k+1,j) : 뒤의 행렬 곱 연산 수를 뜻함
// d(i-1)d(k)d(j) : 앞/뒤의 행렬을 곱할 때 연산 수를 뜻함

• 작은 문제를 해결하며 답을 저장하는 것을 반복한다.

답을 행렬에 메모이제이션해보겠다.

행은 i를 뜻하고 열은 j를 뜻한다. 표시한 곳인 M(1,2)의 최솟값을 구하기 위해 점화식에 대입해보면 위의 그림에서와 같이 나온다. 여기서 k는 1에서 1까지이므로 1만 해당한다.

 

이 그림에서 파란색으로 표시된 부분의 값을 구하려면 같은 색으로 표시된 칸을 곱해서 점화식을 계산한 후, 그 중 최소값을 찾아야한다. 점화식에서 회색부분은 k가 1일 때이고, 연두색은 k가 2일 때, 노란색은 k가 3일 때이다.

=> 이렇게 O(n^3) 짜리 배열의 곱 문제를 O(n)짜리 문제로 탈바꿈 할 수 있다.

 

3. 0-1 배낭 문제

BOJ 12865. 평범한 배낭

[c++] BOJ 12865 :: 평범한 배낭

4. 기타 문제

• 합분해
• ACM Craft
• 내리막길
• RGB거리

---

참고

https://ko.wikipedia.org/wiki/%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95

https://www.zerocho.com/category/Algorithm/post/584b979a580277001862f182

 

 

 부정확한 정보가 담겨있을 수 있습니다! 

 댓글로 알려주세요 :)