L.O.K

3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net ◎ 문제풀이 두 개의 노드에서 공통 부모를 찾는 문제이다. 1) 부모테이블을 만든다. 2) 루트를 찾는다. 3) While문 안에 While문을 넣어 이중for문처럼 하나씩 비교하여 공통부모를 찾는다. ◎ 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Str..

1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net ◎ 문제풀이 트리의 지름의 최대 길이를 구하는 문제이다. 이는 노드A에서 노드B까지 거리의 최댓값을 구하라는 의미이다. 한 노드에서 다른 노드까지 가는 경우의 수를 완전탐색하여 최댓값을 구하는 문제이므로 DFS를 이용하면 된다. 추가로, 문제를 더 빠르게 푸는 방법이 있다. 1) 1번 노드에서 DFS 완전탐색으로 가장 멀리 떨어져있는 노드A를 구한다. 2) 노드A까지 가는 경로는 가중치가 가장 높은 경로를 의미한다. 3) 노드A에서 거리가 가..

https://www.acmicpc.net/problem/14675 14675번: 단절점과 단절선 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 트리의 정점 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 트리의 정점은 1번부터 n번까지 존재한다. 다음 줄부터 N-1개의 줄에 걸쳐 간선의 정 www.acmicpc.net ◎ 문제풀이 뭔가 맥이 빠지는 문제였다. 단절점과 단절선을 없애면 트리가 그래프가 두 개 나와야 한다. 단절선은 무엇을 없애든 그래프가 2개 나온다. 그러므로 무조건 yes이다. 단절점은 단절점의 자식노드가 2개 이상이면 yes이다. 그러므로 트리를 인접리스트로 구현하여 리스트의 크기가 2이상이면 yes를 출력한다. ◎ 코드 package org.example.tree;..

1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net ◎ 문제풀이 특정 노드를 삭제하면 자식 노드들도 삭제가 될 때, 리프노드의 개수를 구하는 문제이다. 풀이는 3단계로 이루어 진다. Step1) 트리를 그래프의 인접리스트 구조로 구현 각 노드의 자식노드를 List에 저장한다. 그래프의 인접리스트 방식으로 트리를 구현하는 것이다. Step2) DFS 탐색으로 노드 삭제 특정 노드를 삭제하면 자식노드와 자식의 자식노드도 삭제해야 한다. DFS탐색으로 자식의 자식까지 삭제하고 삭제 여부를 테이블 자료구조에 저장한..

5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net ◎ 문제풀이 전위순회 결과를 가지고 이진트리를 만든 후 후위순회를 하는 문제이다. 전위순회는 ROOT -> LEFT -> RIGHT 순으로 탐색한다. 그러므로 가장 위에 있는 값이 ROOT이고 다음 값은 LEFT이다. 그리고 그 다음 값은 LEFT의 LEFT이다. LEFT의 LEFT가 없다면 ROOT의 RIGHT이다. 이 구조는 객체참조구조를 이용하면 쉽게 구할 수 있다. ◎ 코드 package org.example.tree; import java...

https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net ◎ 문제풀이 트리에서 너비가 가장 넓은 레벨과 레벨의 너비를 구하는 문제이다. 위 그림에 힌트가 있다. 세로축은 레벨을 의미한다. 가로축을 보면 좌측부터 노드의 번호가 매겨진다. 8번 노드는 1, 4번 노드는 2, 2번 노드는 3, 14번 노드는 4이다. 가로축을 이용하면 너비를 쉽게 구할 수 있다. 레벨2의 2번노드의 가로축 숫자는 3이고 3번 노드의 가로축 숫자는 15이다. ..

1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net ◎ 문제풀이 순회를 하려면 '노드'를 '기억'해야 한다. '기억'을 담당하는 자료구조는 STACK이다. 나는 두 가지를 놓쳐서 이 문제를 어렵게 풀었다. 1) 파이썬의 딕셔너리 자료형을 몰랐다. tree = {} 딕셔너리 자료형은 Map처럼 key-value 구조로 이루어져 있다. 딕셔너리 자료형을 몰라서 인덱스로 접근하는 리스트 자료형을 사용하였다. 2) 재귀호출을 발상하지 못했다. 재귀호출은 함수의 호출을 이용한다. 함수는 STACK영역에 쌓이므로..