프로그래밍 기초
-
검색 트리 개요프로그래밍 기초/알고리즘 2021. 8. 9. 15:26
검색 트리 저장된 데이터를 빠른 시간에 검색하기 위해 트리를 사용하는 검색 알고리즘이다. 검색 트리의 요소 레코드 여러 개의 필드로 구성되는 개체의 모든 정보가 저장된 구조 ex) 사람의 레코드: 주민 번호, 이름, 집 주소, 직장 주소, 집 전화번호 등이 포함될 수 있다. 필드 레코드의 각 정보를 나타내는 부분 검색 키(또는 키) 다른 레코드와 중복되지 않고 레코드를 대표할 수 있는 필드 검색 트리의 종류 자식의 수에 따른 분류 이진 검색 트리 최대 두 개의 자식 노드를 가지는 트리 다진 검색 트리 세 개 이상의 자식 노드를 가지는 트리 저장되는 장소에 따른 분류 내부 검색 트리 메인 메모리 내에 모든 데이터가 존재하는 트리 외부 검색 트리 디스크에 저장된 상태로 검색을 진행하는 트리 검색 키가 포함하..
-
최악의 경우 선형시간 선택 구현 및 테스트프로그래밍 기초/알고리즘 2021. 7. 29. 13:38
최악의 경우 선형시간 선택 최악의 경우에도 선택 알고리즘의 수행 시간이 Θ(n)이 되는 것을 보장하는 선택 알고리즘이다. 최악의 경우 선형시간 선택 알고리즘 분할 알고리즘으로 배열을 n개 씩의 그룹으로 나누고 그룹의 중간 값들의 중간 값을 이용해 선택 알고리즘을 수행한다. 최악의 경우 선형시간 선택 알고리즘 LinearSelect(A[], p, r, i) { 1. 원소의 총 수가 5개 이하이면 원하는 원소를 찾고 알고리즘을 끝낸다. 2. 전체 원소를 5개씩의 원소를 가진 ┌n/5┐개의 그룹으로 나눈다. 3. 각 그룹에서 중앙값을 찾는다. + 이렇게 찾은 중앙값들을 m1, m2,..., m┌n/5┐이라 하자. 4. m1, m2,..., m┌n/5┐들의 중앙값 m을 재귀적으로 구한다. 5. M을 기준 원소로..
-
평균 선형시간 선택 구현 및 테스트프로그래밍 기초/알고리즘 2021. 7. 28. 13:49
평균 선형시간 선택 퀵 정렬의 분할 알고리즘을 이용하여 n 번째 원소를 빠르게 찾아내는 선택 방식이다. 평균 선형시간 선택 알고리즘 분할 알고리즘으로 두 개의 영역으로 나눈 뒤 n 번째 원소가 왼쪽에 포함되면 왼쪽 배열을 아니면 오른쪽 배열을 선택하는 과정을 반복하여 n 번째 원소를 찾는다. 평균 선형시간 선택 알고리즘 Select(A[], p, r, i) { if (p = r) then { return A[p]; } q ← Partition(A, p, r); k ← q - p + 1; if (i < k) then { return Select(A, p, q - 1, i); } else if (i = k) then { return A[q]; } else { return Select(A, q + 1, r, ..
-
선택 알고리즘 개요프로그래밍 기초/알고리즘 2021. 7. 27. 12:38
선택 알고리즘 주어진 집합에서 특정한 순서의 원소를 찾는 것을 선택 알고리즘이라고 한다. 이때, 정렬되지 않은 집합에 대해 특정한 순서의 원소를 찾을 때 시간 복잡도가 최대한 Ο(n)에 가깝게 되도록 하는 것이 선택 알고리즘의 의의이다. 선택의 종류 평균 선형시간 선택 퀵 소트의 분할 알고리즘을 응용한 것으로 기준 값의 위치보다 작은 값을 갖는 순서를 찾는 경우 왼쪽 그룹을 선택하고 기준 값의 위치보다 큰 값을 갖는 순서를 선택하는 경우 오른쪽 그룹을 선택하는 것을 반복하여 원하는 순서의 원소를 찾는 방식, 평균 Ο(n) / 최악의 경우 Ο(n²) 최악의 경우 선형시간 선택 최악의 경우에도 선형시간의 수행 시간을 보장하기 위해 중간 값이 끝 값이 되지 않도록 하기 위해 준간 값을 전체 그룹에서 찾아내도록..
-
특수 정렬 알고리즘프로그래밍 기초/알고리즘 2021. 7. 21. 14:56
특수 정렬 알고리즘 두 원소를 비교하여 정렬하는 경우엔 수행 시간인 Ο(nlogn) 보다 빨라질 수 없다. 그러나 입력 값이 특수한 성질을 만족하는 경우 이러한 한계를 넘을 수 있는 알고리즘이 존재한다. 기수 정렬 입력이 모두 k 이하의 자릿수를 가진 자연수인 경우 사용할 수 있는 정렬 방법으로 Θ(n) 이 소요되는 알고리즘이다. 기수 정렬 알고리즘 RadixSort(A[], n, k) { for i ← 1 to k { i 번째 자리수에 대해 A[1...n]을 안정성을 유지하면서 정렬한다. } } ※ 안정성을 유지한다는 것은 비교한 결과가 같으면 자리가 유지되어야 한다는 의미이다. 계수 정렬 입력의 값이 모두 Ο(n)을 넘지 않는 경우 사용할 수 있는 정렬 방법으로 Θ(n) 이 소요되는 알고리즘이다. 계..
-
힙 정렬 구현 및 테스트프로그래밍 기초/알고리즘 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; } //..
-
퀵 정렬 구현 및 테스트프로그래밍 기초/알고리즘 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..
-
병합 정렬 구현 및 테스트프로그래밍 기초/알고리즘 2021. 7. 9. 11:44
병합 정렬 입력 배열을 반으로 나누고 나눈 배열을 하나의 배열로 병합하여 정렬을 진행한다. 병합 정렬 알고리즘 배열의 크기를 반으로 나누는 과정을 각각의 크기가 1이 될 때까지 반복하고 이후 각각의 배열을 병합할 때 정렬을 진행한다. 병합 정렬 알고리즘 MergeSort(A[], p, r) { if (p < r) then { q ← └(p + r) / 2┘ MergeSort(A, p, q) MergeSort(A, q + 1, r) Merge(A, p, q, r) } } Merge(A[], p, q, r) { 정렬되어 있는 두 배열 A[p...q]와 A[q + 1...r]을 합쳐 정렬 된 하나의 배열 A[p...r]을 만든다. } ※ 병합 정렬 시 배열을 둘로 나누는 것을 반복할 때 logn, 배열을 다시..