[자료구조] 기말고사 Summary

 

 

 

 

# 7. Recursion

- 재귀 호출 – 호출된 함수가 호출하는 함수와 동일한 함수 호출 -> 즉 자기 자신을 호출

- 무한 함수 호출(무한 재귀) 피해야 함 -> 탈출 조건 지정

- recursion은 반복문(iteration)에 비해 속도가 느리다.

 

- 각 연속적인 재귀 호출은 응답이 알려진 상황(기본 상황)에 더 가까이 다가가야 함 

- 기본 사례, base case: 답이 알려진 (재귀 없이 표현될 수 있는) 경우 

-> 함수에서 비 재귀적인 방법이 있나? 

- 각 재귀 알고리즘에는 하나 이상의 기본 사례와, 일반 사례(general case, 재귀 구문)가 있어야 한다. // solution까지 올바르게 도달할 수 있는지 생각해야 함

+ base case가 꼭 하나일 필요는 X -> ex) Quick Sort 

 

Ex) factorial의 base case는 number == 0 -> return 1

- n * (n – 1) * … * 1  =  n * Factorial (n – 1)

-> 재귀 호출은 Factorial (0)의 기본 사례, base case에 더 가까이 도달함

 

* 재귀 함수를 구현 -> 비재귀적인 방법도 있을까? 

-> tail recursion은 가능

- 재귀 함수 호출 -> 비용이 큼 

 

* 피보나치 수열 

An = An-1 + An-2  (A1, A0 = 1)

재귀 함수를 2번 호출 시, 복잡도가 2^n으로 올라감 -> 함수가 여러 번 호출되는 것 지양

예외 - ex) Quick Sort // pivot 기준으로 절반씩 구간 나누기 때문에, 효율성 높음

 

* 순차 탐색을 재귀 함수로 구현할 수도 있음 – 예제를 위한 예제

- base case가 2개 있어도 가능함을 보여줌 – if else 구문으로 1번만 호출됨 (둘 중 하나만)

 

- 반복문을 사용하여 재귀 없이 작성될 수 있음 

- 반복문은 Loop (while) 사용, 재귀는 if 조건문 사용

- 연산 속도 측면에서 일반적으로 재귀는 반복문보다 효율이 떨어짐 

-> 특정 경우, 재귀가 가장 효율적임 (reverse print = 속도 측면에서 재귀가 이득임)

Ex) 포인터 변수가 사용될 때 종종 발생한다.

 

- RevPoint – 역방향으로 프린트 

- 단순히 반복으로 구현 시, indirection 연산 매우 많음 -> 재귀가 구현도 깔끔함 

- next가 null일 경우, return 되어 아래 line이 실행됨 (listPrt -> info 출력) 

 

* 이진 탐색도 재귀로 구현 가능 

Found = BinarySearch (info, 25, 0, 14) // item = 25, first = 0, last = 14

- 이 함수도 else if 구문으로 BinarySearch가 2개 있으나, 한 번에 하나만 호출됨

 

* Call stack – 함수 호출은 오버헤드가 크다 

- 재귀는 이러한 함수를 여러 번 호출하는 것, 되도록이면 반복문으로 구현하는 게 좋음 

- 함수와 명령어들도 메모리에 있다 – 함수 실행 이후, return 시 기존 위치로 돌아가야 함 

- 해당 장소를 반환 주소라고 함

- 함수 호출 시 런타임 스택이 사용됨 (actual params -> former params 넘겨줘야 함)

+ 함수는 only 1 copy 

- 함수의 반환 값은 호출 블록 반환 주소로 다시 가져와서 사용함 – 반환은 무조건 됨

 

* ab 계산하는 예제 (a만큼 계속 (b번) 더한다) 

- 첫 콜스택에서는 외부에서 이 함수를 호출하는 명령어의 주소 100을 저장함 (return adr)

- b가 0이 될 때 까지 1씩 줄이며, 재귀적으로 스택에 쌓아 호출함

- return 되면서 5씩 더해진 값이 넘어간다 -> 최종으로 10을 반환 (주소 100으로)

 

* Tail recursion 

- 함수가 단일 재귀 호출만 포함 + 함수에서 마지막으로 실행되는 명령문인 경우 

- tail recursion을 반복문으로 대체하여, 재귀를 제거할 수 있음 

 

* 언제 재귀를 사용하는 게 좋을까? 

- 재귀 호출의 깊이가 상대적으로 얕을 때 (깊으면 사용하면 X) 

- 비재귀(반복) 버전과 거의 같은 양의 작업을 수행할 때

- 재귀 버전이 비 재귀 솔루션보다 짧고 간결할 때 // 따라서 순차탐색은 비재귀가 올바름

 

* Quick Sort – n log n

- pivot을 기준으로 둘로 나눈다 – 내부 동작 중 재귀적인 구조가 있다

- 이상적으로 pivot이 중간 값으로 나올 경우 n log n, 최악의 경우(끝 값)  n^2

- 1번째 값을 (0번 index) pivot으로 잡고, 왼쪽에서부터 큰 값을 (안 어울리는) first로 탐색, 오른쪽 끝부터 pivot보다 작은 값을last로 찾아 swap

- last가 first보다 더 왼쪽에 있으면 (추월) -> 탐색 종료 // 전체 데이터에 대해 비교 완료 

- last와 pivot을 교체한다. 

 

- splitPoint로 나뉘기 때문에, 피보나치 수열과는 달리 문제 사이즈가 절반씩 줄어들어 효율

 

 

 

 

 

# 8. Binary Search Tree 

- Graph – Tree – Binary Tree – Binary Search Tree 

 

- root node – 최상위 node 

- leaf node - 자식 노드가 없는, 밑에 딸린 노드가 없는 노드 

- level – root는 level 0, root로부터 멀어질수록 level +1, 해당 깊이 depth를 의미 

- Tree의 높이는? Root부터 가장 아래의 leaf까지의 깊이 -> leaf의 level (높이)

* height = number of levels (최대 level이 3 -> height 0,1,2,3 -> 4)

 

* SubTree – 좌측 서브트리 – root node기준으로 좌측의 모든 노드와 엣지들

- 우측 서브트리 – root 기준 오른쪽 노드와 엣지들 (일부분도 가능)

 

* 이진 트리의 구조 Binary Tree (!= tree)

- 각 노드는 최대 2개의 자식 / 꼭 2개의 필요는 없다 

- 루트부터 다른 노드까지의 경로가 고유하다 (여러 경로, cycle 불가능 – 트리의 특성)

- n개의 node -> n-1개의 edge

 

* Binary Tree // 이진 트리라면, 꼭 정렬될 필요는 X 

- n개의 node로 구성된 tree의 최대, 최소 height – 최대 n-1, 최소 n = 2^(h+1) – 1 

Ex) 높이가 2라면, max로 들어갈 수 있는 node가 7개 

- N level tree가 가질 수 있는 최대 노드 수 = 2^n개 (가로 한 줄, 획을 의미) 

- level이 클 수록 탐색 효율은 줄어든다 

 

* class TreeType ADT -> BinarySearchTree – 드디어 정렬된 상태! 

* BinarySearchTree – 특별한 이진 트리

1) 각 노드에는 고유한 데이터 값이 존재

2) 트리의 키 값은 보다 큼과 보다 작음을 사용하여 비교 가능 

3) 각 노드의 키 값은 오른쪽 하위 트리의 모든 키 값보다 작고, 
왼쪽 하위 트리의 모든 값보다 큼 // 마치 루트 입장에서 내려다보면 

* Left tree < Right tree (왼쪽 아무 값 < 오른쪽 아무거나) 

 

- 치명적 단점 – 동일한 데이터도, 삽입 순서에 따라 효율이 달라짐

- 최악 – 1자 모양 (n개의 node와 n – 1 개의 edge)

- 동일한 data를 다루더라도, 깊이에 대한 balancing을 보장하지 않음 

 

+ 삽입할 값은 루트 노드와 비교하여, 더 작으면 왼쪽으로, 크면 오른쪽으로 이동하며 시작

- 새로운 leaf로 삽입될 때 까지 반복한다. 

 

* LengthIs 함수 – countNodes 

1) if ( (Left(tree) == NULL) and (Right(tree) == NULL)) -> 앞이 거짓이면, 뒤를 보지도 않음

-> Right tree가 호출되지 않는 문제 발생 

2) 전체 tree가 비었을 때에는 run time error 발생 

3) 지저분하고 중복되는 코드가 많다 

4) 최종 버전 

If tree is Null

return 0;

Else 

             Return CountNodes(Left(tree)) + CountNodes(Right(tree)) + 1

             // 마지막은 root 개수 추가 

             // 재귀 호출이 내부에 구현된 lengthIs 함수

 

* Binary Search Tree의 장점 – 탐색 효율 

- retrieve 시, ptr->left와 ptr->right 로 나누어 if else구문으로 한 번 호출 Retrieve

- 재귀의 interface 역할로, Wrapper 함수가 사용된다. 

- i = info[midpoint]를 찾는 것이 목적

 

* Binary Search Tree – Insertion -  *& ptr 

- leaf 노드의 우측 or 좌측으로 새로운 node가 동적 할당되어 들어가야 함 

- 해당 포인터에 동적할당 값이 들어가야 한다 -> *& ptr 사용

- 포인터의 참조 변수 전달

 

Void Insert (TreeNode <itemType> * & ptr, itemType item) 

- ptr = new TreeNode <itemType>

 

- & 이 없다면, 주소값 *ptr 이 지역 변수로 전달된다 -> 동적 할당은 해 두었는데, 가리키는 포인터가 유실됨 (지역 변수는 함수 종료 시 사라지기 때문에)

– 따라서 자식 노드를 가리킬 ptr을 참조 변수로 넘기는 것 

- 포인터형 변수의 참조 변수를 가져오겠다! 

 

* Delete – 좌측 subtree 중 가장 큰 우측 값을 찾는다 (나와 가장 유사한, 작은 값)

- root와 가장 유사한 값 – root와 node의 위치를 교환해도, 트리가 유지됨 (delete 시)

 

* 순회 방식 3가지 

// 기준 – 중간 (root)가 언제 스치냐!

// 항상 left는right보다 먼저 처리됨

// 기본적으로 순회는 재귀 구문이 활용된다. 

 

1) Inorder Traversal – 왼쪽 – 중간 – 오른쪽 

- Print (ptr -> left, outFile)

- outFile << ptr -> info ;

- Print (ptr -> right, outFile)

 

// 실행문의 위치가 중요하다 – 좌측 하단부터 / 가운데 출력 / 우측 subtree 출력 

// 정렬된 순서대로 print 할 때, inorder 적합하다. 

 

2) Preorder Traversal – 중간 – 왼쪽 – 오른쪽 

- outFile << ptr -> info;

- Print (ptr -> left, outFile);

- Print (ptr -> right, outFile);

 

// 대입 연산자, 복사 생성자 등 차근차근 생성 시, root 부터 접근해서 생성할 때 

// 가장 첫번째 줄에 데이터를 처리하는 Out file 코드를 둔다. 

 

3) Postorder Traversal

- Print (ptr -> left, outFile);

- Print (ptr -> right, outFile);

- outFile << ptr -> info;                            // delete ptr ; 

 

// delete – 말단 노드부터 접근하여 처리 (삭제) 

 

 

 

 

 

# 9. Complete tree, Heap, Priority Queue, Graph

* Binary Expression Tree 

- leaf 노드에는 operand (피연산자, 숫자), 비 leaf node에는 operator(단일 이진 연산자)

- 왼 or 오 subtree -> root에서 연산자를 표현하기 전, 먼저 계산되어야 하는 수식 

- 트리의 Level – 상대적 평가 우선순위 (연산 우선순위) – 소괄호가 없어도 우선순위 표현 O

- 더 높은 수준의 트리에서의 계산은, 그 아래 작업보다 나중에 계산됨 / 루트에서의 계산은 항상 마지막으로 계산된 내용 (아래에서부터 위로 올라가면서 계산)

 

* root ( - ) , 왼쪽 Leaf 8, 오른쪽 leaf 5인 상황 

// root의 위치를 기준으로 판별하기

- inorder –> 8 – 5 (사람이 읽는 순서, 연산자가 가운데 위치)

- preorder -> - 8 5 (스택으로 처리 가능, 먼저 삽입된 연산자가 나중에 처리)

- post -> 8 5 – (Queue로 처리, 나중에 삽입된 연산자가 나중에 처리)

 

* Infonode – union type 

- 메모리 공간을 공용으로 씀 -> 가장 큰 타입 기준으로 저장 

- 타입에 따라 해석을 달리하는 것 – operator -> 4 byte 중 char니까 1 byte만 가져옴

- binary tree -> 좌 우(각각 하위 subtree root node)로 link 됨

- 재귀 호출을 통해 subtree로 내리며 처리, 내부적으로 재귀는 stack 사용 

- 컴파일러에서 syntax error 검사 시 사용한다. 

 

* Full binary tree – 완벽한 삼각형 구조 – 풀 이진 트리 

- 모든 데이터에 대해 성립하지 X (only 2^n – 1 개만 수용)

- 모든 리프 노드가 같은 level, 모든 비 리프 노드에는 2개의 자식이 있는 이진 트리

 

* Complete binary tree – 완전 이진 트리

- 마지막 level의 리프 노드는 가능한 한 왼쪽에 위치 

- 데이터 수와 무관하게 언제나 성립 가능 

- 마지막 level 제외한 윗부분은 full binary tree

 

* Heap 

- Complete binary tree (완전 이진 트리) 

- 각 node들에 대해, 하위의 값보다 크거나 같음 (부모 >= 자식)

- root가 가장 큰 값 -> max heap 

- root가 가장 작은 값 – min heap (데이터에 - 취해서 max heap으로 처리하면 됨)

// 전체 데이터 중 가장 큰 값을 원한다면 root를 꺼내오면 됨

 

* 우선 순위 큐로 여긴다면? 

- 선입선출 (FIFO) – 기존 큐 

- 응급실에서의 상황 – 우선순위 순서로 처리 / 도착 순서와 무관 

-> root의 max 값이 우선순위가 가장 높은 것으로 판별한다면, (응급 환자) key 값

-> 여기에 다양한 값들이 node에 딸려오는 것

 

* Linked list vs array

1) 배열의 단점 

– 치우친 tree 모양 -> complete binary tree로 해결 가능 

- 빈 공간이 남는다 – 메모리 낭비 -> heap이면 complete binary tree – 낭비가 거의 X

 

2) 배열의 장점 – index random access 가능 (indirection 연산X) 

- root * 2 + 1 -> 왼쪽 left subtree root 

- root * 2 + 2 -> 오른쪽 right subtree root

-> 자기 인덱스 * 2 + 1 = 왼쪽 자식, *2+2 = 오른쪽 자식

- 부모 인덱스로 가고 싶다면? == (자기 인덱스 – 1) / 2

 

+ complete binary tree는 높이가 가장 최소가 되도록 형태 유지 – 비교 연산 효율적 

 

* insertion (새 element 71 추가, Enqueue) 

– 우선 제일 하단 (우하단)에 배치 

- heap이라는 특성이 깨지면 안 됨

- 부모와 자식의 값을 비교한 후, 자식이 더 크면(부모가 나보다 작으면), 서로 위치 바꿈
// (조상과 비교하려고) 위로 차근차근 올라가는 과정 // ReheapUp

 

* delete (max element, root 제거 과정, Dequeue)

- 우하단 값 12(min은 아닐 수 있음)와 root를 교체함 (root는 사라진 것) 

- 끌어올린 작은 값 root에서 leaf 방향으로 내리며, 적절한 값을 찾음

- 자신의 좌측, 우측 자식 node 중 더 큰 값과 swap (maxchild보다도 root가 클 경우 멈춤)
// (손자와 비교하려고) 아래로 내려가는 과정 // ReheapDown

// 새로운 root가 maxChild

 

+ 이때 tail recursion -> 반복문으로 구현할 수 있다. 

- 함수 호출에 들어가는 overhead를 줄일 수 있다. 

 

* Priority Queue (max heap 기반)

- 우선순위 큐 – 언제나 가장 높은 우선 순위의 요소에만 엑세스 가능한 특성을 가진 힙

- array 배열 기반 구현 – 전체 크기/한도 저장 (배열이라 max index need)

 

* Dequeue – 0번째 index를 제거 – root node (즉 pritority가 가장 높은 요소 제거)

- 가장 우측 하단의 Leaf를 root로 올리고, length 1 줄임 

- ReheapDown (힙의 특성을 유지하기 위해, min root를 내려가며 적절한 leaf로 위치 조정)

 

* Enqueue – length를 1 늘리고, 새로운 요소를 배열 끝에 저장 

- ReheapUp (힙의 특성을 유지하기 위해, root에 도달하거나, 적당한 부모를 만날 때 까지 위치 이동) 

 

* Priority Queue를 구현할 때, heap 말고 다른 자료구조를 사용할 때 (9 – 39p.g)

- complete binary tree (max) – logN (enqueue, dequeue 효율) 

- linked list – N

- Binary Search Tree (아직 complete binary tree는 아니기에, 크키 개념 O, but 모양 개념 X)

-> data가 고르게 분포될 경우 (logN, heap과 동일) / 최악의 치우친 경우 N (순차탐색 same)

 

* Graph – 그래프 자료구조

- 노트 세트와 edge 세트로 구성된 데이터 구조 

- G = [ V, E ] / V(G) = 유한하고, 비어 있지 않은 정점 세트 (그래프의 node들의 집합) 

                   E(G) = edge들의 집합

- 정점 – vertex – 그래프의 노드 

- edge or 호 – 그래프의 노드 간 연결을 나타내는 정점 쌍 (방향성을 가지면 arc) 

                  - 시작과 끝 node들의 쌍 -> edge  ex) (1, 2) – node 1과 2를 연결하는 edge

 

- 그래프 > 트리 (그래프가 더 범용적인 알고리즘) 

- 유향 그래프 > 무향 그래프 (유향이 더 범용적)

* 유향 그래프 – 엣지에 방향성이 없는 그래프 (undirected graph)

* 무향 그래프 – 각 모서리가 한 정저에서 다른 정점으로 향하는 그래프 (directed graph)

-> 비방향 edge를 양방향으로 처리하면 됨, 방향성 그래프가 더 범용적이다. 

 

- 인접 정점 – 하나의 edge로 연결된 두 그래프의 node (vertex)들 (바로 연결된 것만 해당)

- 경로 path – 그래프에서 두 개의 노드를 연결하는 일련의 vertex, 노드들의 나열 

- Complete Graph – 가능한 모든 edge가 존재하는 그래프 // 모든 정점이 다른 정점에 직접 연결된 그래프 (모든 경우의 수가 존재하는 경우 의미 -> K)

- 가중 그래프 – Weighted Graph – 각 edge에 값이 있는 그래프 

* Weighted 그래프가 더 범용적 (unweighted -> 모두 동일한 Weight를 주면 되니까)

-> 정보가 소실되면 안된다는 관점에서 범용성을 check하면 쉬움 

 

- Complete Graph – 완전 그래프

- edge의 수 계산 = n ( n-1 ) / 2  // N^2에 비례

-> 비방향성을 고려하여 나누기 2, 방향성 그래프라면 서로 다른 경우라 n ( n-1 )

- K(4) -> 항상 네모 + 12개의 edge 모양 고정 (4 * 3, 방향성 고려 시) Complete directed G

 

+ GetToVertices – 자주 호출할 함수 

- vertex에 인접한 vertex(노드)들을 큐에 리턴 

 

* 우선 탐색 정리 // 사용하는 자료구조가 다르다

1) DFS - 깊이 우선 탐색 – stack

- post order와 같이, 트리의 가장 밑까지 내려간 다음, 올라오며 방문

2) BFS – 너비 우선 탐색 – queue

- level 별로 내려가면서 차례대로 방문 

3) 최고 우선 탐색 – priority queue 사용

- shortest path 탐색 시 활용, min heap 활용 (음수를 취해라)

- 최단 경로 탐색 -> 알고리즘 시간에 (정확하진 않음) 

 

+ cycling이 방지할 수 있기 때문에, 방문한 vertex를 mark해야 한다.

- 방문 여부를 저장할 flag 필요

- clear mark (초기화), mark vertex (마크하는 메소드), ismarked (마크 여부를 체크)

 

* Array implementation – 그래프를 컴퓨터로 구현할 때 

1) 인접 행렬 (array 차원, Matrix 2차원 array로 구현)

- N개의 노드, vertex들로 구성된 그래프를 N*N adjacency matrix로 구현 

- 1 -> edge가 있다, 0 -> edge가 없다 

- 단점: edge가 없는 것들에 대해서도 모두 0이라는 정보를 저장해야 함 -> 낭비 심함 

 

2) 인접 리스트 – adjacency list 

- 값이 존재하는 도시 간 edge weight를 저장 – 메모리 효율 장점

- 하지만 여러 도시가 연결된 경우, vertex 하나 탐색하는데 (ex) 시카고와 아틀란타 연결됨?) 시카고와 연결된 100개의 node 전체를 indirection 연산으로 찾아봐야 한다. -> 비효율

 

* 그래프에서 주어진 데이터의 형태에 따라 인접 행렬 / 리스트 잘 판단하면 됨 

1) 완전 연결 graph – 매우 dense한 밀도 빽빽

- node 대비 edge 비율이 매우 높다. Matrix 표현 시 낭비되는 데이터가 거의 없다

- dense 할수록, matrix에서 유효함 == data (1) 저장

 

2) Sparse – tree와 유사한 그래프 형태

- node n개 -> edge n – 1 개 (최소한의 경우)

- edge 개수가 최소인 그래프 (한 줄 형태) 

- matrix – 메모리 공간 낭비, 효율도 낮음

- 이런 경우에는 인접 리스트 형태가 탐색 효율도 좋다. 

 

 

 

 

 

# 10. 정렬 탐색 알고리즘, Hash

- 정렬의 기준 – 고유키를 가정함 (unique key)

- 배열에 저장된 값에는 관계 연산자가 정의된 유형의 Key가 있음

- 키 값의 크기를 비교할 수 있어야 정렬이 가능함 

- 정렬은 배열 내 요소를 오름차순 or 내림차순으로 재 배열 

 

1. 선택 정렬 – selection sort 

- 배열을 정렬된 부분과 정렬되지 않은 부분으로 나눈다.

- 정렬되지 않은 부분 중 가장 작은 요소를 찾아, 정렬된 part에 추가 

- smallest 값을 찾을 때, 언제나 n – 1 번의 비교 연산이 필요 

-> 최악과 최선의 경우 차이가 없다. (무조건 끝까지 다 봐야 제일 작은 값 찾음)

 

+ N개의 요소로 이루어진 배열을 정렬 시 비교 연산 횟수 

Sum = (n – 1) + (n – 2) + … + 2 + 1 = N (N – 2) / 2 

=> O(N^2) // 0.5 계수는 의미 없음, 비교 연산을 단위 연산으로 할 때의 big-O

 

2. 버블 정렬 – bubble sort 

- 마지막 배열 요소부터 시작 (아래에서부터 시작), 인접 요소 쌍을 비교하여 swap

- 비교하여 작은 요소가, 올바른 위치로 버블 업 된다. (swap이 자주 발생한다)

- 위에서부터 하나씩 요소의 위치를 고정시켜 나간다. 

- 다른 구현 방식 -> swap이 한 번도 일어나지 않았다면 이미 정렬된 상태라는 의미 

-> Boolean으로 flag를 통해 정렬 마무리 -> 이걸 위해서 사용하는 것

 

3. 삽입 정렬 – insertion sort 

- 각 path에서 정렬된 요소가 1 씩 증가 // Sorted 영역이 한 칸 씩 늘어나는 것

- 새로운 카드를 이미 분류된 카드들 사이에 삽입하는 사람처럼 행동  

- 선택 정렬과 헷갈림 -> 선택 정렬은 min 값을 찾아 올림 / 삽입 정렬은 그냥 올림

 

* Sorting Algorithms and average case number of comparison -> 장 이름이 긴 이유 주의!

- Quick Sort 때문에 평균이라는 단어가 사용된 것 (평균 NlogN, 최악 N^2)

+ 정렬 알고리즘 – 동일한 input에 대한 동일한 output (정렬 시간, 효율만 다른 것)

 

1) Simple Sort (N^2) 

- selection sort / bubble sort / insertion sort 

2) more complex sort (NlogN)

- Quick sort / Merge sort / Heap sort 

 

4. 힙 정렬 – Heap Sort 

- 힙은 독특한 binary tree 1) complete binary tree 
2) 각 노드에 저장된 값이 하위 값보다 크거나 같음

 

- max 값 – root를 뜯어냄 – heap의 특성을 유지시킨다 – 다시 root를 빼냄 -> 정렬 완료

- heap을 복원하는 연산이 log N , 이걸 각 root마다 매번 -> N * logN 

* ReheapDown (delete와 연관) -> heap의 구조를 유지하기 위한 불필요한 추가 연산 들어감

-> 다른 nlogn에 비해 조금 느린 이유 

 

+ 먼저 주어진 배열을 heap으로 만들어야 한다. 

- 정렬이 완료된 이후, 최종 모양이 min heap으로 바뀐다. 

 

* heap을 비정렬 배열로 변환하는 과정 – 전체 데이터를 일단 다 아는 상태

- 일단 complete binary tree로 바로 배치한다

- 각각의 subtree가 heap이 되도록 level을 증가시켜가며 처리 

- 각 root를 reheapdown / root node에 대한 처리만 하면 되기에 효율 높음

- leaf node의 level부터 올라가면서 heap을 구성한다. (맨 밑 줄은 날리고 시작)

 

* heap sort는 비교 연산이 (reheapdown) logN 복잡도를 갖는다. -> N회 수행 -> NlogN

- 깊이 자체가 logN 

- 힙 만들기 NlogN, 정렬 알고리즘에서의 비교 총 과정 NlogN

 

5. 퀵 정렬 – Quick Sort

- pivot을 기준으로, 절반으로 나누며 재귀적으로 정렬

- splitVal – 가장 작거나 가장 큰 값이 잡히면 정렬 효율 매우 떨어짐 

- splitVal 왼쪽에는 splitVal보다 작은 모든 값, splitVal 오른쪽에는 큰 모든 값이 위치

- 이후 각각의 첫번째 요소를 (0번 index) splitVal로 지정하여 쪼개진 2 재귀 구문으로 처리

 

* 다른 정렬 알고리즘에 비해 퀵소트가 빠름 -> cache hit 때문에

- 배열의 같은 부분을 참조할수록 cache hit 할 확률 높아진다

- merge sort 경우에는 새 배열을 할당함 -> 참조 확률 낮아짐 

- heap sort는 heap 구조를 유지하는 것에서 비효율 발생 

-> Quick sort가 가장 성능이 우수함 (평균적 상황에서)

 

6. 병합 정렬 – merge sort

- 2개의 size로 쪼개어, 배열의 왼쪽 절반 정렬 / 오른쪽 절반 정렬 / 이후 하나로 병합

- 작게 나뉜 값들의 비교는 매우 쉽다 -> 이후 정렬 된 두 배열에서 가장 작은 값을 꺼내어 상위 배열 정렬 -> 한쪽 하위 배열이 비면, 뒤는 싹 다 복붙 – 이미 정렬된 상태니까

- 한 하위 배열이 빌 때 까지는, 서로 값들을 비교해가며 삽입 

 

+ std sort -> quick sort // 제자리 정렬 – stable sort -> merge sort 

 

+ 위의 6가지 상태로 배열이 정렬된 상태에서 탐색 -> 이진 탐색 

(비정렬 data = 순차 탐색)

- 이진 탐색도 절반씩 나누어 찾아, 재귀 구문이 2개로 보이지만, 조건문을 걸어, 실제로는 1회만 호출된다. 

- tail recursion -> 반복문 변경 가능 (인덱스에 대한 변수를 선언해두고, 절반씩 진행하며 변경)

 

* Stablity & inplace

1) Stablity - 중복되는 값이 있을 때, 정렬 후에도 입력 순서가 유지되는가? Or 뒤집어지는가? 

- heap sort와 quick sort는 뒤집어진다 (unstable sort, 선택, 퀵, 힙)

- merge sort는 stable sort (버블, 삽입, 병합) 

 

2) inplace 제자리 정렬 – 추가적인 메모리 필요 X 정렬 

- 입력되는 데이터의 개수에 비례하여 추가적인 메모리가 필요한 경우 -> merge sort 

 

* Hashing 

- O(1) = 입력 데이터와 무관하게, 상수 시간이 걸린다. 

- 키 값의 함수를 사용하여, 목록의 요소를 빠르게 정렬하고 접근하는 데 사용되는 수단

- 키 값의 function을 해시 function이라고 한다. 

- 보통 전체 size로 나눈 나머지를 구하는 방법으로 Hash function 설정한다.

-> 이미 사용하고 있는 위치에 접근하여 collision이 발생하면? 

 

1) Closed hashing – 데이터 범위 한정된 해시 

2) Open hashing – 데이터 범위 제한 X, open

 

* linear probing 

- Closed hashing에서 충돌을 해결하는 대표적인 방법, rehash 기능 

- 단순하게 1칸 증가하여, 다음 위치로 보낸다 //  (hashValue + 1) / 100

 

* 문제 – rehash 된 값이 삭제될 경우? -> deleted flag를 남겨줌

- 값이 없는 상태라면, 빈 상태로 두면 뒷부분을 더이상 찾지 않음 

- deleted로 뒤의 값을 보게 한다 (linear probing의 가능성이 있으니) 

-> flag나 아니면 값을 한 칸 씩 당기는 방법이나 둘 다 썩 좋지 X -> 오픈 해싱 처리 

 

* Open Hashing의 대표적인 처리 방법 2가지 (bucket, chain) 

1) bucket 

- 하나의 key 값에 대해, array matrix의 형태로 여러 값을 저장할 수 있도록 변경 

- key index 당 하나의 값만 저장 가능했던 1차원 대신, 2차원 array를 쓰는 것

- 무의미한 empty 빈 공간이 많이 발생한다. 유동적인 값의 추가도 어렵다 

 

2) chain

- linked list로 구현 – 동일한 hash (key)값에 대해, 새로운 요소가 추가 시 동적으로 할당

- 값이 치우칠 경우 (하나의 key에 많은 요소가 추가될 경우) indirection 연산 많아짐

 

+ hash function 최적화? (중복되는 key 값이 없도록)

- 하지만 hash func을 복잡하게 만들 순 없다

 

+ 기수 정렬 (Radix 정렬) 

- 주어진 조건이 더 많을 경우 사용 가능하다. (이 정보를 통해 성능을 더 높이는 것)

- 동일한 자릿수의 데이터들에 대해 적용