복습 정리 노트

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 2533번 : '사회망 서비스(SNS)' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Gold III에 해당하며, 문제를 풀이하기 위해 DP의 응용에 대한 이해가 필요합니다. 2533번 : 사회망 서비스(SNS) 주어진 그래프에 대해 선택된 노드를 포함하여 1개의 간선을 통해 인접한 노드들까지 선택한다고 할 때, 모든 노드를 선택되게 하기 위해서는 최소 몇 개의 노드를 지정해야 하는지를 구하는 문제입니다. 가장 쉽게 떠올릴 수 있는 풀이는 DP를 이용하여, 가장 말단 노드부터 재귀적으로 하위 노드들을 모두 선택되게 하기 위해 몇 개의 노드를 지정해야 하는지를 기록해오면서 root 노드까지 계산해오는..

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 16726번 : '영과일 학회방' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Platinum III에 해당하며, 문제를 풀이하기 위해 이분 매칭 알고리즘에 대한 이해가 필요합니다. 16726번 : 영과일 학회방 16726번: 영과일 학회방 영과일은 학회방이 없어질 위기에 처했지만 우수한 학회원들의 실력을 인정받아 학회방을 다시 배정 받을 수 있었다! 이에 행복해진 영과일 총무부장 재현이는 새로운 마음으로 1 × 2, 1 × 1 타 www.acmicpc.net 이전에 네트워크 플로우로 풀이를 시도하다가 이분 매칭에 더 특화된 문제라는 것을 알고 보류했었던 문제입니다. X 표시된 칸을 피해서 '..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 3295번 : '단방향 링크 네트워크' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Platinum II에 해당하며, 문제를 풀이하기 위해 이분 매칭 알고리즘에 대한 이해가 필요합니다. 3295번 : 단방향 링크 네트워크 3295번: 단방향 링크 네트워크 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 상호 네트워크를 이루는 노드의 수 n과 단방향 링크의 수 m이 주어진다. (n ≤ 1,000, m ≤ 50,000) 노드는 0번부터 n-1 www.acmicpc.net 주어진 그래프를 선형 또는 링 형태의 그래프로만 구성되도록 분해한 뒤 그 때 가지는 간선의 ..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 11014번 : '컨닝 2' (+ 1014번 : '컨닝) 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Platinum II이며, 문제를 해결하기 위해 이분 매칭 알고리즘에 대한 이해가 필요합니다. 11014번 : 컨닝 2 11014번: 컨닝 2 최백준은 서강대학교에서 “컨닝의 기술”이라는 과목을 가르치고 있다. 이 과목은 상당히 까다롭기로 정평이 나있기 때문에, 몇몇 학생들은 시험을 보는 도중에 다른 사람의 답지를 베끼려 한 www.acmicpc.net 학생의 자리를 기준으로 왼쪽 위, 왼쪽, 오른쪽 위, 오른쪽 아래 자리는 컨닝이 가능하다고 할 때 아무도 컨닝을 하지 못하도록 배치할 수 ..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 12843번 : '복수전공' 문제의 풀이 코드를 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Platinum III에 해당하며, 문제를 풀이하기 위해 이분 매칭 알고리즘에 대한 이해가 필요합니다. 12843번 : 복수전공 12843번: 복수전공 강의의 개수 n (1 ≤ n ≤ 2,000) 과 수업 간 관계의 개수 m (1 ≤ m ≤ 1,000,000) 이 첫 줄에 주어진다. 다음 n 줄에 대하여 강의의 번호와 어느 학부의 강의인지 알려준다. 강의의 번호는 1부터 N으로 www.acmicpc.net 컴퓨터공학부 수업과 소프트웨어 학부의 겹치는 수업들을 빼고 수업을 듣는다고 할 때 수강할 수 있는 최대한 많은 수업의 수..

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 2570번 : '비숍2', 1799번 : '비숍' 문제의 풀이 코드와 해설을 다룹니다. 문제 난이도는 Solved.ac 기준 Platinum II에 해당하며, 문제를 풀이하기 위해 이분 매칭 알고리즘에 대한 이해가 필요합니다. (1799번의 비숍 문제의 난이도는 Gold I이지만, 이 포스트에서는 더 어려운 문제를 기준으로 풀이를 다룹니다.) 2570번 : 비숍2 2570번: 비숍2 첫째 줄에 정사각형 체스판의 크기 N이 주어진다. 둘째 줄에는 체스판 위에 놓인 장애물의 개수 M이 주어진다. N은 100이하의 자연수이고 M은 음이 아닌 정수이다. 이어 셋째 줄부터 한 줄에 하나 www.acmicpc.net 위와 같이 체스판 위의 ..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 9525번 : '룩 배치하기', 1760번 : 'N-Rook' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Platinum III에 해당하며, 문제를 풀이하기 위해 이분 매칭 알고리즘에 대한 이해가 필요합니다. 9525번 : 룩 배치하기 9525번: 룩 배치하기 체스와 관련된 문제는 처음 알고리즘을 배우기 시작할 때 부터 접하게 된다. 가장 유명한 문제로는 N-Queen 문제가 있다. 이를 변형해서 N-Rook 문제를 만들 수 있다. Rook(룩) 은 체스에서 같은 행이 www.acmicpc.net 빈칸과 폰의 위치를 나타내는 체스판의 입력이 주어졌을 때, 놓을 수 있는 최대 룩의 수를 구..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 2414번 : '게시판 구멍 막기' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Platinum III에 해당하며, 문제를 풀이하기 위해 이분 매칭 알고리즘과 쾨니그의 정리에 대한 이해가 필요합니다. 2414번 : 게시판 구멍 막기 2414번: 게시판 구멍 막기 첫째 줄에 N, M(1 ≤ N, M ≤ 50)이 주어진다. 다음 N개의 줄에는 M개의 문자로 게시판의 모양이 주어진다. 각각의 문자는 붙어 있으며, 구멍이 없는 부분은 '.', 구멍이 있는 부분은 '*'으로 주어진다. www.acmicpc.net 좌표에 주어진 구멍을 구멍이 아닌 칸은 막지 않으면서 일자 모양의 테이프들로 막을 때,..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 1867번 : '돌멩이 제거' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Platinum III 해당하며, 문제를 풀이하기 위해 이분 매칭 알고리즘과 쾨니그의 정리에 대한 이해가 필요합니다. (다만, 쾨니그의 정리에 대해서는 이 포스트에서 다룰 것입니다.) 1867번 : 돌멩이 제거 1867번: 돌멩이 제거 첫째 줄에 n과 k가 주어진다. (1 ≤ n ≤ 500, 1 ≤ k ≤ 10,000) 이후 k개의 줄에는 돌멩이의 위치가 한 줄에 하나씩 주어진다. 줄마다 첫 번째 숫자는 행 번호, 두 번째 숫자는 열 번호를 나타낸다. 입 www.acmicpc.net 격자판 구조에 K개의 돌멩이가 있..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 17402번 : '시간 끌기' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Platinum IV에 해당하며, 문제를 풀이하기 위해 이분 매칭 알고리즘에 대한 이해가 필요합니다. 17402번 : 시간 끌기 17402번: 시간 끌기 첫 번째 줄에 게임판의 사이즈인 N과 M, 그리고 X 표시된 칸의 개수 K가 공백으로 구분되어 주어진다. (1 ≤ N, M ≤ 200, 1 ≤ K ≤ NM) 이후 K개의 줄에 걸쳐 두 자연수 x, y가 공백으로 구분되어 주어진 www.acmicpc.net N×M 크기의 격자판에서 K개의 x자 표시가 있는 부분이 선택한 행과 열의 교차점이 되지 않도록 최대한 많이 선..