Sort

Sort 정렬 알고리즘을 정리해놓는 공간

선택정렬(Selection Sort)

선택정렬은 인덱스를 반복하면서 인덱스 이상의 값들 중 가장 작은 값을 찾아서 인덱스와 교환하는 방식으로 정렬하는 알고리즘이다.
선택정렬은 시간복잡도가 O(N^2)이다.

def selection_sort(arr) :
  for i in range(len(arr)) :
    min_index = i
    # 이 루프를 수행하고나면 min_index에서 가장 작은 값의 index가 저장된다. 
    for j in range(i+1, len(arr)) :
      if arr[min_index] > arr[j] :
        min_index = j
    arr[i], arr[min_index] = arr[min_index], arr[i]
  return arr

위상정렬(Topological Sort)

위상정렬은 유향 그래프의 꼭짓점들을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다.

위상 정렬은 순서가 정해져있는 작업을 차례대로 수행해야할 때 그 순서를 결정하기 위해서 사용한다.

위상정렬은 DAG(Directed Acyclic Graph)에만 적용이 가능하다.
- 방향이 존재하는데 싸이클(순회)가 존재하지 않는 그래프에만 적용가능
위상 정렬에서 시간 복잡도는 O(V+E)이다.
- V는 노드의 개수, E는 간선의 개수

구현

v, e = map(int, input().split())
# 모든 노드에 대한 집입차수를 0으로 초기화
indegree = [0] * (v + 1)
# 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트 초기화
graph = [[] for _ in range(v + 1)]
 
# 방향 그래프의 모든 간선 정보를 입력 받기
for _ in range(e) :
  a, b = map(int, input().split())
  graph[a].append(b) # A에서 B로 이동가능
  # 진입 차수를 1증가
  indegree[b] += 1
 
from collections import deque
def topology_sort() :
  result = []
  q = deque()
  # 처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
  for i in range(1, v+1) :
    if indegree[i] == 0 :
      q.append(i)
 
  while q :
    now = q.popleft()
    result.append(now)
    # 해당 원소와 연결된 노드들의 진입차수에서 1 빼기
    for i in graph[now] :
      indegree[i] -= 1
      # 새롭게 진입 차수가 0이 되는 노드를 큐에 삽입
      if indegree[i] == 0 :
        q.append(i)
        
  for i in result :
    print(i, end=' ')
 
topology_sort()

대표적인 문제

백준 1005번

https://rookedsysc.vercel.app/algorithm/baekjoon/python/1005 (opens in a new tab)

Reference

https://www.youtube.com/watch?v=qzfeVeajuyc (opens in a new tab)

MST 탐색