Was ist Dynamic Programming?

하나의 문제는 단 한 번만 풀도록 하는 알고리즘

일반적인 분할 정복 기법은 동일한 문제를 다시 푼다는 단점이 있음

ex) 피보나치 수열 : 특정한 숫자를 구하기 위해 그 앞에 있는 수자와 두 칸 앞에 있는 숫자의 합을 구해야 함

D[i] = D[i-1] + D[i-2]
-> 동일한 문제를 반복해서 계산하게 됨

하지만 정렬의 경우, 분할 정복 기법 사용 시 동일한 문제를 다시 푼다는 단점이 없음

DP의 기본적인 가정

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
   크고 어려운 문제가 있으면 그것을 먼저 잘게 나누어서 해결한 뒤, 나중에 전체의 답을 구하는 것!

즉, DP는 메모이제이션을 사용한다!
이미 계산한 결과를 따로 저장해 둬서, 나중에 동일한 계산을 할 때 저장된 값을 반환하기만 함!!

피보나치 수열 onhe DP

def fibo(n) :
    if n < 2 :
        return n
    return fibo(n-1) + fibo(n-2)

피보나치 수열 mit DP

dic = {0 : 0, 1 : 1}
def fibo(n) :
    if n in dic :
        return dic[n]
    dic[n] = fibo(n-1) + fibo(n-2)
    return dic[n]

Übung

문제 - 백준, 1463번 : 1로 만들기
https://www.acmicpc.net/problem/1463

1 a = int(input())
2 lst = [0]*(a+1)
3 for i in range(2, a+1) :
4     lst[i] = lst[i - 1] + 1
5     if i % 3 == 0 :
6         lst[i] = min(lst[i], lst[i//3] + 1)
7     if i % 2 == 0 :
8         lst[i] = min(lst[i], lst[i//2] + 1)
9 print(lst[a])

1. 인풋을 받아 a 변수에 정수형으로 저장한다.
2. 메모이제이션을 할 배열을 준비한다.
3. 8번까지의 코드를 a의 값을 구할 때까지 반복한다.
4. 문제에서 세번째 연산에 해당하는 값을 배열에 저장한다.
5. i를 3으로 나눌 수 있다면 6번 줄 코드를 실행한다.
6. lst[i]와 lst[i//3] + 1을 비교하여 더 작은 값을 lst[i]에 저장한다.
7. i를 2으로 나눌 수 있다면 8번 줄 코드를 실행한다.
8. lst[i]와 lst[i//2] + 1을 비교하여 더 작은 값을 lst[i]에 저장한다.
9. 결과를 출력한다.

사실 처음엔 피보나치 수열과 같이 재귀함수를 사용해 풀어 보았다. 무수한 런타임 에러와 메모리 초과의 환영을 받고 황급히 반복문으로 바꾸었다. 과거 자료구조 수업을 들을 당시, 재귀함수는 반복문에 비해서 효율적이지 못하다는 사실을 들었지만, 코딩이 쉽다는 이유로 재귀함수를 애용 해온게 패착이었다. 앞으로 가급적이면 반복문을 활용하도록 하자!