원소들을 효율적으로 관리해야할 일이 있을때 우리는 어떤 전략을 선택해야할까? 원소들을 효율적으로 관리하는 방법은 여러가지가 있다. 이번에는 그 중 하나인 Sqrt Decomposition에 대해 알아보도록 하자. Sqrt Decomposition에서 Sqrt는 Square root의 약자다. 이를 우리나라 말로 번역하자면 평방분할이라고 한다. 하지만 의미적으로 별로 와닿지 않는다고 생각하기 때문에 Sqrt Decomposition이라고 하겠다. 연속적인 원소들을 하나의 묶음으로 Sqrt Decomposition의 기본 아이디어는 정말 간단하다. 연속적인 원소들을 하나의 묶음으로 생각하자는 것이다. 이 때 한 묶음의 크기는 보통 \(\sqrt N\)으로 잡는다.(그래서 Square root라는 이름이 붙은..
문제 링크 https://www.acmicpc.net/problem/6241 문제 요약 \(N\)마리의 소와 \(F\)개의 음식, \(D\)개의 음료가 주어진다. 각각의 소들은 식성이 다 다르기 때문에 좋아하는 음료, 음식들이 전부 다 다르다. 소들은 자신이 좋아하는 음식들 중 한개와 자신이 좋아하는 음료들 중 한개를 동시에 먹을 때 행복하다고 느낀다. 모든 음식과 음료들은 한 소에게만 나눠줄 수 있을 때 행복한 소의 수를 최대로 만드는 문제다. 문제 풀이 얼핏 보면 이분 매칭과 흡사해 보일 수 있다. 하지만 이 문제는 소에게 음료와 음식을 동시에 할당해 줘야 하기때문에 이분 매칭으로는 풀 수 없다. 그렇다면 조금은 다른 풀이를 생각해야 한다. 이 문제에서는 소를 정 중앙에 두고 왼쪽에는 음식, 오른쪽에..
문제 링크 https://www.acmicpc.net/problem/11670 문제 요약 \(N\)개의 줄에 걸쳐 \(A_i\)와 \(B_i\)가 주어진다. 이 때 각각의 \(A_i\)와 \(B_i\)에 대해 \(+,-,*\)중 하나를 선택해서 나온 결과를 모두 다르게 하고 싶다. 이렇게 연산자들을 선택하는게 가능한지, 가능하다면 어떻게 선택해야 하는지 출력하는 문제다. 문제 풀이 \(N\)이 최대 \(2,500\)개가 들어오기 때문에 완전탐색으로는 불가능하다. 우리는 모든 계산의 결과가 유니크해야하다는 것에 주목할 필요가 있다. \(A_i\)와 \(B_i\)의 쌍을 하나의 정점으로 생각하고 \(+,-,*\)한 결과들에 간선을 연결해 보자. 예제 입력을 그래프로 모델링하면 아래와 같은 결과가 나온다. 그..
- Total
- Today
- Yesterday
- max flow
- disjoint set
- DP
- Sqrt Decomposition
- Data Structure
- greedy
- bipartite matching
- Binary Search
- brute force
- graph
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 |