문제 링크 https://www.acmicpc.net/problem/1960 문제 요약 \(N*N\)행렬의 각 열들의 합과 각 행들의 합이 주어졌을 때 원본 행렬을 복구해 출력하는 문제다. 원본 행렬이 가질 수 있는 값은 0또는 1이다. 물론 만들지 못하는 경우도 주어질 수 있으며 이때는 -1을 출력한다. 문제 풀이 이 문제는 전형적인 네트워크 플로우로 문제다.(그리디로도 해결이 가능하다고 한다.) 모델링 또한 너무 간단하다. 우선 왼쪽에는 각 행들을 대표할 수 있는 정점들을 두고 오른쪽에는 각 열들을 대표할 수 있는 정점들을 둔다. 그리고 소스와 왼쪽 정점들을, 싱크와 오른쪽 정점들을 연결해준다. 각각의 \(capacity\)는 행들의 합과 열들의 합으로 설정해 준다. 그 뒤 행들을 대표하는 정점들과 ..
원소들을 효율적으로 관리해야할 일이 있을때 우리는 어떤 전략을 선택해야할까? 원소들을 효율적으로 관리하는 방법은 여러가지가 있다. 이번에는 그 중 하나인 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\)의 쌍을 하나의 정점으로 생각하고 \(+,-,*\)한 결과들에 간선을 연결해 보자. 예제 입력을 그래프로 모델링하면 아래와 같은 결과가 나온다. 그..
문제 링크 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\)로 접근을 하기 쉽다. 하지만 그렇게 접근을 시작하는 순간 문제는 미궁으로 빠지게 된다. 그렇다면 어떻게 접근을 해야할까? 우선 아래와 같은 격자판이 있다고 가정을 해보자. 위 격자판을 그래프로 생각해보자. 정점은 각각의 열과 행이고 돌멩이가 있는 칸은 열과 행을 잇는 간선이라고 생각을 한다. 그렇다면 그래프는 아래와 같이 그려진다. 만약에 \..
문제 링크 https://www.acmicpc.net/problem/2843 문제 요약 \(N\)개의 정점가 \(N\)개의 간선을 가지는 방향그래프가 주어진다. 각각의 정점은 최대 한개의 나가는 간선을 가질 수 있다. 이 때 두 가지의 쿼리를 처리해야 한다. 첫 번재 쿼리는 \(x\)번 정점에서 나가는 간선을 지우는 것이도 두 번째 쿼리는 \(x\)번 정점에서 나가는 간선을 따라 계속해서 움직일 때 마지막으로 도착하는 정점이 어디인지, 만약 영원히 끝나지 않는다면 영원히 끝나지 않는다고 출력을 해야 한다. 문제 풀이 연결된 그래프에서 간선을 지워서 두개의 분리된 그래프로 만드는 작업은 생각보다 어려운 일이다. 하지만 반대로 두개의 분리된 그래프를 하나로 합쳐 새로운 그래프를 만드는 작업은 꽤 쉬운 일이다..
방향 그래프가 주어졌을 때 종종 이 그래프 내에서 \(Cycle\)의 존재 유무를 확인해야 할 때가 있다. 이 글에서는 방향 그래프 내에서 싸이클의 존재 유무를 알아내는 알고리즘을 소개하려 한다.기본적인 알고리즘\(Cycle\)의 정의를 한번 생각해 보자. \(Cycle\)이란 정점 \(u\)에서 시작해 어떠한 경로를 지나 다시 \(u\)로 돌아오는 경로가 있다면 이를 \(Cycle\)이라고 한다. 그리고 그래프 내에 이러한 \(Cycle\)이 한개라도 있다면 \(Cycle\)이 존재하는 그래프가 된다. 그렇다면 특정한 시작 정점 \(u\)를 잡고 \(dfs\)를 실행해 다시 시작정점 \(u\)로 돌아오는 경로가 있는지 확인하는 알고리즘을 만든 뒤 모든 정점에 대해 해당 알고리즘을 실행하면 \(Cycle..
문제 링크 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\)를 통해 ..
