angxxu.log

4256번: 트리 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음 www.acmicpc.net 처음에 스택으로 풀려다가 내가 생각해낸 알고리즘에 비해 코드가 너무 복잡해지는 것 같아서 다 뒤엎고 재귀로 다시 풀었다. preorder에서 루트노드를 순서대로 알 수 있다. 따라서 preorder에서 차례로 가져온 루트노드를 기준으로 inorder를 루트노드 왼쪽은 left 서브트리, 루트노드 오른쪽은 right 서브트리로 나눌 수 있다. postorder 함수를 만들어 inorder에서 검사할 범위(start, end)와 preorder의 root..

2233번: 사과나무 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 2,000)이 주어진다. 둘째 줄에는 벌레가 만드는 2×N자리의 이진수가 주어진다. 셋째 줄에는 썩은 사과의 위치를 나타내는 두 정수 X, Y가 주어진다. 이는 2×N자리 www.acmicpc.net 문제 설명 트리에서 썩은 사과 정점 X, Y가 주어지고, 정점 하나를 제거해서 X, Y를 한번에 없애려면 어떤 정점을 제거해야 하는지에 대한 문제이다. 말은 어렵지만 사과나무는 뒤집힌 트리 모양이고, X, Y를 한 번에 제거할 수 있는 정점은 가장 가까운 공통조상이다. 가장 가까운 공통조상을 구하는 법은 아래 문제에서 풀이한 적이 있다. [BOJ][Java]Q3584 - 가장 가까운 공통 조상 트리 정보가 주어졌을 때, 두 정점 n1,n2의 가장..

트리 정보가 주어졌을 때, 두 정점 n1,n2의 가장 가까운 공통조상을 출력하는 문제였다. 트리 문제는 처음 풀어봐서 그래프처럼 구현해야하나 한참 생각하다가, 어차피 부모만 찾는 거라면 int배열 parent를 생성하여 각 정점의 부모만 저장해주면 될 것 같았다. 따라서 트리 정보를 입력받으며 다음과 같이 parent 배열에 부모 정보를 저장해준다. for(int i = 0; i