다이나믹 프로그래밍1 Advanced Algorithm - 동적 계획법(DP) & 분할정복(Divide&Conquer) 1. 정의 1) 동적 계획법(Dynamic Programming, DP) - 정의: 하나의 큰 문제를 해결하기 위해, 큰 문제를 작은 문제들로 나누어 부분적으로 해결한 후 그로부터 파생된 값인 해를 이용하여 최종적으로 전체 문제를 해결하는 방식의 알고리즘 - 상향식 접근법: 가장 최하위 문제의 해답을 구한 후, 이를 이용하여 상위 문제를 풀어나가는 방식 - 메모이제이션(Memoization) 기법: 프로그램 실행 시 이전에 계산한 값을 저장하여 동일한 연산/계산에 대해서 다시 수행하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술 - 왜 이런 기법들을 사용하는가? → 큰 문제를 작게 쪼개어 풀다보면 중복되는 부분이 발생한다. 동일한 연산에 대해서는 1번의 연산을 수행하여 저장하는 방식을 통해 이를 재활.. 2020. 9. 15. 이전 1 다음
