[알고리즘][개념정리] Dynamic Programming(DP) | 코드 플러스 강의: 알고리즘 기초

* 해당 글은 코드 플러스의 '알고리즘 기초' 강의의 내용을 기반으로 작성하였습니다.

 

 

다이나믹 프로그래밍 (Dynamic Programming: DP)

> == 동적 계획법

> 큰 문제를 작은 문제로 나눠서 푸는 알고리즘

 

 

큰 문제를 작은 문제로 나누어서 푸는 방법 2가지

1. 다이나믹 프로그래밍(Dynamic Programming: DP)

    - 작은 문제들이 중복일 수 있음

2. 분할정복 (Divid & Conqer: D&C)

    - 작은 문제들이 절대로 중복이 되지 않음

 

다이나믹 프로그래밍 조건

1. Overlapping Subproblem: 겹치는 부분 문제

    - 작은 문제들이 중복이어야 한다

2. Optimal Substructure: 최적 부분 구조

    - 문제의 정답을 작은 문제들의 정답을 통해 구할 수 있다 

    - 문제의 크기에 상관없이 어떤 한 문제의 정답은 일정하다 

 

ex) 피보나치 수열

    - 큰 문제: N번째 피보나치 수열을 구하는 문제

    - 작은 문제: N-1번째 피보나치 수와 N-2번째 피보나치 수를 구하는 문제

 

Memoization

    - DP에서 각 문제는 한 번만 풀어야 한다

    - Optimal Substructure를 만족하기 떄문에, 같은 문제는 구할 때마다 정답이 같다

    - 한 번 구한 정답은 나중에 다시 사용하기 위해 배열에 메모해둔다

 

ex) Memoization을 적용한 피보나치 수열

int memo[100];
int fibonacci(int n) {
	if (n <= 1) {
    	return n;
    }
    else {
    	if (memo[n] > 0) {
        	return memo[n];
        }
    	memo[n] = fibonacci(n-1) + fibonacci(n-2);
        return memo[n];
    }
}

 

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

1. Top-down

    - 큰 문제를 작은 문제로 나눈다

    - 작은 문제를 푼 후 큰 문제를 푼다

    - 재귀 사용

2. Bottom-up

    - 크기가 작은 문제부터 풀고, 더 큰 문제까지 점점 푼다

    - 작은 문제를 풀면서 왔기 때문에, 큰 문제는 항상 풀 수 있다

    - 반복문 사용

 

=> 시간 차이: 알 수 없음

=> 재귀 사용 시 스택 오버플로: C++, Java는 거의 발생하지 않음 / Python은 자주 발생

=> Top-down과 Bottom-up 둘다 사용할 수 있게 공부하기

 

문제 풀이 방법

    - 점화식을 쓰자!

    - 모든 경우 다 따져보기