알고리즘 - 동적프로그래밍 Dynamic Programming

동적 프로그래밍

---

동적 프로그래밍에 대해서 다시금 공부하고 있다. 동적 프로그래밍(Dynamic Programming, DP)은 복잡한 문제를 더 작은 하위 문제들로 나누어 해결한 후, 그 결과를 저장하여 재사용함으로써 문제 해결의 효율성을 높이는 기법이다. 이는 주로 하위 문제가 반복해서 나타나는 경우에 사용되며, 각 하위 문제의 결과를 기록(memoization)하거나 테이블 형식으로 정리하여 중복 계산을 방지한다. DP는 최적화 문제에서 자주 사용되며, 두 가지 주요 접근 방식이 있다: 상향식(Bottom-Up)과 하향식(Top-Down).

단순히 말하자면, 동적 프로그래밍은 "이전에 계산한 값을 저장해 두었다가 필요할 때 재사용하는 방법"이다. 이는 중복 계산을 줄이고 문제를 더 빠르게 해결할 수 있도록 한다.

 

 

동적 프로그래밍 예시

---

대표적인 동적 프로그래밍 문제는 피보나치 수열(Fibonacci Sequence)이다. 피보나치 수열에서 각 수는 바로 앞의 두 수의 합으로 정의된다. 예를 들어, 피보나치 수열의 첫 몇 개 항은 0, 1, 1, 2, 3, 5, 8, 13, ... 와 같은 순서로 진행된다.

피보나치 수를 구하는 기본적인 방법은 재귀를 사용하여 구현하는 것이지만, 단순한 재귀 접근은 같은 값을 여러 번 중복 계산하게 되어 비효율적이다. 예를 들어 fibonacci(5)를 계산할 때, fibonacci(3)과 fibonacci(2)를 여러 번 계산하게 되면서 불필요한 시간이 소요된다. 이를 해결하기 위해 DP를 사용하여 이미 계산된 값을 저장해두고 재사용하는 방식으로 효율성을 높일 수 있다.

상향식 (Bottom-Up) 접근 방식
상향식 접근은 작은 문제부터 시작하여 점차 큰 문제를 해결해 나가는 방식이다. 이 방식은 반복문을 사용하여 하위 문제의 답을 차례대로 계산하고 저장해 두었다가, 이를 이용해 최종 결과를 구한다.

 

public class FibonacciDP {
    public static int fibonacci(int n) {
        if (n <= 1) return n;
        
        // 피보나치 값을 저장할 배열 선언
        int[] dp = new int[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];
    }

    public static void main(String[] args) {
        int n = 10; // 예를 들어, 10번째 피보나치 수를 구한다고 가정
        System.out.println("Fibonacci of " + n + " is: " + fibonacci(n));
    }
}

 

1. int[] dp = new int[n + 1]; 부분에서 DP 배열을 선언하여, 각 인덱스에 해당하는 피보나치 값을 저장한다.
2. dp[0]과 dp[1]은 각각 피보나치 수열의 초기 값인 0과 1로 설정한다.
3. for 반복문을 통해 dp[2]부터 dp[n]까지 계산해 나가며 이전 계산값을 재사용하여 빠르게 구한다.
4. 최종 결과는 dp[n]에 저장되며, 이를 반환하여 원하는 피보나치 수를 얻는다.
   
   단순히 말해, 동적 프로그래밍을 통해 피보나치 수열을 구할 때, "계산한 값을 배열에 저장하고 재사용하는 방식"으로 효율성을 높였다.