[Algorithm Week_3] Recursion Recursion - 자기 자신을 호출하는 구조? - 알고리즘 설계 & 문제해결의 필수 Recursion의 예 1) Factorial 2) 자료구조 (LinkedList & Binary Tree) LinkedList Null은 List이다 어떤 A가 List이면, A앞에 노드.. cs-ssupport.tistory.com "Fn은 n번째 피보나치 수" ▶ 1-(b) Solution 1-(a)에서 "추상적인 문제"를 묘사했다면 여기서 "해당 문제에 대한 Algorithm | 점화식"을 설계해야 한다 DP에서 점화식없이 문제를 해결할 수가 없다 2. Build Solutions to your recurrence from the bottom up 정의한 Pr..

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를 선택"하..

Divide-and-Conquer 1. 일단 자르기 : Divide 2. 자른 subProblem들에 대한 해답은 Recursion으로 : Conquer 3. Recursion으로부터 얻어진 결과들을 종합/정리 : Combine 1) Merge Sort 가장 기본적인 "Divide and Conquer" 기법을 사용하는 정렬 알고리즘이다 static void Merge_Sort(int [] list, int left, int right){ if(left < right){ int mid = (left + right) / 2; Merge_Sort(list, left, mid); Merge_Sort(list, mid + 1, right); Merge(list, left, mid, right); } } 1. D..

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

QuickSort Unstable Sort Recursion으로 생각? 1. 배열의 원소중 "pivot" 고르기 2. pivot을 기준으로 1) pivot보다 작은 값들은 pivot의 왼쪽으로, 2) pivot보다 큰 값들은 pivot의 오른쪽으로 분류시킨다 :: Partition 3. pivot을 기준으로 분류된 두 subarray를 각각 정렬한다 "By Recursion" recurse Left recurse Right ※ MergeSort와 QuickSort의 차이점 MergeSort - 일단 Recursion을 던져놓고, "Merge"를 통해서 최종적으로 정렬 더 상세히 살펴보면, MergeSort는 array의 요소가 1개가 남을때까지 계속해서 subarray들을 반으로 나누고, 다 나누었으면 ..

MergeSort Stable Sort Recursion으로 생각? 1. 배열을 2등분 2. 2등분 한 각 subarray들을 정렬 "By Recursion" 3. 정렬된 2개의 subarray들을 "Merge" 최종 "Merge" 방식 i는 왼쪽 subarray 전용 포인터이고, j는 오른쪽 subarray 전용 포인터이다 - 여기서 i, j가 가리키는 각 값들을 비교해서 최종 정렬된 배열에 넣어준다 오름차순 배열이 default이므로, 더 작은 값을 넣어준다 1) i : 4 & j : 1 4 > 1 이므로, j가 가리키는 값인 1을 배열에 넣어주고 j는 증가시켜준다 2) i : 4 & j : 2 4 > 2 이므로, j가 가리키는 값인 2를 배열에 넣어주고 j는 증가시켜준다 3) i : 4 & j : ..

Recursion - 자기 자신을 호출하는 구조? - 알고리즘 설계 & 문제해결의 필수 Recursion의 예 1) Factorial 2) 자료구조 (LinkedList & Binary Tree) LinkedList Null은 List이다 어떤 A가 List이면, A앞에 노드를 연결한 전체도 List이다 Binary Tree 공집합은 Binary Tree이다 T1, T2가 Binary Tree이면,.... Reduction? : 줄이기 & 쪼개기 - 알고리즘을 설계할 때 가장 많이 쓰이는 기술 중 하나 'Reducing one problem "X" to another problem "Y"' - 우리가 풀고 싶은 문제는 X이다 - 이 X를 풀 때 Y의 알고리즘을 호출? - 우리는 Y가 어떤 알고리즘에 의해..

Stable Sort 정렬 방식 상당히 간단한 정렬 알고리즘이다. 그냥 인접한 두 수끼리 크기를 비교해서 왼쪽값이 오른쪽값보다 크면 서로 exchange해주면 된다 이렇게 정렬하면 매번 정렬할 때마다 최댓값은 알아서 오른쪽에 순차적으로 정렬된다 43 1 25 9 16 ▶ Round 1 43 1 25 9 16 1 43 25 9 16 1 25 43 9 16 1 25 9 43 16 1 25 9 16 43 ▶ Round 2 1 25 9 16 43 1 25 9 16 43 1 9 25 16 43 1 9 16 25 43 Java Code static void bubble_sort(int [] list, int n){ for(int i = n - 1; i >= 0; i--){ for(int j = 0; j < i; j..

Stable Sort 정렬 방식 - 두번째 값부터 차례대로 해당 값을 넣을 위치를 전체적인 배열의 자리에서 결정해준다 >> 선택한 값의 "앞에 요소들"을 살펴보고 만약 앞에 요소들 중 자신보다 큰 값이 있다?? 그러면 앞에 요소들을 차례대로 오른쪽으로 shift 해준다 9 17 1 2 12 6 ▶ Round 1 (index 1) 인덱스 0 1 2 3 4 5 요소 9 17 1 2 12 6 - "index(1) 17"앞에는 "9"라는 값이 있다 - 9는 17보다 작다 - 따라서, 여기서는 shift 해줄 필요가 없다 ▶ Round 2 (index 2) 인덱스 0 1 2 3 4 5 요소 9 17 1 2 12 6 - insert하려는 기준 값 = "index(2) : 1" - 해당 값 이전의 요소들을 알아봐야 ..

Unstable Sort 정렬 방식 - 정렬되지 않은 요소들에 대해서 일단 가장 좌측을 최솟값의 index라고 생각 9 17 1 2 12 6 ▶ Round 1 (index 0) 인덱스 0 1 2 3 4 5 요소 9 17 1 3 12 6 정렬 여부 X X X X X X - 정한 index 다음 요소들로부터 진짜 최솟값 index를 찾아내기 (계속해서 index를 update해준다) 인덱스 0 1 2 3 4 5 요소 9 17 1 3 12 6 정렬 여부 X X X X X X - 진짜 최솟값의 index는 "2"니까 index(2)의 값과 index(0)의 값을 서로 교체 인덱스 0 1 2 3 4 5 요소 1 17 9 3 12 6 정렬 여부 O X X X X X - 이러면 0번째 요소는 정렬 완료 ▶ Round..

시간복잡도 (Time Complexity) - Algorithm의 "수행시간"을 이론적으로 분석 Algorithm은 추상적인 존재 이 추상적인 Algorithm을 코드를 통해서 구체화를 한다 - 시간복잡도는 N에 관한 함수로 표현한다 N : 입력으로 주어지는 Data의 크기 - 시간복잡도의 계산방법은 "해당 코드의 기본연산의 개수"를 계산한다 기본연산 : 덧셈 / 뺄셈 / 곱셈 / 나눗셈 / 대입 / ... - 시간복잡도에는 최선/평균/최악으로 나누어지면 여기서 가장 눈여겨봐야하는 것은 "최악 시간복잡도"이다 Why? 항상 시간복잡도는 "upper bound"를 고려해야 하기 때문이다 Example) Selection Sort static void selection_A(int [] list, int n)..