300x250 동적계획법1 [알고리즘] 동적계획법(DP), 다이나믹 프로그래밍 개념정리 다이나믹 프로그래밍이란 하나의 문제를 단 한번만 풀도록 하는 알고리즘이다. DP 동적계획법이라고 한다. 하나의 문제를 딱 한번만 풀어 비효율적인 알고리즘을 개선시키는 방법이다. 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문에제에도 동일하다. 크고 어려운 문제가 있을면 그것을 먼저 잘게 나누어서 해결한 뒤에 처리하여 나중에 전체의 답을 구하는 것이다. 이 과정에서 '메모이제이션(Memoization)이 사용된다. 이미 계산한 결과는 배열에 저장함으로써 나중에 동일한 계산을 해야 할 때는 저장된 값을 단순히 반환만 하면 된다. 가장 기본적인 예시로 피보나치 수열이 있다. 첫번째 코드를 보게되면 오로지 재귀함수로만 문제를 풀게되면 다음과 같은 코드가 나온다. num .. 2021. 6. 22. 이전 1 다음 반응형
