[알고리즘] 다이나믹 프로그래밍 (1)

* 본 포스팅은 나동빈 - 이코테 2021 강의 몰아보기 에서 학습한 내용을 포스팅합니다.

---

출처

동빈나 이코테

 

 

■ 다이나믹 프로그래밍

• 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상하는 방법
• 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다.
• 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운, 보텀업)으로 구성
• 다이나믹 프로그래밍은 동적 계획법이라고도 부른다.

 

 

■ 일반적인 프로그래밍 분야에서의 동적(Dynamic)이란 어떤 의미를 가질까?

• 자료구조에서 동적 할당(Dynamic Allocation)은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'을 의미
• 반면에 다이나믹 프로그래밍에서 '다이나믹'은 별다른 의미 없이 사용된 단어

 

■ 다이나믹 프로그래밍의 사용조건

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

 

---

■ 피보나치 수열

• 피보나치 수열 다음과 같은 형태의 수열이며, 다이나믹 프로그래밍으로 효과적으로 계산할 수 있다.
  
  • 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
• 점화식이란 인접한 항들 사이의 관계식을 의미
• 피보나치 수열을 점화식으로 표현하면 다음과 같다.

 

• n번째 피보나치 수를 f(n)라고 할 때 4번째 피보나치 수 f(4)를 구하는 과정은 이렇다.

■ 피보나치 수열 : 단순 재귀 코드(Python)

# 피보나치 함수(Fibonacci Function)을 재귀함수로 구현
def fibo(x):
    if x == 1 or x == 2:
    	return 1
    return fibo(x - 1) + fibo(x - 2)
    
print(fibo(4))  # 3

 

 

■ 피보나치 수열의 시간 복잡도 분석

• 단순 재귀 함수로 피보나치 수열을 해결하면 지수 시간 복잡도를 가진다.
• 다음과 같이 f(2)가 여러 번 호출되는 것을 확인할 수 있다.(중복되는 부분 문제)

한번 해결한 문제에 대해서 이 문제는 이미 해결한 적 있기 때문에 이 문제의 답은 이거야!라고 알려줄 수 있도록 별도의 메모리 공간에 이미 해결한 문제에 대한 정보를 기록해 놓지 않으면 중복된 부분 문제를 계속 해결하게 되고 그렇기 때문에 수행시간 측면에서 비효율적으로 동작

• 피보나치 수열의 시간복잡도는 다음과 같다.
  • 세타 표기법: θ(1.618 ...ⁿ)
  • 빅오 표기법: O(2ⁿ)
• 빅오 표기법을 기준으로 f(30)을 계산하기 위해 약 10억 가량의 연산을 수행해야 한다.

 

 

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

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

 

---

 

■ 메모이제이션(Memoization)

• 하양식 즉 탑다운 방식에서 사용된다.
• 메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 하나이다.
• 한 번 계산한 결과를 메모리 공간에 메모하는 기법이다.
  • 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져옵니다.
  • 값을 기록해 놓는다는 점에서 캐싱(Caching)이라고 한다.
  • 메모할 때 사용하는 배열 이름을(캐시, 메모, 테이블, DP)라고 불린다.

 

 

■ 탑다운 VS 보텀업

• 탑다운(메모이제이션) 방식은 하향식이라고 하며 보텀업 방식은 상향식이라고 한다.
• 다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식이다.
• 엄밀히 말하면 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓은 넓은 개념을 의미한다.
  • 따라서 메모이제이션은 다이나믹 프로그래밍에 국한된 개념은 아니다.
  • 한 번 계산된 결과를 담아 놓기만 하고 다이나믹 프로그래밍을 위해 활용하지 않을 수도 있다.

 

 

■ 피보나치 수열: 보텀업 다이나믹 프로그래밍 소스코드(Python)

# 앞서 계산된 결과를 저장하기 위한 DP테이블 초기화
d = [0] * 100

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

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

■ 피보나치 수열: 탑다운 다이나믹 프로그래밍 소스코드(Python)

# 한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화
d = [0] * 100

# 피보나치 함수를 재귀함수로 구현(탑다운 다이나믹 프로그래밍)
def fibo(x):
    # 종료 조건 (1 혹은 2일 때 1을 반환)
    if x == 1 or x == 2:
    	return 1
    # 이미 계산한 적 있는 문제라면 그대로 반환
    if d[x] != 0:
    	return d[x]
    # 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
    d[x] = fibo(x - 1) + fibo(x - 2)
    return d[x]
    
print(fibo(99)) # 218922995834555169026

 

 

■ 피보나치 수열: 메모이제이션 동작 분석

• 이미 계산된 결과를 메모리에 저장하면 다음과 같이 색칠된 노드만 처리할 것을 기대한다.

 

 

• 실제로 호출되는 함수에 대해서만 확인해 보면 다음과 같이 방문한다.

 

 

• 메모이제이션을 이용하는 경우 피보나치 수열 함수의 시간 복잡도는 O(N)이다.

d = [0] * 100

def fibo(x):
    print('f(' + str(x) + ')', end=' ')
    if x == 1 or x == 2:
    	return 1
    if d[x] != 0:
    	return d[x]
    d[x] = fibo(x - 1) + fibo(x - 2)
    return d[x]
    
fibo(6) # f(6) f(5) f(4) f(3) f(2) f(1) f(2) f(3) f(4)