알고리즘
-
힙 정렬 (Heap Sort) 힙은 완전 이진트리 기반의 트리형 자료구조로써 최댓값이나 최솟값을 찾아내기 위해 사용됩니다. 힙에는 최대 힙과 최소 힙이 존재합니다. 최대 힙은 부모 노드의 키가 자식 노드의 키보다 같거나 큰 완전 이진 트리이며 최소 힙은 자식 노드의 키가 부모 노드의 키보다 같거나 큰 완전 이진 트리입니다. 힙 구조 생성과 최대 힙 연산에 관해서는 아래 포스팅에서 자세히 설명하였으니 참고하시기 바랍니다. https://yjg-lab.tistory.com/143?category=932096 [자료구조] 우선순위 큐 (priority queue), 히프의 삽입과 삭제 우선순위 큐 (priority queue) 우선순위 큐는 우선순위를 가진 항목들을 저장하는 큐입니다. 일반적으로 큐는 선입선출..
[알고리즘] 힙 정렬 알고리즘 (Heap Sort)힙 정렬 (Heap Sort) 힙은 완전 이진트리 기반의 트리형 자료구조로써 최댓값이나 최솟값을 찾아내기 위해 사용됩니다. 힙에는 최대 힙과 최소 힙이 존재합니다. 최대 힙은 부모 노드의 키가 자식 노드의 키보다 같거나 큰 완전 이진 트리이며 최소 힙은 자식 노드의 키가 부모 노드의 키보다 같거나 큰 완전 이진 트리입니다. 힙 구조 생성과 최대 힙 연산에 관해서는 아래 포스팅에서 자세히 설명하였으니 참고하시기 바랍니다. https://yjg-lab.tistory.com/143?category=932096 [자료구조] 우선순위 큐 (priority queue), 히프의 삽입과 삭제 우선순위 큐 (priority queue) 우선순위 큐는 우선순위를 가진 항목들을 저장하는 큐입니다. 일반적으로 큐는 선입선출..
2021.07.07 -
병합 정렬 알고리즘(Merge Sort) 병합 정렬은 데이터 배열을 정확히 반으로 나누고 나중에 합쳐서 정렬하는 방식입니다. 정확하게 5:5로 나누기때문에 피벗(Pivot)이 존재하지 않습니다. 8 2 6 5 1 4 2 7 위와 같은 수가 있을 때 수들을 오름차순하는 병합 정렬을 해보겠습니다. 8개의 데이터를 나눌 수 없을때까지 반으로 나누면 크기가 1인 배열로 나누어집니다. 8 | 2 | 6 | 5 | 1 | 4 | 2 | 7 나누는 과정이 끝났다면 이제 데이터를 2의 배수만큼 합치고 합치는 순간 각각을 정렬합니다. 1차 합 : 2 8 | 5 6 | 1 4 | 2 7 2차 합 : 2 5 6 8 | 1 2 4 7 3차 합 : 1 2 2 4 5 6 7 8 알고리즘 구현 // Algorithm Analysi..
[알고리즘] 병합 정렬 알고리즘 (Merge Sort)병합 정렬 알고리즘(Merge Sort) 병합 정렬은 데이터 배열을 정확히 반으로 나누고 나중에 합쳐서 정렬하는 방식입니다. 정확하게 5:5로 나누기때문에 피벗(Pivot)이 존재하지 않습니다. 8 2 6 5 1 4 2 7 위와 같은 수가 있을 때 수들을 오름차순하는 병합 정렬을 해보겠습니다. 8개의 데이터를 나눌 수 없을때까지 반으로 나누면 크기가 1인 배열로 나누어집니다. 8 | 2 | 6 | 5 | 1 | 4 | 2 | 7 나누는 과정이 끝났다면 이제 데이터를 2의 배수만큼 합치고 합치는 순간 각각을 정렬합니다. 1차 합 : 2 8 | 5 6 | 1 4 | 2 7 2차 합 : 2 5 6 8 | 1 2 4 7 3차 합 : 1 2 2 4 5 6 7 8 알고리즘 구현 // Algorithm Analysi..
2021.07.06 -
퀵 정렬 알고리즘 (Quick Sort) 퀵 정렬은 특정 데이터를 기준으로 큰 데이터와 작은 데이터를 서로 교환한 후 배열을 두 집합으로 나누는 방식의 알고리즘입니다. 기준이 되는 특정한 데이터, 즉 기준점을 피벗(Pivot)이라고 하며 일반적으로 첫번째 원소를 먼저 피벗으로 지정합니다. 퀵 정렬 알고리즘은 한번 과정을 이해하면 어렵지 않은 알고리즘이기에 정렬 과정을 자세히 풀이하겠습니다. 4 9 1 6 11 10 3 15 2 13 위와 같은 수가 있을 때 수들을 오름차순하는 퀵 정렬을 해보겠습니다. 먼저 피벗 값은 4로 시작하여 4를 기준으로 왼쪽부터 큰 값을 찾고 오른쪽 부터 작은 값을 찾는 과정을 수행합니다. 4 9 1 6 11 10 3 15 2 13 4 2 1 6 11 10 3 15 9 13 큰 ..
[알고리즘] 퀵 정렬 알고리즘 (Quick Sort)퀵 정렬 알고리즘 (Quick Sort) 퀵 정렬은 특정 데이터를 기준으로 큰 데이터와 작은 데이터를 서로 교환한 후 배열을 두 집합으로 나누는 방식의 알고리즘입니다. 기준이 되는 특정한 데이터, 즉 기준점을 피벗(Pivot)이라고 하며 일반적으로 첫번째 원소를 먼저 피벗으로 지정합니다. 퀵 정렬 알고리즘은 한번 과정을 이해하면 어렵지 않은 알고리즘이기에 정렬 과정을 자세히 풀이하겠습니다. 4 9 1 6 11 10 3 15 2 13 위와 같은 수가 있을 때 수들을 오름차순하는 퀵 정렬을 해보겠습니다. 먼저 피벗 값은 4로 시작하여 4를 기준으로 왼쪽부터 큰 값을 찾고 오른쪽 부터 작은 값을 찾는 과정을 수행합니다. 4 9 1 6 11 10 3 15 2 13 4 2 1 6 11 10 3 15 9 13 큰 ..
2021.07.06 -
삽입 정렬(Insertion Sort) 삽입 정렬은 필요할 때만 각 데이터를 적절한 위치에 삽입하는 정렬입니다. 무조건 위치를 교환하는 선택 정렬과 버블 정렬에 비해 다소 효율적이라고 볼 수 있습니다. 1 9 4 6 11 10 3 15 2 13 위와 같은 수가 있을 때 수들을 오름차순하는 삽입 정렬을 해보겠습니다. 삽입 정렬의 경우, 앞에 있는 원소들이 이미 정렬되어 있다고 가정합니다. 1 9 4 6 11 10 3 15 2 13 1 9 4 6 11 10 3 15 2 13 1 4 9 6 11 10 3 15 2 13 1 4 6 9 11 10 3 15 2 13 . . . 1은 앞의 원소가 없으므로 삽입할 위치가 없어 그대로 남습니다. 그 다음 원소인 9는 앞의 원소에서 대소를 비교하여 적절한 위치에 삽입할 수..
[알고리즘] 삽입 정렬 알고리즘 (Insertion Sort)삽입 정렬(Insertion Sort) 삽입 정렬은 필요할 때만 각 데이터를 적절한 위치에 삽입하는 정렬입니다. 무조건 위치를 교환하는 선택 정렬과 버블 정렬에 비해 다소 효율적이라고 볼 수 있습니다. 1 9 4 6 11 10 3 15 2 13 위와 같은 수가 있을 때 수들을 오름차순하는 삽입 정렬을 해보겠습니다. 삽입 정렬의 경우, 앞에 있는 원소들이 이미 정렬되어 있다고 가정합니다. 1 9 4 6 11 10 3 15 2 13 1 9 4 6 11 10 3 15 2 13 1 4 9 6 11 10 3 15 2 13 1 4 6 9 11 10 3 15 2 13 . . . 1은 앞의 원소가 없으므로 삽입할 위치가 없어 그대로 남습니다. 그 다음 원소인 9는 앞의 원소에서 대소를 비교하여 적절한 위치에 삽입할 수..
2021.07.05 -
버블 정렬 알고리즘 (Bubble Sort) 버블 정렬은 옆에 있는 데이터와 비교하여 더 작은 값을 앞으로 보내는 정렬입니다. 1 9 4 6 11 10 3 15 2 13 위와 같은 수가 있을 때 수들을 오름차순하는 버블 정렬을 해보겠습니다. 먼저 배열의 맨 앞부터 두 수씩 비교합니다. 1과 9를 비교하여 1이 더 작으므로 1을 정렬합니다. 그 다음 9와 4를 비교하여 4가 더 작으므로 9와 4의 위치를 교환하고 4를 정렬합니다. 그 다음 9와 6을 비교하여 6이 더 작으므로 9와 6의 위치를 교환하고 6를 정렬합니다. 그 다음 9와 6을 비교하여 6이 더 작으므로 9와 6의 위치를 교환하고 6를 정렬합니다. 1 9 4 6 11 10 3 15 2 13 1 4 9 6 11 10 3 15 2 13 1 4 6 ..
[알고리즘] 버블 정렬 알고리즘 (Bubble Sort)버블 정렬 알고리즘 (Bubble Sort) 버블 정렬은 옆에 있는 데이터와 비교하여 더 작은 값을 앞으로 보내는 정렬입니다. 1 9 4 6 11 10 3 15 2 13 위와 같은 수가 있을 때 수들을 오름차순하는 버블 정렬을 해보겠습니다. 먼저 배열의 맨 앞부터 두 수씩 비교합니다. 1과 9를 비교하여 1이 더 작으므로 1을 정렬합니다. 그 다음 9와 4를 비교하여 4가 더 작으므로 9와 4의 위치를 교환하고 4를 정렬합니다. 그 다음 9와 6을 비교하여 6이 더 작으므로 9와 6의 위치를 교환하고 6를 정렬합니다. 그 다음 9와 6을 비교하여 6이 더 작으므로 9와 6의 위치를 교환하고 6를 정렬합니다. 1 9 4 6 11 10 3 15 2 13 1 4 9 6 11 10 3 15 2 13 1 4 6 ..
2021.07.05 -
선택 정렬 알고리즘 (Selection Sort) 데이터 배열을 내림차순 혹은 오름차순으로 나열하는 과정에서 사용되는 정렬 알고리즘이 존재합니다. 그 중에서 선택 정렬은 데이터 배열에서 가장 작은 데이터를 선택하여 앞으로 보내는 정렬입니다. 1 9 4 6 11 10 3 15 2 13 위와 같은 수가 있을 때 수들을 오름차순하는 선택 정렬을 해보겠습니다. 먼저, 첫번째 원소인 1부터 마지막 원소인 13까지 반복하면서 최솟값을 찾아냅니다. 찾은 후 그 값을 배열의 맨 앞 원소와 교환하고 정렬을 확정합니다. 위 배열에서는 1이 최솟값이므로 그대로 1이 정렬로 확정됩니다. 그 다음 반복에서는 확정된 정렬을 제외한 나머지 원소 배열에서 최솟값을 찾은 후 그 값을 다시 확정된 정렬을 제외한 나머지 원소 배열의 맨 ..
[알고리즘] 선택 정렬 알고리즘 (Selection Sort)선택 정렬 알고리즘 (Selection Sort) 데이터 배열을 내림차순 혹은 오름차순으로 나열하는 과정에서 사용되는 정렬 알고리즘이 존재합니다. 그 중에서 선택 정렬은 데이터 배열에서 가장 작은 데이터를 선택하여 앞으로 보내는 정렬입니다. 1 9 4 6 11 10 3 15 2 13 위와 같은 수가 있을 때 수들을 오름차순하는 선택 정렬을 해보겠습니다. 먼저, 첫번째 원소인 1부터 마지막 원소인 13까지 반복하면서 최솟값을 찾아냅니다. 찾은 후 그 값을 배열의 맨 앞 원소와 교환하고 정렬을 확정합니다. 위 배열에서는 1이 최솟값이므로 그대로 1이 정렬로 확정됩니다. 그 다음 반복에서는 확정된 정렬을 제외한 나머지 원소 배열에서 최솟값을 찾은 후 그 값을 다시 확정된 정렬을 제외한 나머지 원소 배열의 맨 ..
2021.07.05