비선형 자료 구조

그래프 (Graph)

• 그래프는 무엇인가?

  • 정점(node)과 간선(edge)으로 이루어진 자료 구조

  • 노드를 정점 (Vertex)이라고도 함

  • 연결되어 있는 객체들을 표현 가능한 자료 구조 (객체를 정점 객체간의 관계를 간선으로 표현)

• 그래프는 어디에 쓰이는가?
  • 최단 경로 알고리즘(다익스트라, 플로이드 워셜)
  • BFS, DFS 알고리즘

• 파이썬에서 그래프를 쓰려면?

  • 인접 행렬을 사용한 표현

  # 노드 개수(n)와 간선 개수(m)
  n, m = map(int, input().split())
  
  # 인접 행렬
  graph = [[float('inf')]*(n+1) for _ in range(n+1)]
  
  # 자기 자신과의 거리는 0으로 초기화
  for i in range(n+1):
      graph[i][i] = 0
  
  # 간선 정보
  for _ in range(m):
      # start_node와 end_node를 잇는 간선에 대한 distance 
      # (간선의 distance는 없는 경우도 있음 ex: BFS, DFS)
      start_node, end_node, distance = map(int, input().split())
      graph[start_node][end_node] = distance
      
  '''
  예를 들면 아래와 같이 행렬의 형태로 만들어짐
  [
  	[0, 1, 3],
  	[1, 0, 4],
  	[3, inf, 0]
  ]
  '''

• 인접 리스트를 사용한 표현

  # 노드 개수(n)와 간선 개수(m)
  n, m = map(int, input().split())
  
  #노드 맵핑하기 위한 리스트
  graph = [[] for _ in range(n+1)]
  
  # 간선 정보
  for _ in range(m):
      # start_node와 end_node를 잇는 간선에 대한 distance 
      # (간선의 distance는 없는 경우도 있음 ex: BFS, DFS)
      start_node, end_node, distance = map(int, input().split())
      graph[start_node].append((end_node, distance))
      
  '''
  예를 들면 아래와 같이 리스트의 형태로 만들어짐
  [
  	[(1,1), (2,3)],
  	[(0,1), (2,4)],
  	[(0,3)]
  ]
  '''

트리 (Tree)

• 트리이란 무엇인가?
  • 그래프 구조의 일종
  • 그래프와는 다르게 부모 자식 계층으로 구성
    • 경로상 어떤 노드보다 위에 있으면 부모 노드, 아래에 있으면 자식 노드
  • 루트 노드, 내부 노드, 리프 노드로 구성
    • 루트 노드 : 가장 위에 있는 노드, 보통 탐색의 시작점
    • 내부 노드 : 루트 노드와 리프 노드 사이에 있는 노드
    • 리프 노드 : 자식 노드가 없는 노드
  • 간선 수 = 노드 수 - 1 이라는 특징이 있음
  • 임의의 두 노드 사이의 경로는 유일무이하게 존재
    • 트리 내의 두 노드의 경로는 반드시 있음
    • 트리 내 사이클 구조는 없음

#	그래프	트리
방향성	방향 또는 무방향 그래프	방향 그래프
순환성	순환 및 비순환	비순환
루트 노드 존재 여부	없음	있음
노드간 관계성	부모 자식 관계 없음	부모 자식 계층 관계
모델의 종류	네트워크 모델	계층 모델

• 트리은 어디에 쓰이는가?
  • BFS, DFS
  • 힙 구현

• 파이썬에서 트리을 쓰려면?
  • 그래프와 동일

힙 (Heap)

• 힙이란 무엇인가?
  • 트리 구조에 기반한 자료 구조
  • 우선 순위 큐를 구현하기 위한 자료 구조
  • 최대힙과 최소힙이 있음
    • 최대힙 : 부모 노드가 자식 노드보다 크며, 루트 노드가 트리 내에서 가장 큰 값을 가짐
    • 최소힙 : 부모 노드가 자식 노드보다 작으며, 루트 노드가 트리 내에서 가장 작은 값을 가짐

• 힙은 어디에 쓰이는가?
  • 최단 거리 알고리즘
  • 우선 순위를 고려한 데이터 정렬

• 파이썬에서 힙을 쓰려면?

# 힙 모듈
# 기본값으로 최소힙으로 되어있음
# 최대힙으로 사용하기 위해서는 데이터에 -1를 곱해서 삽입하면 됨
import heapq

# 힙으로 사용할 리스트 초기화
heap = []

# 힙에 데이터 삽입
heapq.heappush(heap, data)

# 힙에서 가장 작은 데이터 추출
heapq.heappop(heap)

# 새로운 데이터 삽입하고 힙에서 가장 작은 데이터를 추출 
heapq.heappushpop(heap, data)
# 가장 작은 데이터를 추출하고 새로운 데이터 삽입
heapq.heapreplace(heap, data)

# 기존의 리스트를 힙 구조로 변환
x = [1,5,3,4,2,6]
heapq.heapify(x)

우선 순위 큐 (Priority Queue)

• 우선 순위 큐란 무엇인가?
  • 삽입된 순서에 상관없이 우선 순위가 높은 데이터가 추출 되는 자료 구조
• 우선 순위 큐은 어디에 쓰이는가?
  • 힙을 이용하여 구현되었기 때문에 힙을 사용하는 곳에 사용 가능
  • 최단 거리 알고리즘
  • 우선 순위를 고려한 데이터 정렬

• 파이썬에서 우선 순위 큐을 쓰려면?
  • PriorityQueue 혹은 heapq를 사용할 수 있음
  • 속도는 heapq가 더 빠름

# PriorityQueue 모듈
from queue import PriorityQueue

# 우선 순위 큐 정의
que = PriorityQueue()
que = PriorityQueue(maxsize = n)  # 최대 크기를 지정 가능

# 데이터 삽입
que.put(data) # 최소힙과 같은 구조
que.put((2, "apple")) # (우선순위, 데이터) 형태로 삽입 가능

# 데이터 추출
que.get()

# 큐 사이즈 반환
que.qsize()

# 큐가 비어있는지 확인하는 함수
que.empty() # 비어있으면 True, 데이터가 있으면 False