Joseph's Daily Life Joseph's Daily Life

https://www.youtube.com/watch?v=i4mdSVTjpHY 사용언어는 C++이며 Wilson's Algorithm을 사용하여 마우스 클릭할 때마다 랜덤으로 미로가 생성되도록 만들었습니다.

오늘은 힙 정렬에 대해 공부하였습니다. 힙 정렬을 알기 전에 먼저 이진트리와 힙에 대해 알아야 합니다. [이진트리] 이진트리란 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료구조로 자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 합니다. 완전 이진트리란 이진트리에서 자식 노드들이 왼쪽부터 차곡차곡 채워져 있는 트리를 말하며 완전 이진트리는 마지막 레벨을 제외하고 노드가 모두 채워져 있어야 합니다. 마지막 레벨도 왼쪽부터 채워져 있어야 합니다. 포화 이진트리란 리프 노드를 제외하고 모든 노드들이 2개의 자식 노드를 가집니다. 또한 노드는 왼쪽에서 오른쪽으로 채워져 있습니다. 리프 노드란 자식이 없는 맨 끝에 있는 노드를 말합니다. [힙] 힙 정렬에는 힙을 사용하게 되는데 힙이란 최댓값 ..

병합 정렬은 합병 정렬이라고도 불리며 존 폰노이만이 개발하였습니다. 퀵 정렬과 같이 분할 정복 알고리즘의 하나입니다. [병합 정렬의 과정] 1. 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 2. 그렇지 않은 경우에는 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 3. 각 부분 리스트를 재귀적으로 병합 정렬을 이용해 정렬한다. 4. 두 부분 리스트를 다시 하나의 정렬된 리스트로 병합한다. 병합 정렬에 대해 조금 더 쉽게 설명하자면 1. 먼저 분할 과정을 통해 리스트에 원소가 1개 남을 때까지 분할을 합니다. 2. 새로운 리스트에 2개의 리스트를 비교해가며 작은 값을 넣어줍니다. 3. 둘 중에 하나가 끝날 때까지 반복합니다. 4. 하나가 먼저 끝나면 나머지 리스..

퀵 정렬은 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘으로 분할 정복을 통해 리스트를 정렬합니다. [퀵 정렬 과정] 1. 리스트 가운데서 하나의 원소를 고릅니다. 이렇게 고른 원소를 피벗(pivot)이라고 합니다. 2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눕니다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 합니다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않습니다. 3. 분할된 두 개의 작은 리스트에 대해 재귀적으로 이 과정을 반복합니다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복합니다. 위 그림을 바탕으로 설명하자면 1. 피벗을 정합니다. 2. 앞에서부터 인덱스를 검사하면서 피벗보다 큰..

삽입 정렬이란 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘입니다. 그림과 같이 두 번째 인덱스부터 왼쪽으로 검사하며 자신이 들어갈 위치를 찾아 들어간다. 삽입 정렬의 시간 복잡도는 최악의 경우 O(n^2) 최선의 경우 O(n) 평균 O(n^2)입니다. 삽입 정렬은 거의 다 정렬이 되어 있거나, 정렬이 다 되어있는 경우에는 정말 빠릅니다. 그래프를 보면 평균적으로 청록색 선의 그래프 모양을 띄고, 최선의 경우 초록색 선의 그래프 모양을 띕니다. [C언어 코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 ..

버블 정렬이란 두 인접한 원소를 검사하여 정렬하는 방법입니다. 쉽게 말해, 옆 인덱스와 비교를 하여 값이 더 큰 데이터를 앞이나 뒤로 보내는 정렬 방법입니다. 버블 정렬은 그림에서 보듯이 거품이 올라오는 것처럼 보인다고 하여 버블 정렬이라고 불립니다. 위 그림은 버블 정렬의 정렬 방법 및 순서를 나타낸 것입니다. 왼쪽 인덱스의 데이터가 오른쪽 인덱스의 데이터보다 크다면 스왑 하여 큰 수를 뒤로 보내는 방식을 반복합니다. 버블 정렬의 시간 복잡도는 선택 정렬과 마찬가지로 인덱스가 n 개라고 했을 때 O(n^2)이 나옵니다. 그래프에서는 청록색입니다. 따라서 버블 정렬 또한 n의 값이 커질수록 걸리는 시간이 기하급수적으로 늘어나므로 비효율적인 정렬 알고리즘입니다. 1 2 3 4 5 6 7 8 9 10 11 ..

선택 정렬(Selection Sort)이란 간단하게 얘기하자면 배열에서 가장 작은 것이나 가장 큰 것을 찾아 앞으로 보내는 정렬 방법이다. 이미지와 같이 정렬되지 않은 데이터 중에서 최솟값을 찾아 앞으로 보내준다. 시간 복잡도를 계산해보면 배열의 인덱스 개수가 n 개라고 했을 때 O(n^2)이 나온다. 그래프에서는 청록색이다. 따라서 n의 값이 커질수록 걸리는 시간이 기하급수적으로 늘어나므로 비효율적인 정렬 알고리즘이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 #include void SelectionSort(int data[], int si..