문제 링크 https://www.acmicpc.net/problem/6233 문제 요약 \(N\)마리의 소들이 일렬로 서 있다. 이 소들은 앞을 보고 있거나 뒤를 보고 있다. 이 때 이 소들에 대해서 다음과 같은 연산을 할 수 있다. 1. 특정 길이 \(L\)을 정한다. 이 값은 변하지 않는다. 2. 정확히 \(L\)마리의 연속된 소들의 상태를 반전시킬 수 있다. 3. 상태를 반전시킨다는 것은 앞을 보고 있는 소는 뒤를 보고, 뒤를 보고 있는 소들은 앞을 보는것이다. 2번 연산을 최소한으로 사용해 모든 소들을 앞을 보게 하는것이 문제다. 만약 최소한의 연산 횟수를 가지는 \(L\)이 여러가지면 그중에 작은것을 출력한다. 문제 풀이 우선 문제를 간단하게 만들기 위해 \(L\)이 정해져 있다고 생각을 해보자..
문제 링크 https://www.acmicpc.net/problem/2196 문제 요약 \(B\)자리의 2진수 \(E\)개가 주어진다. 이제 이진수를 두개씩 선택해서 XOR을 진행한다. 이 과정에서 만들어지는 수 또한 선택할 수 있다. 이렇게 해서 만들 수 있는 이진수들 중 이진수 \(S\)와 해밍거리가 가장 가까운 수를 출력하는 문제다. 문제 풀이 이 문제를 어렵게 만드는 요소 중 하나는 XOR과정에서 만들어진 수 또한 XOR연산에 사용할 수 있다는 점이다. 하지만 XOR의 특징을 잘 생각해 본다면 이 문제를 쉽게 해결할 수 있다. \(A\), \(B\), \(C\), \(D\) 네 개의 이진수가 있다고 가정하자. \(A \oplus B\)를 통해 \(X\)를 만들고 \(C \oplus D\)를 통해 ..
문제 링크 https://www.acmicpc.net/problem/7453 문제 요약 길이가 \(N\)인 네 개의 배열이 주어진다. 이 때 네 개의 배열에서 각각 한개의 수를 뽑아 더했을 때 이 합이 0이 되는 경우의 수를 구하는 문제다. 문제 풀이 일단 모든 경우를 전부 보면 \(O(N^4)\)이기 때문에 시간초과가 나기 때문에 다른 방법이 필요하다. 우선 네 개의 배열 \(A\), \(B\), \(C\), \(D\)이 있다. 이 때 \(A\)와 \(B\)의 가능한 모든 합을 저장한 배열을 \(X\), \(C\)와 \(D\)의 가능한 모든 합을 저장한 배열을 \(Y\)라고 하자. 이 때 \(X\)에서 어떠한 수 한개를 뽑고, \(Y\)에서 어떠한 수 한개를 뽑아 이 수가 \(0\)이 된다고 생각을 해..
- Total
- Today
- Yesterday
- Binary Search
- Data Structure
- DP
- disjoint set
- brute force
- Sqrt Decomposition
- max flow
- greedy
- graph
- bipartite matching
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 | 31 |