목록2024/09/17 (2)
미소를뿌리는감자의 코딩
1. 개요잊어버리기 쉬운 알고리즘인 Kruskal's Algorithm과 Prim's Algorithm에 대해서 공부해 보는 시간을 가졌다.두 알고리즘은 Minimum Spanning Tree를 해결하기 위한 대표적인 두 알고리즘이다. Kruskal's Algorithm은 edge가 제일 작은 값들 순으로 접근하여, 해당 edge를 잇는 정점 u, v의 parent node가 동일하지 않다면 합쳐주는 방법이다. - parent node가 동일한데, 해당 edge를 포함시키게 되면 cycle을 형성하게 될 것이기 때문이다. Prim's Algorithm은 edge가 아닌, node를 기준으로 접근하는 방법이다.일단, 특정 node를 선택하고, 해당 노드가 접근할 수 있는 노드까지의 weight 중 가장 ..
1. 문제https://www.acmicpc.net/problem/5639 2. 접근 방법pre order 결과를 가지고, post order의 결과를 도출해야 하는 문제였다. pre order이기에, 순으로 출력될 것이었다.따라서, 처음 주어진 노드의 키는 전체 binary tree의 root node를 나타낼 것이다.따라서, 이를 기준으로 다음으로 주어진 노드를 왼쪽에 배치할 것인지, 오른쪽에 배치할 것인지 결정해 주었다. def get_nodes(): root_num = int(input()) root_node = Node(root_num) while True: try: new_node = Node(int(input())) c..