본문 바로가기

자료구조10

자료구조 | 힙(Heap), 우선순위 큐(Priority Queue) 우선순위 큐는 대표적으로 다익스트라 알고리즘에서 사용된다. (또 A* 알고리즘, 허프만 코딩 알고리즘 등에서도 쓰인다고 한다) 큐, 데큐가 선형 자료구조인 것과 달리, 우선순위 큐는 주로 힙(Heap)으로 구현되는 경우가 많기 때문에 비선형으로 분류된다. 우선순위 큐를 구현하는데 필요한 힙(Heap)이라는 자료구조가 무엇인지 알아보고, 우선순위 큐에 대해서 알아보자. 힙(Heap) Heap은 완전 이진 트리의 일종으로, 1) 최소 힙 또는 2) 최대 힙으로 나뉜다. 힙 속성(Heap Property) 최소 힙(Min-Heap): 각 노드의 값이 그 자식 노드의 값보다 작거나 같음 (루트 노드가 최소값) 최대 힙(Max-Heap): 각 노드의 값이 그 자식 노드의 값보다 크거나 같음 (루트 노드가 최대값).. 2023. 10. 26.
자료구조 | 유니온-파인드(Union-Find) Union-Find Union-Find는 Kruskal 알고리즘을 구현하기 위해 핵심적으로 알아야 할 자료구조이다. Disjoint Set(서로소 집합 자료구조)을 표현할 때 사용하는 자료구조이다. 서로소 집합은 공통 요소가 하나도 없는, 즉 교집합이 전혀 없는 서로 다른 부분집합들을 의미한다. 그리고 Union-Find는 이 Disjoint-Set을 구성하고 각 요소에 대한 조작, 검색을 수행하도록 설계된 개념이다. 구현 해당 자료구조는 언어 자체에 내장되어 있거나 그렇진 않고, 일반적으로 딕셔너리(트리 구조)로 구현한다. Key = 노드 Value = 해당 노드의 부모 노드 (* 루트 노드는 부모 노드로 자기 자신을 가리킨다.) 트리 구조의 부모-자식 관계를 이용하여 어떠한 부분집합의 개별 요소들을.. 2023. 10. 23.
자료구조 | 신장 트리(ST), 최소 신장 트리(MST) 그래프와 트리의 개념을 배우고나면, 그 다음으로 딱 봐도 '실생활에서도 자주 응용되겠는데?' 싶은 개념이 등장한다. 바로 '신장 트리'와 여기서 파생되는 '최소 신장 트리' 개념이다. 신장 트리(Spanning Tree, ST) 신장 트리의 정의 그래프는 V(정점)와 E(간선)의 집합이다. 그리고 어떤 한 그래프에는 수많은 조합의 하위 그래프가 존재할 것이다. 이중에서 특별한 조건을 만족한 하위 그래프를 '신장 트리'라고 부른다. [신장 트리의 조건] 1. 주어진 연결 그래프의 모든 정점을 지나야 한다. 2. 동시에 트리여야 한다. 1) 사이클을 포함하지 않아야 한다. 2) V = E+1 이어야 한다. (V: 정점의 수, E: 간선의 수) 신장 트리(Spanning Tree)에서 '신장'은 원래 이름인 .. 2023. 10. 22.
자료구조 | 이진 탐색 트리(Binary Search Tree, BST) 이진 탐색 트리(Binary Search Tree, BST) 이진 탐색 트리는 이진 트리의 한 종류로, 효율적인 탐색이 가능하도록 노드를 배치한 형태이다. 1. 기본 개념 이진 탐색 트리의 모든 노드에는 다음 두 가지 조건이 재귀적으로 적용된다. 왼쪽 서브트리의 모든 노드의 Key는 자신의 Key보다 작고, 오른쪽 서브트리의 모든 노드의 Key는 자신의 Key보다 크다. 위 이미지를 보면, 어떠한 노드이든 자기자신을 기준으로 반을 나누면 왼쪽은 자신보다 Key 값이 작고, 오른쪽은 자신보다 Key 값이 크다. BST의 특성 이진 탐색 트리는 다음과 같은 특성이 있다. 데이터의 정렬된 순서를 유지하는 속성을 갖는다. BST의 최소값 -> 트리의 가장 왼쪽 값 BST의 최대값 -> 트리의 가장 오른쪽 값 .. 2023. 10. 20.
자료구조 | 이진 트리, 트리 순회(Tree Traversal) 이진 트리(Binary Tree)는 트리 구조의 가장 기본적이고, 기초적인 모델로 간주된다. 특히 컴퓨터 과학에서 트리 구조를 처음 배울 때 이진 트리를 가장 먼저 다루는 이유는 대략 다음과 같다: 이진 트리는 각 노드가 최대 두 개의 자식만을 가질 수 있기 때문에 구조적으로 간단하다. 여러 트리 구조가 이진 트리로부터 파생되었기 때문에(ex: 이진 탐색 트리, 균형 이진 트리 등), 이들을 이해하기 위해 이진 트리에 대한 이해가 선행되어야 한다. 그러므로 이진 트리를 이해하는 시간을 갖고, 이진 트리를 활용하여 트리의 노드를 스캔하는 순회 방법(전위 순회, 중위 순회, 후위 순회)에 대해서도 알아보자. 이진 트리(Binary Tree, BT) 이진 트리는 모든 부모 노드가 왼쪽 자식과 오른쪽 자식만을 .. 2023. 10. 20.
자료구조 | 트리(Tree) 트리(Tree)는 데이터들의 구조가 실제 나무와 비슷하다고 해서 붙여진 이름이다(나무를 거꾸로 뒤집은 모습). 맨 꼭대기 노드인 루트(root)에서 시작하여 가지(branch)와 같은 여러 경로를 통해 맨 아래의 리프(leaf) 노드로 뻗어 나가는 구조를 가지고 있다. 그림 봐도 알겠지만 앞서 배웠던 자료구조들과 다르게 linear 하다고 보기엔 어렵다. 따라서 트리는 비선형 자료구조로 분류된다. 수많은 천재들이 트리를 잘 활용하는 법을 알아내준 덕에 우리는 데이터 관리를 위한 매우 뛰어난 도구를 몇가지 얻게 되었다. 특히 트리 구조는 탐색 기법으로 응용될 때 더 빛을 발하는데, 예를 들어 이진 탐색 트리(Binary Search Tree, BST)나 몬테카를로 트리 탐색(Monte-Carlo tree .. 2023. 10. 20.
자료구조 | 해시 테이블(Hash Table) 해시 테이블은 'Key: Value'의 쌍을 저장하는 구조로, 고유한 Key를 기반으로 빠르게 데이터를 검색할 수 있게 해주는 자료구조이다. 이론적으로는 해시 테이블에서 원소를 찾는 것이 연결 리스트에서 원소를 찾는 것(최악의 경우 O(n)의 수행시간을 가진다)만큼 오래 걸릴 수 있지만 실제로 해싱은 성능이 탁월하다. 합리적인 가정 하에서 해시 테이블에서 원소를 찾는 데 걸리는 평균 수행시간은 O(1)이다. (출처: Introduction to Algorithms) 해싱(Hashing)이라는 개념은 1930년대에 처음 사용되었으며, 데이터 저장 및 검색 분야에 큰 혁신을 가져왔다고 한다. 'Hash'라는 단어는 'hack'에서 유래되었는데, 원래 의미는 '잘게 자르다'이다. 데이터를 작은 부분으로 나누어.. 2023. 10. 19.
자료구조 | 이중 연결 리스트, 원형 연결 리스트 이중 연결 리스트(Doubly Linked List)와 원형 연결 리스트(Circular Linked List)는 연결 리스트를 살짝 변형하여 단점을 개선한 자료구조이다. 연결 리스트를 배열과 비교했듯, 이들 역시 기본형인 단순 연결 리스트와 비교하면서 이해하는 게 효과적일 것 같다. 단순 연결 리스트 vs 이중 연결 리스트 vs 원형 연결 리스트 1. 개념 단순 연결 리스트: 일방향적. Head 노드 → Tail 노드 방향으로 포인터가 다음 노드 주소를 일방향적으로 가리킨다. 이중 연결 리스트: 양방향적. Head 노드 ↔ Tail 노드 양방향에서 다음 노드 주소를 양방향적으로 가리킨다. 원형 연결 리스트: 일방향적이나 순환적. Head 노드 → Tail 노드 일방향으로 포인터가 가리키지만, Tail .. 2023. 10. 17.
자료구조 | 연결 리스트(Linked List) 연결 리스트는 그 유연성과 동적인 특성 때문에 매우 중요한 자료구조로 간주된다. 연결 리스트는 여러개의 노드가 이어지는 형태로 구성되어 있다. '각 노드 = 데이터(data) + 포인터(next)' 이다. 해당 자료구조의 특징에 대해서는 배열(Array)과의 비교를 통해 이해하는 것이 가장 효율적일 것 같다. 그 이후에 단순 연결 리스트의 변형인 이중 연결 리스트, 원형 연결 리스트에 대해 비교해보자. 연결 리스트(Linked List) vs 배열 (Array) 1. 개념적 차이 배열 : 데이터가 메모리 상 연속된 공간에 할당된다. 즉, '논리적 저장 순서'와 '물리적 저장 순서'가 일치한다. 연결 리스트 : 연결 리스트의 노드들은 메모리 상 불연속적인 공간에 존재한다. 즉, '논리적 저장 순서'와 '물.. 2023. 10. 17.
자료구조 | 배열, 스택, 큐 선형 자료구조 데이터를 효과적으로 관리 및 접근하는 방법은 소프트웨어 개발에서 중요한 요소이다. '자료구조 (Data Structure)'는 그 이름에 걸맞게 데이터를 저장, 관리, 조작하기 위한 구조적인 방법을 의미한다. 그 중에서도 선형 자료구조는 이름에서도 알 수 있듯, 데이터 요소들이 선(linear)처럼 일렬로 연결되어 있는 자료구조이다. 선형 구조는 데이터의 시작부터 끝까지 순차적으로 접근한다는 특징을 가진다. 대표적인 선형 자료구조는 다음과 같다. - 기본적인 자료구조: 배열, 문자열, 스택, 큐, 연결 리스트 (단순 연결 리스트) - 심화(응용) 자료구조: 연결 리스트의 변형 (이중 연결 리스트, 원형 연결 리스트), 큐의 변형 (덱) 아래는 위 리스트 중에서 배열, 스택, 큐, 덱에 대한.. 2023. 10. 16.

티스토리툴바