Study/DataStructure 썸네일형 리스트형 [Data Structure] Union-Find 유니온 파인드 그래프 알고리즘의 일종으로, 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이다. 이는 다른 말로 서로소 집합 혹은 Disjoint-Set이라 부른다. 즉, 유니온 파인드 연산은 그래프에서 특정 두 노드가 서로 연결되어 있는지 아니면 연결되지 않았는지 판별하기 위한 알고리즘이다. 유니온 알고리즘은 기본적으로 배열을 이용한다. 각각의 노드들은 배열에 자기 자신의 값을 가지고 있다. 이상태에서 노드는 단절된 상태이다. 만일, 123과 67을 연결하는 간선을 추가하고 싶다면, 2번 배열은 1번에 연결되므로 값을 1로 변경, 3번 배열은 값 2번 배열에 연결되므로 값을 2로 변경한다. 6과 7도 마찬가지로 이를 시행한다. 위 처럼 여러 노드를 연결하여 그래프를 구성하는 방법도 위와 동일하다. .. 더보기 [Data Structure] Priority Queues, Heaps, Graphs and Sets 1. 우선순위 큐 우선순위를 가지는 Queue이다. 기존의 Queue에 priority라는 변수를 추가적으로 선언, Queue를 dequeue할 때, 이 Priority를 기준으로 dequeue한다. 이때, 동일한 Priority를 가지고 있다면, FIFO로 dequeue한다. 2. 힙 Heap은 Binary Search Tree와 유사한 자료구조다. 이는 BST에 우선순위 큐를 위하여 만들어진 자료구조로, 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아낼 수 있도록 만들어진 자료구조이다. max Heap 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리 min Heap 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리 구현은 다음 포스팅을 참조하면 .. 더보기 [Data Structure] Binary Search Tree 1. Tree 트리는 노드로 구성된 자료구조이다. 트리의 기본 조건은 다음과 같다. 시작점을 나타내는 유일한 시작 노드인 'Root Node'를 가진다. Root Node는 0개 이상의 Child Node를 가진다. 해당 Child Node는 Parent Node로써 0개 이상의 Child Node를 가지고 있고, 이는 반복적으로 정의된다. 트리는 기본적으로, 사이클이 존재하지 않는다. 이는 Graph와의 차이점이다. 트리의 구성 요소 Root: 트리의 unique한 시작 노드 Node: 트리를 구성하는 단위 Parent Node: 1개 이상의 Child Node를 갖는 선행 노드 Child Node: 하나의 Parent Node를 갖는 후행 노드 Level: Root Node를 기준으로 Tree의 De.. 더보기 [Data Structure] Recursion 재귀함수 자기 자신을 호출하는 함수이다. 가장 널리 알려진 예제가 펙토리얼(!) 계산 문제이다. 재귀함수를 이용하면 Divide and Conquer, Binary Search Tree 등을 구현할 수 있다. 개념적으로 중요한 함수이지만 실행시간 측면에서는 썩 유리한 함수는 아니다. 호출하는 값이 커질수록, 수행시간이 기하급수적으로 증가하기 때문이다. 더보기 [Data Structure] List Plus 1. Circular Linked List 연결 리스트가 원형으로 돈다. 앞선 Queue와 마찬가지로, front와 rear를 연결해준다. 2. Doubly Linked List 앞 뒤 요소간 연결이 이중으로 연결된 것이다. 앞 요소는 뒷 요소를 가리키고, 이와 동시에 뒷 요소는 앞 요소를 가리킨다. 이 방법을 이용하면, 한 쪽으로만 이동 즉 탐색 시간을 줄일 수 있다. 단, 기존 방식에서 next 포인터가 아닌 별도의 포인터가 하나 더 필요하며, 할당 시 조금 더 복잡해진다. 더보기 [Data Structure] Linked Structure 연결된 구조 기존의 자료구조들은 배열을 기반으로 구성되었다. 이러한 배열구조 기반의 단점은 해당 구조의 크기가 동적으로 할당되기 어렵다는 뜻이다. 즉, 크기에 제한이 생긴다는 단점이 존재한다. 이러한 단점을 보안하기 위해 구상된 것이 'Linked'이다. 쉽게 생각하면, data부와 pointer부 2개의 공간이 존재하고, pointer부에서 다른 객체를 가리키고 이러한 구조가 반복적으로 이루어 진 것이다. struct NodeType { ItemType info; NodeType* next; } 1. Linked Stack 기존의 Stack 구조에 존재하는 데이터 타입을 구조체로 선언하여 위 사진과 같이 선언한다. 연결된 스택은 항상 맨 위를 가리키는 topPtr이 존재하고, 이를 이용해 스택의 LIF.. 더보기 [Data Structures] Stack & Queue 1. Stack LIFO ADT MakeEmpty Boolean IsEmpty Boolean IsFull Push(ItemType newItem) Pop ItemType Top() Variation Array Stack Linked List Stack C++ Header: 2. Queue FIFO ADT MakeEmpty Boolean IsEmpty Boolean IsFull Enqueue(ItemType newItem) Dequeue Variation Linear Quene Circular Queue Priority Queue C++ Header: 더보기 [Data Structures] Unsorted List & Sorted List 1. List 컴퓨터 프로그램에서 리스트는 굉장히 중요한 추상 자료형이다. C++의 겨웅, STL에서 기본적으로 제공하는 자료형이기도 하다. 이론적 관점에서 리스트는 요소들 간의 선형 관계를 가진 동질적인 요소들의 집합이다. 여기에서 말하는 선형 관계란, 첫번째 요소를 제외한 모든 원소들은 고유한 선행 요소를 가지고 있고, 마지막 요소를 제외한 모든 원소들은 고유한 후속 요소를 가지고 있다는 뜻이다. element1 element2 element3 element4 element5 2. Unsorted List 정렬되지 않은 리스트는 리스트의 각 요소들이 특정한 순서에 맞게 정렬되지 않은 경우를 말한다. 3. Sorted List 정렬되지 않은 리스트는 리스트의 각 요소들이 특정한 순서에 맞게 정렬된 경우.. 더보기 이전 1 2 다음
