6. 자료구조 & 알고리즘/6-1. 자료구조

자료구조 - [ 최소 신장 트리 ]

최소 신장 트리 신장 트리란 순환 없이 모든 정점을 연결하는 그래프를, 최소 신장 트리란 모든 정점을 순환 없이 최소 간선 비용으로 모든정점을 연결하는 그래프를 말한다. 절단(Cut) 그래프를 절단(S, V-S) 하면 임의의 S라는 정점의 집합과, V-S 정점의 집합으로 분리된다. 교차(cross) / 존중(respect) S의 정점와 V-S의 정점을 연결하는 간선을 교차(cross)한다고 부른다. 절단선을 기준으로 교차하지 않는 간선의 집합을 존중한다(respect)라고 한다. 경량 간선(light edge) / 안전 간선(safe edge) 절단선을 교차하는 간선 중 가중치가 최소인 간선을 경량 간선이라고 한다. 최소 신장 트리를 만족하며 루프 불변성을 유지하기 위해 경량 간선이면서 그래프를 순환하지..

자료구조 - [ 그래프 ]

그래프 정점(Vertext)과 정점을 연결하는 간선(Edge)의 집합으로 구성된 자료구조를 그래프라 부르며 G=(V,E)로 표기한다. V는 정점의 집합이며, E는 간선의 집합이다. 그리고 정점 u는 정점의 집합 V에 속해있으며, 간선(u,v)는 간선의 집합 E에 속해있다. 완전 그래프 모든 정점끼리 간선으로 연결되어 있는 것을 완전 그래프라고 한다. 무방향 그래프 / 방향 그래프 무방향 그래프는 방향이 없는 간선을 가지고 양방향으로 진행할 수 있으며, 간선은 (u1, v2), (u2, v2)로 표현할 수 있다. 방향 그래프는 방향이 있는 간선을 가지며 각 간선은 한 방향으로만 진행할 수 있다. 간선은 , 로 표현한다. 차수(Degree) 정점에 접한 간선의 수를 차수라고 한다. 무방향 그래프에서는 특정 ..

자료구조 - [ 해시 테이블 ]

해시 테이블 해시 테이블은 키와 값의 구조를 가진 데이터를 저장하며, 해시 함수를 이용하여 키 값을 해시값으로 변환 후, 해시값을 해시 테이블의 인덱스로 사용하는 자료구조이다. 평균적으로 시간 복잡도 O(1)의 탐색 성능을 가지고 있기 때문에 빠른 탐색이 필요할 때 사용한다. 해시 함수를 이용하므로 해시값의 충돌이 발생할 수 있다. 좋은 해시 함수는 충돌 가능성을 낮추므로 최대한 고른 값을 가진 함수를 만들어야 한다. 버킷 : 해시값을 인덱스로 접근할 수 있는 배열. key-value 쌍의 참조값을 가지고 있으며, 배열 접근의 시간 복잡도는 O(1)이다. 엔트리 : 해시 테이블은 키와 값을 저장하는 구조이므로 노드를 이용하여 키와 값을 저장할 수 있다. 해시 함수 : 해시 함수와 보조 해시 함수를 이용하..

자료구조 - [ B-트리 ]

B-트리 B-트리에서는 한 노드가 여러 개의 데이터를 가질 수 있으며 여러 자식 노드를 가질 수 있다. 1. 분기 요소(Branching Factor)라는 개념을 통해 한 노드가 가질 수 있는 데이터와 자식 수가 달라진다. 2. 모든 Leaf노드는 같은 깊이를 가진다. 그러므로 균형 있는 트리이다. 3. 특정 키를 기준으로 작은 키는 좌측에 큰 키는 우측에 배치되며, 좌측 자식은 특정 키보다 작은 키들의 모음이고, 우측 자식은 큰 키들의 모음이다. => 트리를 중위 순회하면 정렬된 키를 얻을 수 있다. 4. 분기 요소(t)가 존재하며 최소 t의 수는 2

자료구조 - [ Binary Heap ]

Binary Heap Heap은 트리에 기반한 특별한 자료구조로 우선순위가 높은 데이터가 부모로 배치되고 우선순위가 낮은 데이터가 자식으로 배치되는 관계를 가지고 있다. 삽입 순서와 상관없이 항상 우선순위가 가장 높은 데이터를 꺼내거나 삭제하기 때문에, 우선순위가 필요한 대기열이나 데이터 정렬이 필요할 때 사용할 수 있다. Heap에는 Binary Heap, Fibonacci Heap 등이 존재한다. Binary Heap은 Complete Binary Tree의 구조를 가지고 있으며, 삽입과 삭제 시 트리를 우선순위에 따라 재배치하는 과정을 거친다. Binary Heap 삽입 삽입시 항상 맨 마지막 Leaf 노드로 삽입되며, 삽입 후 부모의 우선순위와 비교해 Swap 한다. 부모의 우선순위보다 낮을 때까..

자료구조 - [ Red-Black 트리 ]

Red-Black 트리 Red-Black 트리는 AVL 트리와 비슷하게 스스로 균형 잡는 이진 탐색 트리로, 삽입/삭제 시 노드가 가지고 있는 색깔을 이용한 규칙을 통해 불균형을 완화하는 트리이다. 노드의 재배치를 빈번하게 실행하지 않기 때문에 삽입/삭제 연산이 많은 경우 AVL 트리보다 평균적으로 더 나은 성능을 가지고 있고, AVL 트리보다 덜 균형하기 때문에 탐색 횟수는 더 많을 수 있다. => 삽입/삭제 연산이 빈번하면 Red-Black 트리 / 탐색의 성능이 더 중요한 경우 AVL 트리를 이용하는 것이 낫다. 모든 노드는 빨강 또는 검정 루트 노드는 최종적으로 항상 검정 모든 Leaf 노드는 루트 노드와 동일한 색상을 가짐 모든 빨강 노드의 자식은 검정 노드(검정 노드의 자식은 상관 X) => ..