💬 구성요소

• 노드 Node (=정점 Vertex)
  e.g. 도시

• 간선 Edge
  e.g 도로

• 그래프를 탐색 : 하나의 노드를 시작으로 다수의 노드를 방문

• 두 노드는 인접(Adjacent) : 두 노드가 간선으로 연결되어있다.

💬 인접행렬 Adjacency Matrix

2차원 배열로 그래프의 연결 관계를 표현하는 방식

• 연결이 되어있지 않은 노드끼리는 무한 infinity 비용으로 작성

INF = 99999999 # 무한 비용 선언

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

💬 인접 리스트 Adjacency List

• 리스트로 그래프의 연결 관계를 표현하는 방식
• 연결리스트로 구현(파이썬은 기본 자료형이 append()와 메소드 제공)

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

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

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

🤔두 방식의 차이

• 메모리측면
  인접행렬 : 모든 관계 저장하므로 메모리 낭비
  인접리스트 : 연결된 관계만 저장하므로 메모리 효율적

• 속도
  인접행렬 : 빠름 (인덱스로 바로 접근)
  인접리스트 : 느림 (연결된 데이터 하나씩 확인)

💬 큐

• 놀이공원의 대기줄
• FIFO : 선입선출

💬 deque

• collection 모듈의 deque 라이브러리 사용
• 스택과 큐의 장점을 모두 채택
• 데이터 넣고 빼는 속도가 리스트에 비해 효율적
• queue 라이브러리보다 간단
• deque 객체를 리스트로 변경하려면 list()메서드 이용가능

💬 예제

• deque() : deque 생성
• append() : 삽입
• popleft() : 삭제

from collecction import deque

queue = deque()

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

print(queue) #먼저 들어온 순서대로 출력
# 결과 : deque([3, 1])

queue.reverse() # 역순으로 바꾸기
print(queue) #나중에 들어온 원소부터 출력
#결과 : deque([1, 3])

💬 스택

• FIFO : first in last out
• LIFO : last in first out

💬 기초 예제

• append() : 리스트의 가장 뒤쪽에 데이터 삽입
• pop() : 리스트의 가장 뒤쪽에서 데이터 꺼냄

stack = []

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

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