1. 트리 트리는 계층 관계를 갖는 객체들을 표현하기 위해 만들어진 자료 구조이다. 계층 관계표현 이외도 다른 구조보다 같은 연산을 더 빠르게 할 수 있다. (특히 탐색형 자료 구조) 탐색형 트리 자료구조의 유명한 이진 검색 트리는 모든 숫자에 최대 두개의 하위 숫자만 있으며 어떤 숫자에서든 왼쪽 가지를 따라 내려가면 더 작은 수를 오른쪽 가지를 따라 내려가면 더 큰 수를 만날 수 있다. 이와 같은 특별한 규칙에 의해 탐색을 lgn만에 할 수 있게 된다. 트리의 구성 요소 노드 node: 연결된 노드 간에는 상하위 관계가 있다. 간선 edge: 연결하는 선 상위 노드 parent 하위 노드 child 부모가 같은 노드 sibling 부모 노드와 그의 부모 노드들 ancestor 자식 노드와 그의 자식 노..

1. 트리 생성 이 문제는 외벽안의 성벽들을 트리로 나타낸다음 각 잎에서 잎까지의 경로가 가장 긴 거리를 구하는 문제이다. 따라서 일단 주어진 성벽들의 정보를 가지고 트리를 구성해야한다. 이 트리를 생성하는데 약 n*n*n 이 걸릴 것 같다. 1. 서로 비교하여 노드의 벡터에 포함되어있는것을 넣는다 -> 두개를 비교하니 n*(n-1)/2 2. 각 비교할때마다 부모노드에서 자식노드벡터를 제거해야한다 -> n(점점 작아진다 생각보다 빨리 실행될 것이다) 3. 넣은것들 또한 트리로 정리해야하므로 남은 것들을 재귀호출해야한다. -> n 2번은 총 n(n-1)/2 번 실행될것이고 , 1번 또한 n(n-1)/2 번 실행될것이니 대략 n^2만에 트리를 정리하여 서브 트리만 남겨놓는다. 서브트리를 재귀로 정리해야한다...

1. 트리의 순회 이 문제는 트리의 preorder와 inorder가 주어졌을 때 이 정보를 가지고 postorder을 생성하는 문제이다. preorder는 각 서브트리의 루트를 먼저 출력한다. 따라서 preord[0]은 이 트리의 루트가된다. inorder는 서브트리의 왼쪽끝쪽을 조사한다음 서브트리의 루트를 출력한다음 오른쪽을 조사한다. 즉, 트리의 루트가 출력될때 이미 이 루트의 왼쪽 부분은 탐색을 마친 상태이다. 트리의 루트의 오른쪽은 오른쪽 서브 트리이다. 위의 각 순회의 특성을 이용하여 재귀적으로 함수를 구현하면 답을 쉽게 얻을 수 있다. 이 코드의 시간복잡도는 r 과 for문에 지배된다 for문은 각 단계에서 대략 n번 수행되고 r = n이므로 O(N^2)의 시간 복잡도를 가진다. 1 2 3 ..