머가필요해

기사 작위를 갖고 계시는 '토니 호어'로 불리우시는 분이 1961년에 발표한 정말 정말 유명한 알고리즘이다.

이름 그대로 제일 빠른 정렬 알고리즘이 뭐야? 라고 하면 누구나 외치는 "퀵 정렬" !!!

(참고로 '토니 호어'님은 아직도 시니어 연구원으로 계신다고 한다. 무려 90세의 나이임에도 .... @.@)

[ 공부 목차 ]

① Partition

② Balanced partitioning vs Unbalanced partitioning

③ Randomized-Partition

④ Quick-Sort

① Partition (vanilla Partition)

  - 'Quick Sort'에 있어서 가장 중요한 개념이 바로 partition 이다.

  - 기준값(Pivot element) 보다 작은 값은 왼쪽에, 큰 값은 오른쪽에 배치하여 나누는 것을 의미한다.

  - 가장 기본이 되는 partition 방법은 제일 오른쪽 값을 pivot으로 해서 하나씩 비교하는 것이다.

  - 제일 오른쪽 값을 기준으로 제일 왼쪽부터 하나씩 비교해서 작은값 그룹과 큰값 그룹을 만들어 간다.

  - 그런데, "1"값을 만났을 때 작은값 그룹에 묶을 때가 문제가 된다.

  - 이럴 때에는 큰값의 제일 왼쪽에 위치한 것과 swap을 하면 된다. (i값 위치의 변화도 살펴봐야 한다)

  - 이렇게 하다보면 끝까지 진행을 하게 될텐데, 마지막에 위치한 pivot 값은 어떻게 해야할까?

  - 역시 마찬가지로 큰값의 제일 왼쪽값과 swap 하면 된다.

  - 이 과정을 pseudo code로 살펴보면 다음과 같다.

  - Running Time을 계산해보면 다음과 같다.

② Balanced partitioning vs Unbalanced partitioning

  - partitioning을 할 때에 좌우 균형이 잘 맞춰져서 나뉘어지면 좋겠지만,

  - 그렇지 않고 한 쪽에 치우칠 수도 있다.

  - 균형이 맞지 않는 극단적인 경우를 보면 다음과 같다.

  - Running Time은 다음과 같이 구할 수 있다.

  - 즉, 최악의 상황에서는 n제곱, 보통은 n로그n 이라고 정리하면 되겠다.

  - 그러면, 최악의 상황을 막을 방법은 없을까!?

③ Randomized-Partition

  - 최악의 상황이 발생하는 것은 pivot 값을 무조건 제일 끝값을 택하기 때문에 발생을 한다.

  - 그러면, pivot 값을 random하게 선택을 하게 되면 최악의 상황이 벌어질 가능성을 낮출 수 있다.

  - random하게 값을 뽑아서, 그것을 제일 오른쪽(끝) 값과 swap을 한 다음에 partition을 하면 되는 것이다.

  - 그런데, radom 호출 하는 것 자체가 over-head가 될 수도 있다. radom 자체가 비용이 크기 때문이다.

  - 그래서, (첫값 + 가운데값 + 끝값) 3개 중에 중간값을 선택하는 방법도 있긴 하다.

④ Quick-Sort

  - 지금까지 우리는 Partition을 공부했다. 이를 이용해서 Sort는 어떻게 할 수 있을까!?

  - 일단 partition을 한 다음, 왼쪽/오른쪽 각각 QuickSort를 하면 된다.

  - 그렇다 !!! Divide-and-Conquer 알고리즘이다.

  - Quick-Sort의 Running Time은 어떻게 될까?

  - 메모리 사용은?! 위치를 가르칠 변수 정도면 충분하다. 즉, 입력 데이터의 크기에 영향을 받지 않는다.

지금까지 여러 Sorting algorithm을 알아봤는데, 성능 비교 등을 해보면 좋을텐데...^^

다음 기회로~~~

이번에 살펴볼 정렬 알고리즘은 "Heap Sort(힙 정렬)"이다.

보통은 위키피디아의 animated-gif 를 통해서 정렬 알고리즘을 엿볼 수 있었는데,

heap-sort 경우에는 도저히 파악이 안되는 내용이라 다른 자료를 찾아봤다. (내가 무지해서 이해를 못한 것이겠지...)

너무나 친절한 Visualization을 제공해주는 곳은 다음과 같다.

- https://www.cs.usfca.edu/~galles/visualization/HeapSort.html

- 왼쪽 상단의 "Heap Sort" 버튼을 클릭하면 animation을 보여준다.

왜 저렇게 정렬이 되는지 바로 이해가 되시는 분은 그만 공부하셔도 된다!!! ^^

사실 공부하기 전에는 대체 어떤 이유로 이렇게 움직이는 것인지 잘 보이지 않아야 정상일 것 같다 ^^

우리에게 필요한건?

공부!!!

Heap Sort를 알기 위해서는 일단 Heap이 무엇인지 부터 알아야 한다.

⑴ Heap의 정의

⑵ MAX-HEAPIFY()

⑶ BUILD-MAX-HEAP()

⑷ HEAP-SORT

⑴ Heap

Heap은 2가지의 속성을 갖고 있다. 이에 대해서 알아보자.

  ① A nearly complete binary tree

  ② max-heap

① A nearly complete binary tree

일단 tree 구조와 관련한 용어부터 확인해야 이야기가 쉬울 것 같다.

tree 관련한 용어들이 더 있지만, 일단 이 정도만 알아도 될 것 같다.

그러면, tree 구조 관련하여  "complete binary tree"가 뭔지부터 파악하고

"nearly complete binary tree"가 뭔지 이해해보도록 하자.

▷ Complete Binary Tree

  - all leaves the same depth

  - all internal nodes have degree 2

그러면 nearly complete binary tree는 어떻게 생겼을까!?

▷ A Nearly Complete Binary Tree

  - 기본적으로는 Complete Binary Tree 구조를 갖고자 

  - all internal nodes have degree 2, but 마지막 leaf는 1개가 부족할 수 있다.

  - 마지막 depth의 leaves는 왼쪽부터 차례대로 배치

우리가 공부하고자 하는 Heap 구조는 바로 이 "nearly complete binary tree"를 따르고 있다.

왜 그럴까!?

▷ Array

"nearly complete binary tree" 구조를 따를 경우에 이를 array 방식으로 표현하기가 쉽기 때문이다.

반대로 말하면 array를 사용하기 위해서는 nearly complete binary tree 구조여야 한다!!!

이렇게 되면 어떤 장점이 있을까?

그렇다 ! 위치에 대한 계산이 가능해진다 !!!

여기에서 하나 더 확인해볼 것은 "The height of a heap"이다.

▷ The height of a heap

  - 기본적으로 height는 depth와 같은 개념이고, 특정 node를 기준으로 depth가 얼마인지를 의미한다.

  - The height of a heap = The height of the root : 그러면 depth의 의미이다.

  - 그러면, 여기에서 질문 하나

    : 어떤 Heap의 전체 node의 갯수(n)를 알면 height가 얼마인지 알 수 있을까?

  - height를 h라고 하면, 다음과 같다.

② max-heap

'binary heap'은 max-heaps와 min-heaps의 2가지 종류가 있다.

앞에서는 tree 구조에 대해서만 이야기 했지, 각 node에 들어있는 값에 대해서 이야기하지 않았다.

이제는 각 node에 들어있는 값에 대한 이야기이다.

위 그림을 보고 오해를 하면 안된다.

당연하게도 모든 parent-child 를 살펴봐도 모두 저 관계를 만족해야 한다.

그러면 제일 위의 root node에 들어있는 값은 전체 모든 node 중에서 가장 큰 값이 위치하게 된다.

min-heap은 반대이다. root node가 가장 작은 값을 갖는다.

우리는 보통 max-heap을 사용한다.

⑵ MAX-HEAPIFY()

"Max-Heapify" 함수에 대해서 알아보겠다.

함수이기에 입력(input)과 출력(output)이 있고, 그 과정에서 어떤 처리(processing)이 있을 것이다.

① input

  - 입력은 어떤 하나의 node가 된다.

   - 단, 그 노드가 갖고 있는 왼쪽/오른쪽의 subtree들이 이미 max-heap 구조를 갖고 있어야 한다.

② float down

  - "4" node를 기준으로 왼쪽/오른쪽 subtree가 각각 max-heap이기에 max-heapify 가능

  - 그래서 "4" 값과 "14"값을 exchange

  - 그런데, "4" node를 봤더니 max-heap 상태가 아님

  - subtree 들은 각각 max-heap 상태이기에 max-heapify 실행

  - 그래서 "4"와 "8"값 exchange

  - 그랬더니, 처음 "4"에서 실행한 max-heapify가 전체적으로 이루어짐

이렇게 밑으로 흘러가듯이 이루어지는 과정을 "float down"이라고 

③ running time

  - max-heapify의 running time을 알아보자.

⑶ BUILD-MAX-HEAP()

max-heap을 만드는 것에 대한 Pseudo Code를 살펴봅시다!!!

Text에서 floor 함수 표기가 쉽지 않아 조금 이상하게 보이는 부분은 이해해주시길 바라옵니다 ^^

일단 A는 max-heap을 하고자 하는 입력 데이터를 의미한다.

그러면, 밑의 순환문은 어떤 의미일까!?

그러므로, 순환문의 시작 위치는 다음과 같다.

그 다음 index가 하나씩 감소하기 때문에 다음과 같은 흐름으로 진행하게 된다.

전체 길이의 절반 위치에서 시작하는 것은 그 이후의 node는 edge-node 즉, leaves 들이기 때문에

이미 max-heapify가 되어 있어서 굳이 max-heapify를 할 필요가 없는 것이다.

▷ Running time

① Upper bound

  - Pseudo code를 기반으로 해서 찬찬히 살펴보면 다음과 같이 실행 시간(횟수)를 확인할 수 있다.

이를 계산하면 다음과 같이 정리가 된다.

② Tighter bound

그런데, 실제로 분석해보면 이는 지나친 upper-bound라고 볼 수 있다.

즉, 이것 보다는 조금 더 tighter-bound를 계산해볼 수 있는 것이다.

1번 node 기준으로 max-heapify를 한다고 했을 때, "n = 10" 이므로 O(log 10) 소요시간이 걸린다.

그러면, 5번 node 기준으로 max-heapify를 하면 소요시간이 얼마나 걸릴까?

5번 node 위치에서의 "n = 2" 이므로 O(log 2) 소요시간이 걸린다.

4번 node 위치에서는 O(log 3), 3번 node 위치에서도 O(log 3) 이다.

즉, 실제로 많은 node에서 소요되는 시간이 우리가 계산한 O(log n) 값보다 작다는 것이다.

이걸 고려해서 계산을 해보면 다음과 같다.

엇?! 선형(linear)으로 정리가 되었다 !!!

⑷ HEAP-SORT

이제 마무리 단계에 왔다.

앞에서 공부한 것들을 모두 모아서 정렬하는데에 어떻게 사용할 수 있는지 Pseudo Code로 살펴보자.

응!? 이건 뭔가 싶다.

▷ Extract-Max

  - BUILD-MAX-HEAP() 실행을 마치면, root-node에 있는 값이 가장 큰 값이 되게 된다.

  - root-node에 있는 값을 제일 뒤에 있는 node와 교환을 한다.

  - 제일 뒤에 있는 node를 제외한 tree를 가지고, root-node에서 MAX-HEAPFY()를 실행한다.

  - 이 방식 가능한 이유는 이미 BUILD-MAX-HEAP()을 통해, 그 밑의 subtree들이 max-heap 상태이기 때문이다.

▷ Running Time

  - Pseudo Code를 가지고 수행 시간을 살펴보자.

  - Worst-case는 이렇게 되겠지만, Best-case는? 모든 것이 같은 값일 때 !!!

  - 5번 라인의 경우 값이 하나씩 줄어들기 때문에, 시간이 조금씩 더 적게 들겠지만 유의미하지는 않다.

  - 결론적으로 Heap-Sort의 Running Time은 다음과 같이 정리할 수 있다.

▷ Memory

  - Heap-Sort는 추가적인 메모리가 필요하지 않은 in-place 알고리즘이다.

  - 별도의 메모리 공간이 아니라 node 사이의 값을 exchange하는 것으로 처리되기 때문이다.

우아앙~ 너무 힘들었다.

자~ 이번에는 "Merge Sort"에 대해서 알아보자.

한글로는 "합병 정렬" 또는 "병합 정렬"이라고 불리운다.

세계의 모든 지식이 들어있다고 해도 과언이 아닌 위키피디아에서는

Animated GIF 이미지로 Merge Sort를 너무나 잘 설명해주고 있다.

이 알고리즘은 그 유명한 "존 폰 노이만(John von Neumann)"님이 1945년에 개발했다고 한다.

우리의 갓 노이만 형님 !!!

위 Animation을 잘 지켜보면 알겠지만,

"Divide-and-Conquer (분할 및 정복)" 알고리즘의 하나이다.

반절씩 잘라서 나누고, 합치면서 정렬을 하는 것이다.

그런데, 실제 구현을 할 때 divide를 하기 위해서

위의 그림에 있는 모든 박스의 갯수만큼 별도의 메모리 공간을 확보해야 할까?

한 번에 모든 메모리 공간을 확보하는 것 보다는

한 단계씩 나눠서 그 때 그 때 필요한 값을 복사해서 사용하는 방식이 훨씬 효율적이고 똑똑한 방법이 되겠다.

무슨 말이냐고!?

한 단계씩 밟아나가보자 !!!

위 그림과 같이 8개의 입력이 있다고 해보자.

인덱스(index)값의 의미로 "[ ]"로 묶은 형태로 표기해보았다.

우리의 명령(입력)은 다음과 같다.

"1번부터 8번까지의 인덱스를 갖고 있는 입력값을 merge sort 해줘 !!!"

이것을 1-depth 더 들어가서 살펴보면 다음과 같다.

"1번부터 4번까지의 값을 merge sort하고

5번부터 8번까지의 값을 merge sort한 다음에

그 2개의 결과를 merge 해줘"

어!? 여기에서 조금 애매한 표현이 등장했다. merge ???

[5, 6] 과 [1, 3]을 merge 하는 과정을 보면 그냥 합치는 것이 아니라

크기를 비교해서 작은 것부터 차례대로 하나씩 넣어가는 과정이다.

그리고 여기에서 주의해야할 사항이 하나 더 있다.

[5, 6] 과 [1, 3]을 merge 할 수 있는 것은 [5, 6] 과 [1, 3]이 각각 이미 sort가 되어있기 때문이다.

그림으로 살펴보자.

[2, 4, 1, 3]이라는 값을 merge 한다고 하면

반절 크기의 2개의 메모리 공간을 잡아놓고, 거기로 값들을 복사한다.

그리고 2개 메모리 공간의 앞 부분의 값을 비교해서

작은 값 순서대로 하나씩 복사해 넣는 과정으로 정렬이 된 값으로 merge가 된다.

Pseudo Code는 다음과 같다.

p, q, r 값의 정체는 다음과 같다.

merge 작업을 할 시작 위치(p), 끝 위치(r), 그리고 divide를 할 중간값(q)이다.

그러면 pseudo code를 진행하면서 정해지는 값/상태들을 확인해보자.

쪼갠 값들을 저장할 메모리 공간의 크기를 계산하기 위한 n1, n2 값을 계산한다.

divide한 값을 저장할 2개의 메모리 공간을 생성한다.

응?! 4개가 아니라 5개씩 공간을 준비하네?!

그 다음 pseudo code들을 진행해보면 이유를 알겠지.

이제 모든 준비는 끝났다.

여기까지 해서 merge 과정에 대해서 살펴봤다.

이제, 전체적으로 merge sort 하기 위한 pseudo code를 알아보자.

3번 라인은 본래 아래와 같은 notation이다.

Editor에서 사용 가능한 기호 중에서 마땅한 것을 찾지 못해서 ^^

2로 나눈 결과의 소숫점 버림값을 취하겠다는 의미이다.

지금까지 살펴본 내용을 기반으로 Python으로 구현해보면 다음과 같다.

Merge Sort를 어떻게 하는 것인지에 대해서는 이제 다 알아봤다.

남은 것은 Performance 측정이다.

먼저, Merge 과정에 소요되는 시간을 계산해보자.

위 그림에서 보이는 것 처럼

핵심적인 부분은 move와 comapre로 구성되어 있다.

move는 "n1 + n2" 횟수만큼 실행이 되고

compare는 "n1 + n2" 보다 작거나 같은 횟수만큼 실행이 될 것이다.

그렇기 때문에, 전체적으로 2 * (n1 + n2) 횟수보다 같거나 적은 횟수만큼 실행이 된다고 봐도 무방할 것이다.

Merge = Θ(n1 + n2)

그러면, 전체 Merge Sort의 소요 시간은 얼마나 될까!?

MERGE-SORT(A, p, r) 의 소요 시간을 T(n) 이라고 하면,

3번째 라인과 4번째 라인은 n의 이등분된 값을 갖게 되므로 T(n/2) 값을 갖는다고 할 수 있다.

5번째 라인은 바로 앞에서 살펴본 내용에서 n1 + n2 = n 이므로 Θ(n) 값으로 표현해볼 수 있다.

여기에서 생각해볼 것은 1번 라인이 비교문이라는 것이다.

비교문을 통과하지 못하는 경우를 생각해보면, p < r을 만족하지 못하는 경우는 n=1 일 경우일 것이다.

그래서 점화식으로 표현해보면 다음과 같다.

이와 같은 경우는 'Recursion Tree Method(재귀 트리 방법)'을 통해 풀어낼 수 있는데,

중간 과정은 생략하고.... 그래서 계산한 결과는 다음과 같이 정리된다.

위의 이미지에서는 Big-O로 표기되었지만, Big-Theta로 할 수 있다.

그러면 메모리 공간은 얼마나 사용할까?

"n"개 만큼 더 필요로 한다.

최대 n개 공간이 있으면 그것을 이용해서 모두 계산 가능하다.

함수의 증가? 함수의 성장? 함수의 성장률?

한글로 어떻게 표현해야 하는지 좀 애매한 타이틀인데,

구글링을 해봐도 명확하게 번역한 명칭이 확인되지 않는다.

보통은 그냥 "함수의 성장" 정도로 번역하면 적당한 것으로 보인다.

여기에서 하고 싶은 말이 무엇이냐면,

입력값에 대한 결과값, 즉 함수의 값이 어떻게 변화(증가/성장)하는지를 살펴봐야 한다는 것이다.

특히 우리는 지금 알고리즘 공부를 하기 때문에 이에 특화되어 정의해보자면,

입력 크기(n)에 따라 얼마나 많은 시간이나 공간을 필요로 하는 것인지를 살펴보는 것이다.

▶ Notation (표기법)

알고리즘의 성능, 즉 소요시간을 표현하는 3가지 notation을 먼저 알아보자.

① Θ-notation (Big-Theta) : tight

아주 정확하게 일치하는 것은 아니지만, 최대한 근접하게(tight) 표현하는 방법이다.

② Ο-notation (Big-O) : upper-bound

O-notation으로 표현한 값이 실제값과 같거나 더 큰 범위이기 때문에 upper-bound 라고 한다.

③ Ω-notation (Big-Omega) : lower-bound

Ω-notation으로 표현한 값이 실제값과 같거나 더 작은 범위에 속하기 때문에 lower-bound 라고 한다.

보통 'Big-O'라고 부르는 O-notation만 알고 있는 사람도 많은데(me...??? ^^),

위와 같이 3가지 표기법이 존재하고 있고 주로 많이 사용하는 것이 Big-O notation이다.

▶ Asymptotic Notation (점근 표기법)

정확히 문장으로 설명하기에 쉽지 않지만 위와같은 표기법에서 보는 것처럼

정확히 일치하지는 않지만 어떤 추세/경향을 대강(?!) 보여줄 수 있는 표기법을 Asymptotic Notation이라고 한다.

▷ O-notation

  - 아래 그래프를 잘 분석해야 한다. 상당히 많은 의미가 내포되어 있다.

일단 g(n)과 f(n)만 놓고 앞 부분을 살펴보면

때로는 g(n)이 더 높은 값을 갖기도 하고 f(n)이 더 크기도 하다가

어느 순간, n0 값 이후로 g(n)이 지속적으로 더 큰 값을 갖는다.

g(n)도 잘 살펴보면 그냥 g(n)이 아니라 양의 상수 값 c 를 곱한 c * g(n) 값이다.

앞에서의 n0 값 역시 양의 값이다.

위와 같이 깔끔하게 요약할 수 있다.

이럴 때 g(n)은 f(n)의 asymptotic upper bound라고 부를 수 있다.

여기에서 문제를 한 번 풀어볼까!?

위 식이 성립함을 증명해보자.

막막할 수 있으니 바로 설명을 보자면 (^^) 다음과 같다.

여기에서 가장 중요한 부분은 첫 줄이다.

이 문장만 이해할 수 있으면 Asymptotic notation에 대해서 이해한 것이다.

▷ Ω-notation

  - 마찬가지로 그래프를 하나 보자.

간단히 정리하면 다음과 같은 내용이다.

이젠 이해가 될거라 믿는다.

▷ Θ-notation

  - 마찬가지로 살펴보자.

앞에서 공부한 Insertion Sort에 대해서 표기를 해보면 다음과 같다.

Best-Case / Worst-Case가 존재 하므로 Θ-notation은 없고,

O-notaion과 Ω-notation이 존재하고 각각의 값은 위와 같다.

나름 쉽게 정리해본다고 했는데.... 기회가 되면 F2F로 설명을 ^^

알고리즘을 구현하기 위한 소스 코드의 소요 시간(실행에 필요한 시간)은 어떻게 측정할 수 있을까?

실행을 시켜서 완료될 때 까지 걸린 시간을 측정하면 될까?

실행하는 컴퓨터의 CPU가 무엇인지, HDD 또는 SSD를 사용하는 지와 같은 여러 상황에 따라서

똑같은 알고리즘도 시간이 다르게 나올 수 있을텐데...

그리고 작성하는 프로그래밍 언어에 따라서도 실행 시간은 천차만별일 수 있다.

즉, 실제 시간을 측정해서 알고리즘의 성능을 비교 평가하는 것은 어렵다.

그래서, 보통은 Pseudo code의 라인별 수행하는 횟수를 카운트 하는 방식으로 소요 시간을 측정한다.

Insertion sort의 pseudo code는 다음과 같다.

한 줄씩 살펴보자.

입력값 A의 길이가 n이라고 해보자.

보통의 프로그래밍 언어에서 배열은 0부터 시작하지만 pseudo code에서는 1부터 시작한다.

그러면 1번 라인은 총 몇 번 수행이 될까?!

지금 대답을 하지 못하는 분은 개발자로서 조금 문제가 있는 상태이고 (^^)

"n - 1"번이라고 대답하신 분은 보통의 개발자 수준이고

"n"번이라고 대답하신 분은 정말 훌륭한 개발자 이거나 아니면 운으로 맞춘 분일 것이다 ^^

"j = 2"라고 되어 있기에 for문 자체는 "n - 1"번 수행한다고 말하는 것이 일반적이지만

실제 for문 자체는 마지막 조건 체크를 위해 한 번 더 수행을 하기 때문에 "n - 1 + 1"번 수행을 하게 된다.

하지만, 그냥 "n - 1"번 수행한다고 해도 무방하지 싶다.

2번 ~ 4번 라인은 각각 "n - 1"번 수행한다.

5번 ~ 7번 라인이 핵심인데...

처음 "j = 2" 상황에서는 1번 위치에 있는 값하고만 비교하면 되기에 1번만 실행이 될 것이고,

그다음 "j = 3" 상황에서는 2번 위치하고 비교하고 그 다음 1번 위치하고 비교를 하게 된다.

그렇게 해서 "j = A.length" 상황에 되면, 즉 "j = n" 상황이 되면 "n - 1"번 비교를 하게 된다.

이걸 그림으로 표현해보면 아래와 같다.

그래서, while문이 있는 5번 라인은 "1 + 2 + 3 + ... + n"번 실행을 하게 되고 (값 비교를 위해 한 번 더)

6번, 7번 라인은 "1 + 2 + 3 + ... + (n -1)"번 실행을 하게 된다.

8번 라인은 당연히 "n - 1"번 수행한다.

잘 이해가 되시나요?!

여기에서 "예"라고 대답을 하신 분은 .... No! No!! No!!!

8번째 값을 정렬할 차례가 와서

첫번째로 7번 위치랑 비교 =  pass, 6번 위치 비교 = pass

5번 위치랑 비교했더니 여기에서 break

8번째 값을 정렬할 때에는 7번의 비교가 필요한 줄 알았는데,

실제 입력값 상황에 따라 수행 횟수가 가변적이다.

그래서 이를 t변수를 이용해서 표현한다고 하면, 전체적으로 다음과 같이 정리해볼 수 있다.

C 변수는 각 라인을 실행할 때 드는 비용(시간)을 의미한다.

그래서 위 내용을 정리해서 총 실행 시간은 다음과 같이 정리할 수 있다.

여기에서 뭔가 답답하게 만드는 것이 t 변수 값인데,

best/average/worst case에 따라서 값이 달라질 수가 있다.

위 그림에서 왼쪽이 best case이고, 오른쪽은 worst case이다.

다시 말해 이미 정렬이 되어 있는 경우는 best case이고, 역으로 정렬된 경우가 worst case이다.

best case에 대해서 정리해보면 다음과 같다.

결론적으로는 an + b 형식의 식으로 나오고 이는 선형적인 모습을 보인다.

이번에는 worst case를 살펴보자.

정리된 식을 살펴보면,

worst case는 an^2 + bn + c 와 같은 2차 함수 형태로 나타난다.

best case는 입력값 n의 크기가 커짐에 따라 선형적으로 실행 시간이 증가하게 되고

worst case는 입력값 n의 크기가 커짐에 따라 제곱으로 증가하게 된다는 것을 알 수 있다.

그런데, 모든 알고리즘들에 대해서 이렇게 분석하는 것은 너무 어렵다.

이와 같은 과정을 뭔가 단순하면서 명확하게 표현하는 것에 대해서 알아보도록 하자.

지금 말고 다음에.... ^^

이제와서 왠 알고리즘 !? ^^

나름의 이유로 알고리즘을 차분히 조금은 깊게 살펴볼 이유가 있어서 정리를 해보고자 한다.

우선 알고리즘에서 가장 대표적인 문제 유형은 바로 정렬(sort)이다.

크기가 다른 여러 개의 입력값이 있을 때, 이를 크기 순서대로 줄을 세워야 하는 문제이다.

정렬 문제(Sorting Problem)를 해결할 수 있는 알고리즘(Algorithm)은 상당히 다양한데,

그 중에서 가장 첫번째로 언급되는 것이 바로 '삽입 정렬(Insertion Sort)'이다.

삽입 정렬을 한 번에 확인하기 위한 가장 좋은 예시는

위키피디아에서 보여주는 에니메이션이다.

찬찬히 잘 살펴보면 어떻게 하겠다라는 것인지 충분히 이해할 수 있겠지만

그래도 좀 더 설명을 해보자면 다음과 같다.

6번째까지 정렬이 된 상태에서 (1, 3, 5, 6, 7, 8), 7번째 '2' 순서가 되었을 때를 설명해보려고 한다.

일단, 자기 자신의 앞에 있는 '8'과 비교했더니 나(2)보다 큰 값이기에 '8'을 한 칸 앞으로 옮긴다.

그 다음에는 하나 더 앞에 있는 '7'과 비교를 하고 옮기고 ... 그렇게 진행하다가

'1'을 만나게 되는데, 이번에는 '2'보다 작은 값이기에 자기 자신(2)이 '1' 뒤에 위치하면 된다.

'Pseudo Code'는 다음과 같다.

2번째 입력값부터 시작해서 마지막 입력까지 수행을 해야 하는 것이고

기준이 되는 값을 일단 'key'에 저장해놓고,

key랑 비교를 시작할 위치는 key보다 하나 앞선 값이다.

이제 앞에 있는 값들과 비교를 해보고 비교한 값이 크면 비교한 값을 뒤로 한 칸 옮기고

같거나 작으면 비교를 멈추고 거기에 key값을 넣어주면 된다.

Python으로 작성해본 코드는 다음과 같다.

Pseudo code와 거의 동일하다.

뭐 당연히 결과는 잘 나온다.

자~ 이제 시작이다.

살펴봐야할 많은 것들이 있다.

과연 이 알고리즘은 얼마의 시간이 걸릴 것이며, 얼마의 메모리가 필요하고,

Best Case일 때와 Worst Case일 때 어떻게 되는지를 살펴봐야 한다.

거기에다가 하나 더 알아봐야 할 것은 입력값들의 순서가 유지되는지에 대해서도 알아봐야 한다.

하지만, 벌써부터 지칠 수 있으니

다음 기회로.... ^^ (절대 귀찮아서 미루는 것이 아니다! 절대로! 절대로?)

Python Excel Deep Learning

딥러닝의 알고리즘 원리부터 파악하기

파이썬과 엑셀로 시작하는 딥러닝

딥러닝과 파이썬은 쿵짝이 잘맞는 짝꿍같은 느낌인데, 왠지 엑셀은 어울리지 않는 느낌이 든다.

하지만, 딥러닝을 잘 생각해보면 테이블 형식의 데이터들과 수학이 바탕이 되어야 하고

그렇게 생각해보면 엑셀은 딥러닝에 잘 어울리는 도구일 수도 있겠다라는 생각이 든다.

어!? 이거 가스라이팅인가!? ^^

지은이 3명의 소개글을 읽고 공통점을 찾으셨다면~ 센스쟁이 !!!

그렇다!!! 인공지능 대학원 동문 3명이 모여서 책을 썼다!!!

출간한지 얼마 안되는 따끈따끈한 New 책이다 !!!

AI를 공부하는 모두가 Model Researcher일 필요는 없다.

하지만, 그렇다고 해서 딥러닝의 기본기를 배울 필요가 없는 것은 아니다.

인공지능을 공부했다라고 말하기 위해서는

Scikit-Learn, Tensorflow, Pytorch 등에서 제공하는 것을 그냥 가져다가 쓰기만 하는 것이 아니라

그 기본이 되는 원리에 대해서 한 번쯤은 파고들어본 경험은 있어야 한다고 생각한다.

일단, 책의 전체 내용을 간략히 살펴보자.

크게 보면 "분류 문제 → CNN → RNN" 정도에 대해서 진행을 하게 되고

데이터 정규화 및 분할, 소프트맥스에 대해서도 설명을 해주고 있다.

왠지 귀여운 느낌의 차례가 등장했다 ^^

조금 아쉬운 점은 ...

개인적인 취향일 수도 있지만 자고로 개발환경이라고 하면 리눅스(Linux)가 표준이지 않을까 한다!

특히 시장지배적 위치에 있는 우분투(Ununtu) 기준으로 개발환경 설명을 해줘야 하는데.... 없다!!!

어디까지나 개인적인 취향으로... Ubuntu 운영체제에서의 환경 구축은 다음과 같이 하면 된다.

1. Python 설치 및 가상 환경

  - 원하는 버전의 Python을 편하게 사용하기 위해서는 다음 링크를 참조해서 pyenv를 설치하자

    . 다양한 버전의 파이썬을 사용하려면 (pyenv)

  - 실습을 진행할 디렉토리로 이동 후 기본 환경을 맞춰보자

2. Jupyter 설치

  - Jupyter Notebook 사용을 위해 jupyter 패키지를 설치하자

  - 설치가 잘 되었는지 실행해보자

  - 새로운 파일 생성은 책과 조금 다르기에 캡쳐한 화면으로 보여주겠다.

이하 과정은 책을 보면서 따라가면 된다.

사실 위의 내용도 책의 내용과 별 차이 없다 ^^ 괜한 투정~!!!

책의 뒷부분에는 재미있는 것들이 부록으로 제공된다.

Microsoft Excel 뿐만 아니라 `구글 스프레드시트`를 애정하는 분들을 위한 내용도 설명을 해주고 있다.

요즘 Pytorch에 비해 인기가 조금 시들해졌지만,

그래도 아직 그 명성을 떨치고 있는 Tensorflow를 사용하는 다양한 예제도 있다.

이 책의 가장 특징인 엑셀(Excel)을 사용하기 위한 패키지로 여기에서는 `xlwings`를 사용하고 있다.

Jupyter Notebook에서 설치해서 사용하면 된다.

책을 보다가 깜짝 놀란 이미지가 있어서 잠시 공유 !!! ^^

딥러닝을 공부하면서 정말 괴로운 부분이 바로 수학이다.

특히 미분 ... 어렸을 때 잘 공부해뒀어야 했는데 ... 뒤늦게 공부하려면 ... 정말 ... 짜증이 ... ^^

그런데, 컴퓨터를 사용하고 있으면서 그것도 프로그래밍을 하고 있으면서

미분을 컴퓨터에게 시키면 되지 왜 그것을 공부를 하고 있을까!?

기본적으로 컴퓨터는 ... 프로그래밍적으로 미분을 직접 푸는 것은 안된다.

(물론 불가능은 아니겠지만, 어렵다. 그리고 내가 원하는대로 나오는 것은 더더욱 어렵다)

그러면, 기울기를 구하기 위해 미분을 하려면 어떻게 될까!?

미분한 결과를 프로그래밍으로 구현해주면 된다.

위에서 보이는 함수 중에서 `def f_prime(x):` 부분을 보면 알겠지만,

미분이 된 수식을 구현하고 있다.

뭐 그렇다.

이 책을 훑어보다보면 `응? 왜 굳이 Excel이 필요한거지?`라는 생각을 할 수도 있을 것이다.

사실 많은 강의와 서적에서는 Pandas/Numpy/Matplotlib 등으로 잘 설명해주고 있기 때문이다.

하지만, 직접 이 책을 따라하다보면 왜 엑셀을 사용하고 있는지 느낄 수 있을 것이다.

특히, Pandas/Numpy/Matplotlib 등을 이용해서 공부를 해보신 분이라면

엑셀을 통해서 중간에 어떻게 값들이 변해가는지 등을 눈으로 보면서 막혔던 것이 뚫리는 기분을 느낄 수도 있을 것이다.

예제 파일도 제공을 해주고 있으니 편하게 사용해보자.

  - http://infopub.co.kr/new/include/detail.asp?sku=06000248

GitHub로 샘플을 제공해주면 좀 더 좋았을 것 같은데

아쉽지만 공식 홈페이지를 통해 압축 파일을 내려받아야 한다.

용량은 2.7MB 정도이다.

책 제목에서도 나와있지만

딥러닝의 알고리즘 원리를 직접 손으로 하나씩 확인하고픈 사람들에게는 정말 가뭄의 단비같은 책이 될 수도 있다.

하지만, 응용 위주로 딥러닝을 공부했거나 하려고 하는 분들에게는 별 도움이 되지 않는 책이 될 것이다.

그리고, 나름 친절하게 설명하려고 노력은 했지만

딥러닝에 대해 비기너(Beginner)... 아직 한 번도 공부하지 않으신 분들은 따라하기에도 쉽지 않을 수 있다.

많은 공식이 나오는 것은 아니지만,

중간 중간 나오는 공식들이 어떤 의미인지 친절할 정도로 설명은 하지 않고 있기 때문이다.

(설명이 충분치 않은 것이 당연하다! 그걸 다 설명하려면 그것만으로도 책이 나올 것이다 ^^)

즉, 이 책을 추천하고픈 분들은 다음과 같다.

- 딥러닝 공부를 하고 있지만, 대체 GD는 뭐고 Softmax가 뭔지 원리가 궁금한 사람

- 중간 중간 단계에서 값들이 어떻게 변하는지 눈으로 확인하고 싶은 사람

- Tensorflow나 Pytorch에서 제공해주는 것만 사용하다가, 어떻게 구현된건지 궁금한 사람

(눈치 채셨겠지만 ... 같은 대학원 공부를 하고 있는 분들이 저자라서 ... 리뷰를 해봅니다만 ... 나름 솔직한 리뷰입니다 ^^)

이 포스팅은 제공 받은 서적으로 작성한 리뷰입니다.