lca22

• 

  [c++] 백준 - 도로 네트워크(lca) 1. 문제 2. 입 출력 3. 예제 4. 문제 해설 이 문제는 lca를 이용한 문제였다. 문제 자체에서 가장 root노드가 무엇인지 주진 않았지만 1번 노드를 root로 삼아 (왜냐하면 1번 노드는 항상 나오기 때문이다.) 트리를 구성하고 그 후 효율적인 lca풀이를 이용하면 충분히 구할 수 있는 문제이다. 이 문제는 또한 lca를 구성하는 과정에서 구간의 최댓값과 최솟 값을 저장하며 가야하는 문제이다. 따라서 dp문제의 성향이 강하다고 할 수 있겠다. 우선 효율적인 lca 풀이를 위해 tree를 구성해준다. 나는 bfs를 통해 트리를 만들어주었다. void makeTree() { depth[1] = 1; q.push({ 1 }); while (q.size()) { int curr = q.front();.. c++/알고리즘 2023. 3. 3.

• 

  [c++] 백준-LCA2 (Least Common Ancestor) 1. 문제 2. 입출력 및 예제 3. 문제 해설 백준 - lca와 문제는 같다. 그러나 달라진 점이 있다면 노드의 개수가 10000개로 늘었다. 그리고 알아내야하는 노드의 쌍의 수도 늘었다. 이 문제는 그러면 이전 lca문제처럼 bfs나 dfs로 tree의 depth를 알아낸다. depth가 더 큰 쪽을 parent배열을 이용해 작은쪽과 depth를 맞춘다. 한칸 씩 올리다가 만나는 것이 lca에 해당한다. 위의 알고리즘을 사용하면 시간초과가 나게 된다. 그래서 이 문제는 dp를 적용해 lca + dp를 사용해야한다.... 어떤 문제건 두 가지 알고리즘이 섞이면 어렵지만 이 두개는 어려운 것이 두 개가 섞여 더 어려웠다. 한 번에 풀지는 못하고 이 문제의 핵심 아이디어를 찾아 본 후 구현할 수 있었다. .. c++/알고리즘 2023. 2. 8.