[CS]자료구조

한상욱·2024년 9월 24일

CS&자격증후기&잡담

목록 보기

20/21

들어가며

알고리즘을 공부하다보면 자연스럽게 자료구조라는 개념을 접하게 됩니다. 오늘은 필수적인 자료구조들에 대해서 가볍게 알아보려 합니다.

자료구조

자료구조란?

자료구조는 컴퓨터가 효율적으로 데이터를 관리하기 위한 수단입니다. 컴퓨터의 프로세스는 이러한 자료구조를 이용한 연산을 통해 데이터를 처리하죠.

자료구조가 왜 필요할까?

처리하는 데이터의 크기가 커지면 커질수록 필요한 메모리가 증가하게 될 것입니다. 하지만, 컴퓨터가 갖고있는 메모리의 크기는 한정적이죠. 이러한 제한적인 메모리로 효율적인 처리를 위해서 우리는 자료구조를 이용합니다.

배열(Array)

배열은 가장 기본적인 자료구조입니다.

배열은 인덱스와 요소로 구성되어 있으며, 인덱스는 배열에서의 요소의 주소입니다. 그리고 요소는 해당 인덱스의 값이죠. 컴퓨터는 배열을 선언하면 프로세스 메모리 중 배열의 크기만큼 연속된 주소지의 메모리만큼 할당합니다.

다만, 배열은 프로세스 메모리에서 배열의 크기만큼 연속된 주소지의 메모리를 할당받습니다.

베열에서 원소를 추가 또는 삭제는 $O(n)$ 의 시간복잡도를 갖습니다. 따라서, 가장 간단하여 많이 사용하고 다른 자료구조의 하위 데이터 구조로도 사용되지만 데이터의 크기가 커질수록 비효율적인 자료구조입니다.

연결 리스트(Linked List)

연결 리스트는 배열과 다르게 인덱스가 아닌 참조방식으로 구현됩니다.

각 데이터는 노드(Node)에 저장되며, 각 노드는 다음 노드를 참조합니다. 그리고 연결 리스트의 head, tail은 각각 가장 첫 노드와 가장 마지막 노드를 참조합니다.

연결 리스트는 노드를 추가 또는 삭제는 $O(1)$ 의 시간복잡도를 갖습니다. 따라서 시간적인 측면에서 효율적입니다.

배열과 다르게 연속적이지 않은 메모리를 갖게 되어 데이터의 크기가 클수록 효율적으로 메모리를 이용하고 삽입 삭제가 간편하지만, 배열보다 더 큰 메모리를 차지하게 되고 탐색하는 경우 비효율적입니다.

스택(Stack)

스택은 한쪽방향에서 요소가 삽입,삭제되는 Last-In-First-Out(LIFO) 자료구조입니다.

가장 먼저 들어온 요소는 가장 하단에 배치되며, 이후에 순서대로 쌓여가는 구조입니다. 그리고 요소를 삭제하는 경우에는 가장 상단의 요소가 순서대로 삭제됩니다.

항상 한쪽에서 삽입과 삭제가 이루어지므로 삽입과 삭제는 $O(1)$ 의 시간복잡도를 갖게 됩니다.

스택은 동적인 메모리 크기를 가지며, 빠르게 동작할 수 있습니다. 다만, 한번에 하나씩 처리가 가능하고 가장 상단의 요소만 갖고올 수 있습니다.

큐(Queue)

큐는 데이터가 한쪽에서 삽입되면 다른 한쪽에서 삭제되는 자료구조입니다. 마치 터널과 같다고 할 수 있습니다.

스택과 다르게 First-In-First-Out(FIFO)의 특징을 갖고 있으며, 스택과 마찬가지로 동적인 메모리 크기와 삽입과 삭제는 $O(1)$ 의 시간복잡도를 갖습니다.

덱(deque)

덱은 큐에 살짝 더 확장된 버전이며, 양방향에서 모두 데이터의 삽입과 삭제가 가능한 자료구조입니다.

스택과 큐가 합쳐진 개념이기 때문에 덱으로 스택과 큐 모두 구현할 수 있습니다. 마찬가지로 원소의 삽입과 삭제는 $O(n)$ 의 시간복잡도를 갖습니다.

해시 테이블(Hash Table)

해시 테이블은 해시 값으로 변환한 인덱스를 key로 빠르게 데이터를 검색하기 위한 테이블 자료구조입니다.

테이블 내부에 버킷이라는 단위로 key, value를 저장하며 key를 더 작은 메모리를 차지할 수 있도록 hash값으로 변환하여 저장합니다. 여기서 key는 테이블에서 검색하기 위한 index이고, 값은 key, value의 쌍으로 이루어진 데이터입니다.

탐색, 삽입, 삭제 모두 $O(1)$ 의 시간복잡도를 갖습니다.

그래프(Graph)

그래프는 노드와 엣지로 이루어진 collection 데이터입니다. 이때, 방향이 있을수도 없을수도 있습니다.

위치 정보를 나타내거나 네트워크를 구성할 때 많이 사용하는 자료구조로 노드를 탐색하는데에는 $O(N+E)$ , 삽입에는 $O(1)$ , 노드 삭제는 $O(N+E)$ , 엣지 삭제는 $O(E)$ 의 시간복잡도를 갖습니다.

트리(Tree)

트리는 노드를 이용하여 계층적인 구조를 나타내는 자료구조입니다. 종류에 따라 다양한 트리가 존재합니다.

최상위 부모 노드는 ROOT라고 하며, 각 계층은 DEPTH로 나타냅니다. 같은 부모에서 같은 DEPTH인 노드들은 모두 SIBLING 관계를 갖고 있습니다. 만약 자식이 존재하지 않는 노드가 있다면 LEAF라고 합니다.

힙(heaq)

힙은 요소를 정렬하는 형식의 트리형 자료구조입니다. 정렬 방식에 따라서, 최소 힙 또는 최대 힙으로 표현할 수 있습니다.

힙은 루트 노드에서 삽입과 삭제가 이루어지며, 삽입 또는 삭제가 이루어지는 경우 노드간의 크기를 비교한 후 자리를 교체해가며 정렬된 구조를 유지합니다.

이러한 힙의 특성에 따라서 최소값 또는 최대값을 빠르게 찾아낼 수 있습니다. 힙은 우선순위 큐를 만들기 위해서 고안되었습니다.

우선순위 큐(Priority Queue)

우선순위 큐는 큐에 우선순위라는 개념이 도입된 자료구조입니다. 각 요소의 우선순위를 매겨서 우선순위가 더 높은 요소가 먼저 나갈 수 있도록 하는 자료구조입니다.

우선순위 큐는 배열 또는 연결리스트로도 구현이 가능합니다. 하지만, 데이터가 크면 클수록 시간복잡도가 점점 증가하기 때문에 힙을 이용합니다.

힙에서는 요소가 삭제되는 경우 내부의 요소들을 다시 최소 또는 최대힙의 구조를 맞추기 위해서 정렬합니다. 이러한 특성을 이용하여 우선순위 큐를 구현할 수 있습니다.

힙을 통해 구현된 우선순위 큐는 이진 트리의 특성에 의해서 삽입과 삭제에서 $O(\log_{2} {n})$ 의 시간복잡도를 갖습니다.