동적 프로그래밍

ALGORITHM/Theory

동적 프로그래밍

Harimad 2022. 7. 1. 13:46

1. 동적 프로그래밍소개

동적 계획법 - 나무위키 (namu.wiki)

슬라이드 : Dynamic Programming (work in progress) (slides.com)

동적 프로그래밍을 제대로 이해하기 위해서 재귀를 알고있어야 한다.

동적 프로그래밍은 복잡한 문제를 더 간단한 하위 문제의 모음으로 쪼개서

각 하위 문제들을 풀어서 그 답을 저장하는 방식으로 문제를 푸는 것이다.

2. 중복되는 부분 문제

예시 : 피보나치 수열

반복되는 하위 문제들을 가지고 있다.

피보나치 수열은 모든 숫자가 그 앞에 오는 두 개의 숫자의 합과 같은 숫자의 열을 의미한다.

한 숫자의 바로 앞에 오는 두 개의 숫자를 가지고 합을 내면 그 다음 숫자가 되는 것이다.

예를 들어 4번째 숫자를 얻으려면 3번째와 2번째 숫자를 더하면 된다. 그럼 3이 된다.

5번째 숫자는 4번째와 3번째의 합이다.

피보나치 수열에서 5번째 숫자를 구하려면, 이걸 더 작은 조각

즉, 4번째 숫자와 3번째 숫자를 더하는 일로 나눌 수 있다.

아래 피보나치 수열의 트리가 있다.

한 문제를 더 작은 여러 단계로 나누는 것이다. 이건 보통 재귀(Recursion)을 통해서 처리한다.

피보나치 수열은 하위 문제들이 반복되고 중첩된다.

예시2 : 합병정렬

합병정렬은 배열이 있으면 더 작은 조각으로 나눠서 정렬하고 그걸 다시 합치는 과정이다.

mergeSort(10, 24)이 있다고 가정하면, 반으로 나눠서 두개의 정렬된 배열로 나눈다.

24와 10이 되는데, 이 각각은 하나의 요소만 있기 때문에 정렬 되어 있다.

이걸 다시 합병해서 [10, 24]로 만든다.

mergeSort(10, 24, 10, 24) 같은 경우는 쪼갤 때

[10, 24] [10, 24]로 반복되는 경우에는 반복되는 하위 문제로 볼 수 있다.

3. 최적 부분 구조 (optimal substructure)

하위 문제의 최적 해답을 통해서

더 큰 범주의 문제의 최적 해답을 구성할 수 있는 경우에

해당 문제가 최적 부분 구조를 가진다고 한다.

피보나치 수열이 해당된다.

추가 : [알고리즘 설계] 3. 동적계획법(Dynamic Programming) · 괭이쟁이 (laboputer.github.io)

[알고리즘 설계] 3. 동적계획법(Dynamic Programming)

동적계획법은 분할정복처럼 어떤 문제를 풀 때 부분문제의 해를 이용하여 구하는 것을 말합니다. 동적계획법을 이해하기 위해 여러가지 예제를 통해 설명하고 연습문제를 풀어보면서 직접 구

laboputer.github.io

4. 재귀적 솔루션 작성

function fib(n) {
	if (n <= 2) return 1;
	return fib(n-1) + fib(n-2);
}

5. 우리 솔루션의 시간 복잡도

O(2^n) : 지수 👎

6. 우리 솔루션의 문제점

문제점은 fib(3), fib(4), fib(5)가 다시 계산 되고 계산되는데, 하위 문제들이 겹치고 반복된다는 것이다.

그렇지만 여기서 계산했던 값들을 기억할 수 있으면 어떨까하는 것이 이 단원의 핵심이다.

동적 프로그래밍의 핵심이다.

과거에 얻은 지식을 미래의 문제를 더 쉽게 풀기 위해서 사용하는것,

복잡한 문제를 더 간단한 하위 문제들의 모음으로 쪼개서 풀어내는 방법이다.

그러면 시간이 아주 많이 절약될 것이다.

여기서 메모이제이션이라는 전략이 필요하다.

7. Memo에 값을 저장하는 방법 소개

메모이제이션이라는 개념은

우리가 하위 문제에 대해 찾은 결과 값을 저장할 수 있는 구조를 사용해서

다음 번에 모든 작업을 반복하지 않고 그냥 데이터 구조를 보는 것이다.

function fib(n, memo=[undefined, 1, 1]) {
	if(memo[n] !== undefined) return memo[n];
    var = res = fib(n-1, memo) + fib(n-2, memo):
    memo[n] = res;
    return res;
}

8. Memo에 값을 기록하는 솔루션의 시간 복잡도

O(N) 👍

9. Tabulation(표): 상향식 접근

동적 프로그래밍의 핵심은 한 문제를 풀 때 그 문제를 더 작은 하위 문제들로 나누고

각각을 한 번 이상 풀어야 할 때 앞에서 계산한 값을 저장해서

같은 하위 문제를 계속해서 풀지 않는 것이다.

이걸 하는 방법 중 하나가 바로 메모이제이션이다.

두번째 방법은 상향식으로 접근하는 방법이 있다.

상향식이라는 것은 fib(1)과 fib(2)로 시작해서 이것들을 더해 올라가면서 fib(3), fib(4)... fib(7)까지 구하는 것이다.

그러면 결과적으로는 같은 결과가 나온다.

그냥 다른 방향으로 작업을 하는 것일 뿐이다.

function fib(n){
    if(n <= 2) return 1;
    var fibNums = [0,1,1];
    for(var i = 3; i <= n; i++){
        fibNums[i] = fibNums[i-1] + fibNums[i-2];
    }
    return fibNums[n];
}

이걸 Tabulation(타뷸레이션)이라고 한다.

동적 프로그래밍은 2 가지 방식인 ①메모이제이션 과 ②타뷸레이션 이 있다.

타뷸레이션에서는 보통 루프와 같이 순환을 통해서 작업을 한다.

무엇이든 간에 맨 밑 바닥에서 시작하면 된다.

가장 작은 하위 문제를 푼 다음에 그 결과를 테이블에 저장한다. 그래서 용어가 타뷸레이션이(표)다.

보통 배열을 사용한다.

배열에 데이터를 저장하고 루프를 돌면서 앞으로 나아가면서 덧셈을 하는 것이다.

덧셈이 아니라면 데이터를 가지고 어떤 작업을 하는 것이다.

얻고자 하는 숫자를 얻을 때까지 반복한다.