BOJ 백준 22954 그래프 트리 분할 문제: https://www.acmicpc.net/problem/22954 22954번: 그래프 트리 분할 첫 번째 줄에 정점의 개수 $N$, 간선의 개수$M$이 주어진다. ($1 \le N \le 100\,000$, $0 \le M \le 200\,000$) 두 번째 줄부터 $M$줄에 걸쳐서 간선을 나타내는 정수 $u$와 $v$가 주어진다. ($1 \le u, v \le N$, $u www.acmicpc.net 정점 N개, 간선 M개의 그래프가 주어졌을 때 서로 다른 크기의 2개의 트리로 분할하라는 문제이다. 문제에서 주어지는 그래프에는 특별한 제약 사항이 없으므로 이미 그래프가 여러 개의 연결 요소로 분할되어 있을 수도 있다. 그래서 그래프의 연결 요소 개수를..

BOJ 백준 6672 Electricity 문제: https://www.acmicpc.net/problem/6672 6672번: Electricity Blackouts and Dark Nights (also known as ACM++) is a company that provides electricity. The company owns several power plants, each of them supplying a small area that surrounds it. This organization brings a lot of problems - it often happens that there i www.acmicpc.net 처음에는 문제 내용을 제대로 이해하지 못해서 난처했는데, 결국 간단히 정리..

BOJ 백준 19535 ㄷㄷㄷㅈ 문제: https://www.acmicpc.net/problem/19535 19535번: ㄷㄷㄷㅈ 첫 번째 줄에 주어진 트리가 D-트리라면 D, G-트리라면 G, DUDUDUNGA-트리라면 DUDUDUNGA를 출력한다. www.acmicpc.net 정점 수가 N인 트리가 주어졌을 때, 4개의 정점으로 이루어진 ㄷ’ 모양의 서브트리와 ‘ㅈ’ 모양의 서브트리 개수에 3배한 값을 비교하여 해당 트리가 어떤 트리에 속하는지 출력해야 한다. (4 ≤ N ≤ 300,000) 처음에 이 문제를 보고 (트리에서의) 다이나믹 프로그래밍(Dynamic Programming)으로 해결하는 문제일 것으로 예상했다. 그러나 실제로 확인해보니 굳이 거창하게 다이나믹 프로그래밍까지 확장하여 생각할 ..

​​ BOJ 백준 16964 DFS 스페셜 저지 문졔: https://www.acmicpc.net/problem/16964 16964번: DFS 스페셜 저지 첫째 줄에 정점의 수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다. 마지막 줄에는 DFS 방문 순서가 주어진다. DFS 방문 순서는 항상 N개의 정수로 이루 www.acmicpc.net 트리와 트리의 노드를 방문한 순서가 주어졌을 때, 올바른 DFS 방문 순서가 맞는지를 구하는 문제이다. DFS(Depth First Search) 순서를 만족하는 조건을 먼저 생각해봤다. 1) 직전에 방문한 정점의 자식들 중에서 방문하지 않은 정점의 수가 1 이상일 때 현재 방문 중인 정점이 직전에 방문한 ..

BOJ 백준 3665 최종순위 문제: www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 1번부터 n번까지 번호가 매겨진 팀들이 작년과 올해 대회에 참전했는데, 문제에서 알려주는 데이터는 작년 대회에서의 최종 순위와 올해 대회에서 상대적인 순위가 바뀐 팀들의 목록이다. 이를 바탕으로 올해 최종 순위를 구해야 하는데, 최종 순위가 완성될 수 없는 경우도 고려해야 한다. 이와 같은 경우는 다음과 같다. 1) 데이터의 일관성이 없는 경우 2) 확실한 순위를 찾..