여행자의 책

나이브한 방식의 최소 공통 조상 찾기 def solution(N, tree, v1, v2): level = [0 for i in range(N+1)] parent = [0 for i in range(N+1)] visited = [0 for i in range(N+1)] def dfs(here, depth): visited[here] = True level[here] = depth for there in tree[here]: if not visited[there]: parent[there] = here dfs(there, depth+1) root = 1 #root 1로 가정 dfs(root, 1) def LCA(v1, v2): """ v1, v2의 공통조상을 찾아주는 알고리즘 """ #같은 레벨로 만들어 ..

import sys """ 내가 두명의 부하 직원에게 연락하라고 시키면 결과적으로 총 걸리는 시간은 둘 중에 가장 큰 값 """ def solution(): input = sys.stdin.readline #입력받는 부분 N = int(input()) bose_info = list(map(int, input().split())) #트리로 만들어 준다. tree = [[] for _ in range(N)] for me, bose in enumerate(bose_info): if bose != -1: tree[bose].append(me) #dp[i] : i번째 노드를 루트로 하는 서브트리에 뉴스를 전달하는데 필요한 최대 시간 dp = [0 for i in range(N)] def dfs(here): tem..

import sys sys.setrecursionlimit(1000000) def solution(): input = sys.stdin.readline N = int(input()) #wolves[i] : i번째 섬에 있는 늑대 수 wolves =[0 for _ in range(N+1)] #sheeps[i] : i번쨰 섬에 있는 양의 수= sheeps = {i:0 for i in range(1, N+1)} #트리 tree =[[] for _ in range(N+1)] for i in range(2, N+1): t, a, p = input().split() a = int(a) p = int(p) if t == "W": wolves[i] = a else: sheeps[i] = a tree[p].append(..

https://programmers.co.kr/learn/courses/30/lessons/68937?language=python3 코딩테스트 연습 - 트리 트리오 중간값 5 [[1,5],[2,5],[3,5],[4,5]] 2 programmers.co.kr 1. 문제 설명 n개의 점으로 이루어진 트리가 있습니다. 이때, 트리 상에서 다음과 같은 것들을 정의합니다. 어떤 두 점 사이의 거리는, 두 점을 잇는 경로 상 간선의 개수로 정의합니다. 임의의 3개의 점 a, b, c에 대한 함수 f(a, b, c)의 값을 a와 b 사이의 거리, b와 c 사이의 거리, c와 a 사이의 거리, 3개 값의 중간값으로 정의합니다. 트리의 정점의 개수 n과 트리의 간선을 나타내는 2차원 정수 배열 edges가 매개변수로 주..