알고리즘
-
알고리즘...24일지 2021. 7. 22. 14:28
선택 알고리즘 n 개의 원소를 가진 정렬되지 않은 집합에서 최소 원소를 찾는 것은 Ω(n)이 소요된다. 더 나아가 i 번째로 작은 원소를 찾을 때 Ο(nlogn)이 소요되는 정렬을 수행 후 i 번째 원소를 찾는다면 Ο(nlogn)이 소요될 것이다. 선택 알고리즘은 이러한 문제를 Ο(n)에 가깝게 수행하기 위한 알고리즘이다. 평균 선형시간 선택 알고리즘 퀵 정렬의 분할 알고리즘을 이용하여 기준 점 좌측 배열에 원하는 순서의 원소가 존재한다면 좌측 배열에 대해서만 재귀적으로 분할 알고리즘을 적용하여 원하는 위치의 원소를 찾을 수 있게 된다. 평균 선형시간 선택 알고리즘 Select(A[], p, r, i) { if (p = r) then { return A[p]; } q ← Partition(A, p, r)..
-
특수 정렬 알고리즘프로그래밍 기초/알고리즘 2021. 7. 21. 14:56
특수 정렬 알고리즘 두 원소를 비교하여 정렬하는 경우엔 수행 시간인 Ο(nlogn) 보다 빨라질 수 없다. 그러나 입력 값이 특수한 성질을 만족하는 경우 이러한 한계를 넘을 수 있는 알고리즘이 존재한다. 기수 정렬 입력이 모두 k 이하의 자릿수를 가진 자연수인 경우 사용할 수 있는 정렬 방법으로 Θ(n) 이 소요되는 알고리즘이다. 기수 정렬 알고리즘 RadixSort(A[], n, k) { for i ← 1 to k { i 번째 자리수에 대해 A[1...n]을 안정성을 유지하면서 정렬한다. } } ※ 안정성을 유지한다는 것은 비교한 결과가 같으면 자리가 유지되어야 한다는 의미이다. 계수 정렬 입력의 값이 모두 Ο(n)을 넘지 않는 경우 사용할 수 있는 정렬 방법으로 Θ(n) 이 소요되는 알고리즘이다. 계..
-
알고리즘...23일지 2021. 7. 20. 15:56
계수 정렬 입력의 값이 모두 Ο(n)을 넘지 않는 경우 사용할 수 있는 정렬 방법으로 Θ(n) 이 소요되는 알고리즘이다. 계수 정렬 알고리즘 // A[]를 정렬한 결과가 B[]에 저장될 때 CountingSort(A[], B[], n) { // 배열(혹은 딕셔너리) C[] 초기화 for i ← 1 to k { C[i] ← 0; } // 값이 A[j]인 개수 for j ← 1 to n { C[A[j]]++; } // 값이 A[j] 보다 작은 것의 개수 for i ← 2 to k { C[i] ← C[i] + C[i - 1]; } // B[]에 A[]의 자리를 확인하여 저장 for j ← n downto 1 { B[C[A[j]]] ← A[j]; C[A[j]]--; } } 더보기 참고문헌 한빛아카데미.문병로.(..
-
알고리즘...22일지 2021. 7. 19. 14:23
특수 정렬 알고리즘 두 원소를 비교하여 정렬하는 경우엔 수행 시간인 Ο(nlogn) 보다 빨라질 수 없다. 그러나 입력 값이 특수한 성질을 만족하는 경우 이러한 한계를 넘을 수 있는 알고리즘이 존재한다. 기수 정렬 입력이 모두 k 이하의 자리수를 가진 자연수인 경우 사용할 수 있는 정렬 방법으로 Θ(n) 이 소요되는 알고리즘이다. 기수 정렬 알고리즘 RadixSort(A[], n, k) { for i ← 1 to k { i 번째 자리수에 대해 A[1...n]을 안정성을 유지하면서 정렬한다. } } ※ 안정성을 유지한다는 것은 비교한 결과가 같으면 자리가 유지되어야 한다는 의미이다. 더보기 참고문헌 한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘
-
힙 정렬 구현 및 테스트프로그래밍 기초/알고리즘 2021. 7. 18. 11:25
힙 정렬 루트에 항상 가장 큰 값(혹은 가장 작은 값)이 오도록 정렬되는 힙을 사용하는 정렬 방식이다. 힙 만들기 입력되는 배열을 완전 이진트리로 가정하여 힙을 생성한다. 힙 생성 알고리즘 BuildHeap(A[], n) { for i ← └n / 2┘ downto 1 { Heapify(A, i, n); } } Heapfipy(A[], k, n) { left ← 2k; right ← 2k + 1; // 작은 자식 고르기 if (right ≤ n) then { if (A[left] < A[right]) then { smaller ← left; } else { smaller ← right; } } // 왼쪽 자식만 있는 경우 else if (left ≤ n) then { smaller ← left; } //..
-
알고리즘...21일지 2021. 7. 16. 13:49
힙 정렬 구현 배열 arr과 배열의 길이 n을 입력으로 받는 함수를 구현한다. HeapSort.hpp #pragma once #include "../Common.hpp" void BuildHeap(int arr[], int n); void Heapify(int arr[], int k, int n); /// /// 주어진 배열을 정렬한다. /// /// 정렬을 진행할 배열 /// 배열의 길이 /// 중간 결과 출력 여부 void HeapSort(int arr[], int n, bool printData = false) { if (printData) { Common::PrintArray(arr, n); } BuildHeap(arr, n); for (int i = n - 1; i > 0; i--) { Comm..
-
알고리즘...20일지 2021. 7. 15. 14:03
힙 정렬 루트에 항상 가장 큰 값(혹은 가장 작은 값)이 오도록 정렬되는 힙을 사용하는 정렬 방식이다. 힙 만들기 입력되는 배열을 완전 이진트리로 가정하여 힙을 생성한다. 힙 생성 알고리즘 BuildHeap(A[], n) { for i ← └n / 2┘ downto 1 { Heapify(A, i, n); } } Heapfipy(A[], k, n) { left ← 2k; right ← 2k + 1; // 작은 자식 고르기 if (right ≤ n) then { if (A[left] < A[right]) then { smaller ← left; } else { smaller ← right; } } // 왼쪽 자식만 있는 경우 else if (left ≤ n) then { smaller ← left; } //..
-
퀵 정렬 구현 및 테스트프로그래밍 기초/알고리즘 2021. 7. 14. 12:29
퀵 정렬 가장 끝 원소를 기준으로 그보다 작은 원소를 왼쪽에 큰 원소를 오른쪽으로 옮겨 정렬한다. 퀵 정렬 알고리즘 끝 원소를 기준으로 작은 원소를 좌측에 큰 원소를 우측으로 옮기고 좌측 배열과 우측 배열에 대해 같은 과정을 반복한다. 퀵 정렬 알고리즘 QuickSort(A[], p, r) { if (p < r) then { q ← Partition(A, p, r) QuickSort(A, p, q - 1) QuickSort(A, q + 1, r) } } Partition(A[], q, r) { 배열 A[p...r]의 원소들을 A[r]을 기준으로 양쪽으로 재배치하고 A[r]이 자리한 위치를 리턴한다. } ※ 퀵 정렬의 시간 복잡도는 모든 원소들이 한쪽으로 몰리는 최악의 경우 Ο(n²), 평균적으로 Ο(nl..