오예 !!!

이코테 p.300 실전 문제 - 도시 분할 계획 입력 예시 7 12 1 2 3 1 3 2 3 2 1 2 5 2 3 4 4 7 3 6 5 1 5 1 6 2 6 4 1 6 5 3 4 5 3 6 7 4 출력 예시 8 내 소스코드 크루스칼 알고리즘으로 최소 신장 트리를 구한 후, 최소 신장 트리의 간선 중 비용이 가장 큰 간선 제거 # 루트 노드를 찾는 함수 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(..

이코테 p.298 실전 문제 - 팀 결성 입력 예시 7 8 0 1 3 1 1 7 0 7 6 1 7 1 0 3 7 0 4 2 0 1 1 1 1 1 출력 예시 NO NO YES 내 소스코드 서로소 집합 알고리즘의 합집합 연산과 찾기 연산 적용 N과 M의 범위가 모두 최대 100,000이므로 경로 압축 방식의 서로소 집합 자료구조를 이용하여 시간 복잡도를 개선함 a와 b 각각에 대한 찾기 연산의 수행 결과가 같은지 비교하여 그 결과를 result에 저장 후 출력 # 같은 팀 여부 확인 연산 정의 def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] # 팀 합치기 연산 정의 ..

위상 정렬 정렬 알고리즘의 일종 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용 ex) 선수과목을 고려한 학습 순서 결정 그래프에서 선후 관계가 있다면, 위상 정렬을 수행하여 모든 선후 관계를 지키는 전체 순서를 계산할 수 있음 진입차수 (indegree) 특정한 노드로 들어오는 간선의 개수 위상 정렬 알고리즘 진입차수가 0인 노드를 큐에 넣는다 큐가 빌 때까지 다음 과정을 반복한다 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다 새롭게 진입차수가 0이 된 노드를 큐에 넣는다 위 과정을 반복하면서 큐에서 빠져나간 노드를 순서대로 출력하면, 그것이 바로 위상 정렬 수행 결과가 됨 모든 원소를 방문..

신장 트리 신장트리: 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건임 어떠한 그래프에서 신장 트리는 여러 개 존재할 수 있음 크루스칼 알고리즘 가능한 한 최소한의 비용으로 신장 트리를 찾을 때 사용 ex) N개의 도시가 존재할 때, 두 도시 사이에 도로를 놓아 전체 도시가 서로 연결될 수 있게 도로를 설치하는 경우, 최소한의 비용으로 모든 도시를 연결할 때 사용 최소 신장 트리 알고리즘 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘 크루스칼 알고리즘이 대표적인 최소 신장 트리 알고리즘 그리디 알고리즘의 일종 모든 간선에 대하여 정렬을 수행한 뒤, 가장 ..

서로소 집합 서로소 집합이란 공통 원소가 없는 두 집합 의미 ex) {1, 2}와 {3, 4}는 공통 원소가 없으므로 서로소 관계 ex) {1, 2}와 {2, 3}은 공통 원소가 있으므로 서로소 관계가 아님 서로소 집합 자료구조 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 union과 find 두 가지 연산으로 조작 union (합집합) 연산 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 find (찾기) 연산 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 트리 자료구조를 이용하여 집합 표현 트리를 이용한 서로소 집합 계산 알고리즘 union 합집합 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다 A와 B의 루트 노드 A'과 B'을 각각 찾는다 둘..

이코테 p.262 실전 문제 - 전보 입력 예시 3 2 1 1 2 4 1 3 2 출력 예시 2 4 내 소스코드 다익스트라 알고리즘 사용 메시지를 보내고자 하는 도시 c를 시작 노드로 설정 c로부터의 최단 시간 정보가 존재하는 도시를 카운트하여 메시지를 받는 도시 개수를 구함 c로부터의 최단 시간 정보들 중에서 최댓값을 구하여 메시지 전송에 걸리는 총 시간을 구함 import heapq import sys input = sys.stdin.readline INF = int(1e9) # 도시 개수 n, 간선 개수 m, 메시지를 보내고자 하는 도시 c 입력 받기 n, m, c = map(int, input().split()) # 그래프 입력 받기 graph = [[] for _ in range(n + 1)] f..

이코테 p.259 실전 문제 - 미래 도시 입력 예시 1 5 7 1 2 1 3 1 4 2 4 3 4 3 5 4 5 4 5 출력 예시 1 3 입력 예시 2 4 2 1 3 2 4 3 4 출력 예시 2 -1 내 소스코드 ver. 다익스트라 1번 노드에 대해 다익스트라 알고리즘을 적용한 후, 1번 노드부터 k번 노드까지의 거리 구하기 k번 노드에 대해 다익스트라 알고리즘을 적용한 후, k번 노드부터 x번 노드까지의 거리 구하기 연결된 2개의 회사는 양방향으로 이동할 수 있다고 하였으니 특정 간선 정보에 대해 D[a][b]와 D[b][a] 둘 다 설정해줘야 함 import heapq import sys input = sys.stdin.readline INF = int(1e9) # 입력받기 n, m = map(in..

플로이드 워셜 알고리즘 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 구해야 하는 경우 사용 단계마다 '거쳐 가는 노드'를 기준으로 알고리즘 수행 다익스트라와 달리, 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없음 시간 복잡도는 O(N^3) 노드의 개수가 N개일 때, 알고리즘 상으로 N번의 단계를 수행하며, 단계마다 O(N^2)의 연산을 통해 '현재 노드를 거쳐가는' 모든 경로를 고려함 최단 거리 정보를 저장하기 위해 2차원 리스트 사용 다익스트라는 시작 노드에서 다른 모든 노드까지의 최단 거리를 저장하기 위해 1차원 리스트 사용 플로이드 워셜은 모든 노드에서 다른 모든 노드로 가는 최단 거리 정보를 저장하기 위해 2차원 리스트 사용 다이나믹 프로그래밍 방식 노드의 개수..