동적계획법(Dynamic Programming) 알고리즘

 

  • 복잡한 문제를 풀기 위해 작은 하위 문제로 나누고, 이전 계산 결과를 저장하여 반복 계산을 줄이는 방법
  • 피보나치, DFS, BFS, 완전 탐색 등의 알고리즘으로는 반복되는 작업이 많을 때 최적화를 노리는 알고리즘

 

 

 

 

동작 원리

- 문제를 최정 부분 구조로 나누고, 중복되는 하위 문제를 해결.

 

- 문제를 재귀적으로 풀 때 같은 문제를 여러번 계산하지 않고 한 번 계산한 결과를 저장해 다시 사용

 

 

 

 

 

장점

  • 하위 문제들의 결과를 저장해 반복을 줄임
  • 최적화, 그래프탐색 등 중복되는 연산이 있는 다양한 분야에 적용 가능

 

단점

  • 추가적 메모리가 필요할 수 있어 공간복잡도에서 불리할 수 있음
  • 중복 부분 문제를 만족하지 않는 문제에는 적용이 어려움

 

 

 

활용 사례

1. 피보나치 수열 계산 : 이전 2개 항의 합을 저장하기에 중복 계산이 많음. 이를 미리 저장해두어 중복 계산을 피함

 

2. 최장 증가 부분 수열 : 두 문자열에서 공통으로 존재하는 부분 수열 중 가장 긴 것을 찾는 문제

 

3. 배낭 문제 : 제한된 무게 내에서 가장 큰 가치를 찾는 문제

 

4. 동전 거스름돈 문제 : 주어진 금액을 만들기 위해 필요한 최소의 동전 개수를 찾는 문제

 

 

 

 

 

코드 구현 (피보나치 수열)

 

DP를 이용한 코드

 

>> 이전 항의 값을 별도 배열에 저장!

public class FibonacciDP {

    // 피보나치 수열을 동적 계획법으로 계산하는 메서드
    public static int fibonacci(int n) {
        if (n <= 1) {
            return n; // n이 0 또는 1이면 그 값을 반환
        }

        // 피보나치 수를 저장할 배열 선언
        int[] fib = new int[n + 1];
        fib[0] = 0; // F(0) 초기화
        fib[1] = 1; // F(1) 초기화

        // Bottom-Up 방식으로 피보나치 수열 계산
        for (int i = 2; i <= n; i++) {
            fib[i] = fib[i - 1] + fib[i - 2];
        }

        return fib[n]; // n번째 피보나치 수 반환
    }

    public static void main(String[] args) {
        int n = 10; // 예시로 n = 10
        System.out.println("피보나치 수열의 " + n + "번째 값: " + fibonacci(n));
    }
}

 

 

일반 코드

 

public class Fibonacci {

    // 피보나치 수열을 동적 계획법으로 계산하는 메서드
    public static int fibonacci(int n) {
    	if (n <= 0) {
    		return 0;
    	}
        if (n <= 2) {
        	return 1;
        }
       return fibonacci(n-1) + fibonacci(n-2);
    }

    public static void main(String[] args) {
        int n = 10; // 예시로 n = 10
        System.out.println("피보나치 수열의 " + n + "번째 값: " + fibonacci(n));
    }
}