최소, 최대힙에 대해 설명하기 전에


이진힙에 대해 설명을 하자면 


트리로 만든 Heap 인데 완전이진트리여야한다는 조건이 붙는다.



이진 힙을 List로 생성해보자

 0

 7

 -

100 

19 

36 

17 

25 


1번 째 줄은 Index, 두번 째 줄은 원소 값이다.


여기서 부모, 자식간의 관계를 수식으로 나타낼 수 있는데

1. a[i]의 자식은 a[2i], a[2i+1]에 존재한다.


2. a[j]의 부모는  a[j/2]에 존재한다.(소숫점은 버린다.)


위와 같은 공식이 나오게 된다.




최소힙


최소힙은 부모가 자식보다 더 작은 값을 지니는 힙을 말한다.



최대힙


최대힙은 부모가 자식보다 더 큰 값을 지니는 힙을 말한다.

위에 있는 사진이 최대힙이다.





힙정렬


힙정렬의 알고리즘을 보자면



1. 정렬되지 않은 n개의 데이터를 입력 받는다.

2. 해당 데이터를 최대힙으로 구성한다.

3. root를 다른 list의 맨 끝으로 뺀다.

2,3번 반복


시간 복잡도는 O(n log n)이다.

'Dev. > Algorithm' 카테고리의 다른 글

자료구조. 순회(전위 중위 후위)  (0) 2018.03.19
자료구조 트리. Tree  (0) 2018.02.21
자료구조. 스택(stack)과 큐(queue)  (0) 2018.02.20
자료구조. Linked List  (0) 2018.02.18
Horner's role  (0) 2017.03.15

트리의 순회


트리의 순회에는 3가지 방법이 존재한다.





1. 전위 순회


F->B->A->D->C->E->G->I->H


살펴보자면 Root 노드부터 왼쪽->오른쪽으로 탐색을 시작한다.


F를 방문 한 뒤, 왼쪽 자식인 B를 방문한다.

B의 왼쪽 자식인 A를 방문한 뒤, A는 자식이 없으므로 B의 오른쪽 자식 D를 방문한다.

D의 왼쪽 자식인 C를 방문 한 뒤, C는 자식이 없으므로 E로 넘어간다. E도 자식이 없으므로 

Root의 왼쪽 자식을 탐색한다.


2. 중위 순회


A->B->C->D->E->F->G->H->I


왼쪽 -> Root -> 오른쪽으로 탐색을 진행한다.


Root인 F의 왼쪽 자식인 B에는 또 왼쪽 자식이 존재하므로 A를 방문한다. 

A는 자식이 없으므로 A의 부모인 B를 방문. B의 오른쪽 자식인 D에는 왼쪽 자식 C가 존재한다.

C는 자식이 없으므로 C를 방문한 뒤, 부모인 D를 방문, 다음 E를 방문한다.

-반복


3. 후위 순회


A->C->E->D->B->H->I->G->F


왼쪽 -> 오른쪽 -> Root로 탐색을 진행한다.


귀찮다. 안적을래.



'Dev. > Algorithm' 카테고리의 다른 글

자료구조. 최소힙, 최대힙, 힙정렬  (0) 2018.03.19
자료구조 트리. Tree  (0) 2018.02.21
자료구조. 스택(stack)과 큐(queue)  (0) 2018.02.20
자료구조. Linked List  (0) 2018.02.18
Horner's role  (0) 2017.03.15

CNN ( Convolution Neural Network )




합성곱을 사용한 신경망이다.



처리과정을 이미지로 확인해보자.


복잡해 보인다.


간략하게 설명을 하자면


Input으로 특정 이미지가 들어와서 Convolution Layer를 거쳐 Pooling Layer를 지난다. 


Convolution Layer, Pooling Layer를 Feature Map Cycle이라 생각 했다.


그 이유는 해당 Layer를 지나면 Feature를 탐색하기 때문인데.. 해당 과정에 대한 이해를 해보자.




Convolution Layer


Convolution = 합성 곱


뭐랑 뭐를 합성 곱 시키는가?

합성 곱을 하면 뭐가 되는가?


위의 질문에 대한 대답을 아래에 적을 건데.. 사실 다 이해를 못해서 나중에 추가적인 설명을 붙일 거다.


합성 곱은 Input Image 혹은 Pooling Layer를 거친 Data에 Filter(Weight)를 합성 곱을 시켜준다.


출처 : http://deeplearning.stanford.edu/wiki/index.php/Feature_extraction_using_convolution


하나의 Filter를 가지고 Image를 합성 곱 시켜주므로써 Feature를 찾아내는데 보통 Filter는 3*3, 4*4로 이루어진다.

( 물론 개발하는 사람의 마음대로 filter를 조절할 수 있지만 효과적인 filter는 3*3, 4*4라 알려져 있다. )


또한 하나의 Filter로는 하나의 Feature map밖에 나오지 않기에, Filter는 여러 개를 사용하여 여러 개의 Feature map을 만든다.


Stride라는 Hyper-Paramter가 존재하는데 Stride는 filter가 몇칸을 이동할지 결정해주는 paramter이다.

위의 이미지에서는 Stride가 1인 경우이고, Stride가 2라면 (0,0)을 시작으로 다음 칸은 (0,1)이 아닌 (0,2)에서 합성 곱을 진행하는 것이다.


Stride는 작을 수록 Feature map을 잘 만들 수 있을까 하는 의문이 든다. 한번 테스트 해봐야 할 것 같다.




Feature Map은 원본 이미지보다 크기가 작아지기 때문에 연산을 위해 원본 이미지의 크기에 맞춰 줘야한다.

원본 이미지 크기만큼 빈 공간을 0으로 채워주는데 이 과정을 Padding이라고 한다.


출처 : https://www.analyticsvidhya.com/blog/2016/04/deep-learning-computer-vision-introduction-convolution-neural-networks/





Pooling Layer


이 과정은 Feature를 강조하기 위해 만들어진 층인데 N*N 크기의 영역을 1*1 크기로 확 줄여버린다.

Pooling은 3가지 방법이 있는데 Max, Avg, Min 이 있다.

N*N 크기의 영역에서 가장 큰 값, 혹은 해당 영역의 평균 값, 가장 작은 값을 골라서 1*1 크기로 압축 시킨다.


출처 : https://stackoverflow.com/questions/44287965/trying-to-confirm-average-pooling-is-equal-to-dropping-high-frequency-fourier-co






위의 Layer가 Feature Map을 생성하는 과정이다.


Filter가 여러 개이므로 Feature Map도 여러 개가 나온다.


이제 여기서 Classification을 해야되는데, FC Layer를 이용한다.

( FC Layer(fully Connection Layer)는 Dense Layer라고 불리기도 한다. )


FC Layer(Dense Layer)를 거치면 최종 Output이 나오는데 이를 softmax 를 이용해 Classification 하면 된다.



+ Recent posts