[Algorithm Week_4] Divide & Conquer 개요 - Recursion Tree

Recursion? Recursion이란 동일한 문제를 Reduction을 통해서 사이즈를 줄여가는 방식이다 당연히 재귀를 멈춰줄 "Base Case"가 필요하다 Recursive Algorithms의 "Correctness"는 induction으로 증명하고, "Time Complexity"는 점화식을 통해서 구한다 Divide & Conquer? Divide & Conquer이란 Recursion을 사용하는 알고리즘 기법이다 Merge Sort Quick Sort .... Recursion은 "input Size"를 줄여가는 방식이다 여기서 단순히 줄여가는 방식은 효율이 그렇지 뛰어나지 않기 때문에 아예 "줄인다"라는 개념을 "잘라버린다"의 개념으로 바꾼 것이 Divide & Conquer이다 Recu..

2022.03.25