- 최소 공통 조상 이란, 트리안에서 두개의 노드가 같은 부모노드를 찾는 알고리즘이다.
알고리즘 구현
1. 모든 노드에 대한 깊이(depth)를 계산합니다.
2. 최소 공통 조상을 찾을 두 노드를 확인합니다.
1) 먼저 두 노드의 깊이(depth)가 동일하도록 거슬러 올라갑니다.
2) 이후에 부모가 같아질 때까지 반복적으로 두 노드의 부모 방향으로 거슬러 올라갑니다.
3. 모든 LCA(a,b) 연산에 대하여 2번의 과정을 반복합니다.
재귀 함수를 사용하기 때문에 sys.setrecursionlimit 를 설정하고(런타임 에러 방지)(파이썬의 재귀 깊이는 1000으로 매우 짧기 때문)
graph의 정보입력(a 와 b 가 서로 연결 이라는뜻)
루트 노드 부터 깊이와 부모노드를 찾는 재귀 함수 이다.
c[x] = True < 이제 깊이가 입력되었기때문에 True로 설정
d[x] = depth x의 깊이값을 입력 값으로 설정(초기엔 루트노드이니 0)
루트노드와 연결된 값 을 방문하며(바로 위 for문에 입력된 값들)
if c[y] < 깊이가 구해졌다면 생략 (루트노드 부터 아래로 내려가니 부모노드를 찾기 위한 값)
parent[y] = x 가 된다
그리고 다시 재귀하여 y 의 값에 깊이를 1을 더하고 실행.
lca(최소 공통 조상을 찾는 함수)
먼저 알고리즘 구현 2-1 (깊이가 동일하도록 거슬러 올라가기)
깊이르 동일하게 만들어줍니다.
같아 졌다면 두번째 while 문을 통해 2-2 조건 만족하기.
루트노드를 설정하고 찾을 최소 공통 조상을 찾을 갯수 m 을 정하고
최소 공통 조상을 찾을 2개의 노드를 정합니다.
이때 시간 복잡도는 O(NM)이다.
개선된 LCA 알고리즘
노드가 적을때는 위의 방식을 사용해도 시간 초과 판정을 받지않지만
노드의 개수가 매우 많아지게 된다면 시간초과 판정을 받을수있다.
우리는 시간복잡도를 개선하기 위해 메모리를 조금 더 사용하여 시간복잡도를 개선하도록 하고자 한다. (다이나믹 프로그래밍 사용)
시간복잡도는 O(MlogN)가 나온다.
총데이터가 100만개 들어올수 있다고 가정한 코드예시이다.
재귀 함수를 사용할때는 sys.setrecursionlimit 를 사용하자.
a 와 b 가 연결되었다 = 서로 부모 자식 관계
먼저 기존 lca와 동일하지만 다른점은 parent[y][0] 부분인데
우리는 2^i 만큼 거슬러 올라가는 알고리즘 이기때문에 0으로 설정해줘서 바로 위 부모 노드의 값 을 정해준다.
루트노드를 설정해주고 2의 제곱 값 으로 건너띄웠을때 부모값을 기록한다.
a와 b의 깊이 값을 비교하여 a의 깊이가 더 깊다면 스와핑 해준다.
b와 a 의 깊이차이가 (1<<i) 보다 크거나 같다면 b의 값을 set_parent 함수에 기록된 값 만큼씩 건너띔.
1<<i 는 시프트연산으로 1*2^i 라는 의미이다.
a 와 b가 같다면 a 값 을 반환해준다
a의 부모 값 과 b의 조상값이 다르다면 2의 i승 만큼씩 거슬러 올라감.
너무 이해하기 너무 어려웠다. 지금은 알고리즘을 보면 이해는 가지만
문제를 보고 응용하라고하면 힘들것같다. 자주 학습하도록 하자.
