[알고리즘 공부] 트리의 구현과 순회

트리

계층적 관계를 표현하는 자료구조. 특정한 조건을 지키도록 구성한 트리를 이용하면 배열이나 리스트를 사용하는 것보다 같은 작업도 더 빠르게 할 수 있다.

 

트리의 용어 중 꼭 알아야 하는 내용

리프(Leaf) 노드 : 자식이 하나도 없는, 즉 트리에서 가장 하단에 위치하는 노드들을 의미한다. BST에서 리프노드의 수는 전체 노드가 2^k개면 2^(k-1)이다.

트리의 깊이(Depth) : 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수를 깊이라 함. 트리의 높이(Height)는 가장 깊숙히 있는 노드의 깊이를 의미한다.

트리의 재귀적 속성 : 한 노드와 그의 자손들을 모으면 그들도 하나의 트리가 된다.(Subtree) 즉, 모든 트리는 루트와 루트 밑에 있는 subtree들의 집합이다.

 

트리의 순회 순서

root를 언제 방문 할 것인지가 다르다. 항상 left를 right보다 먼저 방문한다.

전위(Preorder) 순회 : root ->left -> right

중위(inorder) 순회 : left -> root -> right : 노드가 작은 값부터 정렬되있는 경우, 작은 숫자부터 차례로 출력 가능

후위(postorder) 순회 : left -> right -> root

 

# 21-3 트리 순회 순서 변경

전위, 중위 순회 값을 알 때 후위 순회 결과 값을 출력하는 문제. 전위 순회는 항상 root부터 찍고, 중위 순회는 root를 중심으로 left를 먼저 방문, right를 나중에 방문하니까 전위 순회에서 root의 값을 알아내면 중위 순회에서 root를 기준으로 왼쪽, 오른쪽으로 subtree를 알 수 있음. 나머지 subtree에 대해 root를 찾아내면서 가장 바닥에 도달했을 때 left와 right를 출력하고 찾아낸 root를 뒤에 출력하는 식으로 재귀호출을 통해 구현가능하다.

inorder에서 root를 구하기 위해 vector.find()함수를 쓸 때 O(n)의 시간복잡도가 있고, 함수가 호출될 때마다 전체의 부분을 slice할 때 slice한 vector를 생성하는 과정에서 O(n)의 시간 복잡도가 발생한다. 모든 노드(n개)에 대해서 printpostorder가 호출되어야 하므로 따라서 알고리즘의 시간복잡도는 O(n^2)이다.

구현을 좀 더 복잡하게 그냥 array로 한다면 slice 과정에서 부분을 저장하는 벡터를 생성하지 않고 그냥 left, right값을 전달해서 좀 더 빠르게 할 수 있을 것 같다. 그리고 중위순회가 정렬된 array라는 점을 이용해서 binary search를 이용할 수 있을 것 같긴 해서 O(n*logn)으로 좀 더 빠른 알고리즘을 만들 수 있을 것 같긴 하다.(물론 이 경우도 트리가 Balanced가 아닐 수 있으니 O(n^2)일 수 있다.) 그럼에도 N<=100이고 C<=100이라서 그냥 이렇게 해도 1초 컷이 가능할 것 같다.

물론 아직까진 구현능력이 좀 부족해서 그냥 책의 코드를 이해하는 수준이다. 막연히 이렇게 하면 되겠지?하는 그런 생각 와중에 이걸 어떻게 구현하지? 너무 느리지 않을까?라는 생각이 많은 것 같다. 특히 이 예제는 vector를 인자로 넘겨받는 과정이 익숙하지 않아서 좀 그랬다.(vector같이 큰 값을 call by value로 리턴하는 게 무섭다고 해야하나) 어쨋든 새롭게 배운 정보를 정리하면 다음과 같다.

1) const vector<int>& v 이런 식으로 vector를 인자로 넘겨줄 수 있다.

참조하는 경우 복사본을 만들지 않고 인수에 접근할 수 있고, const형으로 선언했으므로 함수 내부에서 참조되는 값을 변경할 수 없다. 참조의 장점에 대해서는 알고 있는 내용이긴 한데 포인터를 쓰는 것과 뭐가 다른지 스스로 잘 모르고 있었다는 알게 되서 &로 짜져 있는 코드를 쓸데없지만 포인터 인자로 받을 때로 코드를 수정해보았다.

결론적으로 포인터로 인자를 넘겨줘도 reference하는 기능 자체는 같긴 한데 vector를 포인터 변수로 선언하면 주소 값을 접근하는 거니까 접근할 때 (*v).find() (*v).begin()이런 식으로 해줘야 한다는 점이 불편하고 중간에 vector<int>를 출력하는 slice를 짤 때 vector<int>*의 변수를 동적할당해서 return해줘야 하는 등 훨씬 귀찮다는 점을 알게 되었다. 그냥 &를 쓰면 훨씬 편하게 할 수 있다! 내가 &를 거의 안써서 &가 들어간 코드만 보면 당황하게 되는 것 같지만 익숙해져야겠다.

** reference와 pointer variable의 차이점은 가리키는 대상을 바꿀 수 없냐 있냐의 차이다.

http://blog.daum.net/sbshope/6620810

2) const를 빼고 vector<int>&를 쓰면 slice결과 값을 가져 오면서 rvalue reference 문제가 생긴다. 

error: invalid initialization of non-const reference of type 'std::vector&' from an rvalue of type 'std::vector'라는 내용이다.

이에 대한 자세한 설명은 다음 링크들에 나와 있다.

https://m.blog.naver.com/PostView.nhn?blogId=nortul&logNo=197601619&proxyReferer=https%3A%2F%2Fwww.google.com%2F

C++0x 중 rvalue reference 에 대한 소개입니다[퍼옴]

https://skstormdummy.tistory.com/entry/%EC%9E%84%EC%8B%9C%EA%B0%9D%EC%B2%B4%EB%9E%80

임시객체란

요약하면, lvalue는 대입문에서 왼쪽, rvalue는 오른쪽에 있는 값으로 간단하게 생각해볼 수 있다. reference에 대한 rule 중 하나는상수나 임시객체(표현식이 끝나는 직후 바로 사라지는 객체)의 reference를 만들 수 없다는 것이다. 이들은 모두 rvalue라서 rvalue는 c++ reference를 할 수 없다. 단, const reference로 적어주면 rvalue도 reference가 가능하다. 

즉, slice함수에서 return한 vector는 slice함수를 벗어나면 바로 사라질 임시객체라서 rvalue로 취급되니까 이걸 reference할 수 없어서 에러나는 것이고 여기에 const를 붙이면 print_postorder함수가 끝날 때까지는 이 값이 살아 있을 수 있게 수명이 연장된다는 의미이다.

2) vector<int> 자체를 반환할 수도 있다. 그냥 이건 상식적으로 그럴 수 있는데 내가 막연히 저렇게 큰 array를 반환하는 것에 거부감을 가지고 있는 것 같다. ㅋㅋㅋ

3) 가끔 까먹는 것이지만 vector.end()는 마지막 원소를 가리키는 게 아니라 마지막 원소+1인 빈공간을 가리키는 것이다. 이거 때문에 slice쪼갤 때 좀 헷갈렸다. 

 

# 21-5 요새

성벽이 있을 때 요새 내에서 서로 왕래하는 데 성벽을 가장 많이 넘어야 하는 두 지점을 찾는 문제이다. 일단 보자마자 트리의 지름이라는 백준 문제가 생각났다. DFS를 두번쓰는 풀이말고 책에서 다루는 풀이 식으로 접근해보자면 다음과 같다.

트리에서 가장 긴 경로는 가장 긴 루트와 잎 사이 경로의 길이 혹은 가장 긴 잎-잎 경로의 길이로 생각할 수 있다. 중간 노드의 경우 항상 더 갈 수 있는 여지가 있어서 제외. 아마 루트와 잎 사이의 경로 길이는 모든 노드가 직선으로 연결된 케이스 때문에 계산한 것 같다.

아무튼 root부터 시작해서 자신과 연결된 모든 child에 대해 각 노드를 root로 하는 subtree의 height를 리턴하면서 그 중 가장 큰 값과 가장 작은 값 두개를 취한 후 그 두개를 연결해주면(+2)서 longest distance를 업데이트한다. 그러고 나서 재귀가 끝나면 맨 마지막에 root의 height가 반환되니까 이 값과 longest를 비교해주면 끝. 이렇게 되면 모든 node에 대해서 height을 구하는 거라서 O(n)의 시간복잡도를 가진다.

일단 그 전에 문제에서 바로 트리를 주는 게 아니라서 직접 트리 구조를 만들어주는 번거로움도 있다. 책에서 소개하는 방식은 root에 대해서 n개의 노드에 대해 isChild를 호출하고, 자신의 Child에 대해서 모두 다시 getTree를 하므로 총 O(n^2)만큼 isChild를 호출하는데 isChild 자체가 n개의 노드에 대해서 자기 자신의 직접적인 자식인 지 확인하므로 O(n)의 시간복잡도를 가진다. 따라서 tree를 만들 때 O(n^3)의 시간복잡도가 있는 것. 하지만 n이 100으로 작으므로 Tree를 만들 때 O(n^3)이 드는 알고리즘을 사용해도 문제가 안된다.

근데 사실 radius가 작은 것부터 정렬해서 자기 부모를 한 개씩 찾아가면 부모 성벽은 자신을 포함하는 성벽 중 가장 작은 성벽이 되니까 n개의 노드에 대해 n번씩 자기 부모인지 찾으면 Tree를 만들 때 O(n^2)의 시간복잡도로 만들 수 있긴 하다.

 

이 문제를 보면서 문제를 풀 때 뭐부터 해야하는 지 step by step으로 적어두면 좋을 것 같단 생각이 들었다. 트리에서 가장 긴 경로를 찾는 문제라는 건 빠르게 판단했는데, 요새 간의 포함 관계를 어떻게 트리 형태로 변환할 지 스스로 구체적으로 생각해보지 못해 아쉬웠다. 답안 스케치하는 과정을 연습해야겠다.

아! 가장 긴 경로를 찾는 문제구나! 가장 긴 경로를 찾기 위해서는 tree 내에서 가장 긴 잎-잎 거리 혹은 루트-잎 거리를 구하면 되겠군. 그러면 각각의 노드에 대해 자기 자신을 root로 하는 subtree들의 높이를 재귀적으로 구해서 그 높이들 중 가장 큰 값 2개를 구해서 얘를 자기자신과 연결하기 위해 2를 더해서 longest값을 업데이트 하면 되겠구나. 그러고 마지막에 root를 기준으로 하는 tree의 높이와 longest 값 중 더 큰 값을 반환하게 하면 되겠다. 그러면 이걸 트리로 변환해야하는데, 각 요새 간의 포함관계는 어떻게 구하지? 중심점 간의 거리가 radius 차이보다 작으면 포함된다고 할 수 있구나. 그러면 구하기 위해서 거리를 계산해야하니까 거리를 계산하는 함수를 만들고, Tree를 구성해야겠다. 이런 식의 flow가 있어야 했다.

이런 식으로 구현할 때 이것저것 신경쓸 게 많은데 그 과정을 모두 생략하고 책을 보기만 하는 건 확실히 의미가 없는 것 같다. 이렇게 스스로 생각하는 시간을 좀 가지고 공부를 해야겠다. 느리더라도 말이다.

 

@ 트리 공부하면서 느낀 점

1) 트리 관련 문제는 트리의 재귀적 성질을 어떻게 사용할 수 있는 지 생각해보는 게 중요한 것 같다. 순회 문제의 경우 전위, 중위 순회 간의 관계를 통해 divide-conquer같은 느낌으로 문제를 접근하고, 요새 문제는 subtree의 리프 노드 간 거리의 maximum 값을 이용해서 재귀적으로 값을 구하듯이 말이다.

2) 문제에서 바로 트리 형태로 input을 주지 않으니까 트리를 어떻게 간단하게 구현할 지도 생각해봐야 하는 사항인 것 같다. 경우에 따라 트리 구조를 굳이 생성하지 않아도 되는 경우도 있고, 문제에 따라 당연히 다르겠지만 일단은 vector를 이용하면 간단하게 자신의 child를 각 노드가 나타낼 수 있다. 세그먼트 트리의 경우에는 그냥 Array로 트리를 만들고 2*i+1, 2*i+2로 자기 자식 노드에 접근하듯이 각 노드에 대해서 left, right 나누고 이런식으로 트리 구조를 명시적으로 생성할 필요는 없을 듯.

  

Reference

종만북 21장