📌문제온라인으로 강의를 들으려 하는데 선수 강의가 있는 강의는 선수 강의를 먼저 들어야만 해당 강의를 들을 수 있다. 동빈이는 N개의 강의를 듣고자 한다. 모든 강의는 1~N번까지의 번호를 가진다. 또한 동시에 여러 강의를 들을 수 있다고 가정한다. 동빈이가 듣고자하는 N개의 강의 정보가 주어졌을 때 N개의 강의에 대해 수강하기까지 걸리는 최소 시간을 각각 출력하는 프로그램을 작성하시오 📌풀이위상 정렬 알고리즘 사용각 각의에 대해 인접 노드를 확인할 때 현재보다 강의 시간이 더 긴 경우를 찾는다면 더 오랜 시간이 걸리는 경우의 시간 값을 저장하는 방식으로 결과 테이블 갱신 리스트의 경우 단순 대입 연산을 하면 값이 변경될 대 문제가 발생할 수 있기 때문에 리스트 값을 복제해야 할 때는 deepcopy..
📌문제마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 마을의 이장은 마을을 2개의 분리된 마을로 분할할 계획을 세우고 있다. 마을을 분할할 때는 각 분할된 마을 안에 집들이 서로 연결되도록 분할해야 한다.마을의 이장은 계획을 세우다 마을 안에 길이 너무 많다는 생각을 했다. 일단 분리된 두 마을 사이 길은 필요 없으므로 없앨 수 있다. 그리고 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다. 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하는 프로그램을 작성하시오. 📌풀이전체 그래프에서 2개의 최소 신장 트리 만들어야 함크루스칼 알고리즘으로 최소 신장 트리를 찾은 뒤에 최소 신장 트리를 구성하는 간선 중..
📌문제학교에서 학생들에게 0~N번까지의 번호를 부여했다. 처음에는 모든 학생이 서로 다른 팀으로 구분되어 총 N+1개의 팀이 존재한다. 이때 선생님은 팀 합치기 연산과 같은 팀 여부 확인 연산을 사용할 수 있다.1. 팀합치기 연산은 두 팀을 합치는 연산이다.2. 같은 팀 여부 확인 연산은 두 학생이 같은 팀에 속하는지 확인하는 연산이다.선생님이 M개의 연산을 수행할 수 있을 때 같은 팀 여부 확인 연산에 대해 연산 결과를 출력하는 프로그램을 작성하시오. 📌풀이경로 압축 방식의 서로소 집합 알고리즘 📌코드# 특정 원소가 속한 집합 찾기def find_parent(parent, x): # 루트 노드가 아니라면 루트 노드 찾을 때까지 재귀 호출 if parent[x] != x: p..
📌위상 정렬순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용하는 알고리즘방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것ex: 선수 과목을 고려한 학습 순서 설정 진입 차수: 특정한 노드로 들어오는 간선의 개수 1. 진입차수가 0인 노드를 큐에 넣는다.2. 큐가 빌때까지 다음 과정 반복한다. - 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다. - 새롭게 진입차수가 0이 된 노드를 큐에 넣는다. 📌코드from collections import deque# 노드의 개수, 간선의 개수 입력v, e = map(int, input().split())# 모든 노드 진입차수 0으로 초기화indegree = [0] * (v + 1)# 각 노드에 연결된..
📌신장 트리하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재 하지 않는 부분 그래프 📌크루스칼 알고리즘최소 신장 트리 알고리즘: 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘대표적인 최소 신장 트리 알고리즘이 크루스칼 알고리즘 가장 적은 비용으로 모든 노드 연결모든 간선에 대하여 정렬을 수행한 후 가장 거리가 짧은 간선부터 집합에 포함 1. 간선 데이터를 비용에 따라 오름차순 정렬2. 간선을 하나씩 확인하며 현재의 간선이 사이클 발생시키는지 확인 - 사이클 발생하지 않는 경우 최소 신장 트리에 포함 - 사이클 발생하는 경우 최소 신장 트리에 포함시키지 않음3. 모든 간선에 대하여 2번 과정 반복 📌코드# 특정 원소가 속한 집합 찾기def find_parent(..
📌서로소 집합을 활용한 사이클 판별서로소 집합은 무방향 그래프 내에서의 사이클 판별할 때 사용(방향 그래프 내에서의 사이클 판별은 DFS 사용) 1. 각 간선을 확인하며 두 노드의 루트 노드를 확인한다. - 루트 노드가 서로 다르다면 두 노드에 대하여 union 연산을 수행한다 - 루트 노드가 서로 같다면 사이클이 발생한 것이다.2. 그래프에 포함되어 있는 모든 간선에 대해 1번을 반복한다. 📌코드# 특정 원소가 속한 집합 찾기def find_parent(parent, x): # 루트 노드가 아니라면 루트 노드 찾을 때까지 재귀적으로 호출 if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return pare..
📌서로소 집합공통 원소가 없는 두 집합 📌서로소 집합 자료구조서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조union, find 2가지 연산union: 합집합, 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산find: 찾기, 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 구현 시 트리 자료구조 사용1. union 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다. - A와 B의 루트 노드 A', B'를 각각 찾는다. - A'를 B'의 부모 노드로 설정한다(B'가 A'를 가리키도록 한다.)2. 모든 union 연산을 처리할 때까지 1번 과정 반복한다. 📌기본적인 서로소 집합 알고리즘 소스코드# 특정 원소가 속한 집합을 찾기def find_parent(..
📌문제어떤 나라에 N개의 도시가 있다. 그리고 각 도시는 보내고자하는 메세지가 있는 경우, 다른 도시로 전보를 보내서 다른 도시로 해당 메세지를 전송할 수 있다. 하지만 X라는 도시에서 Y라는 도시로 전보를 보내고자 한다면 그 사이 통로가 있어야 한다. 어느날 C라는 도시에서 위급 상황이 발생했다. 그래서 최대한 많은 도시로 메세지를 보내고자 한다. 메세지는 도시 C에서 출발하여 각 도시 사이 설치된 통로를 거쳐 최대한 많이 퍼져나갈 것이다. 각 도시의 번호와 통로가 설치되어 있는 정보가 주어졌을 때, 도시 C에서 보낸 베세지를 받게 되는 도시의 개수는 총 몇개이며 도시들이 모두 메세지를 받는 데까지 걸리는 시간을 계산하시오. 📌풀이한 도시에서 다른 도시까지의 최단 거리 문제우선 순위 큐를 이용한 다..