SSONG Cloud

1. 정의 : 주어진 두 노드의 가장 가까운 공통 조상을 찾는 알고리즘 2. 예시 - 위와 같은 트리가 있을 때 1) 6번과 7번의 최소 공통 조상은 3 2) 5번과 5번의 최소 공통 조상은 1 3) 4번과 8번의 최소 공통 조상은 4 4) 2번과 3번의 최소 공통 조상은 1 3. LCA 알고리즘 접근 방식 - 각 노드의 depth를 구한다. - 위의 예시에서 1번 노드의 depth는 1이고 2, 3, 4번 노드는 5,6,7,8번 노드는 3이 된다. - 만약 두 노드의 depth가 서로 다르면 작은 것에 맞춰 바꿔준다. 1) 예를 들어 4번과 7번의 최소 공통 조상을 구한다고 한다면 ① depth 구하기 4번은 2, 7번은 3 ② 2로 depth를 맞춰주기 depth를 낮추기 위해서는 그 부모로 접근하면..

1. 위상정렬이란? : 유향 그래프의 꼭짓점을 방향을 거스르지 않도록 나열하는 것 : 위상 정렬을 이해하기 쉽게 표현하면 대학교의 선수과목이 있다. : B라는 과목을 듣기 위해 A라는 과목이 선행 학습 되어야 할 때 올바른 수강 순서를 찾아낼 수 있다. 2. 코드 : 첫째 줄에는 요소의 수와 선행 관계의 수가 주어진다. : 그 다음 선행관계들이 주어진다. : 이 때 해당 요소에 도달하기 위해 선행되어야 하는 요소들의 수를 indegree 배열에 누적에서 더한다. : indegree의 수가 0인 것부터 차례대로 순회할 수 있도록 한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; imp..