다이나믹 프로그래밍1 동적 계획법(다이나믹 프로그래밍, DynamicProgramming), 다른 알고리즘들과의 비교 재귀함수와 비교해 함께 공부하면 좋다. 동적 계획법의 정의 큰 문제를 작은 문제로 나누어 푸는 문제를 말한다. → 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘 동적 계획법 사용 조건 DP는 항상 사용할 수 없기에 아래 사용 조건을 만족할 때 사용한다. 1. 큰 문제를 작은 문제로 나눌 수 있고, 작은 문제의 답을 모아 큰 문제를 해결 할 수 있다. → 최적 부분 구조(Optimal substructure) 2. 동일한 작은 문제를 반복적으로 해결한다. → 중복되는 부분 문제(Overlapping subproblem) Memoization 기법 이전에 풀었던 문제의 정답이나 결과 값을 저장하여, 이후의 문제를 풀 때 다시 계산하지 않고, 미리 계산된 값을 불러와서 문제를 해결하는 방법이다. →.. 2023. 4. 11. 이전 1 다음
