크래프톤정글 3주차; TIL 2 - 파이썬 BST, 최소 신장 트리

2022-11-12

백준 5639번 파이썬 이진 검색 트리

출처: https://velog.io/@yujng/백준-5639번이진-검색-트리-파이썬Python

무엇?

이진 검색 트리의 전위 순회 한 값을 후위 순회로 출력하는 문제.

왜?

입력부터 어떻게 받아야 할 지 난감했던 문제… (지금까지의 문제는 몇 번 입력 받겠다는 조건이 있었는데…😮)
비슷한 로직으로 for + append를 열심히 해보다가 이렇게 복잡하게 안 해도 될거 같은데… 싶어서 솔루션 참고.
재귀의 신기한 점은 이렇게만 해가지고 이게 된다고? 싶은데 진짜 된다는 점. (오히려 거기서 더 복잡하게 들어가서 내가 뭔갈 해보려고 하면 에러 나는 거 같다.)

어떻게?

코치님이 이진 검색 트리를 재귀로 해결할 수 있다고 했는데, 이게 그 케이스 중 하나인 듯.

전위 순회와 후위 순회의 차이점은,

• 전위 순회는 루트 → 왼쪽 자식 → 오른쪽 자식 순으로 출력하고
• 후위 순회는 트리를 왼쪽 자식 → 오른쪽 자식 → 루트 순으로 출력

이때, 이진 검색 트리에서는 이 세 노드가 가진 값이 왼쪽 자식＜ 루트 ＜ 오른쪽 자식 순이다.
전위 순회의 출력 값에서 검색을 할 때, 루트보다 커지는 숫자가 나오면 그 놈이 루트의 오른쪽 자식이다.
첫 번째 반복을 통해 오른쪽 자식을 탐색하면 그것은 레벨 1의 루트의 오른쪽 서브트리를 의미한다.
그리고 이것을 더 작은 트리로 들어가면서 반복.

그런데 후위 순회는 왼쪽 서브 트리부터 출력해야 하므로

1. 왼쪽 노드를 확인(postorder(start+1, mid-1))
2. 오른쪽 노드를 확인(postorder(mid+1, end))
3. 마지막으로 루트 노드를 출력한다.
   • nodes[start], 전위 순회는 루트를 제일 먼저 출력하므로 start 인덱스에 위치한 것이 루트인게 이상하지 않다!

Minimum Spanning Tree Problem - Prim’s Algorithm

출처:https://www.edwith.org/datastructure-2019s2/lecture/40353?isDesc=false
https://www.edwith.org/knu-algorithm/lecture/170196

무엇?

최소 신장 트리 문제를 해결하는 알고리즘 중 하나인 프림 알고리즘
알고리즘 노트에 추가!

왜?

어떻게?