문제 https://www.acmicpc.net/problem/1017 1017번: 소수 쌍 지민이는 수의 리스트가 있을 때, 이를 짝지어 각 쌍의 합이 소수가 되게 하려고 한다. 예를 들어, {1, 4, 7, 10, 11, 12}가 있다고 하자. 지민이는 다음과 같이 그룹지을 수 있다. 1 + 4 = 5, 7 + 10 = 17, 11 www.acmicpc.net 풀이 solved.ac 난이도: Platium 3 짝수와 홀수로 두 집합을 만들어 이분 매칭으로 해결하는 문제. 이분 매칭을 잘 모른다면 다음 기본 문제를 먼저 해결해보고 오자. [백준] No.2188 - 축사 배정 (C++, 이분 매칭) 두 자연수를 더하는 경우는 3가지로 분류할 수 있다. 1. 짝수 + 짝수 짝수끼리 더한 수는 짝수이기 때문..

문제 https://www.acmicpc.net/problem/9577 9577번: 토렌트 희원이가 사용하는 ACM토렌트는 하나의 파일을 공유받을 때 여러 조각으로 나누어, 조각을 지닌 시드가 접속하는 시간에 시드로 부터 일부 조각을 전송 받아 파일을 완성시키는 방법으로 파일이 www.acmicpc.net 풀이 solved.ac 난이도: Platium 4 두 집합의 대응 관계를 해결하는 이분 매칭 문제. 기본 적인 이분 매칭 문제를 해결하고 오면 이해하기 쉬울 것이다. [백준] 축사 배정(2188) 이번 문제에서 두 집합으로 선택되는 것은 시간(A set)과 조각(B set)이다. 파일이 어떤 시더에게 있는지는 상관없이, 접속 시간에 해당 파일을 다운로드할 수 있는 여부가 중요하기 때문이다. 따라서 시더..

문제 https://www.acmicpc.net/problem/2188 2188번: 축사 배정 농부 존은 소 축사를 완성하였다. 축사 환경을 쾌적하게 유지하기 위해서, 존은 축사를 M개의 칸으로 구분하고, 한 칸에는 최대 한 마리의 소만 들어가게 계획했다. 첫 주에는 소를 임의 배정해 www.acmicpc.net 풀이 solved.ac 난이도: Platium 4 이분 매칭 문제들은 최대 유량을 이용하면 간단히 해결할 수 있다. [네트워크 유량] Network Flow(최대 유량, 최소 컷) 알고리즘 이분 매칭 문제는 두 집합에서의 대응 관계를 해결할 수 있다. 대표적으로 작업 배분을 한다고 생각해보자. A집합(인원)이 할 수 있는 B집합(작업)들 중 하나 선택하여 배정받는다. 이때 최대한의 작업을 할 수..

문제 https://www.acmicpc.net/problem/11495 11495번: 격자 0 만들기 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n과 m (2 ≤ n, m ≤ 50)이 주어지며, n은 격자의 행 개수, m은 격자의 열 개수를 나타낸다. 그 다음 n개의 줄에 각각 www.acmicpc.net 풀이 solved.ac 난이도: Platium 2 그래프 모델링이 필요한 최대 유량 문제. 문제의 설명에서는 연산을 한 번씩 진행하여 각 정수를 1씩 줄이지만 생각해보면 어떤 정수끼리 짝을 짓는 가는 중요하지 않다. 예제의 입력을 생각해보면 어떤 짝이든 짝지은 두 정수를 최대한 줄여주면 결과는 동일하다. 여기서 연산을 한번 진행할 때 전체 값의 합은 2씩 줄어드는..

문제 https://algospot.com/judge/problem/read/MATCHFIX algospot.com :: MATCHFIX 승부조작 문제 정보 문제 한때 세계대회 준우승까지 하며 최강의 프로그래머로 칭송 받았던 J씨는 성적이 떨어진 이후 유혹을 이기지 못하고 승부 조작의 세계에 손을 댔습니다. 프로그래밍 대 algospot.com 풀이 종만북 난이도: 중 이 문제를 최대 유량(네트워크 유량)으로 해결하는 방법은 다음과 같다. 이번 문제에서 유량은 승리의 횟수로 생각해 보자. 1. Source에서 각 결승 경기로의 간선 경기는 단 한 번씩만 진행할 수 있기 때문에 간선의 용량은 1로 설정해주자. 결국 모든 경기는 진행되어야 하므로 source에서 각 경기로는 1의 유량이 흐르게 된다. 2. ..

문제 https://www.acmicpc.net/problem/2316 2316번: 도시 왕복하기 2 N개의 도시가 P개의 양방향 길로 연결되어 있다. 이석원은 1번 도시와 2번 도시 사이를 오가며 워해머를 한다. 성실한 이석원은 두 도시 사이를 최대한 많이 왔다 갔다 하려 하는데, 이때 한 번 방 www.acmicpc.net 풀이 solved.ac 난이도: Platium 3 정점 분할 테크닉을 통해 풀어야 하는 최대 유량 문제. 최대 유량에 대해서 잘 모른다면 다음 게시글을 참조하자. [네트워크 유량] Network Flow(최대 유량, 최소 컷) 알고리즘 정점 분할이란 정점에도 간선처럼 가중치를 주기 위해 정점을 하나의 간선으로 만드는 기법이다. 이때 간선을 정점처럼 취급하기 위해 정점을 두개의 정점..

문제 https://www.acmicpc.net/problem/1420 1420번: 학교 가지마! 첫째 줄에 도시의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 100) 둘째 줄부터 N개의 줄에 도시의 모양이 주어진다. 비어있으면 점('.'), 벽은 '#', 도현이의 위치는 K, 학교의 위치는 H이다. www.acmicpc.net 풀이 solved.ac 난이도: Platium 2 최소 컷 (최대 유량)알고리즘에 정점 분할을 적용해야 하는 문제. 정점 분할이란 정점에도 간선처럼 가중치를 주기 위해 정점을 하나의 간선으로 만드는 기법이다. 이때 간선을 정점처럼 취급하기 위해 정점을 두개의 정점(in과 out)으로 분할 한다. in정점은 해당 정점으로 들어오는 간선들과 연결해주고 out정점..

문제 https://www.acmicpc.net/problem/6086 6086번: 최대 유량 첫째 줄에 정수 N (1 ≤ N ≤ 700)이 주어진다. 둘째 줄부터 N+1번째 줄까지 파이프의 정보가 주어진다. 첫 번째, 두 번째 위치에 파이프의 이름(알파벳 대문자 또는 소문자)이 주어지고, 세 번째 위 www.acmicpc.net 풀이 solved.ac 난이도: Platium 4 이름부터가 최대 유량인 최대 유량 문제. 최대 유량 알고리즘과 이번 풀이의 기본 지식을 알기 위해 다음 게시글을 참고 하자. [네트워크 유량] Network Flow(최대 유량, 최소 컷) 알고리즘 기본적인 최대 유량 알고리즘을 적용하기에는 약간 다른 점이 있는데 파이프는 양방향으로 존재하고 같은 두 정점이 여러 간선으로 이어질..

[네트워크 유량] Network Flow(최대 유량) 그래프에서 두 정점 사이에 얼마나 많은 유량(flow)을 보낼 수 있는지 계산하는 알고리즘을 네트워크 유량(Network Flow) 혹은 최대 유량(Maximum Flow) 알고리즘이라고 합니다. 일단 해당 알고리즘에서 사용하는 용어부터 설명하겠습니다. (네트워크 유량 알고리즘에서 간선은 두 정점을 잇는 파이프라고 생각하면 이해하기 쉽습니다.) 용량(Capacity) c(u, v)는 정점 u에서 v로 가는 간선의 용량(가중치)라고 합니다. 유량(Flow) f(u, v)는 정점 u에서 v로의 간선에 실제로 흐르는 유량을 의미합니다. 잔여 용량(Residual Capacity) 간선의 용량과 유량의 차이를 의미합니다. r(u, v) = c(u, v) - ..

문제 https://www.acmicpc.net/problem/4792 4792번: 레드 블루 스패닝 트리 무방향, 무가중치, 연결 그래프가 주어진다. 그래프의 각 간선은 빨간색 또는 파란색으로 색칠되어져 있다. 이 그래프의 스패닝 트리 중 파란색 간선이 정확히 k개인 것이 있는지 없는지 알아내 www.acmicpc.net 풀이 solved.ac 난이도: Platium 3 최소 스패닝 트리(MST)를 적용하여 해결하는 문제. 처음에는 어떤 부분이 MST 문제인지도 감을 못 잡아서 결국 다른 분의 풀이를 보고 해결했다. 4Legs_Archives님의 [백준]레드 블루 스패닝 트리 풀이 문제의 풀이는 난이도에 비해 간단하지만 증명을 어떻게 유도하는 것이 어려웠다. 일단 풀이는 다음과 같다. 1. 파란 간선의..