[Algorithm] 동적 계획법(Dynamic Programming)

동적 계획법(Dynamic Programming)

동적 계획법(Dynamic Programming, DP)란 컴퓨터 프로그래밍 기법 중 하나로, 주로 최적화 문제나 중복되는 부분 문제를 효율적으로 해결하는 데 사용되는 알고리즘 설계 기법이다. 이는 큰 문제를 작은 부분 문제로 쪼개어 해결하는 분할 정복(Divide and Conquer)과 유사하지만, DP는 중복되는 부분 문제들을 한 번만 계산하고 이를 이용하여 전체 문제를 해결한다. 즉,한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘. -> 점화식을 요구하는 이유이기도 하다.

 

DP의 핵심 아이디어는 "작은 문제들의 해를 저장하고 재활용함으로써 전체 문제의 해를 구하는 것"이다. 이를 통해 중복 계산을 피하고 실행 시간을 크게 줄일 수 있습니다. DP는 일반적으로 다음과 같은 두 가지 방법으로 적용된다.

 

동적 계획법의 조건

동적 계획법을 적용하려면 위 정의에서 본 것 처럼 두 가지 속성을 만족 시켜야 하는데,

• 부분 반복 문제(Overlapping Subproblem)
• 최적 부분 구조(Optimal Substructure)

위 두 가지 속성을 만족 시켜야 한다.

그렇다면 이 두 가지 속성은 어떤 것 일까?

 

부분 반복 문제(Overlapping Subproblem)

부분 반복 문제(Overlapping Subproblem)란, 큰 문제를 해결하는 데 있어서 작은 부분 문제들이 반복적으로 발생하는 현상을 말한다. DP에서 중요한 개념 중 하나이며, 이러한 부분 문제들은 동일한 입력에 대해 항상 동일한 결과를 반환한다. 이로 인해 같은 부분 문제들이 여러 번 계산되는 비효율성이 발생할 수 있습니다. DP는 이러한 중복 계산을 피하고자 메모이제이션 또는 Bottom-up 방식을 이용하여 해결한다.

 

최적 부분 구조(Optimal Substructure)

최적 부분 구조(Optimal Substructure)은 큰 문제의 최적해가 작은 부분 문제들의 최적해로부터 구해질 수 있는 성질을 말한다. 즉, 큰 문제를 작은 문제들로 쪼개어 해결하면, 작은 문제들의 최적해를 조합하여 큰 문제의 최적해를 구할 수 있어야 한다. 이는 DP를 적용하기 위한 필수 조건 중 하나이다.

 

동적 계획법 접근 방법

동적 계획법으로 문제를 해결 할때는 크게 2가지 접근 방법을 들 수 있다.

Top-Down 방법과 Bottom-Up 방법이 있다.

 

메모제이션, Memoization

메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이다.
- wikipedia

// 최대 범위 N보다 1 크게 사용.
// memo[0] 초기값 상태 0으로 비워둘것임.
int memo[101];

memo[1] = 1;
memo[2] = 1;

// 메소드로 표현한 피보나치 수열
int fib(int n)
  {
    if (memo[n] != 0) 
      return memo[n];
    
    memo[n] = fib(n-1) + fib(n-2);
    
    return memo[n];
  }

위 처럼 구하고자 하는 숫자의 크기 만큼 배열을 생성하고 계산한 값을 저장하고
저장된 값일 경우(초기값 0이 아닌 경우) 배열의 값을 리턴하는 방식으로 구현하면
중복되던 연산 과정을 줄일 수 있게 된다.

✋이때 저장해 두는 메모리(배열)을 캐시(Cache)라고 부른다.

 

Top - down 방식 (메모제이션, Memoization) 

재귀적인 방법을 통해 큰 문제를 해결하면서 작은 부분 문제들의 해를 메모리에 저장하고, 같은 부분 문제가 다시 호출될 때 저장된 값을 반환하여 중복 계산을 피한다.

Top-Down 방법은 말 그대로 위에서 아래로 접근하는 방법으로 큰 문제에서 부분 문제로 쪼개가며, 재귀 호출을 이용하여 푸는 방법이다.

아래 방식처럼 재귀 호출을 통해 피보나치 수 구하는 방식에 해당한다.

import java.util.HashMap;

public class MemoizationExample {

    private static HashMap<Integer, Long> memo = new HashMap<>();

    public static long fibonacci(int n) {
        if (n <= 1) {
            return n;
        }

        // 이미 계산된 값이 있다면 바로 반환
        if (memo.containsKey(n)) {
            return memo.get(n);
        }

        // 계산하지 않은 값이라면 재귀 호출을 통해 계산하고 메모리에 저장
        long result = fibonacci(n - 1) + fibonacci(n - 2);
        memo.put(n, result);
        return result;
    }

    public static void main(String[] args) {
        int n = 10;
        long result = fibonacci(n);
        System.out.println("Fibonacci(" + n + ") = " + result);
    }
}

 

Bottom - Up 방식

작은 부분 문제들의 해를 순차적으로 계산하여 배열에 저장한 후, 이를 이용하여 큰 문제의 해를 구합니다.

Bottom-Up 방법은 말 그대로 아래에서 위로 접근하는 방법으로 부분 문제에서 부터 문제를 풀어가며 점차 큰 문제를 풀어가는 방법이다.
for문을 이용하여 푸는 방법에 해당한다.

Bottom-Up 방식은 반복문을 이용하여 구현하기 때문에 일반적으로 반복문이 재귀보다 더 효율적이다.

public class BottomUpExample {

    public static long fibonacci(int n) {
        if (n <= 1) {
            return n;
        }

        // 작은 부분 문제들의 해를 저장할 배열
        long[] dp = new long[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;
        long result = fibonacci(n);
        System.out.println("Fibonacci(" + n + ") = " + result);
    }
}

 

참고

https://velog.io/@gillog/%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming

동적 계획법(Dynamic Programming)

https://velog.io/@kimdukbae/%EB%8B%A4%EC%9D%B4%EB%82%98%EB%AF%B9-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D-Dynamic-Programming

[알고리즘] 다이나믹 프로그래밍 (Dynamic Programming)

https://galid1.tistory.com/507

알고리즘 - Dynamic Programming(동적프로그래밍)이란?

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

동적 계획법 - 위키백과, 우리 모두의 백과사전

https://amber-chaeeunk.tistory.com/123

[알고리즘] 다이나믹 프로그래밍이란?