solved.ac Class 4레벨에 속한 문제이다. 문제 주소: https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 문제 해석 문제 풀이 먼저 주어진 입력을 잘 받도록 코드를 구현해야 한다. 임의의 두 점 사이의 거리 중 가장 긴 것을 구하기 위해서는 일반적으로 모든 노드를 dfs 탐색해야 한다. 하지만 이 경우 주어진 노드의 수가 10,000개 이므로 n^2의 시간복잡도에서 통과할 수 없다. 이러한 트리의 지름을 구하는 문제는 ..
배solved.ac Class 4레벨에 속한 문제이다. 문제 주소: https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 해석 루트가 1인 트리의 연결 상태가 주어진다. 루트를 제외한 이 트리의 각 노드의 부모를 구하는 문제이다. 문제 풀이 root인 1을 시작으로 bfs 탐색을 통해 부모 노드를 구해주었다. 문제 코드 import sys from collections import deque input = sys.stdin.readline def solve(n, adj): # bfs를 통해 root부터 탐색..
solved.ac Class 4레벨에 속한 문제이다. 문제 주소: https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 문제 해석 이진 트리를 구현해서 전위, 중위, 후위 순회의 결과를 출력하는 문제이다. 문제 풀이 친절하게 문제에서 전위, 중위, 후위 순회의 결과와 알고리즘을 설명해 주었다. class Node: def __init__(self, name): self.name = name self.left = None self.right..
프로그래머스에 존재하는 연습 문제이다. 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/150367 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해석 이진트리가 주어진다. 이를 이진 포화트리로 바꾸었을 때 더미노드는 0, 존재하는 노드는 1로 가정하여 왼쪽부터 읽어 2진수로 변경할 수 있다. 이때 문제에서 숫자가 주어졌을 때 해당 숫자를 이진트리로 표현할 수 있는지 판단하는 문제이다. 문제 풀이 1. 자릿수 변경 먼저 이 문제를 해결하기 위해서 주어진 수를 이진수로 변경한 뒤, 이진..
https://www.acmicpc.net/problem/1967\ 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 문제 & 테스트 케이스 문제 해석 노드에서 노드까지 가장 먼 거리를 찾는 문제. 코드 1. 제출 from collections import deque n = int(input()) adj = [[] for _ in range(n + 1)] for _ in range(n - 1): a, b, c = map(int, input().split()) adj[a].append((b, ..
