전체 글

1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net ✅ 문제 설명 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이를 트리의 지름이라고 정의할 때, 트리의 지름을 구하는 문제입니다. ✅ 접근 방식 트리의 지름을 구하는 방법은 다음과 같습니다. 1) 시작노드(=아무노드나 가능)에서 가장 먼 노드 A를 구합니다. 2) 노드 A를 기준으로 가장 먼 노드B를 구하면 그 두 노드(A,B) 사이의 거리가 트리의 지름이 됩니다. 이게 왜 가능할까요? 어떤 노드에서 가장 먼 노드를 구하면(1번) 그 노..

14675번: 단절점과 단절선 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 트리의 정점 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 트리의 정점은 1번부터 n번까지 존재한다. 다음 줄부터 N-1개의 줄에 걸쳐 간선의 정 www.acmicpc.net ✅ 문제 설명 트리에서 단절점(cut vertex)과 단절선(bridge)을 구하는 문제입니다. 단절점, 단절선? 단절점: 하나의 컴포넌트(connected componenet)로 이루어진 그래프에서 한 정점을 제거했을 때, 컴포넌트의 개수가 증가하는 정점을 단절점이라고 한다. 단절선: 하나의 컴포넌트(connected componenet)로 이루어진 그래프에서 한 간선을 제거했을 때, 컴포넌트의 개수가 증가하는 간선을 단절선이라고 한다..

5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net ✅ 문제 설명 이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하는 문제입니다. 이진 검색 트리? - 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다. - 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다. - 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다. ✅ 접근 방식 처음 접근한 방법 전위순회 결과를 이용해서 트리를 만들고, 이를 후위순회하려했습니다. 그렇..

9934번: 완전 이진 트리 상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 www.acmicpc.net ✅ 문제 설명 문제를 읽어보면 깊이가 K인 완전 이진 트리가 주어지고, 상근이는 중위순회 방식(왼쪽-> 루트 -> 오른쪽 순)으로 트리를 순회합니다. 이런 환경에서 상근이가 방문한 빌딩 번호가 순서대로 주어질 때, 완전 이진트리를 역으로 유추해 각 레벨에 있는 빌딩의 번호를 출력하는 문제입니다. ✅ 접근 방식 완전 이진 트리라는 점, 상근이가 중위순회를 한다는 것, 그리고 가장 마지막 레벨을 제외한 모든 집은 왼쪽 자식과 오른쪽 자식을 ..

1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net ✅ 문제 설명 이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 문제입니다. (이진 트리: 각 노드가 최대 2개의 자식노드를 가지는 트리) 전위순회, 중위순회, 후위순회? 전위순회 = (루트) (왼쪽 자식) (오른쪽 자식) 중위순회 = (왼쪽 자식) (루트) (오른쪽 자식) 후위순회 = (왼쪽 자식) (오른쪽 자식) (루..

11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net ✅ 문제 설명 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 문제다. 입력 => 첫째줄에 노드의 수 N이 주어지고, 둘째 줄부터 트리 상에서 연결된 두 정점이 주어진다. ex) 아래 그림에서 왼쪽과 같은 입력으로 트리를 그려보면 그림의 오른쪽과 같은 트리를 얻을 수 있다. ✅ 접근 방식 트리의 특징 상, 루트노드에서부터 탐색을 수행하면 부모노드를 거치지 않고선 자식노드에게 갈 수 없다. 루트노드에서 dfs나 bfs로 트리를 탐색하면서 "새롭게 탐색된 노드의 부모노드 = 현재 노드"로 저장해 준다. ✅ 코드 # 트..