[Data Structure] Array, LinkedList / Stack, Queue, Priority Queue(우선순위 큐) / Heap(힙), heapq 모듈

1. Array와 LinkedList에 대해 설명하세요

배열 (Array)

: 배열은 동일한 타입의 요소들을 연속적인 메모리 공간에 저장하는 자료구조입니다. 배열은 고정된 크기를 가지며, 배열의 각 요소는 인덱스를 통해 직접 접근할 수 있습니다. 이러한 특성 때문에 배열에서의 요소 접근(검색)은 매우 빠르게 이루어져 O(1)의 시간복잡도를 가집니다. 그러나 배열은 크기가 고정되어 있어, 배열의 크기를 변경하려면 전체 배열을 새로운 크기의 배열로 복사하는 과정이 필요하며, 이는 비용이 많이 드는 작업입니다. 또한, 배열의 중간에 요소를 삽입하거나 삭제하는 경우, 해당 요소 이후의 모든 요소들을 이동시켜야 하므로 비효율적입니다.

연결 리스트 (Linked List)

: 연결 리스트는 요소들이 메모리상에서 연속적으로 위치하지 않고, 각 요소가 다음 요소의 주소를 가리키는 포인터를 통해 서로 연결되어 있는 자료구조입니다. 연결 리스트는 동적 크기를 가지며, 필요에 따라 요소를 추가하거나 삭제할 수 있습니다. 연결 리스트에서 요소를 삽입하거나 삭제하는 작업은 O(1) 시간에 가능하지만, 특정 요소에 접근(검색)하는데는 처음부터 해당 요소까지 순차적으로 탐색해야 하므로 O(n)의 시간복잡도를 가집니다. 연결 리스트는 단일 연결 리스트(Singly Linked List), 이중 연결 리스트(Double Linked List), 원형 연결 리스트(Circular Linked List) 등 다양한 변형이 있습니다.

 

1-1. Array와 LinkedList의 차이점에 대해 설명하세요.

메모리 할당

• 배열: 고정된 크기의 연속적인 메모리를 할당받는다.
• 연결 리스트: 요소가 추가될 때마다 개별적으로 메모리를 할당받는다.

접근 시간

• 배열: 인덱스를 통한 직접 접근이 가능하여 접근 시간이 O(1)이다.
• 연결 리스트: 순차 접근이 필요하여 O(n)이다.

크기 변경

• 배열: 크기가 고정되어 있어 변경이 어렵다.
• 연결 리스트: 동적으로 크기가 변할 수 있다.

삽입/삭제 연산

• 배열: 중간에 요소를 삽입하거나 삭제하는 경우 비효율적이다.
• 연결 리스트: 요소를 삽입하거나 삭제하는 경우 해당 노드의 포인터만 조정하면 되므로 효율적이다.

 

 

2. Stack과 Queue에 대해 설명하세요.

스택이란 데이터를 임시 저장할 때 사용하는 자료구조로, 데이터의 입력과 출력 순서는 후입선출(LIFO) 방식입니다. 스택에서 데이터를 넣는 작업을 Push라고 하고 데이터를 꺼내는 작업을 Pop이라고 합니다. 파이썬에서는 collections.dequeue 모듈을 사용하여 스택을 간단하게 구현할 수 있습니다. 이는 맨 앞과 맨 끝 양쪽에서 원소를 추가, 삭제할 수 있습니다. 덱(dequeue)에서는 pop() 함수를 사용하면 dequeue의 맨 끝(오른쪽)에 있는 원소 한 개를 삭제하고 원소를 반환합니다. popleft() 함수르르 사용하면 dequeue의 맨 앞(왼쪽)에 있는 원소를 한개 삭제하고 원소를 반환합니다.

큐는 스택과 같이 데이터를 임시 저장하는 자료구조입니다. 큐는 스택과 달리 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO) 방식입니다. 큐에 데이터를 추가하는 작업을 enqueue, 데이터를 꺼내는 작업을 dequeue라고 합니다.

 

2-1. Priority Queue(우선순위 큐)에 대해 설명하세요.

우선순위큐는 인큐할때는 데이터에 우선순위를 부여하여 추가하고, 디큐할때 우선순위가 가장 높은 데이터를 꺼내는 방식입니다. 파이썬에서 우선순위를 부여하는 큐는 heapq모듈에서 제공합니다.

 

2-2. Heap 자료구조의 특징과 heapq 모듈에 대해 설명하세요.

힙은 완전 이진트리로 구성된 자료구조입니다. 이는 우선순위 큐를 위해 만들어진 자료구조이며 구현할 때 삽입/삭제 모두 O(log N)의 시간 복잡도를 가집니다. 최소 힙은 부모 노드의 값이 자식 노드의 값보다 항상 작은 힙이며 최대 힙은 부모 노드의 값이 자식 노드의 값보다 항상 큰 힙입니다.

heapq.heappush(heap, item)

: 힙 불변성을 유지하면서, item 값을 heap으로 푸쉬합니다.

heapq.heappop(heap)

: 힙 불변성을 유지하면서, heap에서 가장 작은 요소를 팝하고 반환합니다. 이때 힙이 비어 있으면, IndexError가 발생합니다.

heapq.heapify(x)

: 리스트 x를 힙으로 변환합니다.

 

 

 

참고

Do it! 자료구조와 함께 배우는 알고리즘 입문

https://www.jongung.com/290