Dynamic Programming #1

 

Dynamic Programming

- 다이나믹 프로그래밍은 동적 계획법이라고도 부른다.

- 일반적인 프로그래밍 분야에서 말하는 동적(Dynamic)는 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법을 의미한      다. 

- 반면에 다이나믹 프로그래밍에서 "Dynamic"은 별다른 의미없이 사용된 단어이다.

 

다이나믹 프로그래밍은 문제가 다음의 조건을 만족할 때 사용할 수 있다.

 

1. 최적 부분 구조 (Optimal Subtructure)

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

2. 중복되는 부분 문제 (Overlapping Subproblem)

• 동일한 작은 문제를 반복적으로 해결해야 한다.  

 

메모이제이션 (Memoization)

- 메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 하나이다.

- 한 번 계산한 결과를 메모리 공간에 메모하는 기법이다.

• 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다.
• 값을 기록해 놓는다는 점에서 캐싱(Chching)라고도 한다.

Top-Down VS Bottom-Up

- top-down 방식은 하향식이라고도 하며, bottom-up 방식은 상향식이라고도 한다.

- 다이나믹 프로그래밍의 전형적인 형태는 bottom-up 방식이다.

• 결과 저장용 리스트는 DP 테이블이라고 부른다.

- 엄밀히 말하면 메모리제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미한다.

• 따라서 메모이제이션은 다이나믹 프로그래밍에 국한된 개념은 아니다.
• 한 번 계산된 결과를 담아 놓기만 하고 다이나믹 프로그래밍을 위해 활용하지 않을 수도 있다.

 

피보나치 수열

- 다이나믹 프로그래밍을 활용 가능한 문제중 가장 대표적인 문제라고 할 수 있다.

위와 같은 피보나치 수열에서 단순한 재귀를 활용 하여 푼다면 아래와 같이 작성된다.

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

하지만 이런식으로 풀게되면 반복 호출이 계속되기 때문에 지수의 시간 복잡도를 가지게 된다.

위와 같이 f(2)가 여러번 반복되어 호출되는 것을 볼 수있다.

빅오 표기법을 기준으로 : O(2^N)의 시간복잡도를 가지게 되는데, f(30)만 계산해도 10억가량이다. 

f(100)을 계산하려면 1뒤에 0이 30개가 넘는다.. 

이러한 방법을 해결하기 위해선 중복된 반복 호출을 해결할 수 있는 다이나믹 프로그래밍을 사용하는 것이다.

 

피보나치 수열은 아까 위에서 작성한 다이나믹 프로그래밍 사용 조건 두가지를 모두 만족한다.

 

다이나믹 프로그래밍을 이용한 bottom-up형식으로 피보나치 수열을 만들어보자.

# DP 테이블 초기화
d = [0] * 100

# 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
d[1] = 1
d[2] = 1

n = 99

# 피보나치 함수를 반복문으로 구현(bottom-up 다이나믹 프로그래밍)
for i in range(3, n+1):
	d[i] = d[i-1] + d[i-2]

print(d[n])

위와 같이 작성하면 메모이제이션을 이용하여 아래와 같은 색칠 된 노드만 처리가 되고, 반복된 호출을 줄일 수 있다.