목록알고리즘 분류 (1)
이것저것
[개념] 다이나믹 프로그래밍 (Dynamic Programming)
다이나믹 프로그래밍(Dynamic Programming) 다이나믹 프로그래밍이라고 쓰면 좀 길어서 줄여서 DP라고도 많이 부른다. 이 글에서도 줄어서 그냥 DP라고 적겠다. DP 문제를 여러 작은 문제(subproblem)들로 나누고 작은 문제의 계산결과를 이용하여 다음 작은 문제의 결과를 찾아가는 것을 반복하여 최종 정답을 찾아가는 알고리즘이다. DP 문제를 푸는 과정은 다음과 같다. 문제의 해답을 찾기 위한 문제풀이과정을 생각한다. 문제풀이 과정 중 반복되는 연산은 결과값을 메모리에 저장하고 이를 다음 연산에 이용하도록 한다. (메모이제이션) 코드를 작성하고 해답을 찾는다. 아래글의 예시를 보면 DP가 어떤 알고리즘인지 어떻게 풀어야하는지 감을 잡기가 쉽다. https://hojun.xyz/13 [백..
스터디/Algorithm
2022. 9. 17. 21:10