자료구조

데이터를 표현하고 관리하고 처리하기 위한 구조

스택 (Stack)

선입후출 First in Last Out 구조의 자료구조
가장 나중에 삽입된 데이터가 가장 먼저 pop 된다.

파이썬의 기본 list는 스택과 동일하게 동작한다.

stack = []
stack.append(1)
stack.append(2)
stack.append(3)
stack.pop()     # 3 삭제

print(stack)    # [1, 2]

큐 (Queue)

선입선출 First in First Out 구조의 자료구조
가장 먼저 삽입된 데이터가 가장 먼저 pop 된다.

파이썬 deque의 구조

from collections import deque  # 양방향 queue

queue = deque()
queue.append(1)
queue.append(2)
queue.append(3)
queue.append(4)

queue.popleft()                # 가장 왼쪽에 있는 데이터 (가장 먼저들어온 데이터) pop
# queue.pop() 가장 오른쪽 (늦게 들어온 데이터) pop == stack

print(queue)                   # deque([2, 3, 4])

그래프 (Graph)

정점(Node, Vertex)와 간선(Edge)로 이루어진 자료구조

그래프의 구조

간선으로 연결되어 있는 정점들을 인접 정점(adjacent vertex)라고 한다.

그래프의 구현

인접 행렬 (Adjacency Matrix)

# 인접 행렬(Adjacency Matrix) 방식 
# 연결 되어 있는 노드는 1, 연결 되어 있지 않은 노드는 무한으로 비용을 표시
# 간선마다 비용이 다르다면 1이 아니라 해당 간선의 비용으로 할당

INF = 9999999
graph =[
    [0, 1, 1, INF],
    [1, 0, 1, INF],
    [1, 1, 0, INF],
    [INF, INF, 1, 0]
]

인접 리스트 (Adjacency List)

# 인접 리스트(Adjacency List) 방식
# 각 노드마다 연결된 노드의 정보(노드, 비용)를 저장

graph = [[] for _ in range(4)]

graph[0].append((1, 1))           # 0번 노드와 1번 노드가 연결 되어 있고, 비용이 1 이다
graph[0].append((2, 1))

graph[1].append((0, 1))
graph[1].append((2, 1))

graph[2].append((0, 1))
graph[2].append((1, 1))
graph[2].append((3, 1))

graph[3].append((2, 1))

인접 행렬 VS 인접 리스트

인접 행렬은 노드들의 모든 관계를 저장하기 때문에, 노드 개수가 많을수록 메모리가 낭비될 수 있지만, 어떤 두 노드가 연결되어 있는지 정보를 얻기 쉽다.

graph[1][2] # 1, 2번 노드의 연결 상태 바로 확인

인접 리스트는 연결 되어 있는 정보만 저장하기 때문에 메모리 사용이 효율적 이지만, 노드의 연결정보를 파악하기 위해서 리스트의 요소를 하나씩 검사해야 하기 때문에 속도가 느리다.