목록TopDown (1)

코딩뚠뚠

[개념정리] DP 동적프로그래밍

Dynamic Programing, DP, 동적프로그래밍, 동적계획법 으로 중요한 알고리즘 중 하나이다. DP란 큰 문제를 작은 문제로 나눠서 푸는 알고리즘이다. 방식은 분할정복과 같으나 분할정복은 계산한 부분문제를 단 한번만 쓰고 더이상 사용하지않는다. 그러나 동적프로그래밍에서는 계산한부분을 남겨놓고 계속해서 필요할때 끌어다 쓴다. 동작방식 1. 구하고자 하는 큰 문제를 작은 문제들로 나눈다. (점화식을 세운다.) 2. 가장 작은 부분문제를 푼 뒤 값을 저장한다. = 메모이제이션 3. 메모이제이션 된 문제들의 값을 이용해 점차 더 큰 문제들의 답을 구한다. 4. 가장 큰 문제를 풀이할때까지 반복한다. ☆무엇을 어떻게 저장할지 정하는게 중요하다. 적용방법 1. Botton-Up 방식 : 반복문을 이용 e..
알고리즘 문제풀이/개념정리 2020. 12. 27. 13:27
이전 Prev 1 Next 다음