본문 바로가기

전체 글

 (147)
문제 해결력을 높이는 알고리즘과 자료 구조 16장 연습 문제 풀이 GitHub - hijkl2e/drken1215_algorithm_solution: 문제 해결력을 높이는 알고리즘과 자료 구조 연습 문제 풀이 문제 해결력을 높이는 알고리즘과 자료 구조 연습 문제 풀이. Contribute to hijkl2e/drken1215_algorithm_solution development by creating an account on GitHub. github.com 연습 문제 16.3번은 너무 복잡하게 푼 것 같아 저자의 풀이를 봤는데 똑같았다. 코드가 단순하지는 않았는데 나름 재미있는 문제였다. 연습 문제 16.5번은 아무리 머리를 굴려도 그래프 모델링이 되지 않아 힌트를 찾아보았다. 찾아보니 Kőnig's theorem을 모르면 풀 수 없는 문제였다. 2차원 격자가 주어지..
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라고 하면 반복 횟수는 최대 ..
문제 해결력을 높이는 알고리즘과 자료 구조 15장 연습 문제 풀이 GitHub - hijkl2e/drken1215_algorithm_solution: 문제 해결력을 높이는 알고리즘과 자료 구조 연습 문제 풀이 문제 해결력을 높이는 알고리즘과 자료 구조 연습 문제 풀이. Contribute to hijkl2e/drken1215_algorithm_solution development by creating an account on GitHub. github.com 연습 문제 15.2번은 proof by AC로 증명하였다. 유용한 성질인 듯 하여 잘 정리해놓았다. 연습 문제 15.3번은 이전 문제에서 얻은 성질을 이용해보려 하였으나 잘 되지 않았다. 결국 에디토리얼을 봤는데 감탄사가 나왔다. 끝
문제 해결력을 높이는 알고리즘과 자료 구조 14장 연습 문제 풀이 GitHub - hijkl2e/drken1215_algorithm_solution: 문제 해결력을 높이는 알고리즘과 자료 구조 연습 문제 풀이 문제 해결력을 높이는 알고리즘과 자료 구조 연습 문제 풀이. Contribute to hijkl2e/drken1215_algorithm_solution development by creating an account on GitHub. github.com 연습 문제 14.5번은 에디토리얼을 보고 풀었다. 정점 개수는 K개로 줄였으나 간선 개수를 ϕ(K)개에서 줄이지 못하였다. 에디토리얼에서는 정말 간단하게 간선 개수를 2개로 줄인다. 또한 0-1 BFS에서는 동일한 정점이 덱에 2번까지 들어갈 수 있다. 이 부분 때문에 WA를 받았다. 오늘은 못 풀었어도 매일 발전..
문제 해결력을 높이는 알고리즘과 자료 구조 13장 연습 문제 풀이 GitHub - hijkl2e/drken1215_algorithm_solution: 문제 해결력을 높이는 알고리즘과 자료 구조 연습 문제 풀이 문제 해결력을 높이는 알고리즘과 자료 구조 연습 문제 풀이. Contribute to hijkl2e/drken1215_algorithm_solution development by creating an account on GitHub. github.com 연습 문제 13.6번은 간결하게 구현하려고 열심히 노력하였다. 여러 소스를 참고하였는데 현재 코드가 그나마 만족스럽다. 끝
문제 해결력을 높이는 알고리즘과 자료 구조 12장 연습 문제 풀이 GitHub - hijkl2e/drken1215_algorithm_solution: 문제 해결력을 높이는 알고리즘과 자료 구조 연습 문제 풀이 문제 해결력을 높이는 알고리즘과 자료 구조 연습 문제 풀이. Contribute to hijkl2e/drken1215_algorithm_solution development by creating an account on GitHub. github.com 연습 문제 12.5번과 12.6번은 굉장히 어렵다. 연습 문제 12.5번은 단순히 quickselect 알고리즘을 구현하는 문제인 줄 알았다. 이 경우 평균 시간 복잡도는 O(N)이 되어 문제의 조건을 만족한다. 자세히 보니 최악 시간 복잡도가 O(N)인 알고리즘을 설계하는 문제였다. 이 문제는 median of ..
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) 끝

티스토리툴바