다이나믹 프로그래밍 - 동적 계획법

다이나믹 프로그래밍이란? 

• 다이나믹 프로그래밍이란 큰 문제를 해결하기 위해서 큰 문제를 구성하고 있는 작은 문제들을 먼저 하나씩 해결해나가는 프로그래밍 기법입니다. 이 기법은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용합니다.

• 이 기법은 최단거리 문제, 행렬 제곱 문제 등의 최적화에 사용되곤 합니다. 왜냐면 다이나믹 프로그래밍 이라는 것이 어떤 문제의 모든 방법을 검토한 뒤에 최적을 찾아내기 때문 입니다. 이러한 방법은 매우 무식하고 단순한 방법처럼 보이기도 하지만 가능한 모든 방법을 찾는데 큰 시간이 걸리지 않는 경우에는 가장 적합한 방법이라고 할 수도 있습니다.

• 모든 방법을 찾아야 한다는 단점을 해결하기 위해 그리디 알고리즘 이라는 기법이 등장하였지만 매번 최적해를 구해주지는 않는다는 단점이 있습니다.

예제 - 피보나치 함수 

def fibo(n):

    global lst_fibo

    if n < 2:

        return 1

    else:

        if n not in lst_fibo:

            lst_fibo[n] = fibo(n-1)+fibo(n-2)

        return lst_fibo[n]

    

lst_fibo = {0:1, 1:1}

fibo(10)

print(lst_fibo)

• fibo 메소드에서 수열을 계산할 때마다 리스트에 입력합니다. lst_fibo 리스트가 없었다면 매번 그 수보다 작은 경우들을 새로 계산했어야 하지만 이전에 계산한 것들은 이미 리스트에 저장해 놓았기 때문에 더 적은 과정을 통해 계산하는 것을 알 수 있습니다. 

• 동적프로그래밍을 적용한 것이 위의 결과이고 적용하지 않은 것이 아래의 결과 입니다. dict 위의 숫자들이 fibo 를 통해 호출된 n 값들을 나열한 것인데, 위의 결과는 19회 밑의 결과는 177회 호출된 것을 알 수 있습니다.

---

부족한 블로그에 방문해 주셔서 감사합니다.

잘못된 부분이나 질문이 있으시면 

댓글로 말씀해주세요.

금방 확인하고 피드백 드리겠습니다.

좋은 하루 되세요. ^^