다이나믹 프로그래밍(Dynamic Programing)

Dp의 역사

수학자인 리처드 벨만이 1940년대에 사용하던 용어였다. 1953년, 벨만은 큰 문제 안에 작은 문제가 중첩되어있는 문제를 해결하는 데 사용하는 이 방법을 '동적 계획법'이라 이름붙였다.(wiki)

예제

피보나치 수열

그림은 적성에 안맞는 모양이다.. 5를 구하기 위해서 4가 1번, 3이 2번, 2가 3번 호출된다. 만약 숫자가 더 커진다면 기하급수적으로 연산량이 늘어 날 것이다.

DP의 조건

1.최적 부분 구조
=> 큰 문제를 작은 문제로 나눌수 있고 작은 문제들을 모아 해결 가능
피보나치 5를 구하기 위해서는 3과 4를 구해야 함
2.중복되는 부분 구조
=>동일한 작은 문제를 반복적으로 해결
fivo(5)을 구하기 위해서는 fivo(3)이 2번을 호출해야하고 fivo(2)연산도 3번(그리다 말았..)호출해야하고

탑다운 vs 바텀업

1.탑다운(하향식):

재귀함수 활용, 반복되는 함수의 연산을 막기 위해 메모라이제이션 활용
장점: 다소 간단한 구현
=>배열에 계산한 값을 저장하면서 만약에 계산했다면 계산한 값을 호출
만약 f(3)을 계산 햇다면 리스트에 f(3)값을 저장한뒤 호출될 때 마다 계산하지 않고 반환한다면 반복되는 연산을 하지 않아도 된다.

2.바텀업(상향식):

반복문 활용,
장점: 재귀를 사용하지 않으면서 얻는 메모리적 이득
=>1부터 n까지 순차적으로 계산

참고:이것이 코딩 테스트다. 위키백과