트리5 프로그래머스 2021 Dev-Matching 77486 - 다단계 칫솔 판매(트리 순회) https://programmers.co.kr/learn/courses/30/lessons/77486 코딩테스트 연습 - 다단계 칫솔 판매 민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, programmers.co.kr - 문제가 처음 나온 5달 전에는 못 풀었는데 지금은 너무 쉽게 풀었음 - 전체 트리를 정의하고, 노드 마다 번 돈을 읽어내려가면서 부모까지 순회하면서 fee를 더해준다. 여기서 민호까지 수수료를 전달해줘야 하므로 parent[0]은 -1로 해준 뒤 순회하는 함수의 basis로 사용해준다. - 이름을 미리 인덱스로 파싱해두는 해쉬를 하나 선언해서 열거형처럼.. 2021. 8. 13. 트리 구현과 순회 - 이론 및 문제 정리 https://www.acmicpc.net/step/23 트리 단계 루트가 1인 트리가 주어질 때, 각 노드의 부모를 구하는 문제 www.acmicpc.net 백준 트리문제에 종만북을 참고하여 정리함. - tree 일반 개념 트리: 계층적인 구조를 표현 - 노드node, 간선edge 으로 구성됨 depth: root~특정 노드까지의 간선 수 , height: root~leaf노드까지의 간선 수(트리의 높이) 트리의 기본적인 성질: 노드가 N개인 트리는 항상 N-1개의 간선를 가진다 트리에서 루트에서 어떤 노드로 가는 경로는 유일하다. 또한 임의의 두 노드 간의 경로도 유일하다. 트리의 재귀적 속성에서 중요한 포인트: 모든 트리는 루트와 루트 밑에 있는 서브트리의 집합이다. struct Node { str.. 2021. 8. 7. 백준 2263 - 트리의 순회(트리 기초 순회이론, 완전탐색) https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net - 어떤 트리를 순회한다 할 때 inorder와 postorder가 주어졌을때 preorder를 구하는 문제이다 - 종만북에서 트리 기초파트를 설명할 때 나오는 TRAVERSAL 문제와 많이 흡사해서 참고하여 풀었다. - inorder와 postorder가 주어졌을 때 postorder의 마지막 노드가 트리의 루트인 점에서 부터 탐색을 시작한다. 그리고 inorder를 기준으로 생각해보면 루트가 나오기 전까지는 왼쪽 부분트리이고 .. 2021. 8. 7. BOJ 1967 - 트리의 지름(tree 구현, 순회, dfs) https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net - 간선의 가중치가 있는 트리에서 서로 가장 먼 노드의 거리를 구하는 문제이다. 최장 경로의 양 끝 노드가 항상 root 이거나 leaf node여야 한다. 따라서 2가지 케이스를 따져야한다. 1. 가장 긴 root-leaf 경로의 길이(즉 트리의 height) 2. 가장 긴 leaf-leaf 경로의 길이 풀이 : dfs 방식 이진트리이기 때문에 노드를 pair로 선언해서 to.. 2021. 8. 7. 이전 1 2 다음
