알고리즘 4주차 - Dynamic Programming

Dynamic Programming(동적 계획법)

피보나치 수열 - DP를 공부하기 전 몸풀기

📖

수학에서, 피보나치 수(영어: Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 처음 여섯 항은 각각 1, 1, 2, 3, 5, 8이다. [위키백과]

Fibo(4) = Fibo(3) + Fibo(2) = 2 + 1 = 3 Fibo(5) = Fibo(4) + Fibo(3) = 3 + 2 = 5 Fibo(6) = Fibo(5) + Fibo(4) = 5 + 3 = 8 .....

Fibo(n) = Fibo(n - 1) + Fibo(n-2)

비슷한 구조가 반복되니 재귀 로 문제를 풀 수 있을 것이다.

# 코드 스니펫
input = 20


def fibo_recursion(n):
    # 구현해보세요!
    return


print(fibo_recursion(input))  # 6765

input = 20


def fibo_recursion(n):
    if n == 1 or n == 2:
        return 1
    return fibo_recursion(n - 1) + fibo_recursion(n - 2)


print(fibo_recursion(input))  # 6765

여기서 input을 100으로만 해도 실행시간이 매우 오래 걸린다.... 즉 비효율적인 구조가 되는 것이다.

1. Fibo(3) 을 구한다고 치면,
Fibo(2) 와 Fibo(1) 을 더하면 됩니다.
이는 1, 1 이기 때문에 빠르게 반환됩니다.
-> 연산량 2번

2. Fibo(4) 를 구한다고 치면,
Fibo(3) 과 Fibo(2) 을 더하면 됩니다.
Fibo(3) 은? 1의 과정을 반복해야 합니다.
Fibo(2) 는 1이므로 빠르게 반환됩니다.
-> Fibo(3) 을 구하고 1 을 더합니다.
-> Fibo(3) 을 구하기 위해서는
	-> Fibo(2) 와 Fibo(1) 을 더하면 됩니다.
	-> 이는 1, 1 이기 때문에 빠르게 반환됩니다.
	-> 연산량 2번
-> 1.의 연산량 + 연산량 1번 = 연산량 3번

3. Fibo(5) 를 구한다고 치면,
Fibo(4) 과 Fibo(3) 을 더하면 됩니다.
Fibo(4) 은? 2.의 과정을 반복해야 합니다.
Fibo(3) 은? 1.의 과정을 반복해야 합니다.
-> Fibo(4) 을 구하고 Fibo(3)을 구합니다.
	-> Fibo(4) 을 구하기 위해서는              # Fibo(4) 를 구하기 위해서 Fibo(3)을 찾고
		-> Fibo(3) 을 구하고 1을 더해야 합니다.
		-> Fibo(3) 을 구하기 위해서는
			-> Fibo(2) 와 Fibo(1) 을 더하면 됩니다.
			-> 이는 1, 1 이기 때문에 빠르게 반환됩니다.
			-> 연산량 2번
	-> Fibo(3) 을 구하기 위해서는              # Fibo(5)를 구하기 위해 Fibo(3)을 찾습니다.
		-> Fibo(2) 와 Fibo(1)을 더하면 됩니다.
		-> Fibo(2) 와 Fibo(1) 을 더하면 됩니다.
		-> 이는 1, 1 이기 때문에 빠르게 반환됩니다.
		-> 연산량 2번
-> 2.의 연산량 + 1.의 연산량 = 연산량 5번

#출처: 스파르타코딩클럽

그 이유는 반복되는 구조의 계산이 진행되기 때문인데 이때 동적 계획법 이라는 개념을 통해 해결할 수 있다.

우리가 했던 걸 기억하기 위한 작업을 해주면 된다.

Dynamic Programming(동적 계획법)이란?

동적 계획법(Dynamic Programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. [위키백과]

즉 여러개의 하위 문제를 풀고 그 결과를 기록하고 이용해 문제를 해결하는 알고리즘이다.

F(string) = F(string[1:n-2]) 라고 수식을 정의했던 것 처럼, 문제를 쪼개서 정의할 수 있으면 동적 계획법을 쓸 수 있다.

문제를 반복해서 해결하는 점이 재귀 방법론과 비슷하지만 그 결과를 기록하고 이용한다 는 점에서 다르다.

결과를 기록하는 것 - 메모이제이션(Memoization)

문제를 쪼갤 수 있는 구조 - 겹치는 부분 문제(Overlapping Subproblem)

피보나치 수열 - Dynamic Programming을 활용

구현의 방법은 다음과 같습니다.
1. 메모용 데이터를 만든다. 처음 값인 Fibo(1), Fibo(2) 는 각각 1씩 넣어서 저장해둔다.
2. Fibo(n) 을 구할 때 만약 메모에 그 값이 있다면 바로 반환한다.
3. Fibo(n) 을 처음 구했다면 메모에 그 값을 기록한다.

# 코드 스니펫
input = 50

# memo 라는 변수에 Fibo(1)과 Fibo(2) 값을 저장해놨습니다!
memo = {
    1: 1,
    2: 1
}


def fibo_dynamic_programming(n, fibo_memo):
    # 구현해보세요!
    return


print(fibo_dynamic_programming(input, memo))

input = 100

# memo 라는 변수에 Fibo(1)과 Fibo(2) 값을 저장해놨습니다!
memo = {
    1: 1,
    2: 1
}


def fibo_dynamic_programming(n, fibo_memo):
    if n in fibo_memo:
        return fibo_memo[n]
    nth_fibo = fibo_dynamic_programming(n - 1, fibo_memo) + fibo_dynamic_programming(n - 2, fibo_memo)
    fibo_memo[n] = nth_fibo
    return nth_fibo


print(fibo_dynamic_programming(input, memo))

#