네트워크 플로우 네트워크 플로우는 특정한 지점에서 다른 지점으로 데이터가 얼마나 많이 흐르고 있는가를 측정하는 알고리즘이다. 이런 문제를 사용하는 곳은 도로망의 교통 흐름을 분석, 전자 회로의 전류, 배수관을 흐르는 유체, 유량등을 연구하는데 사용된다. 유량 : 현재 흐르고 있는 데이터의 양 용량 : 간선에 흐를 수 있는 최대 데이터의 양 이 문제를 빠르게 해결하기 위해 사용하는 알고리즘이 에드몬드 카프 알고리즘과 디닉 알고리즘이 있다. 이 중 에드몬드 카프 알고리즘 부터 공부했다. 에드몬드 카프(Edmonds-Karp algorithm) 설명 위 그래프는 동아리 스터디 시간에 애드몬드 카프 알고리즘을 배울 때 쓴 예시 그래프이다. A에서 D로 갈 때 0/3 이라는 소리는 현재 유량이 0 용량이 3이라는..

일단 알고리즘을 설명하기전 강한 결합 요소부터 설명할려 한다. 강한 결합요소 즉, SCC는 그래프에서 하나의 노드에서 시작해 다른 노드까지 갔다가 다시 자신의 노드로 되돌아 올 수 있는 최대 컴포넌트의 모임이다. 이 그래프를 보면 9에서 시작해 (4,5,7)과 (3,6,8) 과 9로 나눌 수 있다는 것을 알 수 있다. 즉, 여기서 SCC는 3개가 나온다. SCC를 찾는 알고리즘은 2가지가 있다. 그 중 한가지인 코사리주의 알고리즘은 학교 알고리즘 시간에 배웠다. 그 때 교수님께서 다른 방법인 타잔 알고리즘이 있다고 한 것이 기억에 난다. 운이 좋게도 이번 동아리 스터디에서 타잔 알고리즘에 대해 알려줘 공부해 보았다. 코사리주 알고리즘 코사리주 알고리즘은 dfs를 2번하여 강한 결합 요소를 찾는 것이다. ..

학교 동아리에서 매주 배우는 알고리즘을 정리해 볼 것이다. 그 뒤 동아리에서 추천해준 백준문제를 풀어 볼 것 이다. 사용하는 경우 수열에서 임의의 구간에 대한 최대값, 최소값, 합, 곱 등을 빠르게 구할 때 (세그먼트 트리) 수열에서 임의의 구간에 대한 업데이트를 빠르게 할 때 (레이지 세그먼트 트리) 세그먼트 트리 모습 수열 [5,7,3,2,9,8] 을 합의 세그먼트 트리 모습으로 나타내면 이런 모습으로 보여진다. 리프 노드가 수열이고 다른 노드가 합을 나타탠다. 트리는 배열로 나타낼 수 있다. 인덱스 1 의 왼쪽 자식이 2 오른쪽 자식이 3 이런 식이다. 즉, node x의 왼쪽 자식 노드는 2x, 오른쪽 자식 노드는 2x+1이다. 위 트리를 배열로 나타내면 이렇게 나타낼 수 있다. 세그먼트 트리 사..