📖 중복되는 연산을 줄이자
-
메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있는데, 대표적인 방법이 바로 다이나믹 프로그래밍(Dynamic Programming) 기법임
-
다이나믹 프로그래밍에는 2가지 방식이 존재함
- 탑다운 방식(Top-Down)
- 보텀업 방식(Bottom-Up)
-
다이나믹 프로그래밍과 동적 할당의 다이나믹은 같은 의미일까?
- 프로그래밍에서 다이나믹 = '프로그램이 실행되는 도중에'
- 다이나믹 프로그래밍에서의 '다이나믹'은 이런 의미가 아님
-
다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로 피보나치 수열이 있음
- 피보나치 수열이란 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열임
- 피보나치 수열의 점화식은 다음과 같이 표현할 수 있음
- 앞서 언급한 피보나치 수열에서는 첫 번째 항과 두 번째 항의 값이 모두 1이기 때문에 최종적으로 피보나치 수열을 나타낼 때에는 다음과 같이 정의할 수 있음
- 프로그래밍에서는 이러한 수열을 배열이나 리스트로 표현할 수 있음
- 파이썬에서는 리스트 자료형을 이용해 처리
- C/C++와 자바에서는 배열을 이용해 처리
- 점화식에 따라 실제로 피보나치 수를 구하는 과정은 다음과 같음
- 수학적 점화실을 프로그래밍으로 표현하려면 재귀 함수를 사용하면 간단함
✏️ 8-1 .py 피보나치 함수 소스코드
# 피보나치 함수(Fibonacci Function)를 재귀 함수로 구현 def fibo(x): # f(1)와 f(2)은 항상 1이기 때문에 f(1)이나 f(2)를 만났을 때는 호출을 정지 if x == 1 or x == 2: return 1 return fibo(x-1) + fibo(x-2)-
하지만 피보나치 수열의 소스코드를 이렇게 작성하면 f(n) 함수에서 n이 커지면 커질수록 수행 시간이 기하급수적으로 늘어나기 때문에 심각한 문제가 생길 수 있음
-
이 소스코드의 시간복잡도는 세타 표기법을 사용하여 으로 표현할 수 있음
-
하지만 일반적으로는 빅오 표기법을 이용하여 의 지수 시간이 소요된다고 표현함
-
만약 다음과 같이 f(6)인 경우를 계산한다고 하면, 동일한 함수가 반복적으로 호출이 되는 것을 알 수 있음
-
즉, f(n)이 커지면 커질수록 반복해서 호출하는 경우의 수가 많아짐
-
이처럼 피보나치 수열의 점화식을 재귀 함수를 사용해 만들 수는 있지만, 단순히 매번 계산하도록 하면 문제를 효율적으로 해결할 수는 없음
-
이러한 문제는 다이나믹 프로그래밍을 사용하면 효율적으로 해결할 수 있음
-
다이나믹 프로그래밍은 다음 조건을 만족할 때 사용할 수 있음
- 큰 문제를 작은 문제로 나눌 수 있다.
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
-
다이나믹 프로그래밍을 재귀적으로 수행하다가 같은 정보가 필요할 때는 이미 구한 정답을 그대로 리스트에서 가져오면 됨.
✏️ 8-2.py 피보나치 수열 소스코드(재귀적)# 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 리스트 초기화 d = [0] * 100 # 피보나치 함수(Fibonacci Function)를 재귀함수로 구현(탑다운 다이나믹 프로그래밍) 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)) -
파이썬 프로그램을 실행해보면 99번째 피보나치 수를 구하도록 했음에도 불구하고 금방 정답을 도출하는 것을 알 수 있음
-
f(6) 해 법을 다시 메모이제이션 기법을 이용하여 그려보면 6번째 피보나치 수를 호출할 때는 다음 그림처 럼 색칠된 노드만 방문하게 됨
-
물론 재귀 함수를 사용하면 컴퓨터 시스템에서는 함수를 다시 호출했을 때 메모리 상에 적재되는 일련의 과정을 따라야 하므로 오버헤드가 발생할 수 있음
-
따라서 재귀 함수 대신에 반복문을 사용하여 오버헤드를 줄일 수 있음
-
다이나믹 프로그래밍을 적용했을 때의 피보나치 수열 알고리즘의 시간 복잡도는 임
- 한 번 구한 결과는 다시 구해지지 않음
- 따라서 실제로 호출되는 함수에 대해서만 확인해보면 다음과 같이 방문함
✏️ 8-3.py 호출되는 함수 확인
d = [0] * 100 def pibo(x): print('f(' + str(x) + ')', end = ' ') if x == 1 or x == 2: return 1 if d[x] != 0: return d[x] d[x] = pibo(x - 1) + pibo(x - 2) return d[x] pibo(6)f(6) f(5) f(4) f(3) f(2) f(1) f(2) f(3) f(4)- 이처럼 재귀 함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법을, 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 탑다운(Top-Down) 방식이라고 말함
- 반면에 단순히 반복문을 이용하여 소스코드를 작성하는 경우 작은 문제부터 차근차근 답을 도축한다고 하여 보텀업(Bottom-Up) 방식이라고 말함
- 피보나치 수열 문제를 아래에서 위로 올라가는 보텀업 방식으로 풀면 다음과 같음
✏️ 8-4.py 피보나치 수열 소스코드(반복적)
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화 d = [0] * 100 # 첫 번째 피보나치 수와 두 번째 피보나치 수는 1 d[1] = 1 d[2] = 1 n = 99 # 피보나치 함수(Fibonacci Function) 반복문으로 구현(보텀업 다이나믹 프로그래밍) for i in range(3, n + 1): d[i] = d[i-1] + d[i-2] print(d[n]) - 피보나치 수열이란 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열임
-
코딩 테스트에서의 다이나믹 프로그래밍 문제는 대체로 간단한 형태로 출제되므로, 이 책에서 다루는 문제 정도만 바르게 습득해도 코딩 테스트에서 다이나믹 프로그래밍 문제를 풀기에는 어려움이 없을 것임
-
문제를 푸는 첫 번째 단계는 주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것
- 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸리면 다이나믹 프로그래밍을 적용할 수 있는지 해결하고자 하는 부분 문제들의 중복 여부를 확인해보기
-
가능하다면 재귀 함수를 이용하는 탑다운 방식보다는 보텀업 방식으로 구현하는 것을 권장함
- 시스템상 재귀 함수의 스택 크기가 한정되어 있을 수 있기 때문임
