2018-02-15

SPFA

벨만포드 알고리즘에 약간 변형을 줘서 속도향상을 시킨 알고리즘.

기본 골격은 같으나, 벨만포드에서는 모든 간선들을 확인해야 하는 반면,

SPFA는 가장 겉의 for문을 while 문으로 바꾸고, Queue 를 통해서 값이 변경된 정점을 집어넣어 변경된 간선만을 확인하게 된다.

즉, 값의 변화가 이루어지면 inQueue 배열을 true 로 바꾸어주고, pop 할때는 inQueue 배열을 false 로 해준다.

dist 변화는 계속 시켜주되, queue에는 한번만 들어가게 만든다.

그렇다면 벨만포드는 V번 검사를 통해 음수사이클을 확인하는데,

SPFA는 어떻게 확인할까? ---> 이 부분은 참고 자료에 올려놓음.

LCA ( longest common ancestor)

최소 공통 조상을 트리에서 찾는 알고리즘으로 사실 기본 로직은 그렇게 어렵지 않다.

최소 공통 조상은 결국, 트리에서 두 정점의 최단거리를 구하는데 쓰인다는 사실이다. 최단 거리를 찾기 위해서는 결국 공통 조상에서 부터 

각 정점까지의 거리를 더해주기만 하면 되기 때문이다.

일단 전처리 과정을 통해서 트리로 만들어주는 과정이 필요하다. 이는 BFS 나 DFS 를 통해서 하나의 정점을 루트로 잡고 돌리면 된다.

그렇게 트리를 만든 후 기본로직은

1. 두 정점의 높이를 같은 높이로 맞춘다.

2. 높이가 같으면 같아 질 때가지, 각 각의 부모노드로 변경시킨다.

3. 만나는 값이 최소 공통 조상이다.

이를 더 쉽게 풀이하기 위해 DP 로 푸는 방식도 존재한다. 그건 내가 아직 조금 더 완벽하게 숙달해야 겠다.