알고리즘 (9) 썸네일형 리스트형 Kőnig's theorem Kőnig's theorem은 다음과 같이 정의된다. 이분 그래프에서 최대 매칭과 최소 정점 덮개의 크기는 동일하다. 증명 과정을 간략하게 설명한다. 우선 이분 그래프를 적절히 유량 그래프로 변환한다. 이분 그래프에서의 최대 매칭과 유량 그래프에서의 최대 유량의 크기는 동일하다. Max-Flow Min-Cut theorem에 의하여 최대 유량과 최소 컷의 크기는 동일하다. 최소 컷 (S, T)에서 다음 집합은 최소 컷과 크기가 동일한 정점 덮개이다. {소스와 인접한 정점 중 T에 속하는 정점 및 싱크와 인접한 정점 중 S에 속하는 정점} 또한 최대 매칭보다 크기가 작은 정점 덮개는 존재할 수 없다. 따라서 이분 그래프에서 최대 매칭과 최소 정점 덮개의 크기는 동일하다. 여담으로 최소 정점 덮개의 여집합은.. Network Flow 알고리즘 이 글에서는 Network Flow 알고리즘 중 다음 세 가지 알고리즘을 간략하게 설명한다. Ford-Fulkerson 알고리즘 Edmonds-Karp 알고리즘 Dinic 알고리즘 더 강력한 Push-Relabel 알고리즘도 존재하지만 여기서는 다루지 않는다. Ford-Fulkerson 알고리즘 가장 기본적인 알고리즘이다. 동작 과정은 다음과 같다. 잔여 그래프에서 소스에서 싱크로 가는 증가 경로가 존재하면 해당 경로에 유량을 최대로 흘린다. 이를 증가 경로가 존재하지 않을 때까지 반복한다. 알고리즘의 정당성은 Max-Flow Min-Cut theorem을 이용하여 증명할 수 있다. 증가 경로를 찾고 유량을 흘리는 부분은 DFS 또는 BFS로 처리할 수 있다. 최대 유량을 f라고 하면 반복 횟수는 최대 .. Euler's theorem GitHub - hijkl2e/problem_solving: 알고리즘 문제 해결 알고리즘 문제 해결. Contribute to hijkl2e/problem_solving development by creating an account on GitHub. github.com Euler's theorem은 다음과 같이 정의된다. a와 n이 서로소일 때, a^ϕ(n) ≡ 1 (mod n) Euler's theorem은 a와 n이 서로소일 때만 성립한다. 하지만 아래 정리는 a와 n의 서로소 여부에 관계 없이 성립한다. a^ϕ(n) ≡ a^2ϕ(n) (mod n) 끝 Euler's phi function GitHub - hijkl2e/problem_solving: 알고리즘 문제 해결 알고리즘 문제 해결. Contribute to hijkl2e/problem_solving development by creating an account on GitHub. github.com Euler's phi function은 다음과 같이 정의된다. ϕ(n) = n과 서로소인 1부터 n까지의 정수의 개수 naive하게 구하면 O(NlogN)이지만 소인수분해를 하면 O(sqrt(N))에 구할 수 있다. 끝 Union-Find GitHub - hijkl2e/problem_solving: 알고리즘 문제 해결 알고리즘 문제 해결. Contribute to hijkl2e/problem_solving development by creating an account on GitHub. github.com 요약 Union-Find는 다음과 같은 집합 연산을 거의 O(1)에 수행할 수 있는 자료 구조이다. 두 집합을 병합하는 Union 연산 자신이 속한 집합을 찾는 Find 연산 Union-Find를 naive하게 구현할 경우 시간 복잡도는 O(N)이다. union by size(rank) 및 경로 압축 기법을 적용할 시 시간 복잡도는 거의 O(1)이 된다. 연습 문제 1. Association for Control Over Minds su.. Order Statistic Tree GitHub - hijkl2e/problem_solving: 알고리즘 문제 해결 알고리즘 문제 해결. Contribute to hijkl2e/problem_solving development by creating an account on GitHub. github.com 요약 Order Statistic Tree(이하 pbds)는 다음 연산을 O(logN)에 처리할 수 있다. 다만 상수가 조금 크다. K번째 원소 찾기 주어진 원소의 순서 구하기 위의 연산이 필요하면 일단 pbds를 들이대보자. TLE가 발생하면 좌표 압축 + Fenwick Tree로 처리하자. 연습 문제 1. Cookie Selection pair pbds 2. Galactic Collegiate Programming Contest tu.. Fenwick Tree GitHub - hijkl2e/problem_solving: 알고리즘 문제 해결 알고리즘 문제 해결. Contribute to hijkl2e/problem_solving development by creating an account on GitHub. github.com 요약 Fenwick Tree는 구간 질의를 O(logM)에 수행할 수 있는 자료 구조이다. Segment Tree보다 상수가 작으나 수행 가능한 연산이 일부 제한된다. Fenwick Tree의 기본 연산은 PURQ이다. Point Update와 Range Query 모두 비트 연산으로 O(logM)에 수행할 수 있다. 추가적으로 select 연산도 O(logM)에 가능하다. PURQ Fenwick Tree를 응용하면 RUPQ 및 RURQ.. Knuth's Optimization GitHub - hijkl2e/problem_solving: 알고리즘 문제 해결 알고리즘 문제 해결. Contribute to hijkl2e/problem_solving development by creating an account on GitHub. github.com 특정 형태의 점화식을 갖는 dp에 대하여 시간 복잡도를 O(N^3)에서 O(N^2)으로 줄이는 기법이다. 자주 등장하는 주제도 아니고 증명도 매우 어렵다고 하여 증명은 생략하였다. AtCoder Educational DP Contest N - Slimes 문제에 해당 기법을 적용할 수 있다. N이 작기 때문에 O(N^3)으로도 풀린다. O(N^3) 풀이 O(N^2) 풀이 2023/01/06 추가 Knuth's Optimization을 적.. 이전 1 2 다음
