프로그래밍/알고리즘
-
[01] 동적 프로그래밍과 분할정복프로그래밍/알고리즘 2021. 7. 18. 15:53
01_정의 동적프로그래밍(Dynamic Programming) - 동적 계획법, DP 라고도 불리는 알고리즘 - 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 답을 활용하여, 보다 큰 크기의 부분 문제들을 해결한다. - 위의 프로세스를 통해 최종적으로는 전체 문제를 해결하는 알고리즘이다. - 상향식 접근법 : 가장 최하위 해답을 구한 후, 이를 저장하고 해당 결과값을 이용해 상위 문제를 풀어가는 방식 - Memoization 기법을 활용 : Memoization(메모이제이션)이란 프로그램 실행 시 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 하여 전체 실행속도를 빠르게 하는 기술 - 예시) 피보나치 수열 ...(문제를 잘게 쪼개고, 부분 문제는 중복되어 재활용됨) 분할정복 - 문제..