목록2024/05/22 (1)
개발하는 리프터 꽃게맨입니다.
(공사중) 동적 계획법, 다이나믹 프로그래밍 (공사중)
1. 개요동적 계획법 (Dynamic Programming, 이하 DP)는 메모리를 적절히 사용하여 알고리즘의 수행 시간 효율성을 비약적으로 향상시키는 방법입니다. 이미 계산된 결과를 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 하는 것이죠. 예를 들어서 '피보나치 수열' 의 예시를 봅시다. 피보나치 수열은 위와 같은 점화식으로 나타낼 수 있으며이를 가장 간단하게 구현하는 방법은 재귀를 사용하는 겁니다. 이런 식으로 말이죠. 그런데 잘 살펴보면 피보나치 수열을 재귀로 구현하면 상당히 비효율적인 코드 진행을 보입니다. 피보나치 수열 알고리즘을 재귀 함수로 표현한 경우를 상태 트리로 나타내면 위와 같습니다. 이 상태 트리를 보면 알 수 있듯이미 계산된 값을 또 계산하고 있는 것을 볼 수 있습니다...
스터디 자료
2024. 5. 22. 00:58