Dynamic programming 동적 계획법

엄청 예전에 프로그래밍 수업을 들을때 피보나치 수열 값 표시하면서 분명히 들어본거 같은데, 그 당시만해도 딱히 프로그래밍에 관심이 없어서 당시에는 아 이런게 있구나하고 넘어갔지만, 이제서야 동적계획의 Dynamic programming의 중요성을 새삼 느꼈습니다.

 

아래 코드를 보시면,

A = int(input())

def fibo(x):
    if x==1:
        return 1
    if x==2:
        return 1
    return fibo(x-1)+fibo(x-2)

print(fibo(A))

피보나치 수열의 수를 나타내는 코드입니다.

 

그런데 이 같은 경우에는 특정 수를 구하기 위해서 그전의 수를 모두 다 찾아야합니다.

예를 들어서 4를 찾고 싶으면 모든 수를 다 계산해서 2와 3을 더해야하고

 

 

5를 찾고 싶다면 아래 빨간색 칸의 수를 모두 계산 해야합니다.

하지만 Dynamic programming 을 활용하면 이미 왼쪽에서 2와 3을 구한 경우에는 오른쪽에서 3을 다시 계산하지 않아도 된다. 

아래 코드를 보시면 배열 val을 생성하여 범위가 증가할때마다 계속적으로 val.append를 이용하여 그 이전 두개의 합을 계속해서 더해가는 것을 보실수 있습니다. 즉 피보나치 수열의 5번째 숫자를 계산할때, 위 그림에 오른쪽 구역에 있는 3을 다시 더할경우에 3의 값이 배열에 있으므로 다시 1과 2를 더할 필요가 없는것이죠.

A = int(input())

val = [0, 1]

def fibo(x):
    if x==1:
        return 1
    if x==2:
        return 1
    for i in range(2, x+1):
        val.append(val[i-1] + val[i-2])
    return val[x]

print(fibo(A))

백준문제 1463번을 풀다가 동적 계획법의 중요성을 깨닫게 되었는데요. 조만간 백준 1463번 풀이와 함께 돌아오겠습니다.   :D