문제 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 주어진 트리를 전위, 중위, 후위 순회하는 문제였다. 문제 풀이 재귀함수를 이용해 해결했다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include using namespace std; pair G[27];//최대 노드 수 26 int N; int is..
문제 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 노드와 노드 사이의 최장 길이를 찾는 문제였다. 문제 풀이 처음에 모든 정점에서 dfs를 돌려서 Max 값을 구했는데 그랬더니 시간 초과가 났다. V가 최대 100,000이어서 시간 초과가 나는 것은 당연했고 다른 방법을 찾았다. 첫 번째의 dfs로 1번 노드와 비교했을 때 가장 멀리 있는 정점을 찾았고, 그 정점에서 다시 dfs를 해서 최장 길이를 구했다. 솔직히 이 문제가..
문제 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 구라쟁이 지민이를 위해 그룹을 만들어 해결하는 문제였다. 문제 풀이 처음 문제를 봤을 때는 진실을 아는 사람들을 vector에 집어넣고 while로 더 이상 들어가지 않을 때까지 돌린 후, 마지막에 각 파티마다 확인하는 방법을 생각했다. 코드로 옮기기 전부터 너무 비효율적인 것 같아 고민하던 찰나에 유니온 파인드가 생각났고, parent를 만들어서 푸는 방법을 떠올렸다. 진실을 아는 사람들의 paren..
서로소 집합(Union-find), 크루스칼 알고리즘(최소 신장 트리), 위상 정렬과 관련한 문제들이다. 각 알고리즘의 설명 및 구현은 따로 올릴 것이다. 팀 결성 팀 합치기, 같은 팀 여부 확인 연산을 하는 문제로 Union-Find 방법을 이용해 푸는 문제였다. 0번 연산이 union을 만드는 연산, 1번 연산이 같은 parent를 가지는지 확인하는 연산이었다. 각각에 대해 makeUnion, findParent 연산을 만들어서 해결했다. int parent[100001] = { 0 }; int find_parent(int a, int b) { //항상 a
