컴공생 누르지 마세요! 컴공생 울어요.

이코테 p.303 실전 문제 - 커리 큘럼 입력 예시 5 10 -1 10 1 -1 4 1 -1 4 3 1 -1 3 3 -1 출력 예시 10 20 14 18 17 내 소스코드 cost_array 리스트 cost_array[i]는 i번 강의를 듣는 데 걸리는 시간 graph 리스트 graph[1] = [0, 2, 3, 4]라면 1번 노드는 2, 3, 4번 노드와 연결되어 있음을 의미 0번 인덱스의 요소는 건너뜀 위상 정렬 알고리즘 사용 indegree가 0이 될 때 q에 삽입 & result 값 갱신 result[다음 노드] = max(result[다음 노드], result[현재 노드] + cost_array[다음 노드]) 주의할 점) 아래 소스코드의 result = cost_array처럼 단순히 대입 연산..

이코테 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..