LCA (최소공통조상) 알고리즘 완벽 가이드
LCA (Lowest Common Ancestor)
LCA(최소공통조상)는 트리에서 두 정점의 가장 가까운 공통 조상을 찾는 문제이다. 트리 관련 알고리즘에서 가장基础的인 개념 중 하나이다.
1. 브루트 포스 방식
가장 간단한 접근법은 직접 위로 올라가며 찾는 것이다. 먼저 각 정점의 깊이(depth)와 부모 정보(fa)를 전처리한다.
알고리즘:
두 정점 u, v 중 더 깊은 정점을 찾는다.
...
7월 17일 22:27에 게시됨
RMQ 문제 풀이: 슈퍼 피아노, 빈도 값, 인구 조사 문제
P2048 [NOI2010] 슈퍼 피아노
연속 부분 수열의 합을 전처리하고 RMQ를 사용하여 최대값을 찾습니다.
우선순위 큐를 사용하여 최적의 답을 저장합니다.
힙의 맨 위 요소를 꺼내서 계산한 후, 해당 지점을 제외하고 두 개의 새로운 구간을 다시 큐에 추가합니다. 이 과정을 k번 반복합니다.
#include <iostream>
#include <vector>
#include <queue>
#inc ...
7월 2일 00:21에 게시됨