DNF LOVE

4. 정렬 알고리즘(Sorting Algorithm)의 모든 것 - 힙 정렬(Heap Sort) : 힙 정렬이란, 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서, 내림차순 정렬을 위해서는 최대 힙을 구성하고, 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다. ** 잠깐의 자료구조 지식, Heap이란? -> 힙이란, 최소값이나 최대값을 빠르게 찾아내기 위해(우선순위 큐) 완전 이진 트리를 기반으로 하는 트리 구조를 갖는 자료구조이다. >1. n개의 노드에 대한 완전 이진 트리를 구성한다. 이때 루트 노드부터 부모 노드, 왼쪽 자식 노드, 오른쪽 자식 노드 순으로 구성한다.2. 최대 힙을 구성한다. 최대 힙이란 부노드가 자식 노드보다 큰 트리를 말하는데, 단말 노드를 자식 노드로 가진 부모..

정렬 알고리즘의 세 번째 이야기, 퀵 정렬(Quick Sort) 3. 정렬 알고리즘(Sorting Algorithm)의 모든 것 ③ - 퀵 정렬(Quick Sort) : 퀵 정렬은 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. 퀵 정렬은 분할 정복 방법을 통해 리스트를 정한다.1. 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 '피벗'이라고 한다.2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.3. 분할된 두 개의 작은 리스트에 대해 재귀(Recursion)적으로 이 과정을 ..

2. 정렬 알고리즘(Sorting Algorithm)의 모든 것 ② - 선택정렬 : 선택 정렬(Selection Sort)은 다음과 같은 순서로 이루어진다. (출처 - 위키백과)1. 주어진 리스트 중에 최소값을 찾는다.2. 그 값을 맨 앞에 위치한 값과 교체한다.3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. - 선택정렬 역시 버블 정렬과 동일하게 최악의 경우일 때 O(n^2)만큼의 시간복잡도를 갖는다.- 버블정렬과 동일하게 쉬운 개념의 알고리즘이며, 사용할 수 있는 메모리가 제한적인 경우에 사용 시 성능 상의 이점이 있을 수 있다. > 인덱스 크기가 9이고 각 인덱스에 정렬되지 않은 정수가 들어있는 배열이 있다고 했을 때, 이런식으로 마지막 하나의 원소가 남을 때 까지 반복하다 보면 ..