이분 매칭 알고리즘 이분 매칭이란? 이분 매칭을 알기 전에 ‘이분 그래프’라는 것을 먼저 알아야한다. 그래프에서, 정점 그룹을 2개로 완벽하게 분할할 수 있다면 이분 그래프(Bipartite Graph) 라고 한다. 정점 그룹을 완벽하게 분할한다는 것은 “같은 그룹의 정점으로 연결되어 있는 간선이 없도록” 정점을 그룹짓는 것을 말한다. 그래...

문제 링크 : https://www.acmicpc.net/problem/1017 1017 - 소수 쌍 본문 지민이는 수의 리스트가 있을 때, 이를 짝지어 각 쌍의 합이 소수가 되게 하려고 한다. 예를 들어, $\lbrace 1, 4, 7, 10, 11, 12 \rbrace$가 있다고 하자. 지민이는 다음과 같이 짝지을 수 있다. $1 ...

문제 링크 : https://www.acmicpc.net/problem/12100 12100 - 2048 (Easy) 본문 2048 게임은 $4 \times 4$ 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다. 이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로...

문제 링크 : https://www.acmicpc.net/problem/9466 9466 - 텀 프로젝트 본문 이번 가을학기에 ‘문제 해결’ 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해...

문제 링크 : https://www.acmicpc.net/problem/9328 9328 - 열쇠 본문 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 필요하다. 상근이는 일부 열쇠를 이미 가지고 있...

문제 링크 : https://www.acmicpc.net/problem/2623 2623 - 음악프로그램 본문 인터넷 방송 KOI(Korea Open Internet)의 음악 프로그램 PD인 남일이는 자기가 맡은 프로그램 ‘뮤직 KOI’에서 가수의 출연 순서를 정하는 일을 매우 골치 아파한다. 순서를 정하기 위해서는 많은 조건을 따져야 ...

문제 링크 : https://www.acmicpc.net/problem/2473 2473 - 세 용액 본문 KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내...

문제 링크 : https://www.acmicpc.net/problem/2470 2470 - 두 용액 본문 KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 $1$부터 $1\,000\,000\,000$까지의 양의 정수...

문제 링크 : https://www.acmicpc.net/problem/2467 2467 - 용액 본문 KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 $1$부터 $1\,000\,000\,000$까지의 양의 정수로...

문제 링크 : https://www.acmicpc.net/problem/1006 1006 - 습격자 초라기 본문 초라기는 한국의 비밀국방기지(원타곤)를 습격하라는 임무를 받은 특급요원이다. 원타곤의 건물은 도넛 형태이며, 초라기는 효율적인 타격 포인트를 정하기 위해 구역을 아래와 같이 두 개의 원 모양으로 나누었다. (그림의 숫자는 각 구...