[그리디]
매 순간마다 최적의 선택을 함. 현재의 선택이 나중에 미칠 영향을 고려하지 않는다
그리디 알고리즘 유형의 문제는 문제를 풀기위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다
대부분의 그리디 알고리즘의 문제는 최소한의 아이디어를 떠올리고 그것이 정당한지 검토할 수 있어야한다
[구현]
머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정
풀이를 떠올리는 것은 어렵지 않지만 소스코드로 옮기기 어려운 문제
*완전탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
*시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 유형
[DFS/BFS]
코딩 테스트에서 매우 자주 등장하는 유형이므로 반드시 숙지해야 함
*탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
*자료구조 : 데이터를 표현하고 관리하고 처리하기 위한 구조
스택은 후입선출, 큐는 선입선출 구조이다
재귀 함수(Recursive Funciton)는 DFS에 자주 사용된다
활용 : 최대공약수 계산(유클리드 호제법)
def gcd(a, b):
if a % b == 0:
return b
else:
return gcd(b, a % b)유클리드 호제법을 재귀함수로 구현
두 자연수 A, B에 대하여 (A > B) A를 B로 나눈 나머지를 R이라고 했을 때, A와 B의 최대공약수는 B와 R의 최대공약수와 같다
재귀 함수 <-> 반복문 간에 서로 동일한 기능을 구현할 수 있지만 상황에 따라 유불리가 서로 존재하기 때문에 잘 선택해야 한다
DFS (깊이 우선 탐색)
보통 스택으로 구현한다. 재귀함수로도 구현 가능
def dfs(graph, v, visited):
# 현재 노드를 방문 처리
visited[v] = True
print(v, end=' ')
# 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for i in graph[v]:
if not visited[i]:
dfs(graph, i, 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(graph, 1, visited)
BFS (너비 우선 탐색)
보통 큐로 구현한다.
간선의 거리가 모두 같을때 최단거리를 찾을 때 사용할 수 있다
from collections import deque
def bfs(graph, start, visited):
# 큐 구현을 위해 deque 라이브러리 사용
queue = deque([start])
# 현재 노드를 방문 처리
visited[start] = True
# 큐가 빌 때까지 반복
while queue:
v = queue.popleft()
print(v, end=' ')
# 아직 방문하지 않은 인접한 원소들을 큐에 삽입
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i] = 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(graph, 1, visited)
DFS/BFS 구현시 첫 인덱스를 사용하지 않고 다음 인덱스부터 사용한다면 노드의 인덱스가 배열의 인덱스에 그대로 대응되기 때문에 첫 인덱스는 구현의 편의성을 위해 비워놓고 사용하는 편이다
[정렬]
데이터를 특정한 기준에 따라서 순서대로 나열하는 것
*선택정렬 : 처리되지 않은 데이터 중, 가장 작은 숫자를 선택해 맨 앞의 데이터와 바꾸는것을 반복. O(N²)
*삽입정렬 : 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입. 데이터가 거의 정렬되어 있는 상태라면 매우 빠름. O(N²)이지만 모두 정렬이 되어있는 최선의 경우에는 O(N)
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(1, len(array)):
# i부터 1까지 1씩 감소하며 반복함
for j in range(i, 0, -1):
# 왼쪽의 값보다 작으면
if array[j] < array[j-1]:
# 서로 값을 교환한다
array[j], array[j-1] = array[j-1], array[j]
# 현재 값보다 더 작은게 없다면 루프 종료
else:
break
print(array)*퀵 정렬 : 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법. 평균적으로 O(NlogN)이지만 최악의 경우에는 O(N²). 삽입정렬과 다르게 이미 정렬된 데이터에 대해서 최악의 시간 복잡도를 가진다
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
def quick_sort(array, start, end):
# 시작 인덱스가 끝 인덱스보다 크거나 같으면 즉시 종료
if start >= end:
return
pivot = start
left = start+1
right = end
# 좌측 인덱스가 우측 인덱스보다 작을 때
while(left <= right):
# pivot보다 크거나 같은 값을 찾을 때까지 우측으로 한칸씩 이동
while(left <= end and array[left] <= array[pivot]):
left += 1
# pivot보다 작거나 같은 값을 찾을 때까지 좌측으로 한칸씩 이동
while(right > start and array[right] >= array[pivot]):
right -= 1
# 인덱스가 서로 교차하면 피벗과 right를 바꿔준다
if(left > right):
array[right], array[pivot] = array[pivot], array[right]
# 그렇지 않다면 left와 right를 바꿔준다
else:
array[left], array[right] = array[right], array[left]
# 가장 좌측부터 새로운 기준 값 직전까지의 범위로 설정
quick_sort(array, start, right-1)
# 새로운 기준 값 직후부터 가장 우측까지의 범위로 설정
quick_sort(array, right+1, end)
quick_sort(array, 0, len(array)-1)
print(array)분할-정복의 대표적인 알고리즘.
병합 정렬과 더불어 대부분의 프로그래밍 언어들의 정렬 라이브러리의 근간이 되는 알고리즘.
array = [7, 5, 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))파이썬의 장점을 활용해 코드 간결화가 가능하다. 리스트 슬라이싱과 리스트 컴프리헨션 사용
단, 좌우로 분할시키는 과정에서 시간적 손해가 조금 더 있다
*계수정렬 : 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능. 특정조건을 만족할 때만 사용할 수 있지만 매우 빠르게 동작함
데이터의 값과 동일한 인덱스의 값을 1씩 증가시킴. O(N+K)
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8, 0, 5, 2]
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=' ')
데이터가 0과 999,999 단 2개만 존재하는 경우 메모리를 너무 크게 잡아먹는 비효율성이 발생할 수 있다
동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적으로 사용할 수 있다
코딩 테스트에서 정렬 알고리즘이 사용되는 경우를 일반적으로 3가지 문제 유형으로 나타낼 수 있다.
1. 정렬 라이브러리로 풀 수 있는 문제 : 라이브러리 사용법 숙지만 하고 있으면 어렵지 않음
2. 정렬 알고리즘의 원리에 대해서 물어보는 문제 : 각 정렬의 원리를 알고 있어야 문제를 풀 수 있음
3. 더 빠른 정렬이 필요한 문제 : 계수 정렬 등의 다른 알고리즘을 이용하거나 문제에서 기존에 알려진 알고리즘의 구조적인 개선을 거쳐야 문제를 풀 수 있음
[이진 탐색]
*순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법
*이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법. 탐색 범위를 절반씩 줄여가기 때문에 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 = 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 = 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)
추가로 bisect_left, bisect_right라는 라이브러리 함수도 기본 제공된다. c++의 lower_bound, upper_bound와 동일함
값이 특정 범위에 속하는 데이터의 개수를 구하거나 같은 숫자가 몇개가 있는지 구할때 사용할 수 있다
코딩 테스트에서의 이진 탐색은 단골로 나오는 문제이므로 반드시 숙지해 두어야 한다.
문제를 풀때 큰 탐색범위를 본다면 가장 먼저 이진 탐색을 떠올려야 한다.
이진 탐색 트리
다음과 같은 특징을 지닌다
- 부모 노드보다 왼쪽 자식 노드가 작다
- 부모 노드보다 오른쪽 자식 노드가 크다
왼쪽 자식 노드 > 부모 노드 > 오른쪽 자식 노드 가 항상 성립해야 한다
파라메트릭 서치
최적화 문제를 결정 문제(예/아니오)로 바꾸어 해결하는 기법
재귀적으로 구현하는 것보다 반복문으로 구현하는게 더 좋을수 있다
개념적으로는 이진 탐색이지만 문제에 따라 데이터의 정렬 여부는 무관할 수 있다
[다이나믹 프로그래밍] (=동적 계획법)
메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법
이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 함
Top-down과 Bottom-up 방식으로 구현함
핵심은 중복되는 연산을 줄이자는것
동적 계획법은 다음 조건을 만족할 때 사용할 수 있다
- 큰 문제를 작은 문제로 나눌 수 있다. (최적 부분 구조)
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. (중복되는 부분 문제)
동적 계획법으로 해결할 수 있는 대표적인 예로 피보나치 수열이 있다
# 한 번 계산된 결과를 메모이제이션 하기 위한 리스트 초기화
d = [0] * 100
# 피보나치 함수를 재귀함수로 구현(Top-down)
def fibo(x):
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))큰 문제를 해결하기 위해 작은 문제를 호출하기 때문에 재귀는 Top-down 방식이다
한번 계산된 결과를 저장하는것을 메모이제이션(캐싱) 이라고 한다
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100
d[1] = 1
d[2] = 1
n = 99
# 피보나치 함수를 반복문으로 구현(Bottom-up)
for i in range(3, n+1):
d[i] = d[i - 1] + d[i - 2]
print(d[n])반대로 작은 문제를 모아 큰 문제를 해결하기 때문에 반복문은 Bottom-up 방식이다
Top-down 방식과 다르게 앞서 계산된 결과를 저장하기 위한 리스트를 DP 테이블 이라고 부른다
동적 계획법과 분할-정복은 모두 최적 부분 구조를 가질 때 사용할 수 있지만 분할-정복은 중복 부분의 문제가 반복적으로 계산되지 않는다
동적 계획법 문제에 접근하는 방법
그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토 후 풀이 방법이 떠오르지 않으면 동적 계획법을 고려해야 한다.
우선 재귀 함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤에 Bottom-up 방식에서도 그대로 사용될 수 있으면 코드를 개선하는 방법을 사용할 수 있다.
일반적인 코딩 테스트 수준에서는 기본 유형의 다이나믹 프로그래밍 문제가 출제되는 경우가 많음.
[최단 경로]
다익스트라, 플로이드 워셜 알고리즘이 코딩 테스트에서 가장 많이 등장하는 유형.
*다익스트라 최단 경로 알고리즘
음의 간선이 없을 때 정상적으로 동작한다. 실제로 GPS 소프트웨어의 기본 알고리즘으로 채택되기도 한다.
최단거리 테이블을 사용하며 현재 노드까지의 최단거리를 계속 갱신한다.
매 상황에서 방문하지 않은 가장 비용이 적은 노드를 선택해가기 때문에 그리디 알고리즘으로 볼 수 있다.
구현이 쉽지만 느리고, 구현이 까다롭지만 빠른 2가지의 구현 방법이 있다.
간단한 다익스트라 알고리즘
최초 각 노드에 대한 최단 거리를 담는 1차원 리스트를 선언한다.
이후, 단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 매 단계마다 1차원 리스트의 모든 원소를 순차 탐색한다.
한 번 처리된 노드의 최단 거리는 고정되어 더이상 바뀌지 않는다.
총 O(V)번에 걸쳐서 최단 거리가 가장 짧은 노드를 매번 선형 탐색해야 하고, 현재 노드와 연결된 노드를 매번 일일이 확인하기 때문에 O(V²)의 시간 복잡도를 가진다. (V는 노드의 개수)
전체 노드의 개수가 5천개 이하라면 이런 방법으로도 가능하겠지만 1만개가 넘어가는 문제라면 해결하기 어렵다
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)]
# 방문한 적이 있는지 체크하는 목적의 리스트를 만들기
visited = [False] * (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 get_smallest_node():
min_value = INF
index = 0 # 가장 최단 거리가 짧은 노드(인덱스)
for i in range(1, n + 1):
if distance[i] < min_value and not visited[i]:
min_value = distance[i]
index = i
return index
def dijkstra(start):
# 시작 노드에 대해서 초기화
distance[start] = 0
visited[start] = True
for j in graph[start]:
distance[j[0]] = j[1]
#시작 노드를 제외한 전체 n - 1개의 노드에 대해 반복
for i in range(n - 1):
# 현재 최단 거리가 가장 짧은 노드를 꺼내서, 방문 처리
now = get_smallest_node()
visited[now] = True
# 현재 노드와 연결된 다른 노드들 확인
for j in graph[now]:
cost = distance[now] + j[1]
# 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
if cost < distance[j[0]]:
distance[j[0]] = cost
dijkstra(start)
for i in range(1, n + 1):
# 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
if distance[i] == INF:
print("INFINITY")
# 도달할 수 있는 경우 거리를 출력
else:
print(distance[i])
개선된 다익스트라 알고리즘
O(ElogV)를 보장한다. (E는 간선의 개수, V는 노드의 개수)
힙 자료구조를 사용한다.
파이썬은 PriorityQueue와 heapq 둘다 우선순위 큐를 지원하지만 보통 heapq가 더 빠르게 동작한다.
최소 힙은 원소를 꺼내면 가장 값이 작은 원소가 추출되는 특징이 있어서 우선순위 큐와 다익스트라 알고리즘의 기반이 된다.
최단 거리 테이블은 그대로 사용하고 우선순위 큐가 추가 사용된다.
우선순위 큐를 적용한 개선된 다익스트라 알고리즘의 작동 과정
1. 시작점을 설정하여 시작점->시작점 (거리 0) 의 노드를 최단 거리 테이블 갱신과 갱신된 데이터를 우선순위 큐에 (거리, 노드 번호)의 튜플로 넣어준다.
2. 우선순위 큐에서 노드를 꺼내면 현재 노드에서 거리가 가장 짧은 노드가 나오게 된다.
3. 해당 노드와 연결된 간선의 길이를 최단 거리 테이블과 비교하여 더 짧은 경우만 갱신시키고 갱신된 값만 튜플로 생성하여 우선순위 큐에 넣어준 뒤 해당 노드의 처리를 끝낸다.
4. 2-3을 우선순위 큐가 빌때까지 반복한다.
O(ElogV)의 시간 복잡도를 가진다.
우선순위 큐를 필요로 하는 다른 문제 유형과도 흡사하다는 특징이 있다.
최소 신장 트리 문제를 풀 때에도 사용되는 Prim 알고리즘의 구현이 다익스트라 알고리즘의 구현과 흡사하다.
그렇기에 다익스트라 알고리즘을 바르게 이해할 필요가 있다.
직관적으로 전체 과정은 E(개의 원소를 우선순위 큐에 넣었다가 모두 빼내는 연산과 매우 유사하다
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])
간단한 다익스트라 알고리즘과 다르게 최단 거리가 가장 짧은 노드를 선택하는 과정이 우선순위 큐를 이용하는 것으로 대체된다. 또한 최단 거리 테이블과 현재 꺼낸 노드의 거리를 비교하는것 자체가 일종의 방문처리이기 때문에 별도의 방문처리를 하지 않아도 된다.
플로이드-워셜 알고리즘
모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산.
즉, 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용할 수 있다.
다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 모든 노드를 기준으로 알고리즘을 수행하지만, 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않음.
다익스트라 알고리즘이 그리디 유형에 속했다면 플로이드-워셜 알고리즘은 DP 유형에 속한다.
최단 거리 테이블이 1차원이 아닌 2차원이다.
a에서 b로 가는 최단 거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧은지 검사하는 점화식
시간 복잡도는 노드의 개수 N만큼 최단 거리 테이블을 갱신해야 하기 때문에 O(N×N²) = O(N³)이다.
구현 난이도는 매우 간단하지만 N의 크기가 조금만 늘어나도 사용하기 어렵다.
그래프와 최단 거리 테이블을 따로 관리하지 않고 최초 실행시 그래프의 데이터를 받을 때, 최단 거리 테이블에 그래프의 데이터를 그대로 담아서 처리한다.
INF = int(1e9)
# 노드의 개수 및 간선의 개수를 입력받기
n = int(input())
m = int(input())
# 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화
graph = [[INF] * (n + 1) for _ in range(n + 1)]
# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for a in range(1, n + 1):
for b in range(1, n + 1):
if a == b:
graph[a][b] = 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()
[그래프 이론]
*서로소 집합 : 공통 원소가 없는 두 집합
{1, 2} {3, 4} 는 서로소 관계이지만 {1, 2} {2, 3} 은 2가 공통적으로 포함되어 있기 때문에 서로소 관계가 아니다.
*서로소 집합 자료구조 : 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조
union(합집합), find(탐색) 2개의 연산으로 조작할 수 있다.
노드가 어떤 부모를 가지고 있는지의 정보를 담는 부모 테이블을 사용한다.
부모의 정보만 담고있기 때문에 루트를 확인할때는 재귀적으로 거슬러 올라가야 한다.
# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
# 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
if parent[x] != x:
return find_parent(parent, parent[x])
return 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=' ')
기본적인 서로소 집합 알고리즘. 최악의 경우 find 함수는 O(V)로 작동하기때문에 효율적이지 못하다.
하지만 경로 압축이라는 아주 간단한 과정으로 최적화를 할 수 있다.
# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
# 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
union 함수들의 처리 완료후 부모 테이블은 위와 동일하게 나오지만, 이후 find 함수를 한번 호출하면 부모 테이블의 각 노드들의 부모는 루트 노드로 갱신된다.
서로소 집합 알고리즘의 시간 복잡도는 대략적으로 O(V+MlogV)이다.
노드의 개수가 1000개이고 union과 find연산이 총 100만번 수행된다면 대략 1000만번 가량의 연산이 수행된다.
시간 복잡도를 줄일 수 있는 방법은 여러가지가 더 있지만 코딩 테스트 수준에서는 경로 압축만 적용해도 충분하다.
*서로소 집합을 활용한 사이클 판별 : 무방향 그래프 내에서의 사이클을 판별할 때 사용할 수 있다.
방향 그래프에서의 사이클 여부는 DFS를 이용해야 한다.
1. 각 간선을 확인하며 두 노드의 루트 노드를 확인한다
- 루트 노드가 서로 다르다면 두 노드에 대하여 union 연산을 수행한다.
- 루트 노드가 서로 같다면 사이클이 발생한 것이다.
2. 그래프에 포함되어 있는 모든 간선에 대하여 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
else:
union_parent(parent, a, b)
if cycle:
print("사이클이 발생했습니다.")
else:
print("사이클이 발생하지 않았습니다.")
*신장 트리 : 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프.
그래프 알고리즘 문제로 자주 출제되는 유형이다.
최소 신장 트리
최소 신장 트리에 포함된 간선의 개수는 (전체 노드의 개수-1) 이다. 기본적으로 트리가 가지는 특징이다.
크루스칼 알고리즘
대표적인 최소 신장 트리 알고리즘이다. 그리디 알고리즘으로 분류된다.
1. 간선 데이터를 비용에 따라 오름차순으로 정렬한다.
2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다.
- 사이클이 발생하지 않는 경우, 최소 신장 트리에 포함시킨다.
- 사이클이 발생하는 경우, 최소 신장 트리에 포함시키지 않는다.
3. 모든 간선에 대해 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)
간선의 개수가 E개일 때, O(ElogE)의 시간 복잡도를 가진다. (표준 정렬 라이브러리 기준)
*위상 정렬 : 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것
큐 또는 스택으로 구현할 수 있다.
1. 진입차수가 0인 노드를 큐에 넣는다.
2. 큐가 빌 때까지 다음의 과정을 반복한다.
- 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.
- 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.
진입차수 : 특정한 노드로 들어오는 간선의 개수
진출차수 : 특정한 노드에서 나가는 간선의 개수
위상 정렬은 DAG(Direct Acyclic Graph: 순환하지 않는 방향 그래프)에 대해서만 수행할 수 있다.
한 단계에서 큐에 새롭게 들어가는 원소가 2개 이상일 경우 여러가지 답이 존재한다.
모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단할 수 있다.
# 큐를 이용한 위상 정렬
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)
# 진입 차수를 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()
모든 노드를 확인하며 각 노드에서 나가는 간선을 차례대로 제거해야하기 때문에 시간 복잡도는 O(V+E)이다.
'알고리즘 > 공부' 카테고리의 다른 글
| PS 활용 문법들 (0) | 2022.12.29 |
|---|---|
| 코딩 테스트에서 자주 출제되는 기타 알고리즘 (0) | 2022.07.22 |
| 위상정렬 (0) | 2022.07.17 |
| 토막지식/짧은내용들 정리 (0) | 2022.07.16 |
| 그리디 알고리즘, 동적 계획법 (0) | 2022.07.05 |
