목록DP (1)

코딩왕랄프👊🏻

[알고리즘] 다이나믹 프로그래밍 DP

다이나믹 프로그래밍 기억하기 프로그래밍 이라고 생각하면 쉽다. 큰 문제를 작은 문제로 나누어 푸는 문제. 분할 정복과 비슷하지 않나? -> 비슷하지만 차이가 하나 있는데, 그것은 "작은 문제가 중복이 일어나는지 안일어나는지" 이다. 분할정복 : 큰 문제를 해결하는게 어려워 단지 작은 문제로 나누어 푸는 방법. DP : 작은 문제들이 반복되는 것 (답이 바뀌지 않음) 을 이용해 풀어 나가는 방법 푸는 방법? 모든 작은 문제들은 한번만 풀어야 한다. 그래서 정답을 구한 작은 문제를 어디엔가 메모 해 놓는다. (Memoization) 그래서 보다 큰 문제를 풀어나갈 때 앞서 똑같은 작은 문제가 나타날 때 메모한 작은 문제의 결과값을 이용 사용 조건? 1. 작은 문제가 반복이 일어나는 경우 2. 같은 무제는 구..
알고리즘 2022. 4. 13. 16:57
이전 Prev 1 Next 다음