[알고리즘]#7_LCA(Least Common Ancestor)

2024. 3. 12. 11:38· 알고리즘
목차
  1. #1. 개념
  2. 1. LCA(Least Common Ancestor)
  3. 2. Binary Lifting 기법
  4. 3. 동작 방식
  5. 2. LCA 
  6. #3. 예제
  7. 1. LCA
  8. 2. LCA w/ Binary Lifting

#1. 개념

 

1. LCA(Least Common Ancestor)

 

LCA 알고리즘은 트리 자료구조에서 두 노드의 가장 가까운 공통 조상 노드를 찾는 알고리즘입니다. 이때, 가장 가까운 노드란, 주어진 두 노드의 경로 상에서 가장 깊은 곳에 위치한 공통 조상 노드를 의미합니다. LCA 알고리즘을 효율적으로 구현하는 방법으로 Binary Lifting 기법이 있습니다.

 

2. Binary Lifting 기법

 

출저 : https://iq.opengenus.org/binary-lifting-k-th-ancestor-lowest-common-ancestor/

 

Binary Lifting 기법은 주어진 트리 자료구조에서 두 노드의 LCA를 찾는 방법 중 하나입니다. 특히, Binary Lifting 기법은 깊이가 깊은 트리에서 두 노드의 LCA를 찾는데 효율적입니다. BL의 핵심 개념은 각 노드에 대해 미리 점프할 수 있는 조상 정보를 계산해 두고, 이를 이용해 두 노드의 LCA를 찾는 것입니다. Binary Lifting을 활용한 LCA 알고리즘의 사전 처리 과정은 O(n log n) 시간 복잡도 + 두 노드의 LCA를 찾는 과정은 O(log n)의 시간 복잡도를 가지며, 특히 여러 LCA 쿼리를 처리해야 하는 경우에 매우 효율적입니다. 다만, 사전 처리 과정에서 각 노드의 조상 정보를 저장할 추가적인 메모리 공간이 필요합니다.

 

3. 동작 방식

 

1. 깊이 목록 + 부모 노드 목록 초기화 (노드 개수 적을 때)

// BFS로 각 노드의 깊이와 부모 찾기
void bfs(int root) {
    vector<bool> visited(N, false);
    queue<int> q;

    depth[root] = 0;
    visited[root] = true;
    q.push(root);

    while(!q.empty()) {
        int cur = q.front();
        q.pop();

        for(int next : graph[cur]) {
            if(!visited[next]) {
                depth[next] = depth[cur] + 1;
                parent[next] = cur;
                visited[next] = true;
                q.push(next);
            }
        }
    }
}
일반적으로, DFS 혹은 BFS를 통해 부모 목록을 찾고, 깊이 목록을 작성합니다.

 

2. 깊이 목록 + 조상 노드 목록 초기화 (Binary Lifting 적용, 깊이가 깊을 경우)

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5; // 최대 노드 수
const int LOG = 20; // 2^20 = 1048576, MAXN보다 큰 가장 작은 2의 제곱수의 로그 값
int ancestor[MAXN][LOG]; // up[v][j]는 v로부터 2^j 위에 있는 노드
int depth[MAXN]; // 루트로부터의 깊이
vector<int> graph[MAXN]; // 그래프 인접 리스트

// DFS를 사용하여 각 노드의 조상 노드 정보 업데이트
void dfs(int v, int p) {
    ancestor[v][0] = p; // v의 바로 위 부모는 p
    for (int i = 1; i < LOG; ++i) {
        if (ancestor[v][i-1] != -1) ancestor[v][i] = ancestor[ancestor[v][i-1]][i-1]; // v로부터 2^i 위에 있는 노드 계산
        else ancestor[v][i] = -1;
    }
    for (int u : graph[v]) {
        if (u == p) continue; // 부모 노드는 건너뜀
        depth[u] = depth[v] + 1; // 깊이 업데이트
        dfs(u, v); // 재귀적으로 자식 노드 탐색
    }
}

int main() {
    // 그래프 구성 및 사전 처리 로직
    // 루트 노드를 시작점으로 하는 dfs 호출, 루트 노드의 부모 노드는 -1
	dfs(1, -1)

    return 0;
}
LCA 알고리즘을 수행하기 전에 Binary Lifting 기법을 활용하여 각 노드의 조상 노드 정보를 계산하는 사전 처리 과정을 수행합니다. 먼저, 각 노드의 조상 노드 정보를 기억할 2차원 벡터 혹은 배열이 필요합니다. 2차원 배열의 row는 현재 노드를 의미하며, col은 현재 노드로부터 2^col(2의 col승) 위에 위치한 노드를 의미합니다. DFS를 수행하며, 각 노드의 조상 정보 + 깊이 정보를 업데이트해줍니다. 

 

2. LCA 

 

1. 일반 버전

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5;  // 최대 노드 수
vector<int> graph[MAXN];  // 그래프 인접 리스트
vector<int> parent;  // 각 노드의 부모 노드
vector<int> depth;  // 루트로부터의 깊이

// DFS를 사용한 부모와 깊이 계산
void dfs(int curr, int prev) {
    parent[curr] = prev;  // 현재 노드의 부모 저장
    
    for(int next : graph[curr]) {
        if(next != prev) {  // 부모 노드가 아닌 경우에만
            depth[next] = depth[curr] + 1;  // 깊이 설정
            dfs(next, curr);  // 재귀적으로 자식 노드 탐색
        }
    }
}

// 두 노드의 LCA 찾기
int lca(int a, int b) {
    // 항상 a가 더 깊은 노드가 되도록
    if(depth[a] < depth[b]) {
        swap(a, b);
    }
    
    // 깊이 맞추기
    while(depth[a] > depth[b]) {
        a = parent[a];
    }
    
    // 같은 깊이에서 같은 노드가 될 때까지 위로 올라가기
    while(a != b) {
        a = parent[a];
        b = parent[b];
    }
    
    return a;  // LCA 반환
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n;  // 노드 수
    cin >> n;
    
    // 벡터 크기 초기화
    parent.resize(n);
    depth.resize(n);
    
    // 트리 입력 받기 (n-1개의 간선)
    for(int i = 0; i < n-1; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    
    // 루트(0)부터 시작하여 각 노드의 부모와 깊이 계산
    depth[0] = 0;
    dfs(0, -1);  // 루트의 부모는 -1
    
    // 쿼리 처리
    int q;  // 쿼리 수
    cin >> q;
    
    while(q--) {
        int u, v;
        cin >> u >> v;
        cout << lca(u, v) << '\n';
    }
    
    return 0;
}

 

2. Binary Lifting 적용 버전

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5; // 최대 노드 수
const int LOG = 20; // 2^20 = 1048576, MAXN보다 큰 가장 작은 2의 제곱수의 로그 값
int ancestor[MAXN][LOG]; // up[v][j]는 v로부터 2^j 위에 있는 노드
int depth[MAXN]; // 루트로부터의 깊이
vector<int> graph[MAXN]; // 그래프 인접 리스트

// DFS를 사용한 사전 처리
void dfs(int v, int p) {
    ancestor[v][0] = p; // v의 바로 위 부모는 p
    for (int i = 1; i < LOG; ++i) {
        if (ancestor[v][i-1] != -1) ancestor[v][i] = ancestor[ancestor[v][i-1]][i-1]; // v로부터 2^i 위에 있는 노드 계산
        else up[v][i] = -1;
    }
    for (int u : graph[v]) {
        if (u == p) continue; // 부모 노드는 건너뜀
        depth[u] = depth[v] + 1; // 깊이 업데이트
        dfs(u, v); // 재귀적으로 자식 노드 탐색
    }
}

// 두 노드의 LCA 찾기
int lca(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b); // a가 더 깊은 노드로 설정
    // 깊이 맞추기
    for (int k = LOG - 1; k >= 0; --k) {
        if (depth[a] - (1 << k) >= depth[b]) {
            a = ancestor[a][k];
        }
    }
    if (a == b) return a; // 깊이를 맞춘 후 같은 노드라면 그 노드가 LCA
    // 공통 조상 찾기
    for (int k = LOG - 1; k >= 0; --k) {
        if (ancestor[a][k] != ancestor[b][k]) {
            a = ancestor[a][k];
            b = ancestor[b][k];
        }
    }
    return ancestor[a][0]; // 최종적으로 위로 한 칸 올라간 노드가 LCA
}

int main() {
    // 그래프 구성 및 사전 처리 로직
    // 예: dfs(루트노드, -1);
    // LCA 쿼리 예시: cout << lca(노드1, 노드2) << endl;

    return 0;
}

 

다음으로, 주어진 두 노드에 대하여 LCA를 수행합니다. LCA 알고리즘은 작은 5단계로 구성됩니다.

1) 주어진 두 노드 u, v에 대하여 상대적으로 깊이가 더 깊은 정점을 미리 설정한다.
2) 두 노드 u, v의 깊이 값을 비교하고, 그 값이 최소가 되도록 맞춰준다.
3) u, v가 같은 노드라면, 이를 반환하고 종료한다.
4) u, v가 서로 다른 노드라면, 부모 노드를 2^i씩 점프하며 올라가며 LCA를 찾는다.
5) u, v가 서로 같은 부모를 가지게 되었을 때, ancestor[a][0]을 반환한다.

 


 

#3. 예제

 

1. LCA

 

2. LCA w/ Binary Lifting

 

// 예제

 


 

 

 

저작자표시 (새창열림)

'알고리즘' 카테고리의 다른 글

[알고리즘]#10_MiniMax, 최적의 의사 결정  (0) 2025.04.23
[알고리즘]#9_Quick Select  (0) 2024.04.30
[알고리즘]#7_투 포인터  (0) 2023.12.13
[알고리즘]#6_백트래킹  (0) 2023.07.27
[알고리즘]#5_동적 계획법  (0) 2023.07.26
  1. #1. 개념
  2. 1. LCA(Least Common Ancestor)
  3. 2. Binary Lifting 기법
  4. 3. 동작 방식
  5. 2. LCA 
  6. #3. 예제
  7. 1. LCA
  8. 2. LCA w/ Binary Lifting
'알고리즘' 카테고리의 다른 글
  • [알고리즘]#10_MiniMax, 최적의 의사 결정
  • [알고리즘]#9_Quick Select
  • [알고리즘]#7_투 포인터
  • [알고리즘]#6_백트래킹
Hardii2
Hardii2
Hardii2
개발 블로그
Hardii2
전체
오늘
어제
  • 분류 전체보기
    • 알고리즘
    • 웹 개발
      • Node.js
      • React
    • 게임개발
      • DirectX12
      • 관련 지식
      • Unreal C++
      • Unreal 블루프린트
    • 언어
      • Effective C++
      • Basic C++
      • 디자인 패턴
      • 자료구조
      • 기술 질문
    • 문제 풀이
      • BOJ 문제 풀이
      • Programmers 문제 풀이
      • geeksForgeeks 문제 풀이
    • 수학
      • 확률과 통계
      • 게임수학
    • 개인프로젝트
    • 그룹프로젝트
      • PM
      • Dev
    • Github

블로그 메뉴

  • 홈
  • 글쓰기

공지사항

인기 글

태그

  • dfs
  • C++
  • set
  • 우선순위 큐
  • 트리
  • 알고리즘
  • Unreal Blueprint
  • BFS
  • unreal
  • stl
  • BOJ
  • 기술 질문
  • programmers
  • DP
  • 디자인 패턴
  • 개발
  • 최단 경로
  • Effective C++
  • 정렬
  • 그래프

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
Hardii2
[알고리즘]#7_LCA(Least Common Ancestor)
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.