중복되는 연산을 줄이자!
문제를 풀다보면 컴퓨터를 활용해도 해결하기 어려운 문제가 있다.
컴퓨터도 연산속도와 메모리에 한계가 있기 때문에 이를 고려하여 효율적인 알고리즘을 작성해야 한다. 이 중에서 연산이 굉장히 많은 경우 메모리 공간을 약간 더 사용하여서 연산 속도를 비약적으로 증가시키는 방법이 있다.
다이나믹 프로그래밍
다음 조건을 만족하여야지 사용할 수 있다.
- 큰 문제를 작은 문제로 나눌 수 있다.
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
피보나치 수열이 이러한 조건을 만족하는 대표 문제이다. 이 문제를 두가지 방식으로 나누어서 작성해보자.
피보나치 수열에서는 아래의 그림과 같이 중복되는 연산이 계속해서 나타난다.
탑다운(Top-Down) 방식
큰 문제를 해결하기 위해 작은 문제를 호출하는 방식
메모제이션기법을 사용하여 한번 구한 결과를 캐싱해두고 이후에 여기서 반복되는 연산의 결과를 꺼내서 사용한다.
# 한 번 계산된 결과를 메모제이션(Memozation)하기 위한 리스트 초기화
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))보텀업(Bottom-Up) 방식
반복문을 이용하여 작은 문제부터 차근차근 답을 도출하는 방식
DP 테이블을 이용하여 결과를 저장한다.
# 앞서 계산된 결과를 저장하기 위한 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])문제 접근법
- 당연히 먼저 주어진 문제가 다이나믹 프로그래밍 유형임을 파악해야 한다.
- 특정한 문제를 완전 탐색으로 접근했을 때 시간이 매우 오래 걸린다면 다이나믹 프로그래밍을 고려해보자. (중복되는 연산이 있는지 알아보기)
- 재귀함수로 먼저 풀어보고 메모제이션 기법을 적용하는 것도 좋은 아이디어
- 될 수 있다면 보텀업 방식으로 해결해보기 (recursion dept 오류있을수도..)
문제를 좀 풀어보다 보니깐 느꼈던 것은 문제에 접근할 때 가장 최적의 해를 구하는 그리디 방식으로 접근을 해보고 이것이 이전의 과정들에 따라 달라질 수 있다는 것을 파악한다면 즉 100을 구해야 하는데 2,3,4, ... 이렇게 이전의 최적의 해도 필요하다면 다이나믹 프로그래밍을 통해서 작은 문제부터 차근차근 최적의 해를 구해 나가는 것이 중요한 것 같다.
참고 문헌
https://freedeveloper.tistory.com/276
피보나치 이미지
이코테 다이나믹 프로그래밍 코드
