Backtracking 뜻 그대로 "가다가 막히면 왔던 길 다시 되돌아가기"이다 "Tries to construct a solution incrementally by a sequence of correct of best decisions" 단계를 하나하나씩 늘려가면서(incrementally) 우리가 원하는 결과에 대한 sequence를 생성해낸다 하지만 이 때 끝에 도달했는데 결과가 나오지않는다면 다시 "Backtracking"한다 어떠한 탐색이든지 root node가 존재할 것이고 이 root node로부터 Tree 형태로 탐색 범위를 확장시킬 것이다 여기서 이렇게 탐색을 이어나간다고 하자 결국 node로부터의 여러 child node가 존재하는데 "모든 갈림길을 평가 후 best node를 선택"하..

1) Max max(A[0, 1, 2, ....., n-1]) // "Base Case" if n = 1 return A[0] // 1. Divide mid T(n) = 2 X T(n/2) + c ▶ Recursion Tree 결국 "value of node"는 해당 node에서 재귀호출을 제외한 비재귀호출의 연산 수행 횟수이고, C번 호출하기 때문에 모든 노드의 value는 C가 된다 이러면 결국 max알고리즘의 수행 시간은 모든 노드의 value의 합으로 볼수있다 leaf노드를 보게되면 n/2k로 나와있고 이 값은 leaf노드이므로 1이 되어야 한다 리프노드의 개수는 2k이고, 리프노드의 개수는 leaf 노드의 비용이라고 판단할 수 있다 >> 따라서 max-알고리즘의 시간복잡도는 O(n)이라고 할 수..

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..