[Python 문법 공부] 05. 스택 & 큐 & 그래프

1. 스택

• LIFO (Last In First Out) 구조: 나중에 넣은 게 가장 먼저 나옴 (ex. 박스 쌓기)
• 기본 리스트에서 append()와 pop() 메서드를 이용하여 스택 자료구조 구현 가능
  • append() - 리스트의 가장 뒤쪽에 데이터 삽입
  • pop() - 리스트이 가장 뒤쪽에서 데이터를 꺼냄

stack = []

stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()

print(stack) # 최하단 원소부터 출력
print(stack[::-1]) # 최상단 원소부터 출력

# 실행결과:
# [5, 2, 3, 1]
# [1, 3, 2, 5]

2. 큐

• FIFO (First In First Out) 구조: 먼저 넣은 게 먼저 나옴 (ex. 줄 서기)
• collections 모듈에서 제공하는 deque 자료구조를 활용하여 큐 구현
  •  deque
    • 스택과 큐의 장점을 모두 채택
    • 데이터를 넣고 빼는 속도가 리스트에 비해 효율적
    • queue 라이브러리보다 더 간단
    • list() 메서드를 이용하여 deque 객체를 리스트 자료형으로 변경 가능
    • append() - 가장 뒤쪽에 데이터 삽입
    • popleft() - 가장 앞쪽에서 데이터를 꺼냄

from collections import deque

queue = deque()

queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()

print(queue)
queue.reverse()
print(queue)

# 실행결과
# deque([3, 7, 1, 4])
# deque([4, 1, 7, 3])

3. 그래프

• 이코테 p.134
• 노드 (node) = 정점 (vertex) 과 간선 (edge)로 구성
• 그래프 탐색: 하나의 노드를 시작으로 다수의 노드를 방문하는 것
• 두 노드는 인접하다: 두 노드가 간선으로 연결되어 있음
• 그래프 표현 방식 2가지

1. 인접 행렬 (Adjacency Matrix)

• 2차원 배열로 그래프의 연결 관계 표현
• 파이썬에서는 2차원 리스트로 구현
• 연결이 되어 있지 않은 노드끼리는 무한(INF)의 비용으로 작성 (ex. 999999999, 987654321)

INF = 987654321 # 무한의 비용 선언

# 2차원 리스트를 이용해 인접 행렬 표현
graph = [
  [0, 7, 5],
  [7, 0, INF],
  [5, INF, 0]
]

print(graph)

2. 인접 리스트 (Adjacency List)

• 리스트로 그래프의 연결 관계 표현
• 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장
• 원래 연결 리스트라는 자료구조를 이용하는데, 파이썬에서는 2차원 리스트를 이용하여 구현 가능

# 행(row)이 3개인 2차원 리스트로 인접 리스트 표현
graph = [[] for _ in range(3)]

# 노드 0에 연결된 노드 정보 저장
# (노드, 거리) 형태
graph[0].append((1, 7))
graph[0].append((2, 5))

# 노드 1에 연결된 노드 정보 저장
graph[1].append((0, 7))
graph[1].append((0, 5))

# 노드 2에 연결된 노드 정보 저장
graph[2].append((0, 5))

print(graph)

# 실행결과
# [[(1, 7), (2, 5)], [(0, 7), (0, 5)], [(0, 5)]]

인접 행렬 vs 인접 리스트

• 인접 행렬 방식은 모든 관계를 저장하므로 노드 개수가 많을 수록 메모리 낭비 심함
• 인접 리스트 방식은 연결된 정보만 저장하므로 메모리 효율적
• 인접 리스트 방식은 인접 행렬 방식에 비해 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느림
  • 연결된 데이터를 하나씩 확인해야 하므로.
• 특정한 노드와 연결된 모든 인접 노드를 순회해야 하는 경우, 인접 리스트 방식이 인접 행렬 방식보다 메모리 공간 낭비가 적음