2263 트리의 순회, 5639 이진 검색 트리

두개의 문제는 전위,중위,후위순회을 활용해서 문제를 풀어봐야한다.

2263 트리의 순회

https://www.acmicpc.net/problem/2263

1.접근

생각하기 어려웠지만 직접 트리를 그려서 중위탐색과 후위 탐색을 해보면 전위 탐색을 어떤식으로 해야할지 보였다.

2.풀이

중위순회과 후위순회을 그려보면 규칙을 찾을 수 있다. 후위 탐색된 리스트에서 맨 마지막 값은 중위 순회의 루트노드일 것이다.따라서 중위 탐색에서 그 루트노드의 인덱스를 구해서 왼쪽 오른쪽 나눠서 재귀적인 문제로 만들어 풀면 된다.

여기서 후위순회에서 구한 루트값의 인덱스를 구할 때 일일이 탐색하게 되면 시간초과가 날게 분명하므로 

for i in range(n):
     num[in_order[i]-1]=i 루트값이 어디있는지 인덱스를 빠르게 구할 수 있도록 만들어 주는 이 스킬이 중요했다.

<<중위 순회

 

 

<<후위 순회

 

3.코드

4.배운점

• 숫자가 n까지 순서대로 나왔을 때 그 값이 어느 인덱스에 있는지 쉽게 구할 수 있는 코드를 익숙하게 쓰자
• 재귀함수에 범위를 잡아줄 때 많이 어려웠다.오른쪽은 plus를 해준 곳 기준으로 움직였어야 하는데 plus변수 사용이 어려웠다.

 

5639 이진 검색 트리

https://www.acmicpc.net/problem/5639

1.접근

위 문제와 비슷하게 트리를 전위 순회한 결과를 보면 어떻게 재귀적으로 나눠서 풀어야 할지 보였다

2.풀이

전위 순회가 주어지므로 첫 수는 당연히 전체 트리의 루트노드일 것이다.

그 루트노드 값보다 큰것은 오른쪽 작은것은 왼쪽으로 나눠진다는 생각을 가지고 재귀를 만들면 된다.

왼쪽 오른쪽 나눠서 들어가면 또 맨 앞에 있는 숫자가 서브트리의 루트노드일 것이다.

오른쪽과 왼쪽을 구분짓는 구간을 찾기위해서 일일히 해보기 보다는 공부했던 이진탐색을 활용해서 시간을 단축했다.

3.코드

4.배운점

• 재귀 함수나 DFS같은 함수를 만들 때 탈출조건을 더 신중히 생각해서 설정해야겠다.
• 입력이 몇개들어오는지 모를 때는 while에 try,except문을 합쳐서 구현하면 된다. 익숙하지 않아서 쓰지 않았는데 이참에 외워야 겠다.