이해

[알고리즘] 다이나믹 프로그래밍 (DP) 이해하기

다이나믹 프로그래밍(동적계획법)이란? - 큰 문제를 풀기 위해서 작은 문제를 풀어 나가는 방식이며, 작은 문제에서 반복이 없다는 것이 특징입니다. -> 분할 정복 기법과 다른 결정적인 차이 또한 하나의 문제를 단 한 번만 푸는 알고리즘 다이나믹 프로그래밍 조건 1. 큰 문제를 작은 문제로 나눌 수 있다. 2. 작은문제에서 구한 정답은 이것을 포함한 큰 문제에서도 동일한 정답이다. 이러한 조건때문에 시간 복잡도를 훨씬 줄일 수 있습니다!!! 어떻게 구현할까요?? 메모이제이션(Memoization) 기법 활용 말 그대로 메모하는 기법입니다. 작은 문제 계산된 결과값을 배열을 사용해서 저장하고, 나중에 큰 문제에서 동일한 계산을 요구할 때 배열의 저장된 값을 불러오는 것입니다. -> dp 리스트 초기화해서 안..