navis
알고리즘 6강 (탐색) 본문
728x90
학습개요
- 이번 강의를 포함해서 앞으로 두 번의 강의를 통해서, 주어진 저장 매체에서 원하는 데이터를 찾는 탐색 알고리즘에 대해서 살펴본다. 우선 이번 시간에는 순차 탐색과 이진 탐색과 같은 기본적인 탐색 방법을 비롯하여 이진 탐색 트리와 2-3-4 트리에 대해서 학습한다.
학습목표
- 순차 탐색의 개념, 성능, 특징을 이해하고 설명할 수 있다.
- 이진 탐색의 개념, 동작, 그리고 성능과 특징을 이해하고 설명할 수 있다.
- 이진 탐색 트리의 개념, 동작, 그리고 성능과 특징을 이해하고 설명할 수 있다.
- 2-3-4 트리의 개념, 동작, 그리고 성능과 특징을 이해하고 설명할 수 있다.
주요용어
- 순차 탐색(sequential search)
- 리스트 형태로 주어진 원소들을 처음부터 하나씩 차례대로 비교하면서 원하는 값을 가진 원소를 찾는 방법 - 이진 탐색(binary search)
- 정렬된 리스트 형태로 주어진 원소들을 절반씩 줄여가면서 원하는 값을 가진 원소를 찾는 방법 - 이진 탐색 트리(binary search tree)
- 각 노드의 왼쪽 서브트리에 있는 모든 키값은 그 노드의 키값보다 작고, 오른쪽 서브트리에 있는 모든 키값은 그 노드의 키값보다 크다는 조건을 만족시키는 이진 트리 - 후속자(계승자) 노드(successor node)
- 트리에서 어떤 노드의 바로 다음 키값을 갖는 노드 - 2-3-4 트리
- 2-노드, 3-노드, 4-노드로 구성된 균형 탐색 트리
- k-노드는 (k-1)개의 키와 k개의 자식으로 구성 - 노드 분할(node split)
- 2-3-4 트리에서 노드 분할이란 4-노드 하나를 2-노드 셋으로 분할한 후 가운데 2-노드를 부모 노드로 이동시키는 연산
정리하기
- 1. 순차 탐색
⦁ 리스트 형태로 주어진 원소들을 처음부터 하나씩 차례대로 비교하면서 원하는 값을 가진 원소를 찾는 방법
⦁ 성능 → O(n)
⦁ 모든 리스트 형태의 입력에 적용 가능 → 특히 비정렬 데이터 탐색에 적합
⦁ 데이터가 큰 경우에는 부적합 - 2. 이진 탐색
⦁ 정렬된 리스트 형태로 주어진 원소들을 절반씩 줄여가면서 원하는 값을 가진 원소를 찾는 방법 → 분할정복 방법 적용
⦁ 성능 → 탐색 O(logn), 초기화 O(nlogn), 삽입/삭제 O(n)
⦁ 정렬된 리스트에 대해서만 적용 가능
⦁ 삽입/삭제 연산이 빈번한 응용에는 부적합 → 삽입/삭제 후 입력 리스트의 정렬 상태를 유지하기 위해서는 O(n)의 데이터 이동이 필요 - 3. 이진 탐색 트리
⦁ 각 노드의 왼쪽 서브트리에 있는 모든 키값은 그 노드의 키값보다 작고, 오른쪽 서브트리에 있는 모든 키값은 그 노드의 키값보다 크다는 조건을 만족시키는 이진 트리
⦁ 탐색 연산 → 루트 노드로부터 시작해서 값의 크기 관계에 따라 트리의 경로를 따라 내려가면서 진행
⦁ 삽입 연산 → 우선 삽입할 원소를 탐색한 후, 탐색이 실패하면 해당 위치의 자식 노드로서 새 노드를 추가
⦁ 삭제 연산 → 삭제되는 노드의 자식 노드의 개수에 따라 3가지 경우로 나누어 처리
① 자식 노드가 없는 경우 → 남는 노드가 없으므로 별도의 처리가 불필요
② 자식 노드가 하나인 경우 → 자식 노드를 삭제되는 노드의 위치로 올리면서 서브트리 전체도 따라 올림
③ 자식 노드가 두 개인 경우 → 삭제되는 노드의 후속자 노드를 삭제되는 노드의 위치로 올리고, 후속자 노드를 삭제되는 노드로 취급하여 자식 노드의 개수에 따라 다시 처리
⦁ 성능 → 평균 O(logn), 최악 O(n)
⦁ 삽입/삭제 시 기존 노드의 이동이 거의 발생하지 않음
⦁ 원소의 삽입/삭제가 진행됨에 따라 최악의 성능을 갖는 경사 트리 형태가 될 수 있음 - 4. 2-3-4 트리
⦁ 2-노드, 3-노드, 4-노드로 구성된 균형 탐색 트리
- k-노드는 (k-1)개의 키와 k개의 자식을 가짐
⦁ 4-노드의 분할 → 삽입을 위한 탐색 과정에서 4-노드를 만나면 하나의 4-노드를 3개의 2-노드로 분할하고, 가운데 2-노드에 해당하는 키를 부모 노드로 이동시킴
⦁ 성능 → 탐색/삽입/삭제 O(logn)
⦁ 2-3-4 트리를 그대로 구현하면 노드의 구조가 복잡해서 이진 탐색 트리보다 더 느려질 가능성이 많음
'방송통신대 컴퓨터과학과' 카테고리의 다른 글
운영체제 6강 (교착 상태) (0) | 2024.04.17 |
---|---|
인공지능 6강 (논리에 의한 지식 표현) (0) | 2024.04.17 |
운영체제 5강 (병행프로세스) (0) | 2024.04.15 |
인공지능 5강 (지식과 인공지능) (0) | 2024.04.15 |
알고리즘 5강 (정렬) (0) | 2024.04.15 |