💡최대 유량이란? 그래프에서 두 정점 사이에 얼마나 많은 유량(flow)을 보낼 수 있는지 계산하는 알고리즘을 네트워크 유량(Network Flow) 혹은 최대 유량(Maximum Flow) 알고리즘이라고 한다. 아래 용어들은 최대 유량 알고리즘을 이해하는데 도움이 되므로, 미리 짚고 넘어가자. 용량(Capacity) Capacity[u][v]는 정점 u에서 v로 가는 간선의 용량이다. 유량(Flow) flow[u][v]는 정점 u에서 v로의 간선(파이프)에 실제로 흐르는 유량을 의미한다. 잔여 용량(Residual Capacity) 간선의 용량과 유량의 차이를 의미한다. ResidualCapacity[u][v] = Capacity[u][v] - flow[u][v] 즉, 해당 간선에 추가적으로 더 흘려 ..

2023.05.17 - [PS] - [세그먼트 트리] - BOJ_14427 : 수열과 쿼리 [세그먼트 트리] - BOJ_14427 : 수열과 쿼리 ※본 포스팅은 이전 블로그에서 다시 이전해온 글로서 기존 작성일은 23.04.25 입니다. 요즘들어 PS를 하면서 느끼는게, 내가 이전에 공부하고 완전히 이해했던 자료구조 / 알고리즘들이 몇개월 지 kangmanjoo.tistory.com 지난 포스팅에 이어, 다시 한 번 세그먼트 트리로 돌아왔다. 세그먼트 트리는 특정 구간의 합, 곱, 최솟값, 최댓값을 찾을 때 일반적인 배열에서 찾을 때보다 훨씬 빠른 O(logN)의 시간복잡도를 가진다고 하였다. 그렇다면 세그 트리는 무적이고 나는 신인가? 물론 아니다. 세그트리에도 치명적인 단점이 존재하는데, 바로 값의 ..

2023.05.15 - [PS] - [강한 연결 요소 SCC] - BOJ_2150 : Strongly Connected Component [강한 연결 요소 SCC] - BOJ_2150 : Strongly Connected Component 오늘은 SCC 알고리즘에 대해 공부하였다. 강한 연결요소인 SCC를 구하는 문제였다. 2-sat을 풀기전 사전 준비로 풀었는데, 어려웠다.. 💡SCC 알고리즘이란? scc란 쉽게 말하면 전체 노드 집합 속에서, kangmanjoo.tistory.com 저번 SCC 공부는 사실 이번 2-SAT 풀이를 위해서 진행했었다. 2-SAT 풀이를 보기전, SCC에 대한 기본 지식이 없다면 위 글을 먼저 읽어볼 것. 오늘 풀어볼 문제인, 백준 11280번이다. 일단 2-SAT에 대..

오늘은 SCC 알고리즘에 대해 공부하였다. 강한 연결요소인 SCC를 구하는 문제였다. 2-sat을 풀기전 사전 준비로 풀었는데, 어려웠다.. 💡SCC 알고리즘이란? scc란 쉽게 말하면 전체 노드 집합 속에서, 서로 사이클을 이루는 노드들의 집합이다. 이런 형태의 노드 집합이 있으면 전체 집합을 이렇게 3개의 scc집합 (사이클) 로 나누는 것이다. scc를 구할때는 코사라주 알고리즘과 타잔 알고리즘 두가지 종류가 있는데, 타잔알고리즘이 구현이 어려운 대신 범용성이 넓기에 타잔 알고리즘을 사용해 풀었다. 🐒타잔 알고리즘이란? 타잔 알고리즘이란 SCC를 구하는 기법중 하나로, DFS 탐색을 들어갈 때 나의 부모노드를 기록하면서 가는 것이다. 스택에 방문한 노드들을 넣으면서 DFS를 돌다가 나 자신이 부모노..