목록알고리즘 (1)

Beeeam

다이나믹 프로그래밍

다이나믹 프로그래밍(DP) 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 알고리즘이다. 중복되는 계산을 줄이기 위해서 앞에서 계산한 값을 자료구조에 저장을 하는데 이러한 점 때문에 “기억하며 풀기”라고 불리기도 한다. 그럼 DP를 왜 쓸까? DP는 재귀 함수와 많이 유사한데 재귀 함수를 사용하게 되면 위에서 언급한 것처럼 중복되는 계산이 생긴다. 피보나치 수를 예로 들자면 fibonacci(5)를 구하는 것은 재귀 함수로 해도 문제가 없다. 계산 횟수가 그렇게 많지 않기 때문이다. 하지만 fibonacci(100)을 재귀 함수로 계산하면 어떻게 될까? 많은 시간이 걸린다. 그래서 앞에서 계산했던 값들을 다른 자료구조에 저장을 해놓고 연산할 때 이..
Algorithm 2023. 2. 20. 23:26
이전 Prev 1 Next 다음