문제 링크 https://www.acmicpc.net/problem/13344 문제 요약 수식이 주어졌을 때 주어진 수식들이 일관성이 있는지 혹은 모순이 있는지 찾아내는 문제다. 문제 풀이 수식은 크게 두가지 종류가 존재한다. 1. \(u = v\) : \(u\)와 \(v\)는 같다 2. \(u \gt v\) : \(u\)가 \(v\)보다 크다 만약 1번 수식이 없다고 생각을 해보자. 1번 수식이 없고 2번 수식만 있을 때 주어진 수식들이 일관성이 있는지 없는지 어떻게 판단을 할 수 있을까? \(u\)와 \(v\)가 나오고 \(\gt\)가 화살표 처럼 생겼으므로 \(u\)에서 \(v\)로 향하는 방향 그래프를 만들어 보자. 이 때 만약 \(Cycle\)이 있으면 어떻게 될까? \(Cycle\)이 존재하도..
문제 링크 https://www.acmicpc.net/problem/1208 문제 요약 크기 \(N\)인 집합이 주어진다. 이 때 부분집합의 합이 \(S\)가 되는 경우의 수를 구하는 문제다. 문제 풀이 \(N\)이 최대 40이기 때문에 완전탐색으로는 안된다. 따라서 다른 방법이 필요하다. 이런 경우에는 왼쪽 절반과 오른쪽 절반의 모든 경우의 수를 각각 구하고 이분탐색을 통해 이 경우의 수를 합쳐나갈 수 있다. 크기 \(N\)인 집합을 왼쪽부터 \(N \above 1pt 2\)개의 완전탐색 경우의 나머지 오른쪽의 완전탐색 경우를 다 구해 놓는다. 이 때 왼쪽의 경우의 수와 오른쪽 경우의 수를 어떻게 합쳐야 할까? 왼쪽의 경우 중 가능한 한가지 합이 \(x\)라고 가정을 해 보자. 그렇다면 오른쪽 경우의 ..
문제 링크 https://www.acmicpc.net/problem/1867 문제 요약 \(N*N\)격자판위에 돌맹이들이 놓여져 있다. 한번의 작업으로 한개의 행이나 한개의 열에 있는 돌멩이를 모두 제거할 수 있다. 이 때 최소 몇번의 작업을 해야 격자판 위에 있는 돌멩이를 모두 제거할 수 있는지 구하는 문제다. 문제 풀이 처음 이 문제를 본다면 \(greedy\)로 접근을 하기 쉽다. 하지만 그렇게 접근을 시작하는 순간 문제는 미궁으로 빠지게 된다. 그렇다면 어떻게 접근을 해야할까? 우선 아래와 같은 격자판이 있다고 가정을 해보자. 위 격자판을 그래프로 생각해보자. 정점은 각각의 열과 행이고 돌멩이가 있는 칸은 열과 행을 잇는 간선이라고 생각을 한다. 그렇다면 그래프는 아래와 같이 그려진다. 만약에 \..
- Total
- Today
- Yesterday
- bipartite matching
- Data Structure
- brute force
- greedy
- DP
- disjoint set
- Binary Search
- Sqrt Decomposition
- graph
- max flow
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |