본문 바로가기

컴퓨터 공학99

[자료구조] 탐색 트리 (Search Tree) 탐색 트리: 탐색을 위한 트리 기반의 자료 구조 일상생활이나 컴퓨터에서 탐색은 매우 중요한 역할을 한다. 우리가 원하는 데이터를 찾을 때 반드시 거쳐야 하는 과정이 탐색이다. 앞서 이진 탐색을 배웠지만, 레코드의 삽입과 삭제가 빈번히 일어나는 테이블에 대해서는 그다지 효율적이라고 말할 수 없었다. 해싱을 사용하면 매우 효율적이지만 메모리를 많이 사용할 뿐더러 해시 충돌과 오버플로 문제를 처리해야 하므로 매우 복잡하다는 단점이 있다. 그래서 고안된 방안이 탐색에 트리 구조를 이용하는 것이다. 즉 탐색을 위한 이진 트리 기반의 자료 구조가 고안되었는데, 이를 이진 탐색 트리라고 한다. 이진 탐색 트리의 특성 모든 노드는 유일한 키를 갖는다. 왼쪽 서브 트리의 키들은 루트의 키보다 작다. 오른쪽 서브 트리의 .. 2024. 1. 8.
[자료구조] 트리 3. 힙 트리 힙 트리: 여러 개의 값들 중에서 가장 크거나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료 구조 힙은 최대 힙과 최소 힙으로 나눌 수 있으며, 모든 힙 트리는 아래의 두 성질을 만족해야 한다. 모양 성질: 완전 이진 트리의 모양을 나타내야 한다. 힙 성질: 최대 힙 또는 최소 힙의 특성을 갖는다. 최대 힙의 특성: 각 노드에 저장된 값은 그 자식 노드에 저장된 값보다 크거나 같다. 최소 힙의 특성: 각 노드에 저장된 값은 그 자식 노드에 저장된 값보다 작거나 같다. 최대 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리 최소 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리 이번에는 최대 힙을 가지고 다뤄보도록 하겠다! 최대 힙의 구현 최대 힙.. 2024. 1. 8.
[자료구조] 트리 2. 이진 트리의 활용 앞서 이진 트리의 개념과 표현법에 대해 간략하게 공부했다. 그럼 이렇게 이진 트리를 만들고 난 후, 어떻게 트리의 데이터에 접근할 수 있을까? 바로 순회를 이용하는 것이다. 순회란 트리에 속하는 모든 노드들을 한 번씩 방문하여 트리의 데이터에 접근하는 것으로, 트리에서 가장 기본적인 연산이다. 이진 트리의 표준 순회에는 전위 순회, 중위 순회, 후위 순회 3가지 방법이 있다. 이들은 루트의 왼쪽 서브 트리, 오른쪽 서브 트리를 각각 어떤 순서로 방문하느냐에 따라 구분된다. 루트를 방문하는 작업을 V, 왼쪽과 오른쪽 서브 트리를 방문하는 작업을 각각 L과 R이라고 할 때, 각 순회들을 구현하는 방법들은 아래와 같다. 전위 순회: VLR 중위 순회: LVR 후위 순회: LRV 순회의 구현 def preord.. 2024. 1. 8.
[자료구조] 트리 1. 이진 트리 트리: 계층적인 관계를 가진 자료의 표현에 유용한 자료구조 앞에서 배운 리스트나 스택, 큐, 덱 등은 모두 자료들이 일렬로 나열된 선형 자료 구조였으나, 트리는 계층적인 구조를 가지고 있다. 회사의 조직도 컴퓨터의 폴더 구조 인공지능 바둑 프로그램에 쓰이는 결정 트리 트리의 용어 루트 노드: 계층적인 구조에서 가장 높은 곳에 있는 노드 모든 노드는 자신의 서브 트리의 루트 노드이다. 간선: 노드와 노드를 연결하는 선 부모 노드와 자식 노드: 간선으로 직접 연결된 노드 중에 상위 노드와 하위 노드 형제 노드: 동일한 부모 노드를 가지는 노드 조상 노드와 자손 노드: 어떤 노드에서 루트 노드까지의 경로상에 있는 모든 노드들과, 어떤 노드 하위에 연결된 모든 노드 단말 노드(리프 노드): 자식 노드가 없는 노.. 2024. 1. 7.
[자료구조] 탐색 3. 해싱 지금까지 우리가 배운 탐색 방법은 모두 탐색키와 각 레코드의 킷값을 비교하여 원하는 레코드를 찾는 방식이었다. 그러나 해싱은 킷값에 산술적인 연산을 적용하여 레코드가 저장되어야 할 위치를 직접 계산하여 탐색하는 방식이다. 이 때 레코드가 저장될 위치를 계산하는 함수를 해시 함수(hash function)이라고 하며, 해시 함수에 의해 계산된 위치에 레코드를 저장한 테이블을 해시 테이블(hash table)이라고 한다. 해시 테이블은 M개의 버킷(bucket)이 담아져 있는데, 버킷이란 레코드를 담아두는 메모리를 뜻한다. (버킷은 여러 개의 슬롯으로 이루어져 있지만… 복잡하므로 버킷 1개에는 1개의 슬롯만 있다고 가정하자) 그런데 탐색 키의 개수가 엄청나게 많은 경우에는 해시 테이블의 크기가 엄청나게 커야.. 2024. 1. 7.
[자료구조] 탐색 2. 간단한 탐색들 앞에서 탐색과 맵에 대해 간략하게 설명했다. 정렬과 마찬가지로 탐색 역시 간단하게 구현할 수 있는 탐색 알고리즘들이 있는데, 그것들을 살펴보도록 하겠다. 1) 순차 탐색 처음부터 마지막 원소까지 모두 탐색하는 매우 단순하고 직관적인 탐색 알고리즘이다. 리스트 A와 탐색 키 key, 그리고 리스트에서의 탐색 범위 low~high가 주어진다면 그 어떤 테이블에서도 원하는 레코드를 찾을 수 있다. def sequential_search(A, key, low, high): for i in range(low, high+1): if A[i] == key: # key값을 찾은 경우 return i return None 그 어떤 테이블에서도 원하는 레코드를 찾을 수 있다는 장점이 있지만… 결국 n개의 요소를 모두 돌아.. 2024. 1. 7.
반응형

티스토리툴바