[Algorithm] 동적 계획법(dynamic programming)

✨동적 계획법(dynamic programming)

복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.
재귀,메모이제이션을 이용한다.

 

✨메모이제이션(Memoization)

‘중복 계산'을 피하기 위한 기법
이전에 계산한 값을 메모리에 저장한다.

 

 

 

 

✨탑다운방식

재귀적으로 호출함
큰문제를 작은문제로 나눔

 

 

✨바텀업방식

반복문을 사용함
작은 문제로 큰문제를 해결함

 

 

 

 

 

 

 

 

 

 

예시) 백준 알고리즘 수업 - 피보나치 수 1

https://www.acmicpc.net/problem/24416

 

 

제귀함수로 작성한 피보나치

def fib(n):
    if(n<=2):
        return 1
    else:
        return (fib(n-1)+fib(n-2))

 

 

동적 계획으로 작성한 피보나치

def fibonacci(n):
    f[1]=f[2]=1
    for i in range(3,n+1,1):
        f[i]=f[i-1]+f[i-2]

 

동적 계획으로 작성한 피보나치의 경우 외부 메모리 f[]를 활용하여 재귀함수의 호출을 없애고 시간을 단축하였다.

 

 

 

 

 

 

 

 

 

 

 

🎈참고자료

https://ko.wikipedia.org/wiki/%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95

https://adjh54.tistory.com/201#1.%20%EC%B5%9C%EC%A0%81%20%EB%B6%80%EB%B6%84%20%EA%B5%AC%EC%A1%B0%20(Optimal%20Substructure)-1