@동적계획법이란?
다이나믹 프로그래밍(Dynamic Programming), 즉 동적 계획법은 문제를 풀기 위한 한 방법으로 큰 문제를 여러 개의 작은 문제로 나눈 다음 그 결과를 저장해둔 다음 이를 큰 문제 해결에 이용하는 것이다. 이 방법의 가장 큰 장점은 쓸데없는 반복을 없애 실행시간을 확실하게 단축 시킨다는 점이다.
좀 더 구체적으로 설명하자면,
1.전체 문제를 작은 문제로 단순화한다.
2.점화식을 만든다.
3.만든 점화식을 재귀적으로 이용해서 해결한다.
쉽게 생각하면 우리가 프로그램을 짤 때 여러번 쓰일 기능을 편하게 쓰기위해 함수화 시켜놓는 방법과 비슷하다고 볼 수 있다. 함수화 시킴으로 다시 만들지 않아도 되며 이를 통해 많은 시간 단축이 가능하다.
@피보나치 수열?
왜 DP를 사용하는 것인지 보려면 피보나치 수열의 예시를 보면 된다.
피보나치 수를 구하고 싶을 때는 재귀로 함수를 구성하면 된다.
식으로 나타내면 f(n) = f(n-1) + f(n-2)이다.
이 때 DP를 사용하지 않으면 f(n-1)를 구하려고 구한 값을 f(n-2)에서 또 한번 구해야하는 비효율성이 생긴다.
그림으로 보면
f(4)를 구할 때 이용했던 식들과 완전 똑같은 식들을 f(3)를 구할 때 반복한다. 만약 주어진 수가 5가 아니라 아주 큰 수가 될 경우 함수를 호출 하는 횟수는 기하급수적으로 늘어나게 될 것이다. 그렇기에 이미 구한 함수를 배열에 저장해서 필요할 때마다 꺼내 쓰는게 DP다.(O(n^2) 에서 O(f(n))로 시간복잡도가 개선된다)
@메모이제이션이란?
피보나치 수열에서 설명했듯이 구한 함수를 배열에 저장하는 행위를 메모이제이션이라고 할 수 있다. 즉 동일한 문제를 반복해야 할 때 한 번 계산된 결과를 저장해 두었다가 활용하는 것이다.
@구현 방식
Bottom-Up 방식
-아래에서 부터 계산을 수행 하고 누적시켜서 전체 큰 문제를 해결하는 방식이다.
Top-Down 방식
-위에서 부터 바로 호출을 시작해서 결과 값을 재귀를 통해 전이시켜 재활용하는 방식이다.
출처:
https://velog.io/@chelsea/1-%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming-DP
[자료구조와 알고리즘] 동적 계획법(Dynamic Programming, DP)
동적 계획법(Dynamic Programming) - 컴퓨터 공학 스터디 W1 자료구조와 알고리즘 내용에 앞서 학교에서 컴퓨터 공학 이론 스터디를 진행하고 있습니다. 매주 발표하는 내용을 시리즈로 업로드할 예정
velog.io
https://hongjw1938.tistory.com/47
알고리즘 - Dynamic Programming(동적 계획법)
1. 개요 DP, 즉 다이나믹 프로그래밍(또는 동적 계획법)은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으
hongjw1938.tistory.com
'알고리즘' 카테고리의 다른 글
| Queue offer와 add 차이 (0) | 2022.01.08 |
|---|
