💡최대 유량이란? 그래프에서 두 정점 사이에 얼마나 많은 유량(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] 즉, 해당 간선에 추가적으로 더 흘려 ..
소수를 판별하는 알고리즘 중에는 굉장히 유명한 에라토스테네스의 체라는 알고리즘이 존재한다. 소수 판별 문제는 대부분 이 알고리즘으로 풀기 때문에 잘 익혀두면 큰 도움이 된다. 오늘 풀어볼 문제인 boj 1929 번 문제다. 💡에라토스테네스의 체란? 배열을 원하는 범위만큼 생성하여 초기화한다. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다. 이때, 자기 자신은 지우지 않고, 이미 지워진 수인 경우 건너뛴다. 지워지지 않은 테이블이 소수로 판별된 테이블이다. 위 예시는 2의 배수를 모두 지우고, 3의 배수를 지우는 과정이다. 이런 식으로 $N/2$까지 진행하고 남은 테이블을 확인한다. ❓에라토스테네스의 체의 시간복잡도 naive한 방법으로는, 일반적으로 어떤 정수의 소수를 판별할때는 2부터 판..
2023.05.17 - [PS] - [세그먼트 트리] - BOJ_14427 : 수열과 쿼리 [세그먼트 트리] - BOJ_14427 : 수열과 쿼리 ※본 포스팅은 이전 블로그에서 다시 이전해온 글로서 기존 작성일은 23.04.25 입니다. 요즘들어 PS를 하면서 느끼는게, 내가 이전에 공부하고 완전히 이해했던 자료구조 / 알고리즘들이 몇개월 지 kangmanjoo.tistory.com 지난 포스팅에 이어, 다시 한 번 세그먼트 트리로 돌아왔다. 세그먼트 트리는 특정 구간의 합, 곱, 최솟값, 최댓값을 찾을 때 일반적인 배열에서 찾을 때보다 훨씬 빠른 O(logN)의 시간복잡도를 가진다고 하였다. 그렇다면 세그 트리는 무적이고 나는 신인가? 물론 아니다. 세그트리에도 치명적인 단점이 존재하는데, 바로 값의 ..
※본 포스팅은 이전 블로그에서 다시 이전해온 글로서 기존 작성일은 23.04.25 입니다. 요즘들어 PS를 하면서 느끼는게, 내가 이전에 공부하고 완전히 이해했던 자료구조 / 알고리즘들이 몇개월 지나면 기억이 휘발되어 다시 포스팅들을 찾아보고 있는 내 모습이 너무 바보같았다. 그래서 이왕이면 내가 쓴 글을 보고 다시 떠올리자! 하는게 재습득하기도 제일 빠르고 나에게도 도움이 더 될 것같아, 이곳에 정리하기로 결정했다! 오늘 학습한 자료구조는 바로 세그먼트 트리 도대체 세그먼트 트리는 어디에서 활용이 되는 자료구조인가? 가장 대표적으로 활용이 되는 곳은, 바로 구간합을 구할때이다. INDEX 0 1 2 3 4 5 6 7 VALUE 2 1 7 8 5 4 3 1 위와 같은 테이블이 있다고 하자. 이 배열에서 ..
첫 플래티넘 3 솔브다 !! 세그먼트 트리를 활용하는 자료구조 중 재밌는게 없나 찾던 중, 머지 소트 트리라는 이름만 들어도 흥미로운 태그를 찾았다. 심지어 수열과 쿼리 '1' 이라니 안풀 수가 없잖아 ! ❓머지 소트 트리(Merge Sort Tree)란? 일반적인 세그먼트 트리구조란, 해당 구간의 특징 (구간합이든, 최솟값이든.. 등등)을 각 범위를 지칭하는 노드에 저장을 한다. 머지 소트 트리도 마찬가지로, 특정 범위의 value들의 정렬 상태인 배열을 노드에 저장을 하는 구조이다. 사실 세그먼트 트리에 익숙하다면 크게 어렵지 않게 풀 수있다. 이번 문제에서는 개념을 묻는 느낌이라 갱신을 안해서 갱신부분은 고려를 안해보았는데, 이를 다루는 문제들도 풀어보면 좋을 듯싶다. 이 문제에서 한 번 실수했던 ..
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에 대..
티스토리로 블로그를 이전한 뒤, 기념비적인 첫 글이다. 요즈음도 알고리즘을 공부하다보면, 금새 잊곤 하기 때문에 이렇게 하나 하나 글을 써보려 한다. 오늘 공부한 알고리즘은, 바로 "게임 이론" 알고리즘 분류만 보면 상당히 귀엽고 재밌어 보이지만, 상당히 악랄하다. 우선 오늘의 문제를 소개해보겠다. 처음 문제를 보았을 때는, 상당히 간단해 보인다. 그냥 항상 최선의 경우를 고르면 되는거 아님? 아니다 바로 다음과 같은 상황이 야기될 수 있다. 전체 게임 결과를 보았을 때, 최선의 선택을 해야하고, 상대 또한 최선의 선택을 하기에 내가 처음에 2를 뽑으면, 상대에게 5를 내주기 때문에 점수가 더 낮아지게 된다. 따라서 이 경우에서의 "최선의 수"란 다음과 같다. 물론 우리가 보기에는 , 그렇게 어렵지 않다..