동적 계획법(Dynamic Programming)
동적 계획법(DP)
ㆍ입력 크기가 작은 부분 문제들을 해결한 후 해당 부분 문제의 해를 활용해서 보다 큰 크기의 부분 문제를 해결, 최종적으로 전체 문제를 해결하는 알고리즘이다.
ㆍ상향식 접근방법으로 가장 최하위 해답을 구한 후, 이를 저장하고 해당 결과값을 이용해서 상위 문제를 해결한다.
ㆍ 메모이제이션(Memoization)기법을 사용한다.
메모이제이션: 프로그램 실행 시 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 하여 실행 속도를 빠르게 하는 것
ㆍ 문제를 나눌 때 부분 문제는 중복되어 재활용된다.
대표적인 DP) 피보나치수열
분할 정복(Divide and Conquer)
분할 정복(DAC)
ㆍ 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘
ㆍ 하양식 접근방법으로 상위의 해답을 얻기 위해, 아래로 내려가면서 하위의 해답을 구하는 방식이며 일반적으로 재귀 함수를 사용
대표적인 분할 정복) Quick Sort, Merge Sort
공통점 및 차이점
공통점 | 차이점 | |
동적 계획법 | 문제를 더 이상 나눌 수 없을 때까지 분할한다. |
부분 문제는 중복되어 상위 문제 해결 시 사용 메모이제이션(Memoization)기법 사용 |
분할 정복 |
부분 문제는 중복되지 않음 메모이제이션(Memoization)기법 사용 X |
'자료구조 알고리즘 > 이론' 카테고리의 다른 글
[자료구조] Tree 이론 (0) | 2020.01.15 |
---|