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)이라고 할 수..

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