자료구조

Array, LinkedList, HashTable, Stack & Queue 시간 복잡도

1. Arrays - Accessing a value at a given index : O(1) - Updating a value at a given index : O(1) - Inserting a value at the beginning : O(n) - Inserting a value in the middle : O(n) - Inserting a value at the end : O(1) - dynamic array, O(n) - static array - Removing a value at the beginning : O(n) - Removing a value in the middle : O(n) - Removing a value at the end : O(1) - Copying the array :..

4. heap, priority queue, union find

Heap 자료구조의 일종으로 Tree의 형식을 하고 있으며, Tree 중에서도 배열에 기반한 Complete Binary Tree 이다. 배열에 트리의 값들을 넣어줄 때, 1번 index 부터 루트노드가 시작된다. 힙에는 Max heap과 Min heap 두 종류가 있다. Max Heap 이란, 각 노드의 값이 해당 children의 값보다 크거나 같은 complete binary tree를 말한다. Max Heap 에서 최대값을 찾는데 필요한 시간복잡도는 O(1)이다. 하지만 heap의 구조를 계속 유지하기 위해서는 제거된 루트 노드를 대체할 다른 노드가 필요하다. 여기서 heap은 맨 마지막 노드를 루트 노드로 대체한 후, 다시 heapify 과정을 거쳐 heap 구조를 유지한다. 이런 경우엔 O(l..

3. Tree

Tree 트리는 스택이나 큐와 같은 선형구조가 아닌 비선형 자료구조이다. 트리는 계층적 관계를 표현하는 자료구조이다. 트리의 구성 요소 Node(노드) : 트리를 구성하고 있는 각각의 요소 Edge(간선) : 트리를 구성하기 위해 노드와 노드를 연겨하는 선 Root(루트) : 트리 구조에서 최상위에 있는 노드 Terminal or Leaf Node(단말 노드) : 하위에 다른 노드가 연결되어 있지 않은 노드 Internal Node(비단말 노드) : 단말 노드를 제외한 모든 노드로 루트 노드를 포함 이진 트리(Binary Tree) 루트를 중심으로 두 개의 서브 트리로 나뉜 트리이다. 또한 나뉜 두 서브 트리도 모두 이진 트리어야 한다. 재귀적인 성질을 가지고 있다. 추가로 공집합도 이진 트리로 포함시켜..

2. Stack and Queue

Stack Stack은 나중에 들어간 원소가 먼저 나오는 Last In First Out(LIFO) 자료구조이다. 차곡차곡 쌓이는 구조로 먼저 Stack에 들어간 원소는 바닥에 깔리게 된다. 후에 들어간 원소는 그 위에 쌓이고 호출 시 가장 위에 있는 원소가 호출된다. Queue Queue는 먼저 들어간 원소가 먼저 나오는 First In First Out(FIFO) 자료구조이다. Stack과 반대로 먼저 들어간 원소가 맨 앞에 대기하고 있다 호출 시 먼저 호출되는 구조이다.

1. Arrays vs Linked List

Array Array는, 인덱스와 인덱스에 대응하는 데이터들도 이루어진 자료구조이다. 따라서 인덱스로 해당 원소에 접근할 수 있다. 따라서 해당 원소의 인덱스 값을 알고 있으면 O(1)에 접근 할 수 있다. 즉, Random Access가 가능하다는 장점이 있다. 하지만, 삭제 또는 삽입의 과정에서 해당 원소에 접근해 작업을 완료한 후 (O(1)의 시간복잡도 발생) 추가적인 작업이 필요하다. 삭제의 경우, 삭제한 원소를 기준으로 더 큰 인덱스를 가지고 있는 원소들을 오른쪽으로 이동시켜야 하므로 최악의 경우 O(n)의 시간복잡도가 발생한다. 삽입의 경우, 삽입한 원소를 기준으로 더 큰 인덱스를 가지고 있는 원소들을 오른쪽으로 이동시켜야 하므로 최악의 경우 O(n)의 시간복잡도가 발생한다. Linked Li..