백준 검색 결과
248 개의 검색 결과가 있습니다.
코딩/백준 (Python)

백준 5639번: 이진 검색 트리 (Python)

접근 트리 순회 문제 중, 인오더와 포스트오더가 주어졌을 때 프리오더를 구하는 문제가 있었는데 그 문제와 유사하게 생각하면 좋다. 이번에는 프리오더만 주어지지만 추가적으로 '이진 검색 트리'라는 트리의 속성을 이용하여 문제를 해결할 수 있다. 유사 문제: 2021.04.29 - [코딩/백준 (Python)] - 백준 2263번: 트리의 순회 (Python) 백준 2263번: 트리의 순회 (Python) 접근 재귀를 이용하여 문제를 풀 수 있다. 포스트오더의 마지막 숫자는 전체 트리의 루트이다. 인오더의 특성을 이용, 루트를 기준으로 왼쪽트리, 오른쪽트리의 노드 수를 구할 수 있다. 왼쪽 트 ca.ramel.be 주어진 이진 검색 트리의 프리오더를 보면 다음과 같이 생각할 수 있다. 주어진 프리오더의 루트..

2021. 4. 29. 21:50
코딩/백준 (Python)

백준 2263번: 트리의 순회 (Python)

접근 재귀를 이용하여 문제를 풀 수 있다. 포스트오더의 마지막 숫자는 전체 트리의 루트이다. 인오더의 특성을 이용, 루트를 기준으로 왼쪽트리, 오른쪽트리의 노드 수를 구할 수 있다. 왼쪽 트리의 노드수, 오른쪽 트리의 노드수를 이용하여 인오더를 왼쪽 인오더, 루트, 오른쪽 인오더로 나눌 수 있다. 동일하게 포스트오더를 왼쪽 포스트오더, 오른쪽 포스트오더, 루트로 나눌 수 있다. 왼쪽 포스트오더의 마지막 숫자는 왼쪽 트리의 루트이다... 재귀 반복 위의 연산을 반복해주면서 나오는 루트를 순서대로 저장해주면 프리오더를 얻을 수 있다. 그림으로 보면 조금 더 이해하기 쉽다. 그림으로 그리기 시작할 땐 그림이 훨씬 이해하기 쉬울것 같았는데, 막상 그리고나니 그림을 못그려서 그런지 이해하기 어려운 것 같다. 핵심..

2021. 4. 29. 00:32
코딩/백준 (Python)

백준 1991번: 트리 순회 (Python)

접근 트리를 표현하기 위해 Node 라는 클래스를 정의하고 이를 tree에 저장해주었다. 순회 순서에 맞게 출력하는 함수를 작성해주면 된다. 코드 class Node: def __init__(self, item, left, right): self.item = item self.left = left self.right = right def preorder(node): print(node.item, end='') if node.left != '.': preorder(tree[node.left]) if node.right != '.': preorder(tree[node.right]) def inorder(node): if node.left != '.': inorder(tree[node.left]) print(..

2021. 4. 28. 23:17
코딩/백준 (Python)

백준 1167번: 트리의 지름 (Python)

접근 처음에 아무리 생각해도 내 머리 속에서 떠올릴 수 있는 방법은 플로이드 와샬 알고리즘 하나였다. 그렇게 푸는 것이 아니란 것을 알면서도 코딩했더니 결과는 역시나 메모리초과였다. 방법을 고민하다가 알 방법이 없어 검색해보니 굉장히 놀라운 사실을 알 수 있었다. 임의의 노드에서 각 노드까지의 거리를 측정하여 최대 거리를 가지는 노드는 트리의 지름을 이루는 한 노드이다. 즉, 임의의 한 점에서 DFS나 BFS 알고리즘을 이용하여 각 노드까지의 거리를 구하고, 이 중 최대 거리를 갖는 노드에서 시작하여 다시 한번 각 노드까지의 최대 거리를 구한다면 그 최대 거리가 트리의 지름이 된다. 그 증명은 다음의 링크에서 확인할 수 있다. 트리의 지름 증명: 트리의 지름 구하기 트리의 지름 구하기 트리에서 지름이란,..

2021. 4. 28. 22:48
코딩/백준 (Python)

백준 11725번: 트리의 부모 찾기

접근 서로 연결된 노드들을 tree 리스트에 저장해주고, BFS 알고리즘을 이용하여 연결된 노드들을 차례로 탐색해준다. 1을 루트로 시작하므로 1과 연결된 노드들은 1을 부모노드로 가진다. 이를 parent 리스트를 이용하여 저장해준다. 그리고 그 노드들을 queue에 추가해준다. 계속 탐색하면서 중복을 피하기 위해 연결된 노드들 중 부모노드를 가지지 않은 노드들만 차례로 탐색하면 문제를 해결할 수 있다. 코드 import sys n = int(sys.stdin.readline()) tree = [[] for _ in range(n + 1)] for _ in range(n - 1): a, b = map(int, sys.stdin.readline().split()) tree[a].append(b) tree..

2021. 4. 28. 21:56
코딩/백준 (Python)

백준 11780번: 플로이드 2 (Python)

접근 기존에 풀었던 플로이드 기본문제와 같이 플로이드 와샬 알고리즘을 이용하여 풀 수 있다. 다만 새로운 리스트를 작성하여 직전 도시를 저장해주면 된다. 플로이드 와샬 알고리즘 설명 및 기본 문제: 2021.04.21 - [코딩/백준 (Python)] - 백준 11404번: 플로이드 (Python) 백준 11404번: 플로이드 (Python) 접근 문제 풀이에 앞서 플로이드 와샬 알고리즘이 무엇인지 공부해보았다. 이전에 풀었던 다익스트라 알고리즘이 하나의 점에서 출발했을 때 모든 정점까지의 최단 경로를 구했다면, 플로이드 ca.ramel.be 기존 문제에서 어떤 코드가 추가되었는지 코드를 보면서 설명하도록 하겠다. 코드 import sys INF = float('inf') n = int(sys.stdin..

2021. 4. 28. 21:23
반응형