-
Mo's Algorithm on Trees
이 게시글은 LCA(lowest common ancestor)에 대한 지식이 선행되어야 하지만 본 글에서는 소개하지 않습니다. Mo’s Algorithm이란? Mo’s algorithm은 평방 분할(sqrt decomposition)의 일종의 활용 기법으로, 오프라인으로 구간 쿼리 문제를 해결할 때 사용할 수 있습니다. 이미 이에 관한 좋은 글이 있어 (링크)로 대체하겠습니다. Mo’s Algorithm on Trees? 위 Mo’s Algorithm을 Tree에서 하는 것을 의미합니다. Mo’s는 앞서 말씀드렸던 것처럼 구간 쿼리 문제를 해결할 때 쓰이기 때문에 트리에서의 쿼리를 구간 쿼리처럼 나타낼 필요가 있는데요. 이를 Euler Tour on Trees를 이용하여...
-
최대 이분 매칭에 관한 몇 가지 정리
이분 그래프(Bipartite Graph)에서의 최대 매칭(Maximum Matching)은 최대 유량(Maximum Flow)과 같습니다. 이 글에서는 위와 같이 최대 유량과 최대 이분 매칭에 관한 기본적인 문제를 해결 할 수 있는 분들을 위해 최대 이분 매칭에 관한 대표적인 정리를 예제와 함께 다룹니다. 구성은 아래와 같습니다. Minimum Vertex Cover - BOJ 1867 돌멩이 제거 Maximum Independent Set - BOJ 11014 컨닝 2 Minimum Path Cover - BOJ 1671 상어의 저녁식사 Maximum Anti-Chain - BOJ 13441 마법의 나무 Minimum Vertex Cover Vertex...
-
Flow with demands
목차 1. 개요 2. Demands(수요)가 대체 뭐야? 3. Flow with demands 해결법 4. 응용 5. 문제풀이 6. 마무리 7. 참고자료 개요 이번에 소개할 알고리즘은 Flow with demands 입니다. 보통의 간선에 흐를 수 있는 유량에 상한이 있는 최대 유량 문제와 다르게 하한이 있는 최대 유량 문제를 효과적으로 해결하는 알고리즘 이며, 2016년도 한국 ACM-ICPC 예선 H번에서 이 알고리즘을 사용하게 됩니다. 기본적인 아이디어와 작동원리 등을 설명하고 실제로 문제풀이에 어디에 쓰이는지 보이고자 합니다. 일단 기본적으로 최대 유량에 대한 기본...
-
Rabin-Karp 해싱의 충돌쌍 찾기
안녕하세요, 이번 글에서는 Rabin-Karp 해싱의 충돌쌍을 찾는 다양한 방법에 대해 알아보겠습니다. Rabin-Karp 해싱이란? Rabin-Karp 해싱은 문자열의 해쉬함수입니다. 이 글의 내용에서 알 수 있듯이 암호학적으로 안전한 함수는 아니지만 $O(N)$의 전처리를 거치고 나면 문자열 내의 임의의 substring의 해쉬 값을 $O(1)$에 알 수 있다는 특성 덕분에 해당 특성이 필요할 때 활용하면 효과적입니다. 또한 구현이 쉬운 편이기 때문에 굳이 암호학적으로 안전한 함수가 필요없는 상황일 경우에는 Java와 기본 String hashcode를 포함한 다양한 곳에서 사용되고 있습니다. 해싱에 대한 자세한 설명은 제...
-
강화학습 핵심 개념 정리 (1)
강화학습 핵심 개념 정리 (1) Reinforcement Learning Key Concepts 이 시리즈의 목표는 강화학습을 잘 모르는 사람이 해당 분야의 전반적인 흐름을 파악하고 이 글을 토대로 세부적인 내용을 찾아볼 수 있게 하는 것입니다. 이번 글에서는 여러가지 주요 용어를 살펴보고, 다음 글에서는 Q learning 과 Policy Gradient 에 대해서 살펴보겠습니다. 문제 정의 강화학습에서 다루는 문제가 어떤 것인지부터 살펴봅시다. 주변 상태에 따라 어떤 행동을 할지 판단을 내리는 주체인 에이전트가 있고, 에이전트가 속한 환경이 있습니다. 에이전트가 행동을 하면 그에 따라...