[이것이 취업을 위한 코딩 테스트다 with 파이썬] (한빛미디어, 나동빈) Chapter8(1). 다이나믹 프로그래밍

 포스팅 개요

 '혹시나 책에 있을 모든 실수와 오류는 온전히 제 책임이며, 책에 실린 좋은 아이디어와 표현은 모두 리뷰어님들의 조언 덕분입니다. 정말 고맙습니다.'라는 지은이의 글은 나동빈 저자님의 인품을 느낄 수 있는 한 줄이었습니다.

 

 저도 저런 마인드를 가진 사람이 되겠다고 다짐하며 책과의 여정을 떠나보겠습니다.

 

이것이 취업을 위한 코딩 테스트다

---

 포스팅 본문

  다이나믹 프로그래밍이란 메모리 공간을 약간 더 사용하여 연산 속도를 비약적으로 증가시키는 기법이다. 다이나믹 프로그래밍에는 탑다운과 바텀업 방식 2가지가 있다. 다이나믹 프로그래밍은 항상 사용할 수는 없으며, 다음 조건을 만족할 때 사용할 수 있다

   1. 큰 문제를 작은 문제로 나눌 수 있다.

   2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

 

 본 코드는 모두 제 Github에 올려두었습니다. (https://github.com/herjh0405/Coding_Test)

---

 방식을 이야기하기 전에 아이디어를 소개하기 위해 피보나치수열을 이야기하겠다.

8-1. 피보나치 함수 소스코드

# 피보나치 함수를 재귀 함수로 표현
def fibo(x) : 
     if x == 1 or x == 2 :
          return 1 
     return fibo(x-1) + fibo(x-2)

print(fibo(4)) # 3

 재귀 함수를 사용하면 이렇게 간단히 해결할 수 있지만, n이 커질수록 수행 시간이 기하급수적으로 늘어나는 문제가 발생 왜냐? 이미 계산을 마친 함수들을 계속 계산하기 때문 -> 이것을 다이나믹 프로그래밍으로 해결

8-2. 피보나치수열 소스코드(재귀적)

 메모제이션은 다이나믹 프로그래밍을 구현하는 방법 중 한 종류로 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법 / 캐싱이라 하기도 함

# 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 리스트 초기화
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

 재귀 함수를 사용하면 컴퓨터 시스템에서는 함수를 다시 호출했을 때 메모리 상에 적재되는 일련의 과정을 따라야 하므로 오버헤드가 발생할 수 있다 따라서 재귀 함수 대신에 반복문을 사용하여 오버헤드를 줄일 수 있다. 일반적으로 다이나믹 프로그래밍에는 반복문을 이용한 것이 성능이 더 좋다.

재귀적 방법을 통해 여러 번 계산이 필요 없음을 보여주는 코드

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)

8-4. 피보나치수열 소스코드(반복적)

 이처럼 재귀 함수를 이용하여 다미나믹 프로그래밍 소스코드를 작성하는 방법을, 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 탑다운 방식이라고 함. 반면에 단순히 반복문을 이용하여 소스코드를 작성하는 경우 작은 문제부터 차근차근 답을 도출한다고 하여 바텀업 방식이라고 함

# 앞서 계산된 결과를 저장하기 위한 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])

 다이나믹 프로그래밍의 전형적인 형태는 바텀업 방식이다. 바텀업 방식에서 사용되는 결과 저장용 리스트는 'DP 테이블'이라고 부르며, 메모이제이션은 탑다운 방식에 국한되어 사용하는 표현이다.

---

 문제를 푸는 첫 번째 단계는 주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이다.

특정한 문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸리면 다이나믹 프로그래밍을 적용할 수 있는지 해결하고자 하는 부분 문제들의 중복 여부를 확인해보자.

 Tip. 탑다운 방식으로 구현 시 'recursion depth'오류가 발생할 수 있다. 이때 sys 라이브러리의 setrecursionlimit() 메서드를 호출하여 해결할 수 있음을 기억해두자.

 

 이번에는 다이나믹 프로그래밍의 탑다운 바텀업 방식을 피보나치 함수를 구현함으로써 배워보았습니다. 다음 포스팅에서는 이 방식을 이용한 예제를 풀어보겠습니다. 감사합니다.

 Chapter8(2)에서 뵙겠습니다. :)