코딩 테스트를 앞둔 시점에서 전체적인 알고리즘을 작성해보면서 머릿속의 혼동되는 개념들을 정리해보고자 한다.
"그리디(탐욕법)"
개념
현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘으로
탐욕법이라고도 불린다. 다른 알고리즘에 비해서 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형이라는 특징이 있다.최소한의 아이디어를 떠올리 수 있는 능력을 요구한다.
접근 방법
- 해당 문제를 풀 수 있는 아이디어를 떠올린다.
- 해당 아이디어의
정당성을 검토해봐야 한다.
"구현"
개념
머릿속에 있는 알고리즘을 정확하고 빠르게 프로그램으로 작성해야 한다. 대체로 까다로운 조건이 추가되고, 내용이 길어서 이를 정확하게 구현하기 어려운
피지컬을 요구하는 문제들이 출제된다.
종류
- 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
- 시뮬레이션 : 문제에서 제시하는 알고리즘을 한 단계씩 차례대로 직접 수행
접근 방법
여러 문제들을 풀어보면서 느낀 것은 제한된 시간내에서 긴 지문을 읽고 정확하게 조건을 걸면서 풀어내는 것이 너무 어렵다고 생각이 들었다. 또한, 급하게 바로 시작하려다 보니 중간 중간 막혔을 때, 계속해서 코드가 수정되면서 더 시간이 지체되는 경우가 많았다. 따라서 다음과 같이 순서를 지켜서 풀이를 진행해보려고 한다.
- 문제를 처음부터 꼼꼼하고 빠르게 집중해서 읽어내기
- 주어진 예시를 확인하면서 코드 작성전에 공책에
구현방법과 순서대로 작성해보기
2-1. 이때, 어떠한자료구조로 어떻게 저장할 것인지를 결정해야 한다. - 생각해낸 방법대로
소스코드를 구현해보기
"DFS/BFS"
개념
그래프를 탐색하기 위한 대표적인 두 가지 알고리즘
사전 지식
탐색(Search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다.
자료구조(Data Structure)란 데이터를 표현하고 관리하고 처리하기 위한 구조를 의미한다. (push, pop)
스택(Stack)은 후입선출(Last In First Out)의 구조로 나중에 넣은 것이 먼저 나오는 방식이다.
큐(Queue)는 대기줄로 비유할 수 있는데 선입선출(First In First Out)의 구조이다.
재귀 함수(Recursive Function)란 자기 자신을 다시 호출하는 함수이다.
재귀 함수는 반드시 종료 조건을 명시해줘야 한다!
그래프 (Graph)
그래프란 노드(Node)와 간선(Edge)로 표현되며 그래프 탐색이란 하나의 노드
를 시작으로 다수의 노드를 방문하는 것을 말한다. 두 노드가 간선으로 연결되어 있다면, 두 노드는인접하다라고 표현한다.
- 인접 행렬 (Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현하는 방식
- 빠른 인덱스 접근이 가능하고 메모리가 불필요하게 낭비될 수 있음.
- 인접 리스트 (Adjacency List) : 리스트로 그래프의 연결 관계를 표현하는 방식
- 메모리 측면에서는 우수하지만, 리스트이기 때문에 순차적으로 접근해봐야 한다.
DFS (Depth-First-Search)
깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 스택을 이용하여 구현하기 때문에 재귀 함수를 이용할 수 있다. O(N)의 시간이 소요된다.
구현 방법
- 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
- 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
# DFS 메서드 정의
def dfs(graph, v, visited):
# 현재 노드를 방문 처리
visited[v] = True
print(v, end=' ')
# 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for x in graph[v]:
if not visited[x]:
dfs(graph, x, visited)
# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트) - 인접행렬 방식
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9
# 정의된 DFS 함수 호출
dfs(graph, 1, visited)BFS (Breadth-First-Search)
너비 우선 탐색이라는 의미로 가까운 노드부터 탐색하는 알고리즘이다. 선입선출 방식인 큐 자료구조를 이용하여 구현할 수 있다.DFS보다 조금 더 빠르게 동작한다.
구현 방법
- 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
- 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
- 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
from collections import deque
# BFS 메서드 정의
def bfs(graph, start, visited):
# 큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque([start])
# 현재 노드를 방문 처리
visited[start] = True
# 큐가 빌 때까지 반복
while queue:
# 큐에서 하나의 원소를 뽑아 출력
now = queue.popleft()
print(now, end=' ')
# 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
for x in graph[now]:
if not visited[x]:
queue.append(x)
visited[x] = True
# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트) - 인접행렬 방식
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9
# 정의된 BFS 함수 호출
bfs(graph, 1, visited)DFS vs BFS
둘다 연결된 정보를 가지고 탐색해야 하는 것은 동일하지만 상황에 따라서 어느 것을 써야 하는지 구분할 필요가 있다.
특정한 경로가 필요하다면 깊이 우선 탐색이 필요하다. (DFS)최단거리문제에서 모든 거리가 일정하다면 너비 우선 탐색을 이용하여 이전 공간보다 1을 더해주는 방식으로 최단 경로를 구해줄 수 있다. (BFS)
정렬
개념
연속된 데이터를 기준에 따라서 정렬하기 위한 알고리즘으로 상황에 맞게 적절한 알고리즘을 선택해
효율성을 높이는 것이 중요하다.
종류
- 선택 정렬
가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하는 알고리즘
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(len(array)):
min_index = i # 가장 작은 원소의 인덱스
for j in range(i + 1, len(array)):
if array[min_index] > array[j]:
min_index = j
array[i], array[min_index] = array[min_index], array[i] # 스와프
print(array)- 삽입 정렬
데이터를 하나씩 확인하면서, 각 데이터를 적절한 위치에 삽입하는 아이디어로,거의 정렬이 되어있을 때사용하면 효율적이다.
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(1, len(array)):
for j in range(i, 0, -1): # 인덱스 i부터 1까지 감소하며 반복하는 문법
if array[j] < array[j - 1]: # 한 칸씩 왼쪽으로 이동
array[j], array[j - 1] = array[j - 1], array[j]
else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
break
print(array)- 퀵 정렬
기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방식으로 동작하는 정렬 알고리즘
array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
def quick_sort(array):
# 리스트가 하나 이하의 원소만을 담고 있다면 종료
if len(array) <= 1:
return array
pivot = array[0] # 피벗은 첫 번째 원소
tail = array[1:] # 피벗을 제외한 리스트
left_side = [x for x in tail if x <= pivot] # 분할된 왼쪽 부분
right_side = [x for x in tail if x > pivot] # 분할된 오른쪽 부분
# 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬을 수행하고, 전체 리스트를 반환
return quick_sort(left_side) + [pivot] + quick_sort(right_side)
print(quick_sort(array))- 계수 정렬
데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때에 효율적으로 사용할 수 있는 알고리즘이다. 예를 들어, 성적데이터를 저장하고 정렬하는 경우에 사용할 수 있다.
# 모든 원소의 값이 0보다 크거나 같다고 가정
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
# 모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)
count = [0] * (max(array) + 1)
for i in range(len(array)):
count[array[i]] += 1 # 각 데이터에 해당하는 인덱스의 값 증가
for i in range(len(count)): # 리스트에 기록된 정렬 정보 확인
for j in range(count[i]):
print(i, end=' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력파이썬의 정렬 라이브러리
파이썬에서 제공하는 라이브러리인 sorted() 함수는 병합정렬 기반으로 만들어졌는데, 최악의 경우에도 O(NlogN)을 보장한다는 특징이 있다. 또는 리스트의 내장 함수인 .sort()를 사용하면 리스트 내부 원소가 즉시 정렬이 된다.
array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
array.sort()
print(array) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
array = [('바나나', 2), ('사과', 5), ('당근', 3)]
array.sort(key=lambda x: x[1])
print(array) # [('바나나', 2), ('당근', 3), ('사과', 5)]
array = [('바나나', 2), ('사과', 5), ('당근', 3)]
array.sort(key=lambda x: -x[1])
print(array) # [('사과', 5), ('당근', 3), ('바나나', 2)]
array = [('바나나', 2, 5), ('사과', 2, 4), ('당근', 3, 7)]
array.sort(key=lambda x: (x[1], x[2]))
print(array) # [('사과', 2, 4), ('바나나', 2, 5), ('당근', 3, 7)]
array = [('바나나', 2, 5), ('사과', 2, 4), ('당근', 3, 7)]
array.sort(key=lambda x: (x[1], -x[2]))
print(array) # [('바나나', 2, 5), ('사과', 2, 4), ('당근', 3, 7)]정리
삽입정렬은 전체적인 데이터가 거의 정렬이 되어 있을 때, 고려해보기
계수정렬은 제한된 데이터 범위를 가지는 정수 집합이고 중복되는 값이 여러개 등장할 때, 고려해보기
이외에 뚜렷한 데이터의 특징을 파악하지 못하겠다면 일반적으로퀵정렬을 사용하는 파이썬의 라이브러리를 사용하여 구현하기
이진 탐색
이진 탐색(binary search)은 범위를 반씩 좁혀가는 탐색으로 데이터가 정렬 되어 있어야만 사용할 수 있는 알고리즘이다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교하여 탐색하는 방식이다. O(logN)의 시간복잡도를 가진다.
# 이진 탐색 소스코드 구현(재귀 함수)
def binary_search(array, target, start, end):
if start > end:
return None
mid = (start + end) // 2
# 찾은 경우 중간점 인덱스 반환
if array[mid] == target:
return mid
# 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
elif array[mid] > target:
return binary_search(array, target, start, mid - 1)
# 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
else:
return binary_search(array, target, mid + 1, end)
# n(원소의 개수)과 target(찾고자 하는 문자열)을 입력받기
n, target = list(map(int, input().split()))
# 전체 원소 입력받기
array = list(map(int, input().split()))
# 이진 탐색 수행 결과 출력
result = binary_search(array, target, 0, n - 1)
if result == None:
print("원소가 존재하지 않습니다.")
else:
print(result + 1)# 이진 탐색 소스코드 구현(반복문)
def binary_search(array, target, start, end):
while start <= end:
mid = (start + end) // 2
# 찾은 경우 중간점 인덱스 반환
if array[mid] == target:
return mid
# 중간점의 값보다 찾고자 하는 값이 적은 경우 왼쪽 확인
elif array[mid] > target:
end = mid - 1
# 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
else:
start = mid + 1
return None
# n(원소의 개수)과 target(찾고자 하는 문자열)을 입력받기
n, target = list(map(int, input().split()))
# 전체 원소 입력받기
array = list(map(int, input().split()))
# 이진 탐색 수행 결과 출력
result = binary_search(array, target, 0, n - 1)
if result == None:
print("원소가 존재하지 않습니다.")
else:
print(result + 1)다이나믹 프로그래밍
한번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘으로
동적 계획법이라고도 표현하기도 한다. 메모리 공간을 약간 더 사용하여 중복되는 연산을 줄이는 방식이다.
피보나치 함수를 예로 들어서 이해해보자
# 피보나치 함수(Fibonacci Function)를 재귀 함수로 구현
def fibo(x):
if x == 1 or x == 2:
return 1
return fibo(x - 1) + fibo(x - 2)
print(fibo(4))위와 같이 함수를 작성하였을 때, n이 커질수록 수행 시간이 기하급수적으로 늘어나기 때문에 심각한 문제가 발생할 수 있다. 예를 들어 n이 30이면, 약 10억 가량의 연산을 수행해야 한다.
한번 구한 결과는 메모리에 저장해두고 호출하는 방식으로 해결해보자
접근 방법
- 큰 문제를 작은 문제로 나눌 수 있다.
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
탑다운(메모제이션) 방식
큰 문제를 해결하기 위해 작은 문제를 호출한다 (하향식)
# 한번 계산된 결과를 메모제이션(Memozation)하기 위한 리스트 초기화
d = [0] * 100
# 피보나치 함수(Fibonacci Function)를 재귀함수로 구현(탑다운 다이나믹 프로그래밍)
def fibo(x):
# 종료 조건(1 혹은 2일 때 1을 반환)
if x == 1 or x == 2:
return 1
# 이미 계산한 적 있는 문제라면 그대로 반환
if d[x] != 0:
return d[x]
# 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
d[x] = fibo(x - 1) + fibo(x - 2)
return d[x]
print(fibo(99))보텀업 방식
다이나믹 프로그래밍의 전형적인 형태인 보텀업 방식은 반복문을 이용하여 작은 문제부터 차근차근 답을 도출하는 방식이다. (상향식)
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100
# 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
d[1] = 1
d[2] = 1
n = 99
# 피보나치 함수(Fibonacci Function) 반복문으로 구현(보텀업 다이나믹 프로그래밍)
for i in range(3, n + 1):
d[i] = d[i - 1] + d[i - 2]
print(d[n])정리
특정한 문제에서 완전 탐색문제로 풀려고 했을 때, 시간이 매우 오래 걸린다면 다이나믹 프로그래밍을 적용할 수 있는지 확인해보고, 탑다운 보다는 보텀업 방식을 적용해보는 것이 좋다. 문제를 풀어보면서 느낀것은 우선 해당 정답이 단순히 그리디로 풀리는 것이 아닌
처음부터 계산이 필요한 문제가 있다면 n=1부터 올라가면서 답을 도출해내는 것을 시도해보자. 또한, 다이나믹 프로그래밍이라는 유형을 파악했을 때에는점화식을 도출해내기 위해서 고민을 해봐야 한다.
최단 경로
특정 지점까지 빠르게 도달하는 방법을 찾는 알고리즘으로 그리디 알고리즘과 다이나믹 프로그래밍 알고리즘이 그대로 적용된다. 그래프에서 노드와 간선이 있을 때, 최단 경로를 구하는 문제로 출제가 된다.
다익스트라 최단 경로 알고리즘
다익스트라(Dijkstra)알고리즘은 여러개의 노드가 있을 때, 특정한 노드에서
출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 이는 음의 간선이 없을 때 정상적으로 동작한다.
- 출발 노드를 설정한다.
- 최단 거리 테이블을 초기화한다.
- 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
- 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
- 위 과정에서 3,4번을 반복한다.
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정
# 노드의 개수, 간선의 개수를 입력받기
n, m = map(int, input().split())
# 시작 노드 번호를 입력받기
start = int(input())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
graph = [[] for i in range(n + 1)]
# 최단 거리를 테이블을 모두 무한으로 초기화
distance = [INF] * (n + 1)
# 모든 간선의 정보를 입력받기
for _ in range(m):
a, b, c = map(int, input().split())
# a번 노드에서 b번 노드로 가는 비용이 c라는 의미
graph[a].append((b, c))
def dijkstra(start):
q = []
# 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
heapq.heappush(q, (0, start))
distance[start] = 0
while q: # 큐가 비어있지 않다면
# 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
dist, now = heapq.heappop(q)
# 현재 노드가 이미 처리된 적이 있는 노드라면 무시
if distance[now] < dist:
continue
# 현재 노드와 연결된 다른 인접한 노드들을 확인
for i in graph[now]:
cost = dist + i[1]
# 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
if cost < distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(q, (cost, i[0]))
# 다익스트라 알고리즘을 수행
dijkstra(start)
# 모든 노드를 가기 위한 최단 거리를 출력
for i in range(1, n + 1):
# 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
if distance[i] == INF:
print("INFINITY")
# 도달할 수 있는 경우 거리를 출력
else:
print(distance[i])플로이드 워셜 알고리즘
플로이드 워셜(Floyd-Warshall)알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용할 수 있는 알고리즘이다. 각 노드를 반복하면서 해당 노드를 거쳐가는 경로가 더 짧은지 확인하는 방식으로 구현한다. 따라서 N개의 노드가 있을 때 O(N^3)의 시간복잡도를 가지게 된다.
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정
# 노드의 개수 및 간선의 개수를 입력받기
n = int(input())
m = int(input())
# 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화
graph = [[INF] * (n + 1) for _ in range(n + 1)]
# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for x in range(1, n + 1):
graph[x][x] = 0
# 각 간선에 대한 정보를 입력받아, 그 값으로 초기화
for _ in range(m):
# A에서 B로 가는 비용은 C라고 설정
a, b, c = map(int, input().split())
graph[a][b] = c
# 점화식에 따라 플로이드 워셜 알고리즘을 수행
for k in range(1, n + 1):
for a in range(1, n + 1):
for b in range(1, n + 1):
graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
# 수행된 결과를 출력
for a in range(1, n + 1):
for b in range(1, n + 1):
# 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
if graph[a][b] == INF:
print("INFINITY", end=" ")
# 도달할 수 있는 경우 거리를 출력
else:
print(graph[a][b], end=" ")
print()정리
한지점에서 여러지점에 대한 최단경로가 필요하다면
다익스트라알고리즘을 사용하고 여러지점에서 여러지점으로의 최단경로가 필요하다면플로이드워셜알고리즘을 사용하자. 다만,범위가 너무 크다면N^3인 플로이드워셜 알고리즘은 사용하지 못할 수도 있기 때문에 어떠한 알고리즘이 필요한지는데이터의 범위도 살펴보는 것이 좋다.
그래프 이론
코딩 테스트에서 자주 등장하는 기타 그래프 이론 공부하기
사전 개념
서로소 집합이란 공통 원소가 없는 두 집합을 의미한다.
서로소 집합 자료구조란 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조이다.
union, find 연산으로 구성이 된다.
# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
# 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
# 노드의 개수와 간선(union 연산)의 개수 입력받기
v, e = map(int, input().split())
parent = [0] * (v + 1) # 부모 테이블 초기화
# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v + 1):
parent[i] = i
# union 연산을 각각 수행
for i in range(e):
a, b = map(int, input().split())
union_parent(parent, a, b)
# 각 원소가 속한 집합 출력
print('각 원소가 속한 집합: ', end='')
for i in range(1, v + 1):
print(find_parent(parent, i), end=' ')
print()
# 부모 테이블 내용 출력
print('부모 테이블: ', end='')
for i in range(1, v + 1):
print(parent[i], end=' ')서로소 집합을 활용한 사이클 판별
서로소 집합은 무방향 그래프 내에서의
사이클을 판별할 때 사용할 수 있다. 방향 그래프에서의 사이클 여부는DFS를 이용하여 판별할 수 있다.
- 각 간선을 확인하며 두 노드의 루트 노드를 확인한다.
1-1. 루트 노드가 서로 다르다면 두 노드에 대하여 union 연산 수행
1-2. 루트 노드가 서로 같다면 사이클(cycle)이 발생한 것이다. - 그래프에 포함되어 있는 간선에 대하여 1번 과정을 반복하기
# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
# 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
# 노드의 개수와 간선(union 연산)의 개수 입력받기
v, e = map(int, input().split())
parent = [0] * (v + 1) # 부모 테이블 초기화
# 부모 테이블 상에서, 부모를 자기 자신으로 초기화
for i in range(1, v + 1):
parent[i] = i
cycle = False # 사이클 발생 여부
for i in range(e):
a, b = map(int, input().split())
# 사이클이 발생한 경우 종료
if find_parent(parent, a) == find_parent(parent, b):
cycle = True
break
# 사이클이 발생하지 않았다면 합집합(union) 수행
else:
union_parent(parent, a, b)
if cycle:
print("사이클이 발생했습니다.")
else:
print("사이클이 발생하지 않았습니다.")크루스칼 알고리즘
신장트리란 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다.
크루스칼(Kruskal)알고리즘이란 최소한의 비용으로 신장 트리를 찾을 수 있는 최소 신장 트리 알고리즘이다.
- 간선 데이터를
비용에 따라 오름차순으로 정렬한다. - 간선을 하나씩 확인하며 현재의 간선이
사이클이 발생시키는지 확인한다.
2-1. 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다.
2-2. 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않는다. - 모든 간선에 대하여 2번의 과정을 반복한다.
# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
# 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
# 노드의 개수와 간선(union 연산)의 개수 입력받기
v, e = map(int, input().split())
parent = [0] * (v + 1) # 부모 테이블 초기화
# 모든 간선을 담을 리스트와 최종 비용을 담을 변수
edges = []
result = 0
# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v + 1):
parent[i] = i
# 모든 간선에 대한 정보를 입력받기
for _ in range(e):
a, b, cost = map(int, input().split())
# 비용순으로 정렬하기 위해서 튜플의 첫 번째 원소를 비용으로 설정
edges.append((cost, a, b))
# 간선을 비용순으로 정렬
edges.sort()
# 간선을 하나씩 확인하며
for edge in edges:
cost, a, b = edge
# 사이클이 발생하지 않는 경우에만 집합에 포함
if find_parent(parent, a) != find_parent(parent, b):
union_parent(parent, a, b)
result += cost
print(result)위상 정렬
위상 정렬(Topology Sort)은 정렬 알고리즘의 일종으로 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다. 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것'으로 예시로 선수과목을 고려한 학습 순서 설정을 들 수 있다. 자료구조 -> 알고리즘 -> 코딩테스트 준비
진입차수(indegree)란 들어오는 간선의 개수를 의미한다.
- 진입차수가 0인 노드를 큐에 넣는다.
- 큐가 빌 때까지 다음의 과정을 반복한다.
2-1. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.
2-2. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.
만약, 모든 원소를 방문하기 전에 큐가 빈다면, 사이클이 발생한것이다.
from collections import deque
# 노드의 개수와 간선의 개수를 입력받기
v, e = map(int, input().split())
# 모든 노드에 대한 진입차수는 0으로 초기화
indegree = [0] * (v + 1)
# 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트(그래프) 초기화
graph = [[] for i in range(v + 1)]
# 방향 그래프의 모든 간선 정보를 입력받기
for _ in range(e):
a, b = map(int, input().split())
graph[a].append(b) # 정점 A에서 B로 이동 가능
# 진입차수를 1 증가
indegree[b] += 1
# 위상 정렬 함수
def topology_sort():
result = [] # 알고리즘 수행 결과를 담을 리스트
q = deque() # 큐 기능을 위한 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()