최소 공통 조상(LCA) 계산기
트리의 간선을 넣으면 두 정점의 최소 공통 조상과 그 사이 거리·경로를 찾습니다. 한 칸씩 올라가는 방법과 희소 배열(binary lifting)의 뜀 횟수를 나란히 보여 줍니다.
한 줄에 하나씩 「부모 - 자식」으로 적습니다. 정점 40개까지, 간선은 정점 수보다 하나 적어야 합니다.
G와 F의 최소 공통 조상
A
두 정점 사이 거리는 5입니다. 3 + 2 − 2×0 = 5 — 뿌리에서 각각까지의 길이 LCA 위쪽을 두 번 겹쳐 세므로 그만큼을 뺍니다.
경로
G → E → B → A → C → F
정점 6개를 지나므로 간선은 5개입니다. 파랗게 칠한 자리가 LCA로, 두 정점 사이 경로는 반드시 여기를 지납니다.
희소 배열로 푸는 과정
깊이 차 1칸을 이진 표기로 쪼개 1칸 올립니다
1칸 위가 서로 다르므로 아직 LCA 아래입니다 — 둘 다 올립니다
더 올릴 수 없으면 둘은 LCA 바로 아래 — 부모가 답입니다
같은 답을 한 칸씩 올라가 구했다면 3번이 걸렸을 자리입니다. 어떤 자연수든 2의 거듭제곱의 합으로 딱 한 가지 방법으로 쓸 수 있어서 — 그것이 이진수 표기입니다 — 뛰는 횟수가 비트 수를 넘지 않습니다.
희소 배열 up[k] — 2^k칸 위 조상
| 정점 | 깊이 | up[0]1칸 | up[1]2칸 | up[2]4칸 | up[3]8칸 |
|---|---|---|---|---|---|
| A뿌리 | 0 | — | — | — | — |
| B | 1 | A | — | — | — |
| C | 1 | A | — | — | — |
| D | 2 | B | A | — | — |
| E | 2 | B | A | — | — |
| F | 2 | C | A | — | — |
| G | 3 | E | B | — | — |
up[0]은 부모이고, up[k] = up[k−1]의 up[k−1]입니다 — 2^k칸 위는 2^(k−1)칸을 두 번 올라간 자리라는 것이 전부입니다. 정점 7개, 높이 3이라 열이 4개면 충분합니다. 뿌리 위로 넘어가는 칸은 —로 두었습니다.
사용 방법
- 1간선을 한 줄에 하나씩 「부모 - 자식」으로 적습니다. 방향은 무시하고 뿌리에서부터 다시 매깁니다.
- 2뿌리를 지정합니다. 비워 두면 이름 순으로 첫 정점을 뿌리로 삼습니다.
- 3두 정점을 입력하면 최소 공통 조상과 거리, 그 사이 경로가 나옵니다.
- 4뜀 과정 표에서 2의 거듭제곱 칸씩 어떻게 올라갔는지, 한 칸씩이라면 몇 번이었을지 비교해 봅니다.
자주 묻는 질문
트리에서 두 정점을 뿌리 쪽으로 거슬러 올라가다 처음 만나는 정점입니다. 두 정점 사이의 경로는 반드시 그 자리를 지나므로 거리도 곧바로 나옵니다. 한쪽이 다른 쪽의 조상이면 그 조상 자신이 답입니다.
d(u, v) = depth(u) + depth(v) − 2 × depth(lca)입니다. 뿌리에서 u까지, 뿌리에서 v까지의 길이 LCA 위쪽을 정확히 두 번 겹쳐 세기 때문에 그만큼을 빼면 남는 것이 u—lca—v 경로입니다. 이 계산기는 실제 경로도 함께 그려 길이가 맞는지 눈으로 확인할 수 있게 했습니다.
2의 거듭제곱 칸 위 조상만 미리 적어 두는 표입니다. up[0][v]는 부모이고, up[k][v] = up[k−1][up[k−1][v]] — 2^k칸 위는 2^(k−1)칸을 두 번 올라간 자리라는 것이 전부입니다. 이 표만 있으면 어떤 거리든 그 이진 표기를 따라 뛰어 도달할 수 있습니다. 13칸 위로 가려면 13 = 1101₂이므로 8칸·4칸·1칸을 뜁니다. 전처리 O(n log n), 질의 O(log n)입니다.
어떤 자연수든 2의 거듭제곱의 합으로 딱 한 가지 방법으로 쓸 수 있기 때문입니다. 그것이 곧 이진수 표기입니다. 그래서 필요한 칸 수를 이진수로 적고 1이 선 자리마다 한 번씩 뛰면 정확히 도달하며, 뛰는 횟수는 그 수의 비트 수를 넘지 않습니다.
깊이를 맞춘 뒤 두 정점을 같이 올리며 「같아지는」 자리를 찾으려 하는 것입니다. 2^k칸씩 뛰는 방식에서는 한 번에 LCA를 지나쳐 버릴 수 있습니다. 그래서 올라간 자리가 서로 「다를 때만」 올려야 합니다. 큰 k부터 훑어 그렇게 최대한 올리고 나면 둘은 LCA 바로 아래에 서고, 그때 부모가 답입니다.
거절하고 이유를 알려 줍니다. 정점이 n개인 트리는 간선이 정확히 n−1개이고 전체가 이어져 있어야 합니다. 둘 중 하나라도 어긋나면 순환이 있거나 덩어리가 갈라져 있어 「조상」이라는 말 자체가 성립하지 않습니다.
전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.
알아두면 좋은 점
- 검증은 조상 집합을 실제로 훑는 소박한 방법을 정답지로 삼아 했습니다. 무작위 트리 60벌의 모든 정점 쌍에서 두 방법의 답이 완전히 일치하는 것을 확인했습니다. 한 줄로 늘어선 깊은 트리가 자주 나오도록 부모를 뽑았습니다 — 희소 배열이 이득을 보는 자리이자 경계가 어긋나기 쉬운 자리이기 때문입니다.
- 희소 배열 표 자체도 따로 검사합니다. up[k]가 정확히 2^k칸 위 조상인지 부모를 그 횟수만큼 실제로 거슬러 올라가 대조합니다.
- 거리 식이 언제나 경로 길이와 같은지, 경로가 실제로 이어진 간선만 쓰는지, 같은 정점을 두 번 지나지 않는지를 무작위 트리에서 전수로 고정했습니다.
- 뿌리를 바꾸면 조상 관계도 바뀝니다. 같은 간선 목록이라도 뿌리를 다르게 잡으면 LCA가 달라지는 것을 테스트로 남겨 두었습니다.
- 정점은 40개까지 다룹니다. 희소 배열 표를 함께 보이는 것이 목적이라 그보다 크면 화면이 읽히지 않습니다.
- 간선 입력은 위상 정렬·SCC 계산기와 같은 형식을 씁니다. 「A - B」, 「A B」, 「A, B」 모두 읽습니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 1일 · 결과는 참고용 추정치입니다.