동적계획법 알고리즘 (1) 썸네일형 리스트형 [알고리즘] DP 동적계획법 ✅ 동적계획법(DP) 1. 동적계획법이란? - 하나의 큰 문제를 여러 개의 작은 문제로 분할하여 푸는 방법 - 이미 계산된 작은 문제의 결과 값을 별도의 메모리 영역에 저장해두고 활용함. - 메모리를 적절하게 사용하여 수행시간 효율성을 비약적으로 향상시킬 수 있음. 답을 재활용하는 것! "어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는" 방식의 알고리즘 2. 동적계획법 사용 조건 1) 큰 문제를 작은 문제로 나눌 수 있음. 2) 작은 문제에서 구한 값이 그것을 포함하는 큰 문제에서도 동일한 값으로 사용됨 (피보나치 수열) ✅ 분할정복법 VS 동적계획법 공통점 큰 문제를 쪼개서 가장 작은 단위로 분할한다. 차이점 - 분할정복법 : 부분 문제는 서로 중복되지.. 이전 1 다음
