자료구조 (1)

Array

배열은 같은 타입의 자료 여러 개를 일직선으로 저장하는 자료구조이다. 메모리 공간에도 연속적으로 저장되는 특성 때문에 대량의 비트 연산을 쉽게 수행할 수 있다. 모든 자료가 연속적으로 저장되므로, 첫 번째 원소의 주소만 알면 상수 시간에 모든 원소에 접근할 수 있다. 

 

그러나 (맨 뒤에 삽입하는 경우를 제외하면) 삽입과 삭제 연산을 처리하는 데 선형 시간이 걸린다. 삽입 또는 삭제하는 위치 뒤에 있는 요소들을 뒤로 밀거나(삽입) 앞으로 당겨와야(삭제) 하기 때문이다.

 

배열이 꽉 찼다면 메모리를 추가로 할당받아야 한다. 운이 나쁘다면 아예 다른 위치로 값을 옮겨야 할 수도 있다.

LinkedList

값을 연속해서 저장하지 않고, 다음 값의 주소만을 가리키는 방식으로 저장한다. 메모리 상에 연속해서 저장되지 않으므로 임의의 원소에 접근하는 데 선형 시간이 걸린다.

 

반대로 어떤 위치에 값을 삽입하거나 해당 값을 삭제하는 연산은 상수 시간에 가능하다. 값들이 연속해서 저장되지 않기 때문에 뒤에 있는 값들을 밀거나 당겨올 필요가 없기 때문이다. 따라서 삽입과 삭제가 빈번한 상황에서는 Array보다 LinkedList가 적합하다.

 

하지만 삽입(삭제)할 위치까지 가는 데 선형 시간이 걸리기 때문에, 실질적으로 삽입(삭제) 연산도 선형 시간이라 볼 수도 있다.

 

다음(또는 이전) 값을 가리키는 방법에 따라 단방향, 양방향, 순환형 LinkedList가 존재한다.

Array vs. LinkedList

• 메모리 할당
  • Array는 컴파일 시간에 메모리가 할당된다. (물론 동적 할당도 있지만..)
  • LinkedList는 값을 삽입할 때마다 메모리가 하나씩 할당된다.
• Random Access 성능
  • Array는 상수 시간에 가능.
  • LinkedList는 선형 시간에 가능.
• 삽입(삭제) 연산
  • Array는 선형 시간에 가능. 뒤에 있는 값들을 전부 옮겨야 하기 때문이다.
  • LinkedList는 상수 시간에 가능. 값을 새로 만들고 링크만 연결하면 되기 때문이다. 하지만 상술했듯이 삽입(삭제)할 위치까지 가는 데 선형 시간이 걸리므로 실질적으로는 선형 시간으로 볼 수도 있다.

결론

Random Access는 Array, 삽입(삭제)는 LinkedList를 사용하여 작업하자.

ArrayList

List는 Array와 매우 유사하지만, 선언할 때 크기를 명시적으로 지정하지 않는다. Array에서는 인덱스가 중요했지만, List에서는 상대적인 순서가 중요하다.

 

Java 계열 언어에서는 조금 더 다른데, Array의 값은 수정할 수 있는 반면 List의 값은 ``MutableList`` 구현체를 제외하면 수정할 수 없다. Java에서 List란 변하지 않는 값들의 집합을 의미하기 때문이다.

 

List를 구현하는 방법에는 여러 가지가 있다. 그 중 ArrayList는 Array의 빠른 접근 성능을 활용한 구현체이다. 물론 Array 기반이므로 삽입 및 삭제 성능은 좋지 않다.

Stack

값을 밑에서부터 '쌓아서' 저장한다고 생각해 보자. 그러면 값을 어디서 뺄 수 있을까? 맨 밑에서 빼면 쌓은 값들이 우르르 무너질 것이다. Stack은 이름에서 알 수 있듯이 맨 위에서만 값을 삽입(삭제)할 수 있는 자료구조이다.

 

Stack에서는 가장 나중에 넣은 값이 맨 위에 쌓이고, 맨 위의 값이 가장 먼저 뽑힌다, 가장 늦게 넣은 값이 가장 먼저 뽑힌다는 것이다. 이런 특성을 쓸데없이 LIFO(Last In First Out)이라고 부르기도 한다.

 

맨 위를 제외한 어떠한 위치의 값에도 접근할 수 없다. Stack을 배열로 구현하는 경우가 많아 억지로 메모리 연산을 하면 접근할 수도 있겠지만, 자료구조의 의미를 정면으로 부정하는 행위임을 기억하기 바란다. 어차피 Stack을 쓰는 경우는 맨 위의 값만 신경쓰면 되는 상황이 많을 것이다.

 

Array로 구현해도 되고, 어차피 값을 맨 끝에서만 추가(삭제)하기 때문에 LinkedList로 구현해도 된다. 

Queue

Stack과는 다르게 뒤에서 넣고 앞에서 빼는 자료구조이다. 그래서 먼저 넣은 값이 먼저 나온다. 이걸 쓸데없이 FIFO(First In First Out)이라고 부르기도 한다.

 

접속 대기열 처리 등 들어온 순서대로 처리해야 하는 상황에서 사용할 수 있다. 

 

Stack과 마찬가지로 Array와 LinkedList 모두 사용해서 구현할 수 있다. 그런데 Array로 구현하면 데이터를 뒤에 넣는 Queue 특성상 데이터가 계속 뒤로 밀린다. 그러다 Array가 꽉 차면 (실제로는 공간이 남아있음에도 불구하고) 배열이 꽉 찼다고 판정될 수도 있다. 이런 상황에서는 배열의 처음과 끝을 원형으로 이은 것처럼 구현하면 된다. 

 

LinkedList로 구현했다면 리스트의 처음과 끝만 잘 추적하면 된다. 가운데에서 어떻게 연결됐는지는 알 필요 없으니까.

Heap

Heap은 완전 이진 트리 형태를 띠는 자료 구조로, 특정한 연산을 빠르게 수행하기 위해 만들어졌다. 대표적으로 최댓값이나 최솟값을 빠르게 찾는 연산 등을 수행할 수 있다. 

 

사실 정수의 대소 비교 이외에도 일반적인 비교 연산을 수행할 수 있다. 값 중에서 특정한 기준으로 비교했을 때 가장 먼저 와야 하는 값이 Heap의 루트가 된다. 최대 힙은 최댓값이 가장 먼저 와야 하므로 최댓값이 루트에 있는 것이다.

 

(최대 힙이라면) 루트 밑에는 루트보다 약간 작은 값, 그 밑에는 더 작은 값... 이렇게 이어지게 된다. 말인즉슨 부모는 자식보다 반드시 먼저 온다라는 것. 최대 힙에서 자식이 부모보다 클 수는 없다. 그건 버그이다.

삽입

삽입과 삭제 모두 최대 힙을 기준으로 설명하겠다.

 

원소를 삽입할 때, 일단 삽입할 값을 힙의 맨 끝에 추가한다. 그 후 부모와 자신을 비교하면서 자신이 부모보다 먼저 와야 한다면 자신과 부모를 교환한다. 이런 식으로 부모가 자신보다 먼저 와야 할 때까지 값을 위로 올리는 것이다.

일단 리프 노드에 추가하고

위로 올린다.

삽입 연산의 시간복잡도는 $O(\log N)$이다. 그런데 힙이 일직선으로 이어져 있으면 $O(N)$이 될 수도 있다. 왼쪽, 오른쪽에 고르게 추가해야 한다.

삭제

최댓값이 삭제됐으므로 새로운 최댓값을 구해야 한다. 비어버린 루트 자리를 임의의 리프 노드로 채워 보자. 예를 들어 위의 그림에서 7을 루트 노드에 놓을 수 있다.

임시 루트

그런데 7은 루트에 있으면 안 된다. 자신보다 큰 자식이 존재하기 때문이다. 따라서 자신보다 작은 자식이 있다면, 그 자식을 자신과 교환해야 한다. 이렇게 계속 교환하면서 모든 자식이 자신보다 작을 때까지 자신을 밑으로 내린다.

 

왼쪽 자식과 교환해도 되고, 오른쪽 자식과 교환해도 된다. 그건 구현하기 나름이다.

교환 완료

삭제 연산의 시간복잡도도 $O(\log N)$이다. 마찬가지로 힙의 원소가 한쪽으로 쏠려 있는 경우 $O(N)$까지 느려진다.

구현

주로 배열을 사용해 구현한다. $i$번 노드의 왼쪽 자식은 $2*i$번, 오른쪽 자식은 $2*i+1$번 노드로 표현하면 구현이 간단해지기 때문이다.

Priority Queue

먼저 넣은 값이 무조건 먼저 나오는 Queue와 다르게, 원소의 우선 순위를 비교하여 가장 먼저 와야 하는 값을 계산하는 자료구조이다. Heap과 매우 유사하며, 실제로도 Priority Queue는 거의 Heap을 통해 구현된다.

 

값을 계속 추가하면서 최댓값(또는 최솟값)을 찾아야 할 때 사용할 수 있다.

 

다익스트라 알고리즘에서 사용되며, 몇몇 알고리즘 문제를 풀 때 유용하게 써먹을 수 있다.