문제 링크 https://www.acmicpc.net/problem/2843 문제 요약 \(N\)개의 정점가 \(N\)개의 간선을 가지는 방향그래프가 주어진다. 각각의 정점은 최대 한개의 나가는 간선을 가질 수 있다. 이 때 두 가지의 쿼리를 처리해야 한다. 첫 번재 쿼리는 \(x\)번 정점에서 나가는 간선을 지우는 것이도 두 번째 쿼리는 \(x\)번 정점에서 나가는 간선을 따라 계속해서 움직일 때 마지막으로 도착하는 정점이 어디인지, 만약 영원히 끝나지 않는다면 영원히 끝나지 않는다고 출력을 해야 한다. 문제 풀이 연결된 그래프에서 간선을 지워서 두개의 분리된 그래프로 만드는 작업은 생각보다 어려운 일이다. 하지만 반대로 두개의 분리된 그래프를 하나로 합쳐 새로운 그래프를 만드는 작업은 꽤 쉬운 일이다..
문제 링크 https://www.acmicpc.net/problem/1704 문제 요약 \(N*M\)크기의 격자판이 주어진다. 이 격자판에는 0또는 1이 적혀져 있는데 \((x, y)\)를 누르면 \((x, y)\)를 포함 상, 하, 좌, 우 이렇게 다섯개 칸의 상태가 토글된다. 최소한의 연산 횟수를 통해 격자판의 모든 수를 0으로 만드는것이 목표다. 최소한의 연산 횟수를 가지는 것이 여러개라면 사전순으로 빠른 답을 출력한다. 문제 풀이 상태가 토글된다는 것이 이 문제를 푸는 핵심이다. \((x, y)\)를 누르면 해당 칸과 주위 네 방향이 같이 토글된다. 이 때 동일한 칸을 두 번 이상 누를 필요가 없다. 왜냐하면 두번 이상 누르는 순간 기존의 상태와 똑같아 지거나 한번 누른 상태와 똑같아 지기 때문이..
문제 링크 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\)이 된다고 생각을 해..
문제 링크 https://www.acmicpc.net/problem/1090 문제 요약 \(N\)개의 점이 주어진다. 이 때 적어도 한개의 점이 한 점위에 있도록 하기위해 움직이는 최소 횟수 , 적어도 두 개의 점이 한 점위에 있도록 하기위해 움직이는 최소 횟수, ... 적어도 \(N\)개의 점이 한 점위에 있게 하기위해 움직이는 최소 횟수를 구하는 문제다. 문제 풀이 모든 점을 모으는 것이 아니라는 것이 이문제를 어렵게 만드는 요소 중 하나다. 하지만 모든 점을 모으는데 있어 최선의 선택은 \(x\)좌표들의 중앙값, \(y\)좌표들의 중앙값으로 모이는게 최선이라는 생각을 살짝 변형하면 쉽게 풀 수 있다. (\(N\)개의 점을 모두 모으는데 왜 중앙값이 최선이냐에 대해서는 완벽하게 증명을 하진 못하겠다...
문제 링크 https://www.acmicpc.net/problem/1814 문제 요약 크기가 \(N\)인 트리가 주어진다. 이 트리의 정점들을 \(M\)가지의 색으로 칠하려고 하는데 각각의 색들은 색을할 할 때 비용이 든다. 또한 인접한 정점은 서로 색이 달라야 한다. 제약조건을 지키면서 모든 정점들을 칠할 때 드는 최소 비용을 구하는 문제다. 문제 풀이 주어지는 입력이 트리이기 때문에 \(dp\)로 쉽게 풀릴것 같은 생각이 든다. 아래와 \(dp\ table\)을 생각해보자. \(dp[here][color]=\ \)\(here\)를 \(color\)로 색칠하고 \(here\)의 \(subtree\)를 색칠하는데 드는 최소 비용 이 식은 어떻게 채워질 수 있을까? 이식은 아래와 같을 것이다. \(dp[..
문제 링크 https://www.acmicpc.net/problem/1787 문제 요약 문제가 이해를 하기 조금 힘들지만 결국 하는말은 다음과 같다. 어떠한 문자열 \(X\)가 있다고 가정을 하자. 이 때 \(X\)의 \(Prefix\)와 \(Suffix\)를 구하는데 이 때 빈 문자열이면 안되고 서로 동일한 길이여야 한다. 이렇게 뽑았을 때 \(Prefix\)와 \(Suffix\)가 같은 0이 아닌 가장 작은 길이를 구한다음에 \(X\)의 길이에서 뺀뒤 이 값을 답에 누적한다. 이러한 과정을 문자열 \(S\)가 주어지면 \(S\)의 모든 \(Prefix\)에 대해서 반복한다. 문제 풀이 주어지는 문자열 \(S\)의 길이가 \(10^6\)이기 때문에 빠른 풀이를 생각해야 한다. 결론부터 얘기하면 이 문제..
문제 링크 https://www.acmicpc.net/problem/13352 문제 요약 문제는 정말 간단하다. \(N\)개의 2차원 정수 좌표가 주어진다. 모든 좌표들이 최대 두개의 직선위에 놓일 수 있는가, 없는가를 판단하는 문제다. 문제 풀이 이 문제를 풀 수 있는 솔루션은 여러가지가 존재하지만 재미있는 방법 한가지를 소개하려 한다. 아래와 같은 프로그램을 상상해보자. 1. \(N\)개의 점중에 서로 다른 두 개의 점을 임의로 뽑자. 이 때 임의의 두 점을 이어 만든 직선을 \(A\)라고 하자. 2. 직선 \(A\)위에 존재하지 않는 점들이 새로운 직선 \(B\)위에 놓일 수 있는지 확인한다. 3. 만약 가능하다면 최대 두개의 직선으로 모든 좌표를 덮을 수 있다. 4. 만약 불가능 하다면 1번으로 ..
문제 링크 https://www.acmicpc.net/problem/2271 문제 요약 자연수로 이루어진 크기 \(N\)인 배열 \(A\)가 주어진다. 이 때 \(1\leq P\ \lt\ Q\ \lt\ R\ \lt\ S\ \leq\ N\)을 만족하는 \(P\), \(Q\), \(R\), \(S\)에 대해 아래 두가지 수식이 만족하는 경우가 있는지 찾는 문제다. 1. \(A[Q]\ \lt\ A[S]\ \lt\ A[P]\ \lt\ A[R]\) 2. \(A[Q]\ \gt\ A[S]\ \gt\ A[P]\ \gt\ A[R]\) 문제 풀이 우선 2번 경우는 생각하지 말고 1번 경우만 생각해 보도록 하자. \(i\lt j\) 인 임의의 \(i\), \(j\)를 선택했다고 하자. 만약 \(A[i] \lt A[j]\)를..
- Total
- Today
- Yesterday
- brute force
- Sqrt Decomposition
- DP
- max flow
- greedy
- disjoint set
- graph
- bipartite matching
- Binary Search
- Data Structure
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |