II. 기본 자료구조

• 자료 구조 : Data structures
• Linked Lists
• Stacks / Queues / Deques
• Implementation
• Standard Library

자료 구조 : Data structures

이 장은 자료 구조에 대한 이야기입니다. 자료 구조는 알고리즘과 매우 밀접한 관련이 있는데, 어떤 식으로 자료가 저장되어 있는지에 따라 알고리즘의 소요 시간이 크게 달라지기 때문입니다. 특정한 자료구조를 이용해야만 빠르게 작동하는 알고리즘들도 수없이 많고, 알고리즘 자체에 명세처럼 이런 자료구조를 써야 한다고 말하는 경우도 많을 것입니다.

Linked Lists

가장 기본적인 자료구조인 Linked List (연결 리스트) 는, 한 줄로 쭉 연결된 노드 들의 연결로 구성됩니다. 대표적은 Dynamic data structure라고 볼 수 있겠습니다. 우리가 앞서 본 바와 같이, 1개가 있을지 5개가 있을지 10만개가 있을지 모르는 상황에서 배열을 쓰려면 가능한 최대를 잡아야 합니다. 이는 매우 비효율적이기 때문에, 이러한 Dynamic data structure에 대한 고민은 매우 중요하다고 할 수 있습니다.

링크드 리스트를 구현하는 방법은 매우 간단합니다. 각 노드가 데이터 와, 다음 노드로 가는 포인터 를 들고 있으면 됩니다. 노드를 struct node 로 관리하면 좋겠네요. 이제...

• 원소를 추가할 때는, 먼저 새 노드를 만든 다음, 추가하려는 위치를 잡고, 그 앞에 있는 노드의 next pointer를 지금 추가하려는 노드로 잡아주고, 새로 추가한 노드의 next pointer를 관리하면 간단합니다.

• 원소의 삭제는, 삭제하려는 노드 이전 노드를 찾아서 그 next pointer를 삭제하려는 노드의 다음 노드로 보내주면 됩니다. Dynamic memory alloc/dealloc에 주의해 주세요.

자료구조 / 알고리즘을 공부할 때 좋은 rule of thumb 중 하나는, 뭔가를 얻었으면 뭔가를 지불해야 한다는 점입니다. 이 손해는 구현의 난이도일수도 있고, 상수가 크다는 점일 수도 있고, 다른 연산이 느릴 수도 있는데, 링크드 리스트는 이 대표적인 사례 중 하나입니다. 먼저...

• 10만개짜리 리스트 중 5만 6천번째가 뭔지 확인하고 싶으면, head부터 next포인터를 5만6천번 따라가야 합니다.

• 삭제할때, 이전 노드를 찾는 작업이 굉장히 귀찮습니다. ‘지금 보고 있는 노드’ 뿐 아니라, ‘그 직전 노드’ 가 뭔지도 관리하면서 Loop를 돌려야 하기 때문입니다.

후자는 구현상의 문제니 뭐 그렇다고 치더라도, 시간 복잡도로 생각해 보면 임의 위치의 삽입/삭제/접근이 모두 $O(n)$ 시간이 걸린다고 할 수 있습니다.

배열의 경우, 임의 삽입은 개수가 넘어가면 안 될수도 있고, 되더라도 삽입 삭제는 $O(n)$이 걸리는데 비해 접근은 $O(1)$에 할 수 있으므로, 동적 리스트를 얻기 위해 임의접근 속도를 포기했다고 보면 되겠습니다.

변형된 형태의 동적 리스트로, 다음 노드 뿐 아니라 이전 노드로 가는 포인터도 관리하는 double linked list, 구현상의 편의를 위해 Head와 Tail을 이어 버리는 circular linked list 등등이 있습니다.

Stacks / Queues / Deques

스택은 Last-in First-out (LIFO) 형태의 자료구조입니다. 즉, 다음 두 연산을 지원하는 자료구조를 말합니다.

• Element를 맨 위에 추가 (push)

• 맨 위에 쌓은 element를 빠르게 확인하거나 (peek), 가져오기 (pop)

여기서, 할 수 있다 는 말은 사실 빠르게 할 수 있다 는 말입니다. 당연히 스택에서 맨 밑 원소를 보는것도 그 위에 $n$개의 원소를 다 뽑아내면 할 수는 있습니다. 다만 위 두 연산을 $O(1)$에 할 수 있음이 중요합니다.

Queue는 First-in First-out (FIFO) 형태의 자료구조입니다. Stack과는 달리, Element를 위에서 넣고 뺄 때는 아래에서만 뺀다고 생각하면 됩니다.

Deque는 Queue와 Stack의 기능을 합쳐, Front/Rear access와 insert가 모두 $O(1)$에 작동하는 자료구조입니다.

이 세 가지에 대한 자세한 설명은 워낙 좋은 내용들이 많고, 어려운 내용도 아니라서 패스하겠습니다.

Implementation

세 자료구조 모두 개념적으로는 Doubly Linked List로 구현하면 됩니다. 구현의 용이성을 위해 Dynamic함을 포기하고 1차원 배열에다가 배열의 양 끝을 표시하는 index variable 2개를 쓰는 구현도 많이 사용하는데, 이 경우에는 메모리에만 들어가면 원하는 만큼 많이 넣을 수 있다는 기본적인 가정을 위배하는데 비해 시간복잡도상의 이득이 있지는 않으므로 우리의 관심사는 아닙니다.¹

Standard Library

STL에는 stack, queue, deque가 다 있습니다. deque<int> dq; 와 같이 선언하고 쓸 수 있습니다.

• {push/pop}_{back/front}() 의 4개 함수를 제공합니다. 당연히 stack이나 queue는 제약이 있습니다.

• top(), front(), back() 등 peek-형 함수들이 있습니다.

• 미세하게 문법이 다른데, 쓰면서 익히면 됩니다. 특히, stack이나 queue는 어차피 넣고빼는 위치가 정해져 있으므로 그냥 push/pop으로 사용하도록 되어 있습니다. 위 설명은 deque가 기준입니다.

• vector는 스택이 할 수 있는 모든 것을 동일한 시간 복잡도에 할 수 있으므로, stack임을 명시하고 싶은 상황이 아니라면 vector를 써도 됩니다.