알고리즘, 자료구조/알고리즘 개념11 8. 동적계획법(DP) 동적 계획법은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다. 여기서 어떤 부분 문제는 같은 문제를 두 번 이상 풀 수도 있기 때문에, 이 문제에서 답을 여러 번 계산하는 대신 한번만 계산 하고 계산 결과를 저장해 놓고 재사용한다. 따라서 속도의 향상을 꾀할 수 있다. 중복되는 부분 문제 cache - 이미 계산한 값을 저쟁해 두는 메모리 장소 overlapping subproblems - 중복 되는 부분 문제 ex) 대표적인 문제 - 이항계수 조합 nCr, \( \begin{pmatrix} n \\ r \end{pmatrix} \)은 다음과 같은 성질이 있다. 메모이제이션 memoization - 한 번 계산한 값을 저장해 두었다가 재활용하는 최적화 기법 위와 같은 이항계수 문제를 일반적인 재귀함.. 2019. 7. 14. 728x90 이전 1 2 다음
