알고리즘 - 다이나믹 프로그래밍 (Dynamic Programming)

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

 

 

• 개념 : 문제를 더 작은 단위로 쪼개어 해결하는 알고리즘. (분할 정복 알고리즘과 비슷하다. 차이점은 바로 아랫줄.)
• 핵심은, 그 작은 단위의 문제들이 반복해서 일어나기 때문에, 그값들을 저장해놓는 식으로 해결해나가는 알고리즘
• (다이나믹이라는 이름에는 아무 뜻도 없다고 한다.) 

 

 

 

*다이나믹 프로그래밍을 사용하기 위한 조건

 

1. 부분 문제들이 겹치는가 (반복 되는가)   

    ex ) 피보나치 수 : N번째 항(큰 문제) =  N-1번째 항(작은 문제) + N-2 번째 항(작은 문제)

피보나치의 특성을 잘 살펴보면 Fibo(10)을 구할때는 Fibo(9)+Fibo(8)...........Fibo(1) 까지 모두 필요합니다. 이때 메모이제이션을 통해 배열에 저장해놓는다면, Fibo(12)를 구할때는 , 1~10번째 항까지 이미 메모가 되어있으므로, 11번째 항만 연산하면 되므로 효율적입니다.

* 재귀함수로 구현한 피보나치 (Python)

 

def fibonacci(n):
	if n<=1 :
		return n
	
	else : return fibonacci(n-1) + fibonacci(n-2)

 

다이나믹 프로그래밍으로 구현한 피보나치 (memoization)

memo = [0 for i in range(100)]
def fibonacci(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]

        한번 거쳤던 항들은 모두 memo에 저장된다. 따라서, 다음에 구할때는 연산없이 리턴이 가능하다.

 

2. 최적 부분 구조 (문제의 정답을 작은 문제의 정답으로부터 구할 수 있는가)

    ex ) 최단경로 구하기  : A에서 C로 가는 최단경로 (큰 문제) = A에서 B로가는 최단경로(작은 문제) + B에서 C로가는 최단경로(작은 문제)

 

따라서, 정답을 한번 구했으면 Memoization 하여, 반복연산을 없애는 과정이 중요하다.

 

 

 

---

*다이나믹 프로그래밍 구현

 

*Top - down : 위에서 아래로 해결한다. (ex : 재귀함수)

1. 문제를 쪼갠다.
2. 작은 문제를 푼다.
3. 작은 문제의 정답으로 큰 문제를 해결한다.

*bottom - up : 아래에서 위로 (ex : 반복문)

1. 작은 문제부터 풀어나간다.
2. 문제의 크기를 점점 크게 만들어 푼다.
3. 작은 문제들을 해결했기 때문에, 한단계 위의 큰 문제를 풀 수 있다.
4. 최종적인 문제를 해결한다.

 

 

시간복잡도는 비슷한 수준이며, 문제에 따라 구현하기 편한것을 선택하여 풀면 된다. (즉, 어떤것으로 풀어도 큰 상관은 없다) 다만 파이썬 같은경우는 재귀로 풀게되면 메모리초과가 날 가능성이 타 언어보다 높기 때문에, 반복문(bottom_up)으로 푸는게 낫다고한다.

*문제를 해결할때

• 점화식을 정의한다.
• 문제를 어떠한식으로 쪼갤지 (작게 만들지) 생각한다.
• 작은 문제의 답을 통해 어떻게 최종적인 문제를 해결할 수 있을지 생각한다.

 

 

 

예를들어 카드를 i 개 구매하는 문제라고하면, 하나 구매할때, 두개 구매할때, 차근차근 생각해보고, 적어보면 규칙이 보이거나 점화식이 보인다. 비슷한 유형을 풀어보며 감을 기르는게 무엇보다 중요한것 같다.

 

---

* 관련 유형 문제 (boj) 

 

 

 

카드 구매하기 1 (난이도 실버1)

https://infinitt.tistory.com/250

백준 (boj) 파이썬 - 11052 번 : 카드 구매하기

 

 

카드 구매하기 2 (난이도 실버1)

https://infinitt.tistory.com/251

백준 (boj) 파이썬 - 16194번 : 카드 구매하기 2 (DP)

 

 

2xN 타일링 (난이도 실버3)

https://infinitt.tistory.com/217

백준 (boj) 파이썬 - 11727 2xN 타일링