https://www.acmicpc.net/problem/24526 24526번: 전화 돌리기 첫 줄에 부원의 수 $N$과 관계의 수 $M$이 공백을 사이에 두고 정수로 주어진다. ($2 \le N \le 100,000$ , $1 \le M \le $ $500,000$) 둘째 줄부터 $M+1$번째 줄까지 어떤 부원 $U_{i}$가 전화를 받았을 때 다른 부원 www.acmicpc.net 그래프에서 사이클에 포함되는 노드와, 사이클 쪽으로 이동하도록 연결된 노드들을 판별해야 한다. 즉, 사이클 판별과, 사이클에 들어가는 노드들도 판별해야 된다. 문제를 해결하기 위해, 그래프의 간선의 방향을 거꾸로 연결해서, 위상 정렬을 수행하여 위상 정렬의 큐에 들어가지 않는 노드들은 거꾸로 연결된 그래프에서 사이클에 속..

https://www.acmicpc.net/problem/13325 13325번: 이진 트리 각 에지에 양수인 가중치가 부여된 높이가 k인 포화이진트리가 주어져 있다. 높이 k인 포화이진트리는 2k개의 리프를 포함하여 (2k+1 − 1)개의 노드를 가진다. 루트에서 어떤 리프까지의 거리는 www.acmicpc.net 부모노드에서 자식노드 쪽으로 연결되는 트리를 만들고, 이를 이용해서 루트노드(1번 노드)에서 시작해서 리프 노드까지 이동하면서, 각 노드에서 리프노드로 가는데 거리의 최댓값을 max_leaf_cost[노드 번호]에 저장해 놓는다. 그리고 이 과정에서 루트노드에서 리프노드까지 최댓값(max_leaf_cost[1])도 구할 수 있으므로 해당 값으로, 루트노드에서 모든 리프노드까지 거리를 맞춘다...

https://www.acmicpc.net/problem/16437 16437번: 양 구출 작전 2, 3, 5번에 사는 모든 양들은 1번 섬으로 갈 수 있지만 7번 섬에 사는 양들은 1번 섬으로 가기 위하여 6번 섬을 거쳐야 하는데 6번 섬에 사는 늑대들의 수가 7번 섬에 사는 양들의 수보다 많으므로 www.acmicpc.net 1번 섬이 루트가 되도록 트리를 만들고, 트리의 연결을 자식 노드에서 루트 노드 방향으로 연결한다. 그리고, 리프노드부터 시작하여 위상 정렬로 탐색하여, 1번 섬인 루트에 도달하는 양의 수를 구하는 방법으로 문제를 해결했다. 코드 #include #include #include #include #include using namespace std; int n; vector brid..

https://www.acmicpc.net/problem/2610 2610번: 회의준비 첫째 줄에 회의에 참석하는 사람의 수 N이 주어진다. 참석자들은 1부터 N까지의 자연수로 표현되며 회의에 참석하는 인원은 100 이하이다. 둘째 줄에는 서로 알고 있는 관계의 수 M이 주어진다. 이 www.acmicpc.net 유니온 파인드를 이용해서 같은 위원회를 그룹으로 묶었고, 플로이드 와샬을 통해 각 정점 간 최단거리를 저장하여, 각 그룹에서 그룹 내 다른 정점과 최댓값이 최소가 되는 정점을 구하는 방법으로 문제를 해결했다. 코드 #include #include #include #include using namespace std; int n; int m; int adj[105][105]; int parent[1..

https://www.acmicpc.net/problem/2109 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net 마지막날부터, 첫째 날 순으로 해당 날짜에 강연할 수 있는 것 중 가장 강연료가 큰 강연을 고른다. 마지막날부터 고르는 이유는, 뒤에 날까지 강연해야 되는 강연들은 그 앞 날짜에도 강연할 수 있으므로, 마지막날부터, 첫째 날 순으로 해당 날짜에 강연할 수 있는 강연료들을 우선순위 큐에 강연료가 큰 게 먼저 나오도록 우선순위 큐에 넣으면서, 우선순위에서 가장 먼저..

https://www.acmicpc.net/problem/23295 23295번: 스터디 시간 정하기 1 첫째 줄에는 스터디에 참가하고자하는 참가자 수 N과 스터디 시간 T가 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ T ≤ 100,000) 다음 줄부터 참가하고자 하는 참가자들의 시간 정보가 N개 주어진다. 각 정보의 www.acmicpc.net 참가자들이 가능한 시작 시각에 +1, 끝나는 시각에 -1을 체크하여, 체크한 값들을 누적합을 구해서 각 시간대에 몇 명이 참가 가능한지 저장한다. 그리고 구한 누적합에서 슬라이딩 윈도우를 이용해, 스터디 시간에서 최대 합이 되는 구간을 구해서 문제를 해결했다. 코드 #include #include #include using namespace std; in..