0과 1의 쉼터

문제https://www.codetree.ai/trails/complete/curated-cards/intro-parent-node-of-the-tree/introductionCode Tree | Learning to Code with Confidence풀이각 노드의 부모 노드를 구하는 문제다.주어진 트리 정보에 대해 dfs를 하며 각 부모 노드를 구하면 된다. private static void dfs(int node) { for (int child : tree.get(node)) { if (parent[child] == -1) { parent[child] = node; dfs(child); ..

문제https://www.acmicpc.net/problem/11438풀이기존에 선형 탐색으로 O(N)만에 LCA를 구하는 방법으로는 이 문제를 해결할 수 없다.2025.01.15 - [PS/Baekjoon Online Judge] - [백준 11437] LCA [Java] [백준 11437] LCA [Java]문제https://www.acmicpc.net/problem/11437풀이DFS를 통해 모든 노드의 부모 노드와, 깊이를 구한 후 LCA를 구하는 기본 문제입니다.이를 위해서 양방향 그래프를 구성해야 합니다.문제에서 트리의 루트는 1kyr-db.tistory.com각 쿼리에 대해 O(logN)안에 LCA를 찾을 수 있는 방법에 대해 알아보자.깊이가 다른 두 노드의 깊이를 맞추고 LCA를 탐색하는 ..

문제https://www.acmicpc.net/problem/3584풀이문제에서 주어지는 간선이 부모-자식 관계를 나타내고 있기 때문에 별도의 알고리즘 없이 dfs으로 선형탐색하면 된다. 우선 정점 u에 대해 루트 노드까지 탐색하며 방문 표시를 해주자.정점 v에 대해 루트 노드까지 방문하지 않은 노드까지 탐색하면 된다.소스코드보기

문제https://www.acmicpc.net/problem/2533풀이우선, 주어지는 루트가 없으며, 어디서 탐색해도 상관없다.그래프를 구성 후 dfs를 진행하자. 얼리 어답터의 수가 최소가 되도록 만드는 방법에 대해 알아보자.맨 처음 리프노드는 자기 자신이 얼리 어답터라고 가정해야 한다.하지만, 부모 노드가 존재한다면 리프 노드는 얼리 어답터가 아닌 상태가 정답이다.여기서 dp는 두 상태(EARAY, GENERAL)에 대해 고려해야 한다.dp[i][j] : 상태가 i일때 j ~ N에 필요한 최소 얼리 어답터의 수dfs를 통해 방문을 진행하면 방문 표시와 함께 현재 정점이 얼리 어답터인 경우를 세주자.리프 노드까지 도달 후 리프 노드들이 얼리 어답터라고 표시된 후 부모 노드로 돌아와서 부모 노드의 두 ..

문제https://www.acmicpc.net/problem/3584풀이주어지는 트리에 대해 두 정점의 공통 조상을 찾는 문제다.이미 부모-자식에 대한 정보가 주어지므로, 입력과 동시에 parent를 바로 구성할 수 있다. 공통 조상을 구해야하는 두 정점 중 한 정점으로부터 루트노드까지 방문해주고,다른 정점도 동일하게 방문하지 않은 부모 노드를 따라 방문하면 된다.이미 방문한 적 있는 부모노드는 공통 조상 노드이므로 탐색을 중단하고 반환해주면 된다.소스코드보기