프로그래밍 기초/알고리즘
-
이진 검색 트리 출력 함수 구현프로그래밍 기초/알고리즘 2021. 9. 21. 13:55
이진 검색 트리 출력 이진 검색 트리를 화면에 출력하는 함수를 구현한다. 노드 출력 알고리즘 노드를 동일한 간격으로 출력하기 위해 다음의 제약 사항이 존재해야 한다. 모든 노드는 동일한 크기를 갖는다. 최대 깊이의 노드 간의 간격은 노드의 크기와 같다. 최대 깊이에 빈 노드가 없다고 가정하여 최대 크기를 구한다. 구한 최대 크기를 모든 깊이에 사용하여 출력한다. 깊이가 n 일 때, 노드의 개수 및 공백의 개수는 다음과 같다. 노드의 수 2ⁿ - ¹ 개 공백의 수 n + 1 개 따라서 최대 깊이에서 출력에 필요한 크기는 다음의 식을 만족한다. 출력에 필요한 크기 = (공백의 수 + 노드의 수) * 노드의 크기 ※ 깊이에 따라 노드의 수가 달라지므로 공백의 크기는 출력에 필요한 크기 - (노드의 수 * 노드..
-
AVL 트리 구현 및 테스트프로그래밍 기초/알고리즘 2021. 9. 20. 17:45
AVL 트리 이진 검색 트리를 기반으로 노드에 Balance Factor(이후 BF)를 추가하여 BF의 상태에 따라 트리의 균형을 유지한다. ※ AVL 트리는 노드의 수가 n일 때 최대 깊이가 Ο(logn)이 되게 된다. AVL 트리의 개념 기본적으로 삽입과 삭제는 이진 검색 트리의 알고리즘을 그대로 따르며 이후 BF에 따라 보정하는 작업을 진행하여 트리의 균형을 유지한다. BF는 노드의 왼쪽 서브 트리의 깊이와 오른쪽 서브 트리의 깊이의 차이이다. 정상 상태일 때 BF의 범위는 [-1, 1]이 되게 되며 노드의 삽입 혹은 삭제를 통해 이 범위를 넘게 되면 균형이 무너진 것으로 판단한다. AVL 트리의 회전 알고리즘 BF가 무너진 노드를 x, x의 자식을 c, c의 자식을 c²라 하면 회전이 필요한 경우..
-
레드 블랙 트리 구현 및 테스트프로그래밍 기초/알고리즘 2021. 9. 19. 17:03
레드 블랙 트리 이진 검색 트리를 기반으로 노드에 색상을 추가하여 색상 규칙을 기준으로 트리의 균형을 유지한다. ※ 레드 블랙 트리는 노드의 수가 n일 때 최대 깊이가 Ο(logn)이 되게 된다. 레드 블랙 트리의 삽입 알고리즘 레드 블랙 트리의 삽입에서는 먼저 삽입하는 노드의 색상을 레드로 간주하고 삽입을 진행하며 삽입한 노드를 x, 부모 노드를 p, 형제 노드를 s라고 할 때 발생 가능한 모든 경우는 다음과 같다. p가 블랙인 경우 삽입 연산을 종료한다. s가 레드인 경우 p와 s를 블랙으로 바꾸고 p²을 레드로 바꾼다. 만약 p²가 루트면 p²를 블랙으로 바꾸고 종료한다. 연산 결과 p²이 레드이면 p²을 문제 발생 노드로 두고 재귀적으로 처리한다. s가 블랙인 경우 삽입된 위치에 따른 추가 연산을..
-
균형 잡힌 이진 검색 트리 개요프로그래밍 기초/알고리즘 2021. 8. 15. 17:59
균형 잡힌 이진 검색 트리 개요 이진 검색 트리의 문제점 이진 검색 트리의 경우 저장과 검색에 평균 Θ(logn) 시간이 소요되지만 운이 좋지 않아 트리의 균형이 깨지게 된 경우엔 Θ(n)에 가까운 시간이 소요되게 된다. 이러한 문제를 극복하기 위해 이진 검색 트리를 구성할 때 균형을 유지할 수 있도록 해야 하며 대표적으로 레드 블랙 트리와 AVL 트리가 존재한다. 이진 검색 트리의 균형 유지를 위한 각 트리의 특성은 다음과 같다. AVL 트리 높이 균형 성질을 만족한다. 높이 균형 성질 트리 내부의 모든 노드는 자식과의 높이 차이가 1 이하가 되어야 한다. 레드 블랙 트리 노드에 색상 정보를 추가하여 다음의 특성이 만족되도록 해야 한다. 루트는 블랙이다. 모든 리프(NIL)는 블랙이다. 노드가 레드이면..
-
이진 검색 트리 구현 및 테스트프로그래밍 기초/알고리즘 2021. 8. 10. 12:06
이진 검색 트리 이진 검색 트리의 특성은 다음과 같다. 각 노드는 서로 다른 키 값을 하나씩 갖는다. 최상위 레벨에 루트가 있으며, 각 노드는 최대 두 개의 자식 노드를 가진다. 노드의 왼쪽 서브 트리의 모든 노드의 값은 항상 노드의 값보다 작다. 노드의 오른쪽 서브 트리의 모든 노드의 값은 항상 노드의 값보다 크다. 이진 검색 트리에서의 검색 특정 키를 가진 노드를 검색하는 방법은 다음과 같다. 이진 검색 트리의 루트 노드에서부터 비교를 시작한다. 주어진 키와 노드의 키를 비교하여 주어진 키가 노드의 키가 같으면 노드를 반환한다. 주어진 키가 노드의 키보다 작으면 왼쪽 서브 트리로 이동하여 다시 비교한다. 주어진 키가 노드의 키보다 크면 오른쪽 서브 트리로 이동하여 다시 비교한다. 위 과정을 노드를 찾..
-
검색 트리 개요프로그래밍 기초/알고리즘 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, ..