핵심 자료구조 정리

Array

Array는 연관된 data를 메모리상에 연속적이며 순차적으로 미리 할당된 크기만큼 저장하는 자료구조입니다.

Array는 Linked List와 비교되는 특징들이 있습니다.

• 고정된 저장 공간 (fixed size)
• 순차적인 데이터 저장

Array는 lookup과 append가 빠르다는 장점이 있습니다. index를 통해 O(1)으로 데이터에 접근할 수 있기 때문이죠. 따라서 조회가 자주 일어나는 작업에서 Array를 많이 사용합니다.

반면 Array는 fixed-size라는 특성을 갖고 있어 메모리 낭비나 추가적인 overhead가 발생할 수 있습니다. 추가적인 overhead는 동적 배열 처럼 fixed-size 이상의 데이터가 들어올 경우 더 큰 배열을 생성하는 등의 operation입니다.

Array는 순차적인 데이터이기 때문에 중간에 삽입, 삭제 복잡도 역시 O(n)입니다. 중간에 하나의 데이터를 넣거나 삭제 하는 경우 나머지 데이터들의 순서를 맞추기 위해 이동이 필요하기 때문입니다.

Array의 시간 복잡도

• access - O(1)
• append - O(1)
• 마지막 원소 delete - O(1)
• insertion - O(n)
• deletion - O(n)
• search - O(n)

Array의 size를 넘는 양의 데이터 처리

아까 위에서 array는 fixed-size 특징을 갖는다고 했습니다. 만약 이 이상의 데이터가 들어오는 경우 다음과 같이 2가지 방식으로 해결하는 것이 일반적입니다.

• Dynamic Array(동적 배열) - 기존 사이즈보다 더 큰 array를 선언하여 데이터를 옮긴 뒤 할당합니다. 기존에 사용하던 array는 삭제 합니다.
• Array대신 Linked List를 사용합니다. size 예측이 어려운 경우 데이터가 추가될 때마다 메모리 공간을 할당받는 방식도 사용 가능합니다.

Dynamic Array

Array는 fixed-size이기 때문에 size이상의 데이터가 추가되면 저장할 수 없습니다. Dynamic Array는 resize를 통해 유동적으로 size를 조절하여 데이터를 저장하는 자료구조 입니다. Array의 fixed-size를 보완하기 위해 고안되었습니다.

doubling

resize의 대표적인 방법으로 기존 배열의 size보다 2배 큰 배열을 선언하고 데이터를 옮기는 방법입니다.

분할상환 시간복잡도 (Amortized time complexity)

Dynamic array의 데이터 추가는 O(1)의 복잡도를 갖습니다. 그러나 특정 size를 넘어가는 순간 resize가 일어나게 되어 O(n)의 복잡도를 갖게 됩니다.

append는 O(1)이 대다수이고 특정 상황(resize)에서만 O(n)이 발생합니다. 결론적으로 이는 amortized O(1)이 됩니다.

가끔 O(n)이 발생하지만 전체적으로 O(1)의 작업들로 이루어져 있기 때문입니다.

장/단점

• 장점
  • 데이터 접근과 할당이 빠르다 O(1)
  • append가 빠르다 O(1)
• 단점
  • 데이터 추가, 제거가 느리다 O(n) - shifting 작업 때문
  • resize시 성능이 낮아진다.
  • 사용하지 않는 메모리 공간이 발생할 수 있다.

Linked List

Linked List는 Node로 구성된 자료구조입니다. Node에는 데이터 값과 다음 Node의 address가 저장되어 있습니다. Linked List는 물리적인 메모리상에서 비연속적으로 저장되지만 논리적인 연속성을 가진 자료구조 입니다.

논리적 연속성

각 Node들은 next address의 정보를 가지고 있기 때문에 논리적으로 연속성을 유지하며 연결되어 있습니다. 따라서 Array에 비해 메모리 사용이 좀 더 자유롭지만 next address를 추가적으로 저장해야 하기 때문에 데이터 하나당 차지하는 메모리가 더 큽니다.

시간복잡도

Linked List는 데이터 삽입/삭제 시 next address의 주소값만 변경하면 되기 때문에 O(1)의 복잡도를 갖습니다. 그러나 배열처럼 Index의 개념이 없어 특정 데이터를 검색/접근 하는 속도는 떨어지는 편입니다.

• access - O(n)
• search - O(n)
• insertion - O(n)
• deletion - O(n)

Array vs Linked List

Array는 메모리 상에서 연속적으로 데이터를 저장하는 자료구조입니다. Linked List는 다음 원소의 메모리 주소값을 저장하여 논리적으로 연속성을 유지하는 자료구조입니다.

데이터 조회의 경우 Array는 O(1), Linked list는 O(n)의 복잡도를 갖습니다. 반면 삽입/삭제는 Array가 O(n), Linked list가 O(1)의 복잡도를 갖죠.

데이터를 얼마나 저장할지 미리 알고 있고, 조회를 많이 하는 경우 Array를 사용하는 것이 유리합니다. 반면 데이터의 갯수가 불확실하고 삽입,삭제가 잦은 경우 Linked list를 사용하는게 유리할 수 있습니다.

이러한 차이는 저장하는 메모리 구조의 차이에서 기인합니다. Array는 메모리상에서 연속적으로 존재하지만 Linked list는 불연속적으로 저장하기 때문이죠. 이 사실에 입각하여 Array와 Linked list의 특성을 바라보아야 합니다.

lookup(조회)

Array는 메모리상에서 연속적으로 데이터를 저장하였기 때문에 index를 통한 즉시 접근(random access)이 가능합니다(O(1)). 반면 Linked list는 메모리상에서 불연속적이기에 순차 접근만 가능합니다(O(n)).

insert/delete

Array의 경우 append가 아닌 데이터 삽입/삭제는 해당 원소보다 큰 인덱스의 원소를 한 칸씩 shift해줘야 합니다. 따라서 시간 복잡도가 O(n)입니다.

반면 Linked list는 어떤 노드이던 next address만 수정하면 논리적 연속성이 유지됩니다. 따라서 시간복잡도가 O(1)입니다.

하지만 Linked list는 추가/삭제를 위한 index까지 도달하는데 O(n)의 시간이 걸리기 때문에, 실질적으로 Linked list의 추가/삭제도 O(n)으로 보는 경우가 많습니다.

memory

Array는 선언시 fixed size를 설정하여 메모리를 할당하기에 사용하지 않는 공간을 할당받아 메모리 낭비가 발생할 수 있습니다.

Linked list는 runtime에서 size를 늘리고 줄일 수 있습니다. 따라서 initial size를 고민할 필요가 없고, 그만큼 메모리 낭비가 없습니다. 하지만 컴파일 타임에 메모리를 할당받지 않고 데이터 하나당 size가 더 크므로 전체적인 성능이 더 느릴 수 있습니다.

Linked List가 더 유리한 경우

• O(1)의 삽입/삭제가 자주 필요한 경우
• 데이터의 갯수를 예측할 수 없는 경우
• 조회 작업을 많이 하지 않는 경우

Array가 더 유리한 경우

• 조회 작업을 자주 해야 하는 경우
• 데이터의 갯수를 미리 알고 있을 때
• 데이터를 반복문을 통해 빠르게 순회해야 하는 경우
• 데이터의 크기를 알고 있다는 가정 하에 메모리를 적게 쓰고 싶을 때

Memory Allocation

Array는 compile 단계에서 memory allocation이 일어납니다. 이를 Static Memory Allocation이라고 부르며 Stack memory 영역에 할당됩니다.

Linked List는 runtime에서 새로운 node가 추가될 때 마다 memory allocation이 일어납니다. 이를 Dynamic Memory Allocation이라고 하며 Heap memory 영역에 할당됩니다.

Queue

큐는 FIFO(First In First Out)의 자료구조입니다. 대표적 연산인 enqueue, dequeue는 O(1)의 시간 복잡도를 갖습니다. 큐는 캐시 구현, 프로세스 관리, BFS구현 등에 사용됩니다.

큐는 크게 2가지 구현 방식을 갖고 있습니다.

• Array-Based queue: array를 이용해 구현하는 방법으로 enqueue와 dequeue 과정에서 남는 메모리가 발생합니다. 이를 줄이기 위해 Circular queue 형식으로 많이 구현합니다.
• List-Based: Linked list 형태의 구현으로 재할당이나 메모리 낭비의 걱정을 할 필요가 없습니다.

Array-base queue는 메모리를 효율적으로 관리하기 위해 일반적으로 Circular queue로 구현합니다. enqueue가 계속 발생하여 fixed-size를 넘어가면 dynamic array와 마찬가지로 확장이 필요합니다. 따라서 enqueue의 시간 복잡도는 amortized O(1)입니다.

List-base의 경우 singly-linked list로 구현하는 것이 보통입니다.

두 종류의 구현법 모두 enqueue와 dequeue는 O(1)의 복잡도를 갖습니다. Array-base는 전반적으로 퍼포먼스가 더 좋지만, resize와 같은 worst case에서 훨씬 느릴 수 있습니다. List-Base의 경우 enqueue를 할 때 마다 memory allocation이 필요하므로 전반적인 runtime이 느릴 수 있습니다.

Circular Queue

Array-based queue에서 front와 tail의 개념을 갖고 큐를 구현하는 방식입니다. 인덱스와 상관없이 큐의 구현이 가능해져 메모리 낭비를 줄일 수 있습니다.

이 외에도 양쪽에서 enqueue, dequeue가 가능한 deque와 우선순위가 높은 순서로 dequeue 할 수 있는 priority queue가 존재합니다.

Priority queue

우선순위큐는 들어간 순서와 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조 입니다.
Priority queue는

• push - O(logn)
• pop - O(logn)

의 복잡도를 갖습니다.

Heap

힙은 그 자체가 우선순위큐의 구현과 일치합니다. Heap은 완전 이진트리 구조로 다음과 같은 조건을 만족합니다.

• 각 node에 저장된 값은 child node에 저장된 값보다 작거나 같다(min heap)

즉, root node에 최대/최소 값이 존재하는 자료구조 입니다.

일반적으로 tree는 Linked list를 이용하지만, Heap은 array를 기반으로 구현하는 경우가 많습니다. 그 이유는 push 연산시 새로운 node를 힙의 '마지막 위치'에 추가해야 하는데, array기반은 이 과정이 쉽기 때문입니다.

일반적으로 구현의 편의를 위해 0번째 index는 사용하지 않습니다. 이렇게 하면 다음과 같은 조건이 만족됩니다.

• n번 째 node의 left childe node = 2n
• n번 째 node의 right childe node = 2n+1
• n번 째 node의 parent node = n//2 (몫)

push의 경우 맨 마지막 위치에 삽입한 뒤, 힙의 조건을 만족할 때 까지 parent node와 swap을 반복합니다. heap tree의 높이는 일반적으로 (균형이 잡힌 경우) logN이기에 O(logN)의 복잡도를 갖습니다.

pop은 root node를 추출한 뒤, 맨 마지막에 있던 node를 root의 위치로 가져옵니다. 이후 heap의 조건을 만족할 때 까지 child와 swap을 반복합니다. 마찬가지로 O(logN)의 복잡도를 갖습니다.

그러나 항상 logN을 만족하는 것은 아닙니다.

위 와 같이 불균형한 tree역시 heap의 조건을 만족합니다. 이렇게 데이터의 push 순서가 우연히 최악이 될 경우 linked-list와 차이점이 없게 되어 O(N)의 복잡도를 갖습니다.

Stack

스텍은 Last In First Out의 자료구조 입니다. 후위 표기법 연산, 괄호 유효성 검사, 웹 브라우저 방문 기록, DFS구현 등에 사용됩니다.

스텍에 데이터를 추가하는 것을 push, 데이터를 추출하는 것을 pop이라고 하며 두 연산 모두 O(1)의 시간 복잡도를 갖습니다.

stack은 재귀적인 특징이 있어 프로그램 개발에 자주 사용되는 자료구조 입니다.

2개의 stack을 이용한 queue의 구현, 2개의 queue를 이용한 stack구현 등의 문제를 해결해보면 좋습니다.

Binary Search Tree

이진 탐색 트리는 정렬된 이진 tree입니다. 모든 노드의 left subtree는 노드의 값보다 작은 값들을 지닌 node로 구성되어 있고, right subtree는 노드의 값보다 큰 노드로만 구성되어 있습니다.

즉, 다음과 같은 2 가지 조건을 만족합니다.

1. root node의 값보다 작은 값은 left subtree, 큰 값은 right subtree에 존재한다.
2. subtree도 1번 조건을 만족한다.
   

검색과 저장, 삭제의 시간복잡도는 모두 O(logN)이며, worst case는 한쪽으로만 치우친 tree로 O(N)입니다.

worst case를 막기 위해 삽입마다 tree의 높이를 조절하는 균형 이진 탐색트리를 구현하는 경우도 많습니다. 대표적으로 AVL트리, 레드-블랙트리, B 트리 등이 존재합니다. 이와 관련된 내용은 독립적인 포스팅으로 알아보겠습니다.

Hash table

해시 테이블은 효율적인 탐색을 위한 자료구조로 key-value 쌍의 데이터를 입력받습니다. hash function h에 key값을 넣어 얻는 아웃풋 h(key)를 위치로 지정하여 key-value 쌍을 저장합니다.

저장, 삭제, 검색의 시간 복잡도는 모두 O(1) 입니다.

key에 대한 hash function의 output이 범위에 고르게 분포하며 독립적인 값을 가져야하고, 연산속도가 빠른 것이 좋은 hash function입니다.

hash function을 통해 key값을 특정 범위의 숫자로 치환 되기에 모든 형태의 키 값을 (number, string 등) 일정 범위의 index로 치환하는 것이 가능합니다.

이때 "키 k값을 갖는 원소가 위치 h(k)에 hash된다." 또는 "h(k)는 키 k의 해시값이다" 라고 표현합니다.

key는 반드시 존재해야 하며, 중복되는 key가 있어선 안됩니다.

해시 테이블의 데이터를 저장할 수 있는 각각의 공간을 slot 또는 bucket이라고 부릅니다.

하지만 아무리 hash function을 잘 짠다고 하더라도 다른 인풋에 대해 같은 아웃풋이 나오는 경우가 존재합니다. 이런 현상을 collision이라고 하며 이를 해결하기 위한 방법들이 몇 가지 존재합니다.

해시 테이블의 시간복잡도는 저장, 삭제, 검색 모두 기본적으로 O(1)이지만, collision으로 인해 최악의 경우 O(n)이 될 수 있습니다.

공간효율성의 경우 데이터가 저장되기 전 미리 저장공간(bucket)을 확보해야 하기 때문에 떨어지는 편입니다.

Collision

서로 다른 key의 해시값이 똑같은 경우를 말합니다. 이런 경우 크게 2가지 방법으로 해결합니다.

• open addressing - 미리 정한 규칙에 따라 hash table의 비어있는 slot을 찾습니다. Linear Probing, Quadratic Probing, Double Hashing 등으로 나뉩니다.

• separate chaining - linked list 형태를 이용하여 slot을 추가하고 데이터를 저장합니다.

Open addressing

collision이 발생하면 미리 정한 규칙에 따라 hash table의 비어있는 slot을 찾습니다. 추가적인 메모리를 사용하지 않으므로 separate chaining에 비해 메모리를 적게 사용합니다.

Linear Probing, Quadratic Probing의 경우 충돌이 발생한 해시 값으로 부터 일정한 값 만큼 (+1, +2, +3,...) / (+1^2, +2^2, +3^2, ...)건너 뛰어, 비어 있는 slot에 데이터를 저장합니다.

충돌이 여러 번 발생한다면 여러 번 건너 뛰어 빈 slot을 찾습니다. 충돌 횟수가 많아지면 특정 영역에 데이터가 집중적으로 몰리는 clustering 현상이 발생한다는 단점이 있습니다. 클러스터링 발생시 평균 탐색 시간이 증가하게 됩니다.

Double Hashing의 경우 이중해시라고도 불리며 probing방식 중 하나입니다. 클러스터링 문제를 해결하기 위해 고안되었으며, 2개의 함수를 준비하여 하나는 최초의 해싱값을 얻기 위해 사용하고 다른 하나는 collision이 발생한 경우 탐사 이동폭을 얻기 위해 사용합니다.

clustering은 이동폭이 동일하여 발생하는 문제로 이를 해결할 수 있습니다.

separate chaining

linked list 또는 tree를 이용하여 collision을 해결하는 방법으로 충돌이 발생하면 linked list에 노드를 추가하여 데이터를 저장합니다.

• 삽입 - O(1)의 시간복잡도를 갖습니다.
• 검색 - 기본적으로 O(1) 이지만 최악의 경우 O(n)의 시간 복잡도를 갖습니다.
• 삭제 - 삭제를 위해선 검색을 해야 하므로 검색의 시간복잡도와 동일합니다. 일반적으로 O(1), 최악의 경우 O(n) 입니다.

worst case의 경우 모든 key가 동일한 해시값을 갖게 되어 길이 n의 linked list가 생성됩니다. 당연히 이런 경우 O(n)의 시간 복잡도를 갖습니다. (물론 이렇게 되면 안사용 하므로 의미가 없을것입니다..)

collision이 많이 발생하면 BST, 레드블랙트리 등을 이용하여 검색 worst case의 복잡도를 O(logN)으로 낮추기도 합니다.