알고리즘/Graph4 키 순-서 & 플로이드-워셜 알고리즘 키 순-서 백준 2456번 문제https://www.acmicpc.net/problem/2458 1. 문제 2. 문제 풀이2.1 아이디어자신의 키 순서를 알기 위한 조건은 그래프상 모든 학생들과 연결되어 있어야 한다는 것이다. 예를 들어 5번은 3번과 6번에 연결되어 있지 않다.이 때문에 3번과 6번이 자신과 비교해서 어디에 위치해 있는지 알 수 없기 때문에 순서를 매길 수 없다. [순서를 알 수 없는 경우] 따라서 어떤 학생이 정방향과 역방향을 포함해서 모든 학생들과 연결되어 있으면 그 학생의 키 순서를 알 수 있다. 노드가 연결되어 있다는 것은 노드 간에 경로가 존재한다는 것이다.때문에 모든 노드간 가능한 모든 경로를 탐색하는 플로이드-워셜 알고리즘을 사용해서 이 문제를 해결할 수 있다. .. 2024. 8. 2. LCA2 LCA2 백준 11438번 문제 https://www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 1. 문제 2. 풀이 2.1 풀이 방법 2.1.1 LCA 트리에서 공통의 조상을 찾는 것은 LCA 알고리즘을 통해 해결할 수 있다. LCA 알고리즘은 다음과 같은 과정으로 두 노드 간의 공통 조상을 찾는다. 1. 두 노드의 깊이가 다르면 같아질 때까지 한쪽 노드의 깊이를 올린다. 2. 두 노드가 같아질때까지 깊이를 한칸씩 올린다. 다음과 같은 트리가 주어졌.. 2023. 2. 20. Union-Find 알고리즘을 케이크처럼 쉽게 이해하는법 Union-Find Union-Find 알고리즘은 다수의 노드로 트리를 만들 때 사용된다. 각 노드들을 병합해서 트리로 만드는 것이 Union 노드가 병합될 수 있는지를 확인하는것이 Find라서 Union-Find이다. 1. 노드로 트리 만들기 1부터 5까지의 노드가 있다고 하고 이 노드들로 트리를 만든다고 해보자 [노드] 우선 1과 2를 병합(연결) 할 수 있다 [1, 2 병합] 다음으로는 3과 4, 5를 병합해본다 [3과 4, 5 병합] 여기에 1과 3을 병합할 수 도 있다. [1-3 병합] 각각 연결된 노드가 있는 1과 3을 병합해도 트리가 되는 데는 문제가 없다. 그러나 2와 4는 병합할 수 없다 [병합 불가 경우] 왜냐하면 노드 2와 4는 같은 트리 내에 있는 노드이기 때문이다. 따라서 이 두 .. 2023. 2. 7. 줄-세우기 줄-세우기 백준 2252번 문제 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 1. 문제 2. 풀이 2.1 풀이 방법 이 문제에서 학생들의 키를 비교한 관계를 그래프로 나타내면 DAG(Directed Acyclic Graph)가 된다. 따라서 학생들의 키를 위상 정렬을 사용해서 정렬할 수 있다. 2.1.2 Directed Acyclic Graph DAG는 말 그대로 사이클이 없는 방향 있는 그래프를 .. 2022. 8. 23. 이전 1 다음
