Dynamic Programming

다이나믹 프로그래밍

다이나믹 프로그래밍 소위, DP라고 불리우는 이 알고리즘 방식에는 크게 두 가지 방법이 있다. 

재귀함수를 이용하는 방법과 처음 값부터 마지막 값까지 반복문을 이용하여 풀어가는 것이다.

이번 포스팅에서는 재귀함수를 통하여 푸는 방식을 설명하려 하는데, 가장 핵심은 

수 많은 횟수 가운데 1부터 첫 스타트를 끊는 것이 아니라, N번까지 진행되었을 때를 생각하여 정리하는 것이다.

예를 들어, 1->2->3->5->8-> ... 이렇게 증가하는 피보나치 수열이 있다고 하자

이를 n회 진행되었을 때를 생각하며 푸는 방식이다. 

다음 문제는 재귀함수로 푼 방식인데 간단히 소개해주겠다.

정수 N이 주어졌을 때 다음 보기의 조건을 만족하여 1을 만든다. 
연산 시의 횟수를 최소화하여 값을 내어라

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.

2. X가 2로 나누어 떨어지면, 2로 나눈다

3. 1을 뺀다.

하나씩 구하는 방법이 있지만 우선 이런 문제에 접할 경우 N으로 주어진 값이 1로 만들어지는데 필요한 최소 연산을 F[N]이라 하자 

F[N]은 결국 F[N/3]+1 , F[N/2]+1 , F[N-1]+1 이 세 가지 방법을 사용해서 최소 값을 구하는 것이다. 

(방법이기에 +1을 진행한 것)

F[N] = Math.min(F[N/3]+1,F[N/2]+1,F[N-1]); 

여기서 함수 부분을 재귀로 돌리면서 해당 값만 다음과 같이 진행하면 됩니다.

<예시>

다음을 확인하시면 dividedByNumbers() 라는 함수에서

d[n] = dividedByNumbers(n-1) + 1

이 부분에서는 구하려는 값 f[n]에서 f[n-1]+1에 해당되는 부분입니다.  

이 부분은 3으로 나눌 때의 경우와 2로 나눌 때의 경우 외에 지속적으로 돌아가야 하는 부분이기에 조건문의 별도로 적어줍니다.

if(n % 3 == 0) {

    int temp = dividedByNumbers(n / 3) + 1;

    if(d[n] > temp) d[n] = temp;

}

이 부분에서는 3으로 나누었을 때의 함수 값과 비교하는 부분입니다. 

물론 3으로 나눈 경우의 횟수가 더 많아야 하는 것이 당연한 것이기에 이 전 경우와
비교하여 더 큰 경우(횟수)를 d[n]에 넣어주면서 계속 반복합니다. 

2로 나눈 경우도 마찬가지입니다. 

이렇게 계속 반복하다보면 1에 도달하게 되고 그 횟수는 d[n]이 될 것이기에 

이를 반환해주면 됩니다. 관련 코드는 아래 링크에 있습니다. 

다이나믹 프로그래밍 예제