Dynamic Programming (동적 프로그래밍)

Kim Yuhyeon·2022년 3월 7일

DP 알고리즘 이론 자료구조

알고리즘 + 자료구조

목록 보기

12/161

정의

Dynamic Programming (동적 계획법)

큰 문제를 작은 문제로 나누어 푸는 문제
(Dynamic(동적)이라는 이름의 의미는 딱히 없다고 함)
메모리를 적절히 사용하여 수행 시간 효율적을 비약적으로 향상 시킨다.

Divide and Conquer(분할 정복)과의 차이?
작은 문제의 반복이
일어나지 않는가 -> 분할 정복
일어나는가(답이 바뀌지 않음을 이용) -> DP

Memoization (메모이제이션)

이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하고, 다시 사용한다.
결과 저장용 리스트는 DP 테이블이라고 부른다.
(계산된 결과를 담아 놓기만 하고 다시 활용하지 않을 지도..)

조건

1. Overlapping SubProblem(중복되는 부분 문제)

동일한 작은 문제를 반복적으로 해결해야 하는 경우이다.

2. Optimal Substructure(최적 부분 구조)

큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.

방식

1. Top-down(탑다운)

하향식
큰 문제를 풀 때 작은 문제가 아직 풀리지 않았다면 그 때 작은 문제를 해결
재귀 함수로 구현하는 경우가 대부분 Top-down 방식
소스 가독성 증가

// 계산된 결과를 저장하기 위한 DP 테이블 초기화
int d_T[100] = {0, };

int fibo_T(int n){
    if (n <= 2)
        return 1;
    if (d_T[n] == 0){ // 연산 값이 있는지 없는지 검사 후 없으면 새로 연산
        d_T[n] = fibo_T(n-1) + fibo_T(n-2);
    }
    return d_T[n]; // 있으면 바로 반환
}

2. Bottom-up(보텀업)

상향식
작은 문제부터 차근 차근 구해나가는 방법
풀기 쉽지만 가독성이 저하될지도?

// 계산된 결과를 저장하기 위한 DP 테이블 초기화
int d_B[100] = {0, };

int fibo_B(int n){
    //첫 번째 피보나치 수와 두 번째 피보나치 수는 1
    d_B[1] = 1;
    d_B[2] = 1;

    //피보나치 함수 반복문으로 구현 (보텀업 DP)
    for (int i=3; i<=n; i++){
        d_B[i] = d_B[i-1] + d_B[i-2];
    }
    return d_B[n];
}