PS 일지

시작하기 전에그래프에서 최단 경로를 찾는 알고리즘은 크게 세 가지가 존재한다고 알고 있었다. Dijkstra- 시작점이 존재해야 함. 그래프의 간선 가중치가 음이 아닌 정수일 때만 가능Floyd-Warshall- 모든 정점 쌍 사이의 최단 경로를 구할 때 사용, 음수 가중치 및 음의 사이클 판별 가능Bellman-Ford- 시작점이 존재해야 함. 음수 가중치 및 음의 사이클 판별 가능 Claude 선생님과 함께 알고리즘 복습을 하던 중에 SPFA라는 것을 접하게 되었다.SPFA 또한 그래프에서 최단 경로를 찾는 알고리즘이며, 이를 알기 위해선 Bellman-Ford를 먼저 알아야 한다.여기서는 Bellman-Ford의 원리만 간단히 설명하겠다.Bellman-Ford정점이 $N$개인 그래프의 어떤 최단 경..

🔗 백준 2042번 - 구간 합 구하기 문제를 보자. 세그먼트 트리를 입문하면서 처음 만나게 되는 문제로 유명하다.여기서는 세그먼트 트리를 사용하지 않는, $O(M \sqrt{N})$ 풀이를 소개하려 한다.아이디어원래 세그먼트 트리에선, 구간을 반씩 쪼개어 총 $O(N\log{N})$개의 구간 합을 관리하는 아이디어를 사용한다.구간을 쪼갠다는 아이디어 자체는 같다. 여기서는 길이가 동일한 구간을 $O(\sqrt{N})$개 만들어서 각 구간의 길이 또한 $O(\sqrt{N})$이 되도록 관리한다.보통 구간 하나하나를 버킷이라 칭한다. 적용각 버킷별로 합을 저장하는 배열을 만들어 놓자.만약 위 그림처럼 특정 구간의 합을 구하려고 할 때,초록색 부분만 하나하나 직접 더해주고 파란색 부분은 미리 구해놓은 ..

정의방향 그래프에서, 모든 정점들이 서로 도달 가능한 최대 부분 그래프⇒ SCC 내 임의의 정점 $u,v$에 대해, $u \rightarrow v$경로와 $v \rightarrow u$경로가 모두 존재특성모든 방향 그래프는 하나 이상의 SCC로 분해될 수 있음SCC들은 서로 겹치지 않음 (SCC 정의가 최대 부분 그래프이기 때문)모든 정점은 정확히 하나의 SCC에 속함방향 그래프의 SCC들을 하나의 정점으로 압축하면 DAG가 됨.SCC 찾기코사라주 알고리즘각 정점에 DFS Finishing Time을 기록Finishing Time ⇒ 오일러 경로 테크닉에서 out time의 개념과 동일함모든 간선의 방향을 뒤집은 전치 그래프에서, 탐색 종료의 역순으로 정점을 방문하여 생긴 DFS 트리가 하나의 SCC가 ..

나중에 까먹을 때를 대비한 기록용 포스팅 레퍼런스 : https://justicehui.github.io/hard-algorithm/2019/05/22/Li-Chao-Tree/(설명도 쉽게쉽게 되어있어서 많이 도움되었습니다.)  핵심은 특정 구간에서 Line들의 lower(혹은 upper) hull을 관리할 수 있다는 것이다.CHT 문제를 풀 때 사용할 수 있다. +) 덤으로 Dynamic Segment Tree에 대한 개념도 공부하게 되었다.필요 시에만 노드를 생성하며, 직선이 존재할 수 있는 범위가 $[s,e]$일 때 하나의 쿼리에 $O(log(e-s))$개의 노드만 추가된다.