컴퓨터공학과와 비슷한 과를 졸업해서 코딩을 많이 했었지만 막상 ‘이론’적인 내용에 대해서는 공부해본 적이 없었다. 따라서 좀 더 유연한 사고를 하기 위해 자료구조에 대해 공부하고 정리해보고자 한다. 물론 자료구조를 공부하는데 있어서 어떤 언어를 사용해도 무관하지만 가장 좋아하는 Python을 이용하고자 한다.

자료구조(Data Structure)

자료구조에 대한 설명을 할 때 가장 많이 사용되는 예시가 학교인 것 같다. 누구나 다 한 번은 ‘학교’라는 사회를 경험했기 때문인지 몰라도 이해하는데 가장 쉽고 빠르기 때문인 것 같다.

‘민수’라는 학생과 ‘영수’라는 학생만 있는 교실이 있다고 가정하자. 담임선생님 입장에서는 학생이 2명 뿐이니 관리하거나 통제하기 쉽다. 수학여행을 가더라도 각각의 이름만 불러도 쉽게 집합시킬 수 있다. 하지만 만약 30~40명 씩 있는 교실의 담임선생님은 수학여행을 가서 그들을 어떻게 통제할까? 각각의 이름을 불러 통제하기에는 시간과 에너지가 낭비 될 것이고, 이름도 잘 생각이 안 나서 결국에는 아모르파티가 될 가능성이 높다.

이 문제를 쉽게 해결하기 위해서는 그들을 모두 합쳐 하나의 공통체를 만들면 되는데, 바로 ‘반’이다. 1반, 2반, 개나리반, 쟁반 등등.

컴퓨터과학의 관점에서 보면 각각의 학생은 데이터가 될 것이고, 그들을 묶는 방법을 ‘자료구조’라고 한다. 즉, 대량의 데이터를 효율적으로 다루고 관리하기 위해 사용하는 구조(도구)이다. 더 정확하게는 데이터들의 모임이나 관계, 데이터에 적용할 수 있는 함수나 명령을 의미한다. 코드상에서 어떤 데이터 구조를 사용하느냐에 따라 알고리즘, 프로그램 등의 효율이 달라지기 때문에 적절한 자료구조의 이용이 매우 중요하다.

자료구조의 종류에는 배열(Array), 큐(Queue), 스택(Stack), 링크드 리스트(Linked List), 트리(Tree) 있고 이 밖에도 다양한 자료구조들이 있다. 차근차근 공부하면서 자료구조에 대해 마스터를 해 볼 생각이다.

배열(Array)

배열(Array)은 우리가 가장 흔히 접했던 자료구조 중 하나이다. 특히 python을 이용하는 사람이라면 첫 페이지부터 다루게 되는 자료구조이기도 하다. 배열이란 데이터를 나열하고, 각각의 데이터를 인덱스에 대응하도록 구성한 데이터 구조이다. Python에서는 리스트 타입이 배열 기능을 제공하고 있다. 물론 리스트에는 배열의 기능보다 더 많은 기능을 제공하고 있다.

배열이 필요한 이유는 비슷한 종류의 데이터를 효율적으로 관리할 수 있고 데이터를 순차적으로 저장할 수 있기 때문이다.

배열의 장점
- 각 데이터에 인덱스 번호가 있기 때문에 위치를 찾기 쉽다 -> 빠른 접근이 가능하다.
배열의 단점(Python에서는 느끼지 못한다……)
- 본래의 길이를 처음부터 정해줘야하는 불편함이 있다.
- 배열의 데이터 중 중간에 있는 데이터를 지우게 되면 빈 공간이 생긴다.
- 데이터를 추가할 때는 공간을 추가로 할당해줘야한다.

array_data1 = [1,2,3,4,5] # 1D 배열
array_data2 = [[1,2,3,4,5], [6,7,8,9,10]] # 2D 배열

큐(Queue)

큐(Queue)는 운영체제 또는 네트워크 기능에서 많이 사용되는 자료구조로 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있도록 하는 구조이다. 즉, 식당에서 줄을 서면 먼저 온 손님이 가장 먼저 먹는 원리와 같은 구조이다. 흔히 FIFO(First-In, First-Out) 또는 LILO(Last-In, Last-Out) 방식을 사용한다고 알려져있다.

큐(Queue)에서 주로 사용하는 용어가 있다.

Enqueue : 큐에서 데이터를 넣는 기능
Dequeue : 큐에서 데이터를 꺼내는 기능

Python으로 큐 다루기

import queue
queue_data = queue.Queue()

queue_data.put('justin') # Enqueue
queue_data.put('sakong') # Enqueue

print(queue_data.qsize()) # queue의 크기
print(queue_data.get()) # Dequeue

2
justin

print(queue_data.get()) # Dequeue

sakong

큐(Queue)는 주로 운영체제에서 멀티태스킹을 위한 프로세스 스켸줄링 방식을 구현하기 위해 많이 쓰인다.

Python으로 Enqueue, Dequeue 기능 구현(List 활용)

queue_list = list()

def Enqueue(data):

	queue_list.append(data)
    
def Dequeue():

	out = queue_list[0] # 데이터 추출
    del queue_list[0] # 추출한 데이터 삭제
    
    return out # 추출된 데이터 반환

for i in range(5):
	Enqueue(i)
    
print(len(queue_list)) # 5
print(Dequeue()) # 0