매일 조금씩

문제 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 풀이 트리의 지름을 구하는 공식을 알면 쉽게 풀 수 있다. 트리 내 임의 정점을 선택하여 해당 노드에서 거리가 가장 먼 노드를 구한다. 해당 노드에서 DFS 알고리즘을 수행하여 가장 먼 거리를 구하면 그 값이 트리의 지름이 된다. 아래 블로그 내용을 참고하였다. https://blog.myungwoo.kr/112 트리의 지름 구하기 트리에서 지름이란, 가장 먼 두 정점 사이의..

문제 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오. 예를 들어 위와 같은 이진 트리가 입력되면, 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식) 중위 순회한 결과 : DBAECFG // (왼쪽 자식..

#문제 https://www.acmicpc.net/problem/15900 15900번: 나무 탈출 평소에 사이가 좋지 않던 성원이와 형석이가 드디어 제대로 한 판 붙으려고 한다. 성원이와 형석이 둘과 모두 똑같이 친한 인섭이가 대결 종목을 정해 가져왔다. 바로 '나무 탈출' 이라는 보드게 www.acmicpc.net #풀이 Leaf Node의 모든 Depth를 더했을 때 짝수인지 홀수인지에 따라 승패가 결정된다. Node정보를 인접 리스트로 저장한다. (방향성이 없으므로 양쪽에 모두 저장) 현재 Node의 Parent Node는 인접 리스트에서 제거한 후 dfs 탐색을 한다. 인접 노드가 없는 경우 해당 노드는 Leaf Node이므로 현재까지 구한 depth를 count에 더한다. count의 짝/홀 ..