honey_pot

온라인으로 총 N개의 강의를 듣고자 한다. 모든 강의는 1번부터 N번까지의 번호를 가진다. 또한 동시에 여러 개의 강의를 들을 수 있다. 각 온라인 강의는 선수 강의가 있을 수 있는데, 선수 강의가 있는 강의는 선수 강의를 먼저 들어야만 해당 강의를 들을 수 있다. 듣고자 하는 N개의 강의 정보가 주어졌을 때, N개의 강의에 대하여 수강하기까지 걸리는 최소 시간을 각각 출력하는 프로그램을 작성하시오 입력 조건 첫째 줄에 듣고자 하는 강의의 수 (1

N개의 집과 집들을 연결하는 M개의 길이 있다. 길은 어느 방향으로든지 다닐수 있고, 길을 유지하는데 드는 유지비가 있다. 마을을 2개로 분할하려고 할 때 각 분리된 마을 안에 집들이 서로 연결되어야 한다. 즉, 각 분리된 마을 내의 두 집 사이에 경로가 항상 존재해야 한다. 마을에는 집이 하나 이상 있어야 한다. 이 조건을 만족하도록 길들을 없애고 나머지 길의 유지비의 합을 최소로 하는 프로그램을 작성하시오. 입력 조건 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. (2

학교에서 학생들에게 0번부터 N번까지의 번호를 부여했다. 처음에는 모든 학생이 서로 다른 팀으로 구분되어, 총 N+1 개의 팀이 존재한다. 이때 선생님은 '팀 합치기' 연산과 '같은 팀 여부 확인' 연산을 사용할 수 있다. '팀 합치기' 연산은 두 팀을 합치는 연산이다. '같은 팀 여부 확인' 연산은 특정한 두 학생이 같은 팀에 속하는지를 확인하는 연산이다. 선생님이 M개의 연산을 수행할 수 있을 때, '같은 팀 여부 확인' 연산에 대한 연산 결과를 출력하는 프로그램을 작성하시오. 입력 조건 첫째 줄에 N,M이 주어진다. M은 입력으로 주어지는 연산의 개수이다. (1

위상 정렬 (Topology Sort) 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것' 특정한 노드로 '들어오는' 간선의 개수인 진입차수(Indegree)를 알아야 함 차례대로 모든 노드를 확인하면서, 해당 노드에서 출발하는 간선을 차례대로 제거한다. O(V+E) 👉 노드와 간선을 모두 확인하기 때문 기본적으로 위상 정렬 문제에서는 사이클이 발생하지 않는다고 명시하는 경우가 많음 알고리즘 1. 진입차수가 0인 노드를 큐에 넣는다. 2. 큐가 빌 때까지 다음의 과정을 반복한다. 2-1. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다. 2-2. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다. 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단한..

신장 트리 (Spanning Tree) 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 간선의 개수 = 노드의 개수 -1 크루스칼 알고리즘 최소 신장 트리 알고리즘 ➡ 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘 그리디 알고리즘 모든 간선에 대하여 정렬을 수행한 뒤에 가장 거리가 짧은 간선부터 집합에 포함시킨다. 핵심 원리 : 가장 거리가 짧은 간선부터 차례대로 집합에 추가 ( 사이클을 발생시키는 간선은 제외하고 연결한다.) O(ElogE) (E : 간선의 개수) ➡ 간선을 정렬하는 작업이 O(ElogE) 로 가장 시간이 오래 걸림 알고리즘 1. 간선 데이터를 비용에 따라 오름차순으로 정렬한다. 2. 간선을 하나씩 확인하며 현재의 간선이 사..

크루스칼 알고리즘 - 그리디 알고리즘 위상 정렬 알고리즘 - 큐/ 스택 자료구조 이용 그래프 트리 방향성 방향 그래프 혹은 무방향 그래프 방향 그래프 순환성 순환 및 비순환 비순환 루트 노드 존재 요부 루트 노드가 없음 루트 노드가 존재 노드간 관계성 부모가 자식 관계 없음 부모와 자식 관계 모델의 종류 네트워크 모델 계층 모델 노드의 개수가 적을 때 ➡ 플로이드 워셜 노드와 간선의 개수가 오무 많을 때 ➡ 우선순위큐 이용 다익스트라 서로소 집합 ( Disjoint Sets) : 공통 원소가 없는 두 집합 서로소 집합 자료구조 (union-find 합치기 찾기 구조) 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조. union (합집합) ➡ 2개의 원소가 포함된 집합을 하나의 집합..

어떤 나라에는 N개의 도시가 있다. 도시 X에서 Y로 향하는 통로가 있다면 X도시에서 Y도시로 메시지를 보낼 수 있다. 만약 X➡Y 통로는 있지만 Y➡X 통로가 없다면, X에서 Y로는 메시지를 보낼 수 있지만 Y에서 X로 메시지를 보낼 수는 없다. C라는 도시에서 위급 상황이 발생해 최대한 많은 도시로 메시지를 보내고자 한다면 , 각 도시의 번호와 통로가 설치되어 있는 정보가 주어졌을 때, 도시 C에서 보낸 메시지를 받게 되는 도시의 개수는 총 몇 개이며 도시들이 모두 메시지를 받는 데까지 걸리는 시간은 얼마인지 계산하는 프로그램을 작성하시오. 입력 조건 첫째 줄에 도시의 개수 N, 통로의 개수 M, 메시지를 보내고자 하는 도시 C가 주어진다. (1

공중미래 도시에는 1번부터 N번까지의 회사가 있는데 특정 회사끼리는 서로 도로를 통해 연결되어 있다. 방문 판매원 A는 현재 1번 회사에 위치해 있으며, X번 회사에 방문해 물건을 판매하고자 한다. 연결된 두 회사는 양방향으로 이동할 수 있고, 연결된 도로는 1만큼의 시간으로 이동한다. A는 1번 회사에서 출발하여 K번 회사를 방문한 뒤에 X번 회사로 가는 것이 목표다. A가 회사 사이를 이동하게 되는 최소 시간을 계산하는 프로그램을 작성하시오. 예를 들어 n = 5, x = 4, k =5 이고 회사 간 도로가 7개면서 각 도로가 다음과 같이 연결되어 있다. (1, 2), (1, 3), (1, 4), (2, 4), (3, 4), (3, 5), (4, 5) 이때 A가 4번 회사에 가는 경로는 (1 - 3 ..