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

재귀호출

• 함수안에서 동일한 함수를 호출하는 방식
• 시간복잡도 : O(n)
• 스택 기반 방식

동적계획법, 분할 정복

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