트리 자료구조에 대한 개념과 트리에서의 다이나믹 프로그래밍 기본기(+트리를 만들지 않고 트리를 탐색하는 방법)

1. 그래프와 트리 그래프(graph)란 정점들과 정점 둘을 잇는 간선들로 이루어진 집합 위는 9개의 정점(원)과 10개의 간선(실선)들로 이루어진 그래프이다. 각 원의 내부에 쓰여 있는 숫자는 편의상 정점에 매긴 번호를 의미한다. 간선(edge)은 항상 두 정점을 잇게 된다. 그래프의 간선에는 가중치가 있을 수 있다. 특별한 언급이 없다면 간선의 가중치는 1로 간주할 수 있다. 가중치가 존재한다면, 예를 들어 1-3 간선의 가중치가 3이라면 1번 정점에서 3번 정점으로 가기 위해선 길이 3인 간선을 지나야한다고 표현한다. 그래프의 간선에는 방향성이 있을 수 있다. 예를 들어 1번 정점과 3번 정점사이 놓인 1-3 간선의 경우 1 > 3 또는 3 > 1 방향성을 가지는 것이 가능하다. 방향성 간선을 갖고..