728x90
반응형
본 글은 "나동빈"님의 [이것이 코딩 테스트다]를 참고하여 작성하였으며, 필자가 직접 문제를 풀며 관련된 문제들을 찾아 정리하였습니다.
시리즈 보기
[코테 알고리즘] 파이썬 기본 / 관련 문제
[코테 알고리즘] 파이썬 주요 라이브러리 / 관련 문제
[코테 알고리즘] 그리디 / 관련 문제
[코테 알고리즘] 구현 / 관련 문제
[코테 알고리즘] DFS, BFS / 관련 문제
[코테 알고리즘] 정렬 / 관련 문제
[코테 알고리즘] 다이나믹 프로그래밍 / 관련 문제
[코테 알고리즘] 최단 경로 / 관련 문제
[코테 알고리즘] 그래프 이론 / 관련 문제
서로소 집합
- 서로소 집합 자료구조
- 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조
- 서로소 집합 : 공통 원소가 없는 두 집합
- union-find 자료구조
- union
- 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
- find
- 특정한 원소가 속한 집합이 어디 연산인지 알려줌
- union
서로소 집합 자료구조
- 트리 자료구조를 사용하여 집합을 표현
- 알고리즘
- union(합집합) 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인
- A와 B의 루트 노드 찾기
- 각의 루트 노드를 부모 노드로 설정
- 모든 union(합집합) 연산을 처리할 때까지 반복
- union(합집합) 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인
- 유의할 점
- union 연산을 효과적으로 하기 위해 ‘부모 테이블’이 필수
- 루트 노드를 즉시 계산할 수 없고, 부모 테이블을 계속 확인하면서 거슬러 올라감
- 루트를 찾기 위해서는 재귀적으로 부모를 거슬러 올라가야함
# 특정 원소가 속한 집합 찾기
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
v, e = map(int, input().split())
parent = [i for i in range(1, v+1)]
for i in range(e):
a, b = map(int, input().split())
union(parent, a, b)
사이클 판별
- 무방향 그래프
- 서로소 집합을 이용해 사이클 판별
- 루트 노드가 같다면 사이클이 발생
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
def union(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
v, e = map(int, input().split())
parent = [i for i in range(1, v+1)]
# 사이클 발생 여부
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, a, b)
if cycle:
print("사이클 발생")
else:
print("사이클이 발생하지 않음")
- 방향 그래프
- DFS를 이용하여 판별
문제
집합의 표현
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
n, m = map(int, input().split())
parent = [i for i in range(n+1)]
def find_parent(x):
if parent[x] != x:
parent[x] = find_parent(parent[x])
return parent[x]
def union(a, b):
a = find_parent(a)
b = find_parent(b)
if a < b:
parent[b] = a
else:
parent[a] = b
for _ in range(m):
q, a, b = map(int, input().split())
if q == 0:
union(a, b)
else:
if find_parent(a) != find_parent(b):
print("NO")
else:
print("YES")
신장 트리
- 신장 트리
- 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하는 부분 그래프
크루스칼 알고리즘
- 가장 적은 비용으로 모든 노드를 연결한 신장트리를 만듦
- 그리디 알고리즘
- 모든 간선에 대해 정렬을 수행
- 알고리즘
- 가장 거리가 짧은 간선부터 집합에 포함
- 사이클을 발생하는 경우 포함 x
- 구체적 알고리즘
- 간선 데이터를 비용에 따라 오름차순 정렬
- 간선을 하나씩 확인하며 현재 간선이 사이클을 발생하는지 확인
- 사이클 발생하지 않는 경우 최소 신장 트리에 포함
- 사이클 발생하는 경우 최소 신장 트리에 포함하지 않음
- 모든 간선에 대해 2번 반복
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
def union(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
v, e = map(int, input().split())
parent = [i for i in range(v+1)]
# 모든 간선을 담을 리스트와 최종 비용을 담을 변수
edges = []
result = 0
# 간선에 대한 정보 입력 받기
for i 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, a, b)
result += cost
print(result)
- 시간 복잡도
- O(ElogE)
문제
최소 스패닝 트리
import sys
input = sys.stdin.readline
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[a] = b
else:
parent[b] = a
v, e = map(int, input().split())
parent = [i for i in range(v+1)]
edges = []
for _ in range(e):
a, b, c = map(int, input().split())
edges.append((c, a, b))
edges.sort()
answer = 0
for edge in edges:
cost, a, b = edge
if find_parent(parent, a) != find_parent(parent, b):
union_parent(parent, a, b)
answer += cost
print(answer)
도시 분할 계획
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
parent = [i for i in range(n+1)]
edges = []
for _ in range(m):
a, b, c = map(int, input().split())
edges.append((c, a, b))
edges.sort()
def find_parent(x):
if parent[x] != x:
parent[x] = find_parent(parent[x])
return parent[x]
def union_parent(a, b):
a = find_parent(a)
b = find_parent(b)
if a > b:
parent[a] = b
else:
parent[b] = a
total = 0
maximum = 0
for edge in edges:
c, a, b = edge
if find_parent(a) != find_parent(b):
union_parent(a, b)
total += c
maximum = c
print(total - maximum)
위상 정렬
- 순서가 정해져 있는 일련의 작업을 차례로 수행할 때 사용하는 알고리즘
- 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열
- 진입차수
- = 특정한 노드로 들어오는 간선의 개수
- 알고리즘
- 진입차수가 0인 노드를 큐에 넣음
- 큐가 빌 때까지 과정 반복
- 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거
- 새롭게 진입 차수가 0이 된 노드를 큐에 넣음
- 답이 여러 개라는 것이 특징
from collections import deque
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())
# a에서 b로 이동 가능
graph[a].append(b)
# 진입 차수를 1 증가
indegree[b] += 1
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)
- 시간 복잡도
- O(V+E)
문제
선수과목
import sys
input = sys.stdin.readline
from collections import deque
n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]
indegree = [0] * (n + 1)
for _ in range(m):
a, b = map(int, input().split())
graph[a].append(b)
indegree[b] += 1
def topology():
answer = [0] * (n+1)
q = deque()
for i in range(1, n+1):
if indegree[i] == 0:
q.append((i, 1))
while q:
now, time = q.popleft()
answer[now] = time
for new in graph[now]:
indegree[new] -= 1
if indegree[new] == 0:
q.append((new, time+1))
return answer
answer = topology()
for a in answer[1:]:
print(a, end = " ")
줄세우기
import sys
input = sys.stdin.readline
from collections import deque
n, m = map(int, input().split())
student = [[] for _ in range(n+1)]
inDegree = [0] * (n+1)
for _ in range(m):
a, b = map(int, input().split())
student[a].append(b)
inDegree[b] += 1
que = deque()
for i in range(1, n+1):
if inDegree[i] == 0:
que.append(i)
while que:
now = que.popleft()
print(now, end=" ")
for new in student[now]:
inDegree[new] -= 1
if inDegree[new] == 0:
que.append(new)
트리 순회
import sys
N = int(sys.stdin.readline().strip())
tree = {}
for n in range(N):
root, left, right = sys.stdin.readline().strip().split()
tree[root] = [left, right]
def preorder(root):
if root != '.':
print(root, end='') # root
preorder(tree[root][0]) # left
preorder(tree[root][1]) # right
def inorder(root):
if root != '.':
inorder(tree[root][0]) # left
print(root, end='') # root
inorder(tree[root][1]) # right
def postorder(root):
if root != '.':
postorder(tree[root][0]) # left
postorder(tree[root][1]) # right
print(root, end='') # root
preorder('A')
print()
inorder('A')
print()
postorder('A')
반응형
'코딩 테스트 > 파이썬 알고리즘' 카테고리의 다른 글
| [코테 알고리즘] 소수 판별&투 포인터 / 관련 문제 (0) | 2024.03.21 |
|---|---|
| [코테 알고리즘] 최단 경로 / 관련 문제 (0) | 2024.03.11 |
| [코테 알고리즘] 다이나믹 프로그래밍 / 관련 문제 (0) | 2024.03.10 |
| [코테 알고리즘] 정렬 / 관련 문제 (0) | 2024.03.08 |
| [코테 알고리즘] DFS, BFS / 관련 문제 (1) | 2024.03.08 |
