트리
[프로그래머스](Lv.3)길 찾기 게임[2019 KAKAO BLIND RECRUITMENT][파이썬/트리/전위순회/후위순회/Preorder/Postorder/Tree]
https://school.programmers.co.kr/learn/courses/30/lessons/42892 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 길 찾기 게임 전무로 승진한 라이언은 기분이 너무 좋아 프렌즈를 이끌고 특별 휴가를 가기로 했다. 내친김에 여행 계획까지 구상하던 라이언은 재미있는 게임을 생각해냈고 역시 전무로 승진할만한 인재라고 스스로에게 감탄했다. 라이언이 구상한(그리고 아마도 라이언만 즐거울만한) 게임은, 카카오 프렌즈를 두 팀으로 나누고, 각 팀이 같은 곳을 다른 순서로 방문하도록 해서 먼저 순회를 마친 팀이 ..
[백준/BOJ]#2078:무한이진트리[트리/수학/파이썬/python]
https://www.acmicpc.net/problem/2078 2078번: 무한이진트리 첫째 줄에 두 정수 A, B(1 ≤ A, B ≤ 2,000,000,000)가 주어진다. 잘못된 입력은 주어지지 않는다고 가정한다. www.acmicpc.net 트리 문제라고 명시되어있지만 사실상 수학 문제다!! #2078_무한이진트리 a,b=map(int,input().split()) l=0 r=0 while a>1 and b>1: if a>b: l+=a//b a%=b else: r+=b//a b%=a l+=a-1 r+=b-1 print(l,r)
[백준/BOJ]#15805:트리 나라 관광 가이드[트리/파이썬/python]
https://www.acmicpc.net/problem/15805 15805번: 트리 나라 관광 가이드 윤호는 K개의 도시들이 트리 형태로 연결되어 있는 트리 나라의 관광 가이드이다. 윤호가 새롭게 맡게 된 패키지는 트리 나라의 루트 도시에서 시작해서 모든 도시를 순회하고 오는 상품이다. www.acmicpc.net 파이썬 코드 #15805_트리나라관광가이드 from collections import Counter n=int(input()) city=list(map(int,input().split())) cntcity=Counter(city) visited=[0 for _ in range(len(cntcity.keys()))] parent=[0 for _ in range(len(cntcity.keys(..
[LeetCode] #106. Construct Binary Tree from Inorder and Postorder Traversal [트리/해쉬/분할정복/파이썬/python]
https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/ Construct Binary Tree from Inorder and Postorder Traversal - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 전위순회(inorder traversal)와 후위순회(postorder traversal)에 대한 개념을 아는지, 그것을 활용하여 재귀를 통해 bin..
[백준/BOJ] #1967: 트리의 지름 [트리/BFS/python/파이썬]
https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net #1967_트리의 지름 from collections import deque n = int(input()) tree = [[] for _ in range(n+1)] for _ in range(1,n): parent, child, weight = map(int, input().split()) tree[parent].append([weight, child]) tree[child]...
[백준/알고리즘] #5639: 이진검색트리 [파이썬(python)/트리]
https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net #5639_이진검색트리 import sys sys.setrecursionlimit(1000000000) input = sys.stdin.readline def postorder(left,right): if left > right: return else: root=preorder[left] div = right+1 for i in range(left+1,right+1): if root
[백준/알고리즘] #1991: 트리순회 [파이썬(python)/트리]
https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net #1991_트리순회 import sys input = sys.stdin.readline N = int(input()) def preorder(root): if root != '.': print(root, end='') preorder(tree[root][0])#left preorder(tree[root][1])#right def inorder(root): #중위 if root!='.':..
[백준/알고리즘] #9934: 완전 이진 트리 [파이썬(python)/트리]
https://www.acmicpc.net/problem/9934 9934번: 완전 이진 트리 상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 www.acmicpc.net #9934_완전이진트리 import sys input = sys.stdin.readline K=int(input()) tree = list(map(int,input().split())) bin_tree = [[] for _ in range(K)] def binary_search(tree,depth): if len(tree)==1:#last layer bin_tree[dep..
[백준/BOJ/알고리즘/파이썬(python)]#11725_트리의 부모 찾기[트리/그래프]
https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 루트 1부터 시작해서 dfs로 탐색하는 알고리즘으로 풀었다. 방문유무 정보 저장하는 배열을 하나 만들고 방문하지 않았다면 부모노드를 업뎃하면서 dfs탐색하면 된다. 재귀로 한 번 풀고 큐로 한 번 풀었다. 파이썬 코드_재귀 풀이(recursion) #11725_recursion import sys input = sys.stdin.readline sys.setrecursionlimit(10**9) N = int(input()) tree = [[] for _ in..