백준 2236
-
[백준 2263] - [분할정복] - 트리의 순회(java)알고리즘/분할정복(Divide and conquer) 2018. 11. 29. 15:38
문제 링크 : https://www.acmicpc.net/problem/2263 이 문제는 좀 변태적인 문제라 확신한다. 중위 순회(In-order) 가 주어지고 후위 순회(Post-order)가 주어졌을때 전위순회(Pre-order)를 구하라는 문제이다. 예제 입 출력은 아래와 같다. 입력3 1 2 3 1 3 2출력2 1 3 하지만 예제 입출력에는 노드가 3개여서 예제 입출력을 기준으로 풀면 구하기 힘들다.그래서 예제로 트리하나를 만들었고 전위, 중위, 후위 순회의 값을 먼저 구한뒤 이 값이 나오도록 유도해봤다. 위의 트리를 만들어 보았고 각각 전위, 중위, 후위 순회를 구해봤다. 전위 순회 : 1 -> 2 -> 4 -> 7 -> 8 -> 5 -> 3 -> 6 -> 9 중위 순회 : 7 -> 4 -> ..