[자료구조/알고리즘] python 다이나믹프로그래밍 개념 및 예제

들어가기 전에...

최근 진행한 코딩테스트에서, 문제를 풀다 테스트 케이스 몇개에서 실패를 경험하였다.

복기를 해보니, 문제의 느낌만 보고 그리디 알고리즘을 통해 구현을 진행한것이 원인이였다.

해당 그리디 알고리즘을 통해 순간에서 최선의 선택을 통해 구현을 하다보니,

최적의 해를 놓치는 케이스가 발생하였고,

이를 해결하기 위한 적합한 방식은 모든 경우의 수에서 최적의 해를 구하는 것이였다.

이를 효과적으로 하기 위한 알고리즘은 다이나믹 프로그래밍이였으며, 이번 기회에 정리하고자 한다.

다이나믹 프로그래밍

• 복잡한 문제를 작은 문제로 나누어 해결하는 방법
• 이미 계산한 작은 문제의 답을 기억해 두었다가 재사용
• 이렇게 하면, 같은 계산을 반복하지 않아도 되기 떄문에 효율적
• 메모리 공간을 조금 더 사용하지만, 수행 시간을 획기적으로 줄일 수 있다

언제 사용할 수 있는가?

• 최적 부분 구조
  • 큰 문제를 작은 문제로 나눌 수 있고, 이에 대한 답을 모아 큰 문제를 해결할 수 있을때
• 중복된 하위 문제
  • 동일한 작은 문제를 반복적으로 해결해야 할때

대표적인 예시

• 피보나치 수열
  • 피보나치 수열은 현재 항을 계산하기 위해 이전 두 항의 합을 구해야함

피보나치 수열 점화식

 

<반복문 구현>

def fibo(x):
	if x<=2:
		return 1
	
	a, b = 0,1
	for i in range(x-1):
		a, b = b, a+b
	return b

 

시간 복잡도 : T(n) = n+1  --> O(n)

특징

• 불필요한 연산을 계속 수행해야 한다.

 

<재귀함수 구현>

def fibo(x):
	if x==1 or x==2:
    	return 1
    return fibo(x-1) + fibo(x-2)

시간 복잡도 : T(n) = T(n-1) + T(n-2) + c --> O(2^n)

특징

• 코드 구성이 간단하다.
• 시간 복잡도가 크다. 
• 재귀의 특징에 따라 Stack Overflow가 발생할 수 있다.
• 불필요한 연산을 계속 수행해야 한다.

다이나믹 프로그래밍이 필요한 이유

• 기존의 재귀적인 방법과, 반복을 이용한 방법은 매우 비효율적이다.
• 그 이유로는 부분 문제가 너무 많이 중복 된다.
• 예를 들면 fibo(5)를 수행하면 fib(0)과 fib(1)은 많은 중복이 발생한다. 그때마다 연산을 계속 진행하기에는 낭비가 크다
• 단, 추가적인 메모리 공간이 필요하다.

방식 1) TopDown - 메모이제이션

• 메모이제이션(memoization) 이란 한번 구한 계산 결과를 메모리 공간에 메모해 두고, 같은 식을 다시 호출하면 메모한 결과를 가져와 사용
• 탑다운 방식은 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 하향식으로 불림
• 재귀함수를 통해 구현 가능

# 피보나치 수열을 재귀함수로 구현(topdown)
def fibo(x):
  # fibo(1)=fibo(2)=0
  if x==1 or x==2:
    return 1

  # 이미 계산한 적있는 문제라면 그대로 반환
  if memo[x] != 0:
    return memo[x]

  # 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
  memo[x] = fibo(x-1)+fibo(x-2)
  return memo[x]

방식 2) BottomUp - 타블레이션

• 타블레이션(tabulation) 이란 하위 문제부터 천천히 해결하면서 더 큰 문제를 해결하는 기법
• 작은 문제부터 큰 문제까지 하나하나 테이블을 채워간다는 의미 (상향식 의미)
• 다이나믹 프로그래밍의 전형적인 형태이며, 반복문을 통해 구현 가능

# 작은 문제부터 해결해서 저장할 dp테이블
dp = [0]*100

# fibo(1)=fibo(2)=0
dp[1]=1
dp[2]=1
n=99

# 피보나치 수열을 반복문으로 구현(bottom up)
for i in range(3, n+1):
  dp[i] = dp[i-1]+dp[i-2]

print(dp[n])

 

반복적 동적계획법(바텀업) VS 재귀적 동적계획법(탑다운)

• 재귀적 동적계획법은 함수를 계속 호출하는 데에 따르는 오버헤드가 발생할 수 있어서 반복적 동적계획법보다는 느리다. 
• 하지만 그 차이는 미세하여서 무시가 가능할 정도
• 이에따라, 반복적 동적계획법을 많이 사용하는 것으로 보임

 

 

출처:

https://jiyoungtt.tistory.com/43

피보나치수열_Fibonacci Sequence

https://doing7.tistory.com/75

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