-
DP (Dynamic Programming) 동적계획법
- 개념 : 큰 문제를 작은 문제로 나누어서 푸는 문제
- 작은 문제들을 계산한 값을 여러 번 사용하기 때문에 Memoization (메모이제이션)이 필요하다.
Memoization?
컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해,
매번 다시 계산하지 않도록 하여 전체적인 실행 속도를 빠르게 하는 기술
→ 즉, 계산된 결과를 배열에 저장한 뒤, 다음 계산에서 필요하면 저장된 값을 불러옴. 시간 복잡도가 훨씬 줄어든다.
- 구현 방식 : Bottom-up 방식과 Top-down 방식
- Bottom-up 방식 : 작은 문제부터 계산해 나가는 방식, for문 이용해서 처음 값부터 다음 값을 계산해 나가는 방식
- Top-down 방식 : 큰 문제를 풀 때 작은 문제가 아직 풀리지 않았다면 그 때 푸는 방식, 일반 재귀와 같은 방식
Bottom-up Top-down 장점 함수를 호출하지 않으므로, 시간과 메모리를 소량 절약할 수 있다. 점화식 그대로 호출되기에, 소스의 가독성이 좋다. 단점 소스의 가독성이 저하된다. 작성하기에 조금 더 어렵다. 문제에 따라 자신에게 맞는 방식으로 풀면 된다.
'알고리즘' 카테고리의 다른 글
Greedy Algorithm (0) 2020.03.17 Floyd-Warshall (0) 2020.03.17 Dijkstra (0) 2020.03.17 Binary Serach (0) 2020.03.16 DFS & BFS (0) 2020.03.16