🌼 Dynamic Programming (다이나믹 프로그래밍/동적 계획법)

🌼 Dynamic Programming (다이나믹 프로그래밍/동적 계획법)

🌼 다이나믹프로그래밍

• 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법
• 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다.
• DP의 구현은 일반적으로 두 가지가 있다.
  • 상향식(Bottom Up)
  • 하향식(Top Down)
• 다이나믹 프로그래밍은 동적 계획법이라고도 부른다.
• 프로그래밍 분야에서의 Dynamic?
  • 자료구조에서 동적 할당(Dynamic Allocation)은 '프로그래밍 실행되는 도중 필요한 메모리할당 기법'이다.
  • 반면, Dynamic Programming의 Dynamic은 별다른 의미 없이 사용한다.

🌼 다이나믹프로그래밍의 조건

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

1. 최적 부분 조건(Optimal Substructure):
   • 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.
2. 중복되는 부분 문제(Overlapping Subproblem)
   • 동일한 작은 문제를 반복적으로 해결해야 한다.

 

🌼 피보나치 수열

• 피보나치 수열은 다음과 같은 형태의 수열이며, 다이나믹 프로그래밍으로 효과적으로 계산할 수 있다.

1 1 2 3 5 8 13 21 34 55 89 ...

• 점화식이란 인접한 항들의 관계식을 의미
• 피보나치 수열의 점화식
  • An = An-1 + An-2, A1 = 1, A2 = 1
•  피보나치 수열이 계산되는 과정은 다음과 같이 표현할 수 있다.
• n번째 피보나치 수를 f(n)이라고 할 때, 4번째 피보나치수 f(4)를 구하는 과정은 다음과 같다.

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

 

🌼 피보나치 수열의 시간복잡도

• 단순 재귀함수로 구현하게 되면 지수 시간 복잡도를 가지게 된다.
• f(x)가 여러번 호출되는 것을 확인할 수 있다. (중복되는 문제)
• 시간복잡도: O(2^N)

 

🌼 피보나치 수열의 효율적인 해법: 다이나믹 프로그래밍

• DP 사용조건을 만족하는지 확인
  • 최적부분구조: 큰 문제를 작은 문제로 나눌 수 있다.
  • 중복되는문제: 동일한 작은 문제를 반복적으로 해결
• 피보나치수열은 DP 사용 조건을 만족한다.

 

🌼 메모제이션(memozation)

• 메모제이션은 DP 구현 방법중 하나이다.
• 한번 해결한 결과를 메모리제 저장하는 기법
• 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져옴.
• 값을 기록해 놓는다는 점에서 캐싱(Caching)이라고도 한다.

 

🌼 Top Down vs Bottom Up

• 탑다운(메모제이션) 방식은 하향식이라고도 하며, 바텀업은 상향식이라고도 한다.
• DP의 전형적인 형태는 바텀업 방식이다.
  • 결과 저장용 리스트는 DP 테이블이라고 부른다.
• 엄밀히 말하면 메모제이션은 이전에 계산된 결과를 일시적으로 저장해 놓는 개념을 의미한다.
  • 따라서 메모제이션은 DP에 국한된 개념은 아니다.
  • 한번 계산된 결과를 담아 놓기만하고 DP에 활용하지 않을 수도 있다.

1️⃣ Top Down(하향식)

dp = [0] * 100

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

 

2️⃣ Bottom Up(상향식)

dp = [0] * 100

d[1] = 1
d[2] = 1

for x in range(3, n + 1):
	dp[x] = dp[x-1] + dp[x-2]
print(dp[n])

 

 

🌼 다이나믹프로그래밍 vs 분할정복

• DP와 분할정복은 모두 최적 부분 구조를 가질 때 사용할 수 있다.
• 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 상황
• DP와 분할정복의 차이점은 부분문제의 중복이다.
• 분할정복은 동일한 부분 문제가 반복적으로 계산되지 않는다.

• 분할 정복의 대표적인 예시인 퀵정렬을 살펴보겠다.
  • 한 번의 기준 원소(Pivot)가 자리를 변경해서 자리를 잡으면 그 기준 원소의 위치는 바뀌지 않는다.
  • 분할 이후에 해당 Pivot을 다시 처리하는 부분 문제는 호출하지 않는다.

🌼 DP문제에 접근하는 방법

• 주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이 중요하다.
• 가장 먼저, 그리디, 구현, 완전탐색 등의 아이디어로 문제를 해결할 수 있는지를 검토
  • 다른 알고리즘 풀이가 떠오르지 않는다면 DP를 고려
• 일단 재귀함수로 비효율적인 완전탐색 프로그램을 작성한 뒤에(탑다운) 작은문제에서 구한 답이 큰 문제에서 그래도 사용될수 있으면, 코드를 개선
• 일반적인 코딩테스트 수준에서는 기본 유형의 DP 문제를 출제