About Dev

https://www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 알고리즘 : BFS or DFS 풀이 날짜 : 2023.07.14. 백준 11437번과 동일한 문제이다. https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고,..

https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 알고리즘 : DFS 풀이 날짜 : 2023.07.10. 두 노드에 대해 root 노드 방향으로 탐색을 하고자 했다. 두 노드의 level 차이를 알아야 한다. 그럼 모든 노드의 level과 부모의 정보를 저장해야 한다. 만약에 두 노드의 모든 조상에 대하여 각각 비교하고자 한다면 최악의 경우에 N / 2 = 5000 * 5000..

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 알고리즘 : DFS or BFS 풀이 날짜 : 2023.07.10. 트리의 특징을 잘 생각해보자. Root 노드부터 탐색을 시작한다면, 먼저 탐색되는 애들은 무조건 레벨이 높을 것이다. 한 route를 쭉 따라가던지(DFS), 레벨 순서대로 탐색을 하던지(BFS), 해당 노드에 대한 부모 노드는 이미 방문 처리 되었을 것이고, 자식 노드들만 남을 것이다. 트리의 특징과 그에 따른 전제 조건을 잘 생각하면 된다. 처음에는 어떤..

https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 알고리즘 : DFS, DP, 우선순위 큐, 위상 정렬 풀이 날짜 : 2023.06.09., 2023.12.03. 리뷰 풀이 설명 처음에 현재 건물 `바로 전 단계` 건물들의 건설 시간 중, 최댓값만 더해주었다. 하지만 다음과 같은 상황일 때 문제가 생겼다. 1, 2, 3번 건물이 4번 건물의 바로 전 단계이다. 1은 총 10초, 2는 총 17초, 3은 총 14초가 걸리므로, 4를 짓기 위해서..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 알고리즘 : classic DFS, BFS 풀이 날짜 : 과거, 2023.06.05., 2023.11.17. 리뷰 그래프 완전 탐색론인 DFS와 BFS의 전형적인 구현 문제이다. 둘의 비교는 다음 글에서 해보았다. [백준] - DFS + DP vs BFS vs Dijkstra 더보기 import java.io.BufferedReader; impor..