동적 계획법(다이나믹 프로그래밍, DynamicProgramming), 다른 알고리즘들과의 비교

재귀함수와 비교해 함께 공부하면 좋다.

 

동적 계획법의 정의

큰 문제를 작은 문제로 나누어 푸는 문제를 말한다.

→ 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘

 

동적 계획법 사용 조건

DP는 항상 사용할 수 없기에 아래 사용 조건을 만족할 때 사용한다.

1. 큰 문제를 작은 문제로 나눌 수 있고, 작은 문제의 답을 모아 큰 문제를 해결 할 수 있다. → 최적 부분 구조(Optimal substructure)

2. 동일한 작은 문제를 반복적으로 해결한다. → 중복되는 부분 문제(Overlapping subproblem)

 

 

Memoization 기법

이전에 풀었던 문제의 정답이나 결과 값을 저장하여, 이후의 문제를 풀 때 다시 계산하지 않고, 미리 계산된 값을 불러와서 문제를 해결하는 방법이다.

→문제를 세부적으로 나누어서 해결 할 때 이전에 계산했던 결과를 재활용한다.

→값을 기록해 놓는다는 점에서 캐싱(Caching)이라고도 한다.

→Top-Down(하향식) 방식의 문제 풀이이다.

 

피보나치 수열로 이해하는 다이나믹 프로그래밍

재귀함수로 피보나치 수열을 풀이했을 때 n값이 커질 수록 중복되는 부분문제로 인해 시간 복잡도가 엄청 커지는 문제가 있었다.

따라서 문제를 좀 더 효율적으로 해결하기 위해 다이나믹 프로그래밍으로 풀이 해보겠다.

 

Memoization을 사용해 f(6)를 구하는 과정

색칠된 노드들인 f(6)-f(5)-f(4)-f(3)만 방문하게 된다.

실제 코드에선 호출되는 함수는 아래 그림과 같다.

실제 코드에서 호출되는 함수 방문 순서

f(6) - f(5) - f(4) - f(3) - f(2) - f(1) - f(2) - f(3) - f(4)

DP를 적용했을 때의피보나치 수열 알고리즘의 시간 복잡도는 O(N)이다.

f(1)을 구한 다음 그 값이 f(2)를 구하는데 사용되고, f(2)의 값이 f(3)을 푸는 데 사용되는 방식으로 이어지기 때문이다.

또한, Memoization의 특징에 따라 한번 구한 결과는 다시 구해지지 않는다.

#Memoization하기 위한 리스트 초기화
memoization = [0] * 100
def fibo(x):
		if x == 1 or x == 2:
				return 1
#이미 계산 한 적 있으면 그대로 반환
		if memoization[x] != 0:
				return memoization[x]
#계산한 적 없으면 점화식(피보나치 점화식: f(n) = f(n-1) + f(n-2)에 따라 피보나치 결과 반환
		memoization[x] = fibo(x - 1) + fibo(x - 2)
		return memoization[x]

print(fibo(6))

 

하향식(Top-Down) vs 상향식(Bottom-Up)

DP문제를 푸는 방법에는 하향식(Top-Down)과 상향식(Bottom-Up)이 있다.

• 하향식(Top-Down)

큰 문제를 해결하기 위해 작은 문제로 나눠서 ‘재귀적으로’ 구하고, 이를 취합해 큰 문제의 해를 구한다.

한 번 계산된 결과를 기억하기 위해 Memoization 기법을 사용한다.

점화식을 이해하기 쉬운 장점이 있다.

• 상향식(Bottom-Up)

가장 작은 문제들로부터 답을 구해가며 전체 문제의 답을 찾는 방식이다.

재귀 호출을 하지 않기 때문에 메모리 사용량을 줄일 수 있는 장점이 있다.

프로그래밍 언어에서는 반복문을 사용해서 구현한다.

DP의 전형적인 방식이며, 부분해의 결과를 임시적으로 저장하는 배열을 DP테이블이라고 한다.

 

DP vs 분할 정복(Divide and Conquer)

DP와 분할 정복은 모두 ‘최적 부분 구조’를 가질 때 사용할 수 있다.

DP와의 공통점은 큰 문제를 작은 문제로 나눌 수 있고, 작은 문제의 답을 모아 큰 문제를 해결할 수 있다.

DP와 분할 정복의 차이점

• 부분 문제의 중복
• DP 문제에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복된다.
• 분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않는다.

DP vs 그리디(Greedy)알고리즘

매 단계마다 현재 최적이라고 판단되는 것만 근시안적으로 선택한다.

전체적인 최적해는 보장하지 못하는 경우가 많다.

→단순히 가장 좋아보이는것만 반복적으로 선택해도 최적의 해를 구할 수 있는지 그 정당성을 분석하는게 중요하다.

반면, DP는 작은 문제에 대한 모든 가능성을 고려하여 다음 크기의 문제에 대한 최적해를 구하기 때문에 항상 최적의 결과를 얻을 수 있다.

 

DP 사용법

주어진 문제가 DP 유형인지 파악해라.

→ 그리디, 시뮬레이션, 완전탐색 등의 알고리즘으로 문제를 풀 수 있는지 검토한 후 풀 수 없다고 생각이 들면 DP를 사용해라

 

재귀 함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤에 작은 문제에서 구한 답이 큰 문제에서 그대로 사용 될 수 있다면 DP로 코드를 개선하면 된다.

→ 피보나치 수열의 예제 처럼 재귀 함수를 작성 한 뒤 나중에 Memoization 기법을 적용해 소스 코드를 수정하는 것도 괜찮다.

 

DP 적용 단계

1. 문제의 특성을 분석하여 최적 부분 구조가 성립하는지 확인한다.
2. 주어진 문제에 대해 최적해를 제공하는 점화식을 도출한다.
3. 가장 작은 부분 문제부터 점화식의 해를 구한 뒤 이를 테이블에 저장한다.
4. 테이블에저장되어 있는 부분 문제의 해를 이용하여 점차적으로 입력 크기가 큰 상위 문제의 해를 구한다.(상향식)

➕참고

일반적인 프로그래밍 분야에서 동적(Dynamic)의 의미란?

자료구조에서 동적 할당(Dynamic Allocation)은 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법을 의미한다.

반면에 DP(Dynamic Programming)에서 Dynamic은 별다른 의미가 없다고 한다.

 

알고리즘 만든 사람도 멋있다는 이유로 Dynamic이란 단어를 프로그래밍에 결합,,,했다고 한다,,,

 

---

[참조]

https://velog.io/@kimdukbae/다이나믹-프로그래밍-Dynamic-Programming #다이나믹 프로그래밍
https://veggie-garden.tistory.com/21 #DP로 푸는 피보나치 수열 이해 
https://data-marketing-bk.tistory.com/entry/동적-계획법DP과-분할-정복-마스터하기?category=901221 #재귀함수와 비교하는 피모나치 수열 
https://velog.io/@jxlhe46/알고리즘-다이나믹-프로그래밍 #DP와 다른 알고리즘 비교

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

동적 계획법(DP)과 분할 정복 마스터하기

[Python] 다이나믹 프로그래밍 (DP)