[자료구조] 다이나믹 프로그래밍1 (Dynamic Programing) with Python

🟡 다이나믹 프로그래밍(Dynamic Programing)이란?

다이나믹 프로그래밍(Dynamic Programing)은 동적 프로그래밍이라고도 부르며 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제해결 패러다임으로 볼 수 있다.

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

🟡 프로그래밍에서 동적의 의미

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

🟡 DP의 사용 조건

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

큰 문제를 작은 문제로 나눌 수 있고, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 경우를 의미

ex) 이진 탐색과 피보나치 수열의 경우를 비교

• 이진 탐색은 특정 데이터를 정렬된 배열 내에서 그 위치를 찾기 때문에 그 위치를 찾은 후 바로 반환할 뿐 그것을 재사용하는 과정을 거치지 않는다.
• 피보나치 수열은 f(n) = f(n-1)+f(n-2)인데, 아래와 같은 트리 구조로 함수가 호출되게 한다.

위에서 보면 f(3), f(2), f(1)과 같이 동일한 부분 문제가 중복되어 나타난다.

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

동일한 작은 문제를 반복적으로 해결해야 하는 경우

위의 그림에서 A-X 사이의 최단 거리는 AX2이고 X-B는 BX2이다. 다른 경로를 선택한다고 해서 전체 최단 경로가 변할 수 없다.

→ 전체 최단 경로 : AX2-BX2

이와 같이, 부분 문제에서 구한 최적 결과가 전체 문제에서도 동일하게 적용되어 결과가 변하지 않을 때 다이나믹 프로그래밍을 사용할 수 있다.

피보나치 수열도 동일하게 이전의 계산 값을 그대로 사용하여 전체 답을 구할 수 있어 최적 부분 구조를 갖고 있다.

부분 문제가 반복적으로 나타나지 않는다면 재사용이 불가능하니 부분 문제가 중복되지 않는 경우에는 사용할 수 없다.

→ 위와 같은 조건을 만족하는 경우에 동적 프로그래밍이 사용 가능하다. 작은 문제의 결과 값이 항상 같다는 점을 이용해서 큰 문제를 해결하는 방법이라는 것을 기억해두자.

🟡 Dynamic Programing을 사용하는 이유

일반적인 재귀 방식과 Dynamic Programing과 매우 유사하다. 가장 큰 차이점은 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복 되어 비효율적인 계산이 될 수 있다는 것이다.

🟡 재귀함수로 피보나치 수열 구현하기

• 피보나치 수열은 Dynamic Programing로 해결할 수 있는 문제들 중 하나이다.

👉 피보나치 수열을 점화식으로 표현

👉 피보나치 수열을 재귀 함수로 구현

def fibo(n):
	if n == 1 ot n == 2:
			return 1
	return f(n) = f(n-1)+f(n-2)
print(fibo(4))
>>> 3

피보나치 수열을 재귀 함수로 구현할 경우 f(n-1), f(n-2)에서 각 함수를 1번씩 호출하면 동일한 값을 2번씩 구하게 되고 이로 인해 100번째 피보나치 수를 구하기 위해 호출되는 함수의 횟수는 기하급수적으로 증가한다.

→ f(n-1)에서 한 번 구한 값을 f(n-2)에서 또 다시 같은 값을 구하는 과정을 반복하게 된다.

하지만 Dynamic Programing을 이용하여 한 번 구한 작은 문제의 결과 값을 저장해두고 재사용 한다면 앞에서 계산된 값을 다시 반복할 필요가 없이 약 200회 내에 계산이 가능해진다.

즉, 매우 효율적으로 문제를 해결할 수 있게 된다. 시간복잡도를 O(n^2) → O(f(n))으로 개선할 수 있다.

🟡 메모이제이션(Memoization)으로 피보나치 수열 구현하기

메모이제이션(Memoization) 이란?

• Dynamic Programing을 구현하는 방법 중 한 종류이다.
• 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 호출하면 메모한 결과를 그대로 가져오는 기법 → (값을 기록해 놓는다는 점에서 캐싱(caching)이라고도 한다.)

memoization = [0] * 100

def fibo(n):
		if n == 1 or n == 2:
				return 1
		if memoization[n] != 0:
				return memoization[n]
		memoization[n] = fibo(n-1) + fibo(n-2)
		return memoization[n]

print(fibo(5))

👉 메모이제이션을 사용하여 f(5)을 구하는 과정

메모이제이션을 적용했을 때의 피보나치 수열 알고리즘의 시간 복잡도는 O(N)이다. 왜냐하면 f(1)을 구한 다음 그 값이 f(2)를 구하는 데 사용되고, f(2)의 값이 f(3)을 푸는데 사용되는 방식으로 이어지기 때문이다.

→ 메모이제이션은 리스트에 값이 정해져 있고 한 번 구한 결과는 다시 계산하지 않는다.

🟡 Dynamic Programing 구현 방식

👉 Bottom-UP (Tabulation)

- **작은 문제부터 답을 구해가며 전체 큰 문제를 해결하는 방식**
- 타블레이션(Tabulation)을 사용하여 다이나믹 프로그래밍을 구현하는 방식 중 하나
    - 타블레이션(Tabulation) : 하위 문제부터 천천히 해결하면서 더 큰 문제를 해결하는 기법
- ‘**상향식 방식**’이라고도 한다.
- 재귀 호출을 하지 않기 때문에 시간과 메모리 사용량을 줄일 수 있는 장점이 있다.
- Dynamic Programing의 전형적인 형태

dp = [0]*100
dp[1] = 1
dp[2] = 1
n = 99

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

👉 Top-Down (Memozation)

• 큰 문제를 해결하기 위해서 작은 문제를 호출하는 방식
  • 메모이제이션(Memoization)을 사용하여 Dynamic Programing을 구현하는 방식 중 하나
  • 위에서부터 바로 호출을 시작하여 결과 값을 재귀 함수를 통해 전이시켜 재활용하는 방식이다.
  • ‘하향식 방식’이라고도 한다.
  • 점화식을 이해하기 쉬운 장점이 있다.

✔️ Dynamic Programing과 Memoization 차이

• Memoization은 이전에 계산된 결과를 일시적으로 기록해 놓은 넓은 개념을 의미하기 때문에 별도의 개념이다.
  → 한 번 계산된 결과를 담아 놓기만 하고 DP를 위해 활용하지 않을 수도 있다.
  

👉 분할 정복 (Divide and Conquer)

• Dynamic Programing과 분할 정복의 공통적은 ‘최적 부분 구조’를 가질 때 사용할 수 있다는 것이다.
  • 큰 문제를 작은 문제로 나눌 수 있고, 작은 문제의 답을 모아 큰 문제를 해결할 수 있는 경우
• Dynamic Programing과 분할 정복의 차이점은 ‘부분 문제의 중복’이다.
  - Dynamic Programing은 문제에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복된다.
  - 분할 정복은 동일한 부분 문제가 반복적으로 계산되지 않는다.

분할 정복의 대표적인 예시는 퀵 정렬이다.

한 번 기준 원소(Pivot)가 자리를 변경해서 자리를 잡으면 그 기준 원소의 위치는 바뀌지 않는다.

분할 이후 해당 원소를 다시 처리하는 부분 문제는 호출하지 않는다.

→ 분할 후 한쪽 정렬이 끝났으면 이후에는 정렬을 할 필요가 없다고 생각하면 된다. (부분 문제가 반복되지 않는다.)

Reference

https://ko.wikipedia.org/wiki/%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95
https://namu.wiki/w/%EB%8F%99%EC%A0%81%20%EA%B3%84%ED%9A%8D%EB%B2%95
https://www.zerocho.com/category/Algorithm/post/584b979a580277001862f182