분할정복

재귀호출, 동적계획법, 분할 정복

재귀호출 함수안에서 동일한 함수를 호출하는 방식 시간복잡도 : O(n) 스택 기반 방식 동적계획법, 분할 정복 DP : 입력 크기가 작은 부분 문제들을 해결후 memoization 기법을 사용해 보다 큰 크기의 문제를 해결, 상향식 분할 정복 : 문제를 나눌 수 없을 때 까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘, 하향식 공통점 : 문제를 잘게 쪼갬 차이점 : 동적 : 상위 문제 해결시 재활용, 부분 문제 중복 분할 : 부분 문제를 서로 중복되지 않음 재귀호출은 계속 계산하지만 DP는 이전 계산한 값을 저장하기 때문에 계속 쓸 수 있다. 시간복잡도 비교적 나아진다. 대신 공간 복잡도는 희생된다