Kbckbc's Blog - Bravo my life!

여기 쓴것은 제가 공부하면서 제가 저한테 느낀걸 쓴겁니다. 제대로 공부하시려면 책 혹은 google 에서 지대로 찾아서 하세용~~

• How fast can we sort??
  • sort 를 공부하기에 앞서 최고의 알고리즘이 낼 수 있는 time complexity 는 어떻게 될까? 정답은 omega(nlogn) 이다. 더 정확히 이야기 하자면 comparison sort 일 경우에 해당된다. 정말 신기하지 않나? 이런걸 어떻게 계산할 수 있지?? 하튼 나는 수학이랑은 좀 거리가 먼갑다. 이산수학 책에 아주 설명이 쉽게 나와있어서 이 부분을 집고 넘어가고자 한다. 수학 잘하시는 분들은 답 보지말고 해보세요.(실은 수학하고 큰 상관 없는듯^^) 힌트! decision tree 이용!
  • 해답은 이 그림 ㅎㅎ
    
    
    
    
    

• Divide and conquer algorithm 이란 뭔가?
  • 걍 상식적으로 어떠한 문제를 풀 때, 잘게나눈다음 공략한다.. 이정도로 알고 있었는데 이것도 정의가 나와 있군. 뭐 밑에 처럼 말해줘야 가오(?)가 살지 않겠나? 여기서 뽀인트는 recursively 하게 breaking down 한다는거~! 밑에는 wikipedia 에서 가져옴.
  • In computer science, divide and conquer (D&C) is an important algorithm design paradigm. It works by recursively breaking down a problem into two or more sub-problems of the same (or related) type, until these become simple enough to be solved directly.
  • 예를 들면 quick sort, merge sort 도 여기에 해당된다.

• 'Internal sorting' vs 'External sorting'
  • Internal sorting : main memory 에 data set 이 다 들어가는 경우 쓰는 알고리즘
  • External sorting : main memory 보다 큰 set 을 정렬할 때 쓰는 알고리즘
    

• Stable sorting
  • Sorting 이 stable 하다는 말이 심심찮게 나온다. 뭔말이냐? 같은 key 값의 순서를 바꾸지 않는다는 것이다. 예를들면 3,3,4,5 이렇게 있는게 원래 순서인데 unstable 한 sorting은 3,3,4,5 로 바꾸어 버린다. ㅎㅎ 같은 3이라서 같게 보일지 모르지만 unstable 은 동등한 자리에 있는 key 값을 바꿀수도 있다는 것이다. 좀 더 명확히 나타내면 3(a),3(b),4,5 편의상 같은 3에 a,b 를 붙여서 구분하였다. unstable 한 것은 3(b),3(a),4,5 이렇게 바뀌어 버릴 수 있다는 것이다.
    
    
• Insertion Sort
  • 알고리즘
    • 정렬된 list 에다가 item 을 적절한 위치에 insert 한다. 그래서 insert!
    • 예제
      정렬전: 31 | 25 12 22 11
      1회전 : 25 31 | 12 22 11
      2회전 : 12 25 31 | 22 11
      3회전 : 12 22 25 31 | 11
      4회전 : 11 12 22 25 31 |
  • 설명
    • | 는 어느 item 까지 정렬이 되어 있는지 표시한다.
    • 1회전 : 처음 시작에서 이미 31 | 이다. 하나는 sorting 할 필요가 없으니 두번째 부터 비교하는 거다. 처음 대상이 25인데 이것을 정렬된 list 안에 insert 하는 것이다. 그러면 31 보다 작으니 25가 앞으로 간다.
    • 3회전 : 이부분이 중요하다. 이것이 selection sort 보다 insertion 이 왜 약간 더 나은 성능을 보이는지 설명해준다. 대상 item 은 22 인데 이것을 적절한 위치에 넣고 싶다. 그래서 정렬된 부분의 item 들이랑 비교를 하면서 swap 을 하는데 12 와 비교를 하고는 자리를 바꾸지 않는다. 왜냐? 22가 더 크니까 바꿀 필요가 없다는 것이다. 만약 여기 예제가 더 큰 set 이어서 12 앞에 더 숫자가 있다고 했으면 그녀석들하고는 비교 조차 해볼 필요가 없는것이다. 오케? 여기서 이해 됐음 다행이고... 좀더 설명해보자. 밑에 time complexity 설명에서 보면 1회전에서 1번 2회전에서 2번 3 회전에서 3번 ....  이렇게 해야 하는데 지금 말한 3회전에서는 몇번 했는가? 2번밖에 swap 이 안 나왔다. 그러니까 2번하고 땡. 다음회전으로 넘어갈 수 있다. 그러나 selection sort 에서는 각 회전마다 가장 작은(즉 대상 item)을 찾기 위해 끝까지 다 비교해봐야 한다. 그렇기 때문에 selection sort 보다 성능이 약간이나마 더 좋다는 것이다.
  • 장점
    • 간단하며 작은 item 들에 대해서(10 ~ 20개사이) 성능이 좋다.
    • 다른 복잡한 알고리즘에서 부분적으로 이용된다.
    • 다른 O(n^2) 알고리즘(bubble, selection sort) 보다 더 좋은 성능을 보여 준다
    • 거의 정렬되어 있을 경우 성능이 O((k+1)n) 이 된다. k는 LOO 갯수(LOO 는 left out of order, 즉 정렬 안되어 있는 item). 이말이 뭐냐? 겁나게 빨라진다는 거. 왜냐? 거의 정렬이 되어 있다면 insertion sort 는 정렬된 list로 item 을 옮길 필요가 없어진다. 그래서 순서가 잘못되어 있는 item 만을 insert 하면 되는거다. 그렇기 때문에 만약 순서 잘못 되어 있는 item 만난다면 그 item 에 대해서 최대 n 번의 step 이 필요하다 그렇기 때문에 O((k+1)n) 이 된다. 여기서 하나더! 만약 selection sort 일 경우 생각해봐라. 정렬 되어 있다고 해서 select 를 하기 위해 list 를 다 봐야 한다. 어느게 낫냐?
  • 단점
    • O(n^2) 이기 때문에 item 이 많은 경우 성능이 느리다.
    • array 로 구현을 할 경우 정렬된 list 에 item 을 넣을 때 swap 이 많이 일어날 수 있다. (정렬된 위치안에서 자기 위치 찾아갈 때.) 많이 일어난다면 array 의 item 을 모두 한칸씩 뒤로 밀어야 하는데 이 cost 가 크다. 특히 write cost 가 클 경우가 있는데 이럴 경우는 selection sort 가 더 나은 성능을 보인다. selection sort 는 가장 작은 item(즉, 대상 item) 을 찾기만 하면 swap 한번만 하면 되기 때문이다. 그래서 array 보다는 list 구현이 더 좋은데 적절한 위치를 찾아서 연결만 하면 괜찮기 때문이다.
  • Time complexity
    • 1회전에서 1번, 2회전에서 2번, 3회전에서 3번... n회전에서 n번 swap 이 일어날 수 있다. 그러면 1 + 2 + 3 .. + n-1 + n 인데 이것은 계산해보면 O(n^2) 이라는 것을 알 수 있다.

• Selection Sort
  • 알고리즘
    • 가장 작은 것은 select 한 다음에 그것을 첫번째 item 과 swap 한다. 이 과정을 반복한다.(ascending 일 때..)
    • 예제
      정렬전: | 31 25 12 22 11
      1회전 : 11 | 25 12 22 31
      2회전 : 11 12 | 25 22 31
      3회전 : 11 12 22 | 25 31
  • 설명:
    • | 는 어느 item 까지 정렬이 되어 있는지 표시한다.
    • 1회전 : 가장 작은 걸 찾아서 첫번째랑 swap. 11 이랑 31 swap.
    • 위의 과정 반복
  • 장점
    • 이것도 마찬가지로 간단하며 작은 item 들에 대해서(10 ~ 20개사이) 성능이 좋다.
  • 단점
    • O(n^2) 이기 때문에 item 이 많은 경우 성능이 느리다.
  • Time complexity
    • 1회전에서 n번 2회전에서 n-1번 .. n-1 회전에서 1번 compare 가 생긴다. 이것 다 더해서 계산하면 O(n^2) 나온다.

• Bubble Sort
  • 알고리즘
    • 한 아이템을 그 뒤에 것이랑 비교해서 순서가 어긋나 있으면, 즉 뒤에놈이 더 작으면, swap 한다. 이 과정을 모든 item 에 대해 반복한다.(당연히 끝에 정렬된 부분을 만나면 더 하지 않아도 된다.) 한회전이 끝나면 가장 큰 item 이 젤 뒤로 가게 된다. 이 과정을 반복한다. 이것을 애니메이션처럼 생각을 해보면 한 회전이 끝날 때 마다 가장 큰 item 이 뒤에 차곡차곡 쌓이게 된다. 이게 bubble 이 올라가는 것이랑 비슷하다고 해서 bubble sort 이다.
    • 예제
      정렬전: 31 25 12 22 11
      1회전 : 25 12 22 11 31
      2회전 : 12 22 11 25 31
      3회전 : 12 11 22 25 31
      4회전 : 11 12 22 25 31
  • 설명:
    • 1회전 : 31 이 끝까지 간 것이 보일 것이다. 한번에 31이 끝으로 간 것 아니다. swap swap ... 계속해서 끝까지 간 것이다. 가장 끝부분을 주목해보면 큰 숫자가 차곡차곡 쌓이는 것을 볼 수 있다.
  • 장점
    • 알고리즘 자체가 어렵지 않다.
    • 교육용 알고리즘이라는 소리도 있음.
  • 단점
    • O(n^2) 알고리즘 중에서도 가장 성능이 나쁘다. 이게 왜그럴까? 잘 생각해보삼. 부연설명에 있는 말이 답이다.
  • Time complexity
    • O(n^2)
  • 부연설명
    • 공부를 하다보면 Insert 랑 Bubble 이랑 굉장히 흡사하다고 생각이 드는데 결정적인 차이가 뭐냐하면(이것도 selection 에서 설명한 이유랑 비슷하지만) 대상이 되는 모든 item 에 대해서 compare 를 해봐야 한다는 것이다.(swap 이 일어나든 안 나든) 여기서 오해가 될 만한 말이 대상이 되는 모든 item 들이다. 당연히 bubble 도 단계가 진행되면 가장 뒤에 정렬된 item 이 쌓인다. 이것들은 대상에 포함이 안된다는 말이다.(바보가 아닌이상) Insertion 의 가장 큰 장점은 정렬되어 있는 list 에 넣는 것이기 때문에 하다가 적절한 자리에 넣으면 더 이상 진행을 안해도 된다.

• Quick sort
  • 알고리즘
    • 기본 생각이 pivot 이라는 것을 하나 잡아서 그것보다 작은것은 왼쪽에 그것보다 큰것은 오른쪽에 둔다. 그러면 list1 - pivot - list2 이렇게 되는데 그러면 list1 list2 를 다시 quick sort 한다. recursion 하게. 여기서 pivot 이라는 것은 원래 list 안에서 임의의 숫자를 고르는 것이다.
    • 요건 좀 더 설명하께.
      • 1. n 개의 item 안에서 pivot 을 임의로 잡는다.
        2. 오름차순 방향으로 가면서 pivot 보다 큰놈을 찾는데 이것은 i 인덱스를 쓴다. 큰놈을 찾았다면 stop.
        3. 내림차순 방향으로 가면서 pivot 보다 작은놈을 찾는데 이것은 j 인덱스를 쓴다. 작은놈 찾았다면 stop.
        4. if( i<j ) { i 랑 j 랑 swap; 2번으로 진행; }
           else { 5번으로 진행 }
        5. pivot 이랑 j 가 가리키는 item 이랑 swap;
           quicksort(list1) 호출;
           quicksort(list2) 호출;
           (pivot 을 중심으로 list1 - pivot - list2 이렇게 있다고 생각한다.)
    • 예제
      • 그림보삼 ㅎㅎ
        
        
        
        
        
        
        
        
        
        
  • 장점
    • O(nlogn) 의 다른 알고리즘 보다 훨씬 빠르다. quick sort 의 inner loop 가, 즉 swap 하는 부분, efficiently implemented 되기 때문. 다음은 wikipedia 에서 긁어온 내용.'Typically, quicksort is significantly faster in practice than other \Theta(n~\log~n) algorithms, because its inner loop can be efficiently implemented on most architectures, and in most real-world data it is possible to make design choices which minimize the possibility of requiring quadratic time.'
    • merge sort, quick sort 둘다 paralleized 구현이 알고리즘이랑 잘 맞아 떨어져서 활용하기 좋다. quick sort 가 더 좋은건 merge 는 중간의 결과가 merge 가 되어야 하기 때문에 sync 하는 과정이 필요하지만 quick 은 각각의 결과가 서로 영향을 주지 않으므로 sync 없이 더 빨리 연산이 가능하다.
  • 단점
    • recursion 으로 구현할 경우 stack 용량이 커질수 있다.
  • Time complexity
    • average behavior 가 O(nlogn) 로 성능이 좋다. worst case 는 O(n^2) 이다.
    • 왜 O(nlogn) 이냐? 반씩 줄어드는 알고리즘을 생각할 때는 tree 구조를 떠올려라. quick sort 가 되는 모양을 tree 로 그려볼수가 있는데 n 개의 node 가 있을 경우 tree 의 height 는 logn 이 나온다. 즉 모든 depth 를 다 내려가는데 logn 만큼의 시간이 걸리는 것이고 각 depth 마다 걸리는 정렬 시간이 n 이므로 O(nlogn) 이다. 각 depth 마다 걸리는 시간은 왜 n 인가? same level 의 item 다 더하면 n 개이므로! 나중에 heap sort, merge sort 모두 O(nlogn) 이 걸리는데 (worst case 는 다르지만) O(nlogn) 이 걸리는 알고리즘의 동작을 이해할 때 tree 을 연관시켜 생각하면 쉽다.
    • 그러면 최악의 경우는 왜 O(n^2) 인가? 만약 거꾸로 정렬된 숫자들을 오름차순으로 정렬한다고 생각해보자. 가장 왼쪽으로 pivot을 잡고 quick sort 를 하면 pivot 보다 모두 작으므로 모두 pivot 의 왼쪽 list 에 오게 된다. 그러면 pivot 의 오른쪽에는 item 이 없기 때문에 quick sort 의 기본 바탕인 반타작이 안된다. 생각해보세용~

• Merge sort
  • 알고리즘
    • 말그대로 정렬된 list 끼리 이어 붙이기를 하는것. 머 별로 설명 필요 없고 예제 고고싱
    • 예제
      • 그림보삼
        
        
        
        
        
        
        
        
  • 장점
    • Time complexity 가 best, average, worst 모두 O(nlogn) 이다.
  • 단점
    • 추가적인 공간이 필요하다. merge sort 시행할 때 중간 결과 어디에다가 쓸래? 생각해봐라. 정렬 되어 있는 것을 merge 할때도 O(nlogn) 이다.
  • Time complexity
    • Merge sort 도 결국 n + n = 2n, 2n + 2n = 4n, ... 이런식으로 반타작한것을 붙여나가는 것이다. 위에서 설명한 Tree 구조를 생각하면 된다. Tree 의 height 를 h라 놓고 전체 item 갯수를 n 이라 하면 n = 2^h -1 이다. h로 정리하면 h = log(n+1) 이고 h 는 integer 이므로 log(n+1) 의 floor 가 item 갯수에 따른 tree height 이 된다.
    • 우리가 지금 tree 의 height 를 왜구하고 있는가? Merge sort 의 최고 depth를(즉, 회전이라고 해야 하나.. 뭔말인지 이해 하지?) 구한 것이다. 이제 하나의 depth 에 걸리는 시간을 구하면 되는데 그것은 n 이다. 그래서 두개를 곱하면 O(nlogn) 이 되는것이다. 곱하는 이유는 .... 설마..ㅎㅎ 아차차 하나의 depth 에 걸리는 시간이 n 인 것은 각 tree 의 same level 의 item 갯수가 n개를 초과할 수 없기 때문이다.

• Heap Sort
  • 알고리즘
    • 말 그대로 heap 구조를 이용해서 sort 를 하는 것이다. heap 에다가 넣어놓고 그냥 root 를 계속 뽑아내면 그게 정렬된 결과이다. 그러면 heap 은 뭐길래 root 만 뽑으면 정렬이 된다는 거야? heap 이 뭐야? heap 이 뭐냐 하면 'a heap is a specialized tree-based data structure that satisfies the heap property' 이란다. wikipedia 에서 가져온 정의인데 아주 깔끔한 정의인것 같다. 좀 덜 긁어 왔지만. Tree 인데 complete binary tree 이면서 max(혹은 min) tree 이다. complete binary tree 는 뭘까? complete binary tree 가 말로 설명하기 좀 까다로운데, binary tree 인데 node 들이 위에서 아래로, 왼쪽에서 오른쪽으로 차곡차곡 붙어있는 것을 말한다. 그리고 max(min) tree 라는 것은 어떤 node 가 항상 자식보다 크면 max tree, 작으면 min tree 이다. complete binary 랑 max(min) 를 둘다 만족하는 것이 heap data structure 이다. 그러니까 specialized 된 tree-based 맞지? 그러니까 어떤 숫자들이 있을 때 그것들이 만약 .. 정말로 운좋게 heap data structure 를 만족하면서 있다면(그럴리는 없겠지만) 그냥 root 를 item 다 뽑을 때 까지 꺼내면 된다. 그게 heap sort.
    • 이건 소스가 영 -_- . 하튼 소스는 대충 다음과 같다.
      void HeapSort() {
      for() {
      adjust;
      }
      for() {
      root node 빼네고
      adjust
      }
      }
    • adjust 라는 함수는 heap property 에 맞게 node 의 위치를 조절해주는 함수이다. heap 에서 insert, delete 써서 정렬하고자 하는 item 넣어도 되는데 adjust 라는 새로운 함수 쓰는 이유는 heap 의 insert, delete 는 O(nlogn) 만큼 걸려서 그것보다 더 나은 adjust 를 사용한다. adjust 는 O(tree height 만큼) 이 걸린다고 한다. 즉, O(nlogn) 만큼. 그래서 첫번째 for 문에서 tree 를 우선 heap property 에 맞게 해놓고 난 다음에 두번째 for 문에서 root 에 있는 node 를 item 갯수만큼 빼낸다. 빼내고 나서는 다시 adjust 를 불러주는데 root 를 빼내면 tree 구조가 깨지기 때문이어서 그렇다.
  • 장점
    • best, average, worst 가 모두 O(nlogn) 이다. 근데 merge 도 그렇다. 그러나 merge 는 추가적인 space가 O(n) 만큼 필요하고 heap sort 는 O(1) 만 있어도 된다. 그러나 O(n) 을 사용하는 merge sort 보다 살짝 느리다. O(1) 쓰는 merge 보다는 당근 더 빠름.
  • 단점
    • 일반적인 속도에서 quick sort 가 더 낫기 때문에 굳이 heap 을 선택하는 경우가 별로 없다. quick sort 가 더 나은 이유는 'due to better cache behavior and other factors' 라고 한다. cache performance 가 quick sort 가 더 좋다고 하는데 이건 이유를 좀 더 이해를 해야 겠다.
  • Time complexity
    • O(nlogn)
    • 이것 역시나 tree 구조를 이용해서 정렬하는거다. 에고 거의 같은 설명이니 여기까지 차근 읽어 왔음 알겠지

• Radix Sort
  • 알고리즘
    • 예를 트럼프 카드 섞기로 들겠다. 트럼프에는 무늬와 숫자 두가지가 있다. 그러므로 정렬해야할 key 가 하나가 아니라 두개이다. 그러므로 우선 하나의 key 에 대해서 item 을 구분한 다음에 나머지 key 로 또 다시 구분하면 된다. 즉 처음에는 무늬로 카트를 나눈다. 그다음에 같은 무늬안에서 숫자로 패를 나눈다. 그러면 정렬이 된다.
      이러한 정렬에는 MSD 와 LSD 가 있다.
      MSD(Most significant digit first) - 우선 순위 높은 key 부터 분류해서 내려간다.
      LSD(Least siginificant digit first) - 우선 순위 낮은 key 부터 분류해서 올라간다.
    • 아니. 트럼프 예제를 가지고 어떻게 숫자 정렬에 이용을 하냐고? 이름을 생각해라. Radix 다 진법가지고 한다. 예를 들어 10진수 이면 1의자리, 10의 자리, 100의 자리.. 이렇게 각 자리수를 key 로 생각하고 분류를 한다.
    • 예제
      • 그림
        
        
        
        
        
        
        
        
        
        
        
        
        
  • MSD, LSD 성능은 같나?
    • 이건 좀더 찾아보자. LSD 가 좀 더 나은데 확실히 이해를 못하겠다.
  • 장점
    • 근데 장점이 뭐지?? -_-a
  • 단점
    • 성능이 key 의 size 와 r 의 선택에 따라 좌우된다.(best case 찾는것도 일이겠구만.)
    • 이것 역시 O(n) 만큼의 space 가 필요하다.
  • Time complexity
    • O(d(n+r)) 이다.
      d = 몇번의 pass (회전) 이 있는가.
      n = 몇개의 item 이 있는가.
      r = radix
    • 이게 왜 이렇게 되냐면 예를 들어 item 이 100개 있고 이것의 숫자 범위가 [0,9999] 이고, radix 10을 이용해 정렬을 한다고 하면,
      d = 4 ( 1, 10, 100, 1000 자리. 즉 4개있다.)
      n = 100
      r = 10
      Time complexity 에서 r 을 더하는 이유는 하나의 pass(회전) 이 끝나면 그것을 다시 list 로 이어 줘야 하는데 그것의 갯수가 r 이기 때문이다. 즉 4번의 pass * ( 100 + 10 ) 이다.