[이코테] 다이나믹 알고리즘-피보나치 수열

다이나믹 알고리즘

= 동적 계획법(프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법)

• 한번 해결된 부분 문제의 정답을 메모리에 기록해 다시 계산하지 않도록 하는 문제 해결기법. 점화식(인접한 항들 사이의 관계식)을 코드로 옮겨서 구현한다!
• 메모리를 적절히 사용해 수행 시간 효율성을 비약적으로 향상시키는 방법으로 이미 계산된 결과는 별도의 메모리 영역에 저장해 다시 계산하지 않도록 한다.

구현방법

1. 탑다운 : 재귀함수를 이용해 큰 문제를 해결하기 위해 작은 문제 호출
2. 보텀업 : 반복문을 이용해 작은 문제를 먼저 해결하고 해결된 작은 문제를 모아 큰 문제 해결

필요 조건

1. 최적 부분 구조
   큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.
2. 중복되는 부분 문제
   동일한 작은 문제를 반복적으로 해결해야한다.

ex) 피보나치 수열 - 점화식 : 인접한 항의 사이의 관계식을 의미한다.

피보나치 수열은 4번째 수를 알기위해 2,3번째를 알아야하고 (조건 1 해당) 2를 두번 부른다(조건 2)

def fibo(x):
	if x==1 or x==2: #피보나치 수열은 2번째까지 숫자가 1이기에 1로 내보냄
		return 1
	return fibo(x-1)+fibo(x-2)
print(fibo(4))

재귀함수로 구현하면 지수시간 복잡도를 갖는다. 그럼 n이 클 때 여러번 호출됨
그래서 보텀업 방식 사용!

보텀업(상향식)

먼저 계산했던 값 활용해서 다시 씀 , 반복문 쓴다.

결과 저장용 리스트는 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])

탑다운(메모이제이션, 하향식)

한 번 계산한 결과를 메모리 공간에 메모하는 기법.

• 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다.
• 값을 기록해 놓는다는 점에서 캐싱이라고도 한다.
• 구현과정에서 재귀함수를 사용, 큰문제 해결하기 위해 작은 문제를 꺼냄
• 다이나믹 프로그래밍을 적용했을 때 피보나치 수열 알고리즘의 시간복잡도는 O(N)이 된다.

재귀함수를 이용한 코드

• 오버헤드가 발생할 수 있어 재귀함수 대신 반복문을 사용하면 성능이 더 좋다.

# 한 번 계산된 결과를 메모이제이션(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))

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

둘다 최적 부분 구조를 가질 때 사용할 수 있다. (큰 문제를 작은 문제로 나눌 수 있음)

차이점은 ‘부분 문제의 중복’(예시 - 퀵정렬 : 한번 자리변경하면 그 원소 위치 안바뀜)

• 다이나믹 프로그래밍 문제에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복
• 분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산 x