개요
-
균형 잡힌 이진 검색 트리 개요프로그래밍 기초/알고리즘 2021. 8. 15. 17:59
균형 잡힌 이진 검색 트리 개요 이진 검색 트리의 문제점 이진 검색 트리의 경우 저장과 검색에 평균 Θ(logn) 시간이 소요되지만 운이 좋지 않아 트리의 균형이 깨지게 된 경우엔 Θ(n)에 가까운 시간이 소요되게 된다. 이러한 문제를 극복하기 위해 이진 검색 트리를 구성할 때 균형을 유지할 수 있도록 해야 하며 대표적으로 레드 블랙 트리와 AVL 트리가 존재한다. 이진 검색 트리의 균형 유지를 위한 각 트리의 특성은 다음과 같다. AVL 트리 높이 균형 성질을 만족한다. 높이 균형 성질 트리 내부의 모든 노드는 자식과의 높이 차이가 1 이하가 되어야 한다. 레드 블랙 트리 노드에 색상 정보를 추가하여 다음의 특성이 만족되도록 해야 한다. 루트는 블랙이다. 모든 리프(NIL)는 블랙이다. 노드가 레드이면..
-
검색 트리 개요프로그래밍 기초/알고리즘 2021. 8. 9. 15:26
검색 트리 저장된 데이터를 빠른 시간에 검색하기 위해 트리를 사용하는 검색 알고리즘이다. 검색 트리의 요소 레코드 여러 개의 필드로 구성되는 개체의 모든 정보가 저장된 구조 ex) 사람의 레코드: 주민 번호, 이름, 집 주소, 직장 주소, 집 전화번호 등이 포함될 수 있다. 필드 레코드의 각 정보를 나타내는 부분 검색 키(또는 키) 다른 레코드와 중복되지 않고 레코드를 대표할 수 있는 필드 검색 트리의 종류 자식의 수에 따른 분류 이진 검색 트리 최대 두 개의 자식 노드를 가지는 트리 다진 검색 트리 세 개 이상의 자식 노드를 가지는 트리 저장되는 장소에 따른 분류 내부 검색 트리 메인 메모리 내에 모든 데이터가 존재하는 트리 외부 검색 트리 디스크에 저장된 상태로 검색을 진행하는 트리 검색 키가 포함하..
-
선택 알고리즘 개요프로그래밍 기초/알고리즘 2021. 7. 27. 12:38
선택 알고리즘 주어진 집합에서 특정한 순서의 원소를 찾는 것을 선택 알고리즘이라고 한다. 이때, 정렬되지 않은 집합에 대해 특정한 순서의 원소를 찾을 때 시간 복잡도가 최대한 Ο(n)에 가깝게 되도록 하는 것이 선택 알고리즘의 의의이다. 선택의 종류 평균 선형시간 선택 퀵 소트의 분할 알고리즘을 응용한 것으로 기준 값의 위치보다 작은 값을 갖는 순서를 찾는 경우 왼쪽 그룹을 선택하고 기준 값의 위치보다 큰 값을 갖는 순서를 선택하는 경우 오른쪽 그룹을 선택하는 것을 반복하여 원하는 순서의 원소를 찾는 방식, 평균 Ο(n) / 최악의 경우 Ο(n²) 최악의 경우 선형시간 선택 최악의 경우에도 선형시간의 수행 시간을 보장하기 위해 중간 값이 끝 값이 되지 않도록 하기 위해 준간 값을 전체 그룹에서 찾아내도록..
-
정렬 알고리즘 개요프로그래밍 기초/알고리즘 2021. 6. 23. 08:26
정렬 알고리즘 정렬이란? n개의 원소를 순서대로 배열하는 것으로 실생활에 다양하게 사용되는 알고리즘이다. 가령 학생을 키 순서대로 줄을 세운다거나 세무서에서 고지서를 날리기 위해 주민등록 번호순으로 정렬하는 것 등을 예로 들 수 있다. 정렬의 종류 정렬에는 여러 종류가 있으며 대표적으로 다음과 같은 정렬이 존재한다. 선택 정렬 가장 큰 원소 또는 가장 작은 원소를 찾아 첫 위치 또는 마지막 위치와 자리를 바꾸는 정렬, 평균 Ο(n²) 버블 정렬 두 개의 원소를 비교하여 정렬 방향에 따라 서로 자리를 바꾸는 연산을 반복하는 정렬, 평균 Ο(n²) 병합 정렬 원소를 두 구역으로 나누는 것을 반복한 뒤 병합하며 자리를 바꾸는 연산을 반복하는 정렬, 평균 Ο(nlogn) 퀵 정렬 특정 값을 기준으로 영역을 나누..