기하 및 그래프 알고리즘 간단 정리

*기하

그라함 스캔 과정

1. 극값 찾기(y값 작은거, 같다면 x값 작은거)

2. 극값기준 각도순 정렬

3. n번 루프돈다. 스택 크기 2이상 유지하면서 b[i] 0이하이면 pop. 밖에서 push

4. 필요에 맞게 마지막에 처음점 추가(다각형의 선분으로 무언가 할 때)

볼록껍질 최단거리 찾는법

1. 그라함 스캔을 돌려서 볼록 껍질을 형성한다. (마지막에 첫점 추가)

2. n번 루프돈다. j=1부터, j가 1이랑 다를때만 방향벡터 ccw가 양수이면 j++해준다.

j==s.size()-1이 되면 0으로 낮춰준다.

3. 양수가 아니게 되면 i와 j의 거리를 비교해서 최대인지 확인한다

-----------------------------------------------------------------------

*그래프

플로이드 와샬

1. n <= 500일때만 사용하자.

2. 바깥부터 k i j 순으로 루프 돌리고, k거쳐가는거랑 그냥가는거 길이 비교해서

작은 값으로 갱신해준다.

3. 모든 정점사이의 비용 계산에 용이 -> 모든 정점의 연결상태 파악 가능

벨만포드 -> 시작점 존재

0. 초기에 비용 무한대로 초기화. 시작점 비용은 0으로

1. 음수가중치가 존재할 때 사용. 사이클이 없어야한다.

2. 가장 바깥에서 n번 돌린다.(n번째에 갱신이 발생하면 음수사이클 존재)

3. 그 안쪽에서 정점 개수만큼 루프를 돈다.

4. 정점마다 연결된 간선 크기만큼 루프 돌면서, 목적지가 갖고 있는 거리가,

이곳에서 그 정점으로 가는 거리보다 크다면 갱신한다.

5. 이걸 확인할 때, 현재 위치까지의 비용이 무한이 아니어야 한다.

다익스트라

1. 가중치가 양수인 그래프의 최단거리를 젤 수 있다.

2. 방문처리와 우선순위큐가 필요하다(민힙), pii 배열의 인덱스가 시작점, first 비용, sec 목적지 

3. 비용을 무한대로 초기화해주고, 시작점은 0으로 만든다.

4. 시작점을 pq에 넣고, pq가 빌 때까지 실행한다.

5. pq에서 확인하는 지점을 방문처리 한다.(top)

6. 그 지점과 연결된 간선들을 확인할 것인데, 그 연결된 지점이 방문한 지점이면 스킵한다.

7. 거리비교해서 갱신조건 만족할 때만 push한다.

LCA (최소공통조상)

1. DFS로 각 노드의 깊이 계산, 2^0번째 부모 계산

2. 2^k번째 부모는 2^k-1번째 부모의 2^k-1번째 부모임을 이용해서 배열 채우기

3. 비교하고자 하는 노드의 높이를 같게 맞추기(탑다운으로) (뭐가 깊고 뭐가 얕은 노드인지 구분해서)

4. 이때 최대 높이는 (int)floor(log2(n))

5. 높이차이가 2^k보다 커질때마다 깊은점을 k번째 부모로 갱신

6. 높이를 맞춘 이후에, 두 노드가 같다면 그게 답

7. 이번에도 kmax부터 내려오면서 deep과 swall의 부모가 다르다면 둘다 k번째 부모로 갱신

8. 루프를 빠져나오면 0번째 부모가 답