[ 알고리즘 ] DP(Dynamic Programming) - 동적계획법

 

 

안녕하세요 !

 

이번 글에서는 DP를 알아보도록 하겠습니다.

 

 

---

 

DP란?

 큰 문제를 작은 문제로 나눠서 해결하는 방법을 말합니다.

 주어진 문제에서 반복되는 작은 문제를 찾고, 이를 해결하면 큰 문제가 해결되는 것입니다.

 

 

 

예를 들어서 피보나치 수열로 설명할 수 있습니다.

 

피보나치는 1, 1, 2, 3, 5, 8, 13, ... 으로 

 

n번째 수 = n-1번째 수 + n-2번째 수 의 형태로 표현할 수 있습니다.

 

public int fibonacci(int n) {
        int[] dp = new int[n+2];

        dp[1] = 1;
        dp[2] = 1;
        
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }

        return dp[n];
    }

 

코드로 표현하면 이렇게 작성할 수 있겠습니다.

 

1번째, 2번째 수는 1을 반환하게 하고 그 뒤의 수들은 n-1번째와 n-2번째의 수를 합한 값을 반환하게합니다.

 

만들어둔 fibonacci라는 함수 안에서 재귀 호출되면서 작은 문제를 해결해서 큰 문제를 해결하는 방식으로 문제가 풀립니다.

 

이렇게 작은 문제를 해결해서 저장해놓는 Memoization을 사용하기 때문에 메모리를 차지한다는 단점이 있지만, 작은 문제로 큰 문제를 해결하면서 반복 계산하는 것을 줄일 수 있다는 장점을 가집니다.

 

동적 계획법을 이해하고 잘 사용하기 위해서는 DP와 관련된 문제들을 해결해보면서 익히는 것이 필요한 것 같습니다.

 

 

---

 

 

 

오늘은 이렇게 동적 계획법이라는 문제 해결 알고리즘을 알아봤습니다.

 

다음 글에서도 유익한 내용으로 찾아뵙겠습니다.

 

감사합니다 !