[Algorithm] Dynamic Programming, 동적 계획법

Kozel·2023년 3월 16일

algorithm

다이나믹 프로그래밍이란?

큰 문제를 작은 문제로 나눠서 해결하는 알고리즘이다.

분할 정복: 작은 문제의 중복이 없다.
다이나믹 프로그래밍: 작은 문제의 중복이 있다.
위의 분할 정복과의 차이점에서 보이듯이 작은 문제의 중복이 있을 때 사용한다.

다이나믹으로 해결할 수 있는 문제

겹치는 부분 문제가 있는 경우 (Overlapping Subproblem)
- 큰 문제를 작은 문제로 쪼갤 수 있는 경우
최적화 부분 구조 (Optimal Substructure)
- 작은 문제를 풀어나감으로써 큰 문제의 정답을 구할 수 있는 경우

다이나믹 프로그래밍 최적화의 핵심

작은 문제의 답은 한번만 구해야 한다.
- 같은 풀이를 반복해선 안된다.
최적화 부분 구조를 만족하기 때문에, 같은 문제를 구할 때마다 정답이 같다.
구한 답은 버리지 않고 저장해 둔다.
- 해당 과정을 Memoization이라고 한다.
- ex) 배열

다이나믹 프로그래밍의 구현 방식

다이나믹 프로그래밍의 대표적인 예인 피보나치 수를 구하는 경우로 두가지 방식을 살펴보자.

Top-Down

위에서 아래로 내려오는 방식으로, 원하는 값을 먼저 부른 다음에 그 값을 이루는 작은 값들을 이용해 값들을 수집해 나가는 방식이다.
메모제이션과 재귀함수를 사용하여 구현한다.

javascript code

// question: 구하려는 수의 값

const arr = Array(question + 1).fill(0);

const fibonacci = (number) => {
    if(number === 0) return 0;
    if(number === 1) return 1;
    if(arr[number] !== 0) return arr[number];

    arr[number] = fibonacci(number - 1) + fibonacci(number - 1);

    return arr[number];
}

console.log(fibonacci(question));

java code

// question: 구하려는 수의 값

int[] arr = new int[question + 1];

System.out.print(fibonacci(question));

static int fibonacci(int number) {
    if(number == 0) return 0;
    if(number == 1) return 1;
    if(arr[number] != 0) return arr[number];

    arr[number] = fibonacci(number - 1) + fibonacci(number - 1);

    return arr[number];
}

Bottom-Up

아래에서 올라오는 방식으로, 작은 문제부터 계산하여 전체 큰 값까지 구해내는 방식이다.
메모제이션과 반복문을 사용하여 구현한다.

javascript code

// question: 구하려는 수의 값

const arr = [0, 1];

for(let i = 2; i < question + 1; i++) {
    arr.push(arr[i - 1] + arr[i - 2]);
}

console.log(arr[question]);

java code

// question: 구하려는 수의 값

ArrayList<Integer> arr = new ArrayList<>();
arr.add(0);
arr.add(1);

for(int i = 2; i < question + 1; i++) {
    arr.add(arr.get(i - 1) + arr.get(i - 2));
}

System.out.print(arr.get(question));