WannaBeDeveloper

5639번: 이진 검색 트리 www.acmicpc.net 이 문제는 이진 검색 트리를 전위 순회한 결과가 주어졌을 때 해당 트리의 후위 순회한 결과를 출력하는 문제이다. 이전의 트리의 순회 문제의 경우 중위 순회와 후위 순회가 주어져야 트리의 구조를 정확히 파악할 수 있었다. 반면에 이진 검색 트리의 경우 특별한 조건 하에 트리가 만들어지기 때문에 전위 순회한 결과만 주어졌을 때 트리의 구조를 온전히 파악할 수 있다. 이진 검색 트리란 기존의 이진 트리에서 검색을 편하게 하기 위해 특정 조건을 추가한 트리로, 각 노드에 대해 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작고, 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 커야 한다. 그렇다면 이러한 조건을 이용해 전위 순회를 이..

2263번: 트리의 순회 www.acmicpc.net 이 문제는 이진 트리의 중위 순회와 후위 순회가 주어졌을 때 해당 트리의 전위 순회를 출력하는 문제이다. 트리의 전위 순회를 출력하기 위해서는 해당 트리를 먼저 파악해야 한다. 그렇다면 중위 순회와 후위 순회만으로 어떻게 트리를 유추해낼 수 있을까? 우선 트리의 루트부터 차근차근 구해나가보자. 트리의 루트를 알 수 있는 가장 쉬운 방법은 바로 후위 순회의 맨 끝을 보는 것이다. 왜냐하면 후위 순회는 왼쪽 자식 -> 오른쪽 자식 -> 루트 순으로 순회하기 때문이다. 그 다음, 루트를 알게 되면 중위 순회로부터 해당 루트의 왼쪽 자식 트리와 오른쪽 자식 트리가 어떤 노드들을 가지고 있는지를 알 수 있다. 왜냐하면 중위 순회는 왼쪽 자식 -> 루트 -> 오..

1991번: 트리 순회 www.acmicpc.net 이 문제는 이진 트리를 입력받았을 때 해당 트리를 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 문제이다. 우선 이진 트리를 어떤 방식으로 구현해야 할지 고려해야 한다. 이진 트리의 각 노드에 반드시 필요한 요소로는 노드의 이름, 노드의 왼쪽 자식 노드, 그리고 노드의 오른쪽 자식 노드가 있다. 여기서는 트리 내 모든 노드들이 이름으로 서로 다른 알파벳을 가지기 때문에, 노드를 정의할 때 노드의 이름, 왼쪽 자식의 이름, 오른쪽 자식의 이름을 가지는 Node 클래스의 인스턴스로 정의한다. 그 다음에 주어진 데이터를 바탕으로 트리를 구성할 때..