트리

문제 설명n개의 점으로 이루어진 트리가 있습니다. 이때, 트리 상에서 다음과 같은 것들을 정의합니다. 어떤 두 점 사이의 거리는, 두 점을 잇는 경로 상 간선의 개수로 정의합니다. 임의의 3개의 점 a, b, c에 대한 함수 f(a, b, c)의 값을 a와 b 사이의 거리, b와 c 사이의 거리, c와 a 사이의 거리, 3개 값의 중간값으로 정의합니다. 트리의 정점의 개수 n과 트리의 간선을 나타내는 2차원 정수 배열 edges가 매개변수로 주어집니다. 주어진 트리에서 임의의 3개의 점을 뽑아 만들 수 있는 모든 f값 중에서, 제일 큰 값을 구해 return 하도록 solution 함수를 완성해주세요.https://school.programmers.co.kr/learn/courses/30/lessons/..

문제 설명간선에 가중치와 방향성이 없는 임의의 루트 있는 트리가 주어졌을 때, 아래의 쿼리에 답해보도록 하자.정점 U를 루트로 하는 서브트리에 속한 정점의 수를 출력한다.만약 이 문제를 해결하는 데에 어려움이 있다면, 하단의 힌트에 첨부한 문서를 참고하자.https://www.acmicpc.net/problem/15681        제한 사항      풀이문제를 요약하면, 주어진 정보로 트리를 만들고 쿼리로 주어진 노드의 서브트리의 개수를 구하는 것이다. 해당 문제에서는 트리를 만들 때, DFS를 통해 만들어주면 쉽게 문제를 풀 수 있다.DFS를 통해 트리를 만들다 리프 노드에 도착하면 순회를 종료하고 부모로 올라간다. 예를 들어, 1번 노드는 리프 노드이기 때문에 해당 노드의 서브트리는 존재하지 않는..

문제 설명트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.https://www.acmicpc.net/problem/1167      제한 사항      풀이문제를 요약하면, 트리의 지름을 구하는 것이다.트리의 지름이란 트리에 있는 노드 간의 거리가 가장 먼 두 노드의 거리를 말한다.트리의 지름을 구하는 방법은 크게 두 가지이다.DFS를 이용하는 방법DP를 이용하는 방법DFS를 이용하는 방법은 간단하다.임의의 노드를 고른 뒤 DFS를 통해 가장 먼 노드를 찾아낸다.가장 먼 노드는 트리의 지름에 포함되는 노드이다.따라서, 그 노드에서 가장 먼 노드를 다시 구하면 그 거리가 트리의 지름이 된다. 이를 증명하는 것은 간단하다.트리의 지름..

문제 설명이진 트리는 매우 중요한 기본 자료 구조이다. 아래 그림은 루트 노드가 유일한 이진 트리이다. 모든 노드는 최대 2개의 자식 노드를 가질 수 있으며, 왼쪽 자식이 순서가 먼저이다. 노드 n개로 이루어진 이진 트리를 BT라고 하자. BT의 노드는 1부터 n까지 유일한 번호가 매겨져 있다.아래 그림에 나와있는 BT의 루트는 3번 노드이다. 1번 노드는 오른쪽 자식만 가지고 있고, 4와 7은 왼쪽 자식만 가지고 있다. 3과 6은 왼쪽과 오른쪽 자식을 모두 가지고 있다. 나머지 노드는 모두 자식이 없으며, 이러한 노드는 리프 노드라고 부른다.BT의 모든 노드를 순회하는 방법은 전위 순회(preorder), 중위 순회(inorder), 후위 순회(postorder)로 총 세 가지가 있다. 이 세 방법은 ..

문제 설명 민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, 조직을 운영하던 민호는 조직 내 누가 얼마만큼의 이득을 가져갔는지가 궁금해졌습니다. 예를 들어, 민호가 운영하고 있는 다단계 칫솔 판매 조직이 아래 그림과 같다고 합시다. 민호는 center이며, 파란색 네모는 여덟 명의 판매원을 표시한 것입니다. 각각은 자신을 조직에 참여시킨 추천인에 연결되어 피라미드 식의 구조를 이루고 있습니다. 조직의 이익 분배 규칙은 간단합니다. 모든 판매원은 칫솔의 판매에 의하여 발생하는 이익에서 10% 를 계산하여 자신을 조직에 참여시킨 추천인에게 배분하고 나머지는 자신이 가집니다. 모..

전위 순회는 루트-왼쪽-오른쪽 중위 순회는 왼쪽-루트-오른쪽 후위 순회는 왼쪽-오른쪽-루트 위와 같은 순서로 트리의 노드를 방문하여 출력하는 문제이다. 이진트리이기 때문에 왼쪽, 오른쪽의 노드만을 가지며 이를 구현하는 class를 만들어 활용하면 문제를 쉽게 풀 수 있다. 다음은 Java로 작성한 코드이다. import java.util.ArrayList; import java.util.Iterator; import java.util.Scanner; public class traversal { static class node{ String value; String left; String right; public node(String v, String l, String r) { value = v; left..

트리(Tree)란? 트리란 그래프의 일종으로, 비순환적인 그래프를 말한다. 즉, 사이클이 없는 그래프를 트리라고 한다. 사이클이 존재하지 않아 모습이 나무를 닮아 트리라는 이름이 붙여졌다. 노드가 n 개라면 간선 n-1개로 이루어진 그래프이다. 이 특징 또한 사이클이 없기 때문에 성립한다. 트리 기본 용어 리프(leaf) 이웃한 노드가 하나만 있는 노드를 말한다. 나무 중 제일 끝에 위치한 나뭇잎과 같이 제일 끝에 있는 노드를 의미한다. 루트(root) 제일 위에 위치한 노드라고 생각하면 된다. 나무의 시작인 뿌리와 같이 트리의 시작으로 설정한 노드이다. 부모(parent) 노드 어떠한 노드보다 위에 위치하며 루트 쪽에 가까이 위치한 노드를 의미한다. 자식(child) 노드 어떠한 노드보다 아래에 위치하..