본문 바로가기

전체 글149

[자료구조] 트리 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.
[자료구조] 탐색 1. 탐색과 맵 (Map) 우리는 매일 인터넷에서 원하는 정보를 찾고, 사전 등에서 궁금한 내용을 찾아본다.그러나 매우 방대한 인터넷에서, 우리가 알고 싶은 정보를 어떻게 찾아낼 수 있는 걸까?이 개념을 자료구조에도 적용해보자. 우리가 저장한 데이터에서 정보를 찾아내는 것을 탐색이라고 한다. 빠르고 효율적인 탐색을 위해서 데이터를 잘 정리해둘 필요가 있다.사전의 경우 가나다 순이 아니고 뒤죽박죽 정리되어 있다면… 아마 우리가 원하는 정보를 탐색할 수 없을 것이니까…탐색은 레코드(record)의 집합(table)에서 원하는 레코드를 찾는 작업이다. 레코드들은 서로를 구별하여 인식할 수 있는 키(key)를 가지고 있는데 이를 탐색 키(search key)라고 한다. 즉 탐색이란 테이블에서 원하는 탐색키를 가진 레코드를 찾는 작업이다... 2024. 1. 7.
반응형

티스토리툴바