나작코

그래프(Graph)란 인터넷, 도로, 운송, 전력, 상하수도망, 신경망, 화학성분 결합 등 광범위한 분야에서 활동되는 자료구조입니다. 연결된 정점 간 관계를 표현할 수 있습니다. 모든 정점이 서로 연결된 완전 그래프는 정점이 N개일 경우 간선의 수는 n(n-1)/2개입니다. 가중치(Weighted) 그래프는 간선에 값이 있어 이동 비용이 발생합니다. 가중치는 실제 두 정점 사이의 거리가 될 수도 있고, 두 정점을 연결하는 간선을 지나는 데에 소요되는 시간일 수도 있습니다. 응용에 따라 가중치가 음수인 경우도 존재합니다. 최소 신장 트리(Minimum Spannig Tree)를 찾기 위한 알고리즘과 다양한 최단 경로를 찾는 알고리즘에 활용할 수 있습니다. 그래프는 정점(Vertex)과 간선(Edge)의 집..

우선순위 큐(Priority Queue)란 가장 높은 우선순위를 가진 항목에 접근하거나 삭제하는 연산과 임의의 우선순위를 가진 항목을 삽입하는 연산을 지원하는 자료구조입니다. 스택이나 큐도 일종의 우선순위 큐로, 스택의 경우 가장 마지막으로 삽입된 항목이 가장 높은 우선순위를 가지며, 최근 시간일수록 높은 우선순위를 부여하는 우선순위 큐입니다. 큐의 경우 먼저 삽입된 항목이 우선순위가 더 높습니다. 따라서 이른 시간일수록 더 높은 우선순위를 부여하는 우선순위 큐입니다. 우선순위 큐는 배열, 연결 리스트, 힙을 이용하여 구현할 수 있습니다. 정렬된 배열과 연결 리스트에서의 삽입과 삭제의 시간 복잡도는 각각 O(N)과 O(1)입니다. 그러나 힙의 경우에는 각각 O(logN)이므로 일반적으로는 힙 자료구조가 ..

이진 힙(Binary Heap)이란 완전 이진 트리로서 부모의 우선순위가 자식의 우선순위보다 높은 자료구조입니다. 다른 트리 자료구조와 다르게 중복 값을 허용합니다. 각 노드에 대해 부모의 우선순위가 자식의 우선순위보다 높은 것을 힙 속성(Heap Property)이라 합니다. 이진 힙에는 키가 작을수록 높은 우선순위를 가지는 최소 힙(Minimum Heap)과 클수록 더 높은 우선순위를 가지는 최대 힙(Maximum Heap)이 있습니다. 최솟값 또는 최댓값을 빠르게 찾아내는 데 유용합니다. 그러나 형제 노드 간 우선순위 보장이 없으므로 반 정렬 상태입니다. 최소 힙 삽입과 삭제 구현 코드 import java.util.ArrayList; class MinHeap { ArrayList heap; pub..

해시 테이블(Hash Table)이란, 키와 값을 대응시켜 저장하는 데이터 구조입니다. 키를 배열의 인덱스로 그대로 사용하면 메모리 낭비가 심해질 수 있습니다. 해시 테이블에서는 이러한 문제를 해결하여 키를 간단한 함수를 사용해 변환한 값을 배열의 인덱스로 이용하여 항목을 저장합니다. 이를 해싱(Hashing)이라고 합니다. 해싱에 사용되는 함수를 해시 함수(Hash Function), 해시 함수가 계산한 값을 해시값(Hash value) 또는 해시 주소라고 합니다. 배열을 이용하여 해시 테이블 직접 구현한 코드 class HashTable { Integer[] table; int elementCount; HashTable() {} HashTable(int size) { this.table = new I..

레드 블랙 트리(Red-Black Tree)란 노드에 각 색을 부여하여 트리의 균형을 유지하며 탐색, 삽입, 삭제 연산의 수행 시간이 각각 O(logn)을 넘지 않는 매우 효율적인 자료구조입니다. 일반적으로 삽입이나 삭제를 수행할 때 트리의 균형을 유지하기 위해 상당히 많은 경우를 고려해야 한다는 단점이 있습니다. 그러나 좌편향 레드 블랙(Left-Leaning Red-Black; LLRB) 트리는 삽입이나 삭제 시 고려해야 하는 경우의 수가 적으며, AVL 트리, 2-3 트리, 2-3-4 트리, 일반 레드 블랙 트리보다 매우 우수한 성능을 보입니다. LLRB 트리는 다음의 조건을 만족합니다. 루트와 null은 블랙 루트로부터 각 null까지 2개의 연속된 레드 link는 없음 루트로부터 각 null까지..

AVL 트리란 트리가 한쪽으로 치우쳐 자라나는 현상을 방지하여 트리 높이의 균형을 유지하는 이진 탐색 트리를 의미합니다. 트리에 노의 삽입이나 삭제로 인해 균형이 깨졌을 때, 회전 연산을 통하여 트리의 균형을 유지합니다. 왼쪽과 오른쪽 서브트리의 높이 차이가 2 이상일 때 불균형이 발생했다고 합니다. AVL 트리에서 삽입 또는 삭제 연산을 수행할 때 트리의 균형을 유지하기 위해 LL, RR, LR, RL 회전 연산이 사용됩니다. 각 회전 연산은 두 종류의 기본적인 연산으로 구현되는데, 오른쪽으로 회전하는 rotateRight와 왼쪽으로 회전하는 rotateLeft입니다. AVL 트리에서의 삽입과 삭제 구현 코드 class Node { int key; int height; Node left; Node ri..

이진 탐색 트리(Binary Search Tree; BST)란 이진 탐색의 개념을 트리 형태의 구조에 접목한 자료구조입니다. 이진 탐색을 수행하기 위해 단순 연결 리스트를 변형시킨 것입니다. 이진 탐색은 정렬된 데이터의 중간에 위치한 항목을 기준으로 데이터를 두 부분으로 나누어 가며 특정 항목을 찾는 탐색 방법입니다. 각 노드 n에 저장된 키가 n의 왼쪽 서브트리에 있는 노드에 저장된 키보다 크고 n의 오른쪽 서브트리에 있는 노드의 키보다 작은 것이 이진 탐색 트리의 조건입니다. 각각의 서브 트리도 이진 탐색 트리를 유지하면서 중복된 키를 허용하지 않습니다. 특징 중 하나는 트리를 중위 순회(Inorder Traversal)하면 오름차순으로 정렬된 출력을 얻을 수 있다는 점입니다. 또 균형이 유지된 이진..

이진 트리(Binary Tree)는 각 노드의 자식 수가 2 이하인 트리를 의미합니다. 데이터의 구조적인 관계를 잘 반영하고, 효율적인 삽입과 탐색을 가능하게 하며, 이진 트리의 서브트리를 다른 이진 트리의 서브트리와 교환하기가 쉽습니다. 이진 트리에는 두 종류의 특별한 형태를 가진 트리가 존재합니다. 모든 이파리의 깊이가 같고 각 내부의 노드가 2개의 자식을 가지는 포화 이진 트리(Perfect Binary Tree)와 마지막 레벨을 제외한 각 레벨이 노드들로 꽉 차있고, 마지막 레벨에는 노드들이 왼쪽부터 빠짐없이 채워진 완전 이진 트리(Complete Binary Tree)입니다. 완전 이진 트리를 저장하기 위해 배열을 사용하는 경우, 레퍼런스를 저장할 메모리 공간이 필요 없으므로 매우 효율적입니다...

트리(Tree)란 실제 트리를 거꾸로 세워 놓은 형태의 자료구조입니다. 노드와 링크로 구성되어 있습니다. 하나의 노드에서 다른 노드로 이동하는 경로가 유일하며, 모든 노드는 서로 연결되어 있습니다. 배열이나 연결 리스트는 데이터를 일렬로 저장하기 때문에 일반적으로 탐색 연산이 순차적으로 수행되어야 한다는 단점을 가집니다. 트리는 이러한 문제점을 보완하여 다양한 형태로 광범위하게 응용됩니다. 일반적인 트리(General Tree)는 HTML과 XML의 문서 트리, 자바 클래스 계층구조, 운영체제의 파일 시스템, 탐색 트리, 이항 힙, 피보나치 힙과 같은 우선순위 큐에서도 사용됩니다. 이를 메모리에 저장하려면 각 노드에 키와 자식 수만큼의 레퍼런스를 저장해야 합니다. 따라서 트리 노드의 최대 차수가 k라면,..

데크(Double-ended Queue; Deque)란 양쪽 끝에서 삽입과 삭제를 허용하는 자료구조입니다. 스택과 큐 자료구조를 혼합한 자료구조라고 할 수 있습니다. 예를 들어 스크롤, 문서 편집기 등의 undo 연산, 웹 브라우저의 방문 기록 등에 사용됩니다. 웹 브라우저 방문 기록의 경우, 최근 방문한 웹 페이지 주소는 앞에 삽입하고 일정 수의 새 주소들이 앞쪽에서 삽입되면 뒤에서 삭제가 수행됩니다. 데크를 배열이나 이중 연결 리스트로 구현한 경우, 스택과 큐의 연산 수행 시간과 같습니다. 하지만 양 끝에서 삽입과 삭제를 할 수 있으므로 프로그램이 복잡해집니다. 자바는 java.util 패키지에서 Deque 인터페이스를 제공하며 이는 Queue에서 상속됩니다. 주요 메소드 삽입 addFirst(): ..