복습 정리 노트

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 3692번 : '펭귄들의 행진'의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Diamond V에 해당하며 문제를 풀이하기 위해 최대 유량 알고리즘(Network Flow)에 대한 이해가 필요합니다. 3692번 : 펭귄들의 행진 3692번: 펭귄들의 행진 남극의 한 빙하 지대 어딘가에 펭귄 여러 마리가 살고 있다. 각 펭귄들은 바다에 떠 있는 여러 얼음 조각 위에 나뉘어 서 있다. 한 얼음 조각 위에 여러 마리의 펭귄이 있을 수도 있으며, 펭귄이 www.acmicpc.net 문제가 길어서 작은 캡쳐본에 내용을 모두 담는 것이 불가능합니다. 이미지의 설명이 부족하면 링크를 통해 문제 전문을 읽어보시는 것이 ..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 1585번 : '경찰', 2365번 : '숫자판 만들기'의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Platinum 티어에 해당하며, 문제를 풀이하기 위해 최대 유량 알고리즘과 최소 비용 최대 유량 알고리즘에 대한 이해가 필요합니다. 1585번 : 경찰 1585번: 경찰 첫째 줄에 차가 총 몇 대 있는지 주어진다. 이 값을 N이라고 하고, 50보다 작거나 같은 자연수이다. 둘째 줄에는 차가 동호도로에 들어가는 시간이 주어진다. 총 N개의 수가 공백 한 칸을 사이에 www.acmicpc.net 기존 최소 비용 최대 유량 문제들에 비해 고려해야할 요소들이 많아서 상당히 귀찮았던 문제입니다. 차가 들어가는 ..

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge의 15892번 : '사탕 줍는 로봇', 17222번 : '위스키 거래', 1258번 : '문제 할당'의 풀이 코드와 해설을 다루고 있습니다. 문제의 난이도는 Solved.ac 기준 Platinum 티어에 해당하며, 문제를 풀이하기 위해 최대 유량 알고리즘에 대한 이해가 필요합니다. 15892번 : 사탕 줍는 로봇 15892번: 사탕 줍는 로봇 첫 번째 줄에 성원이네 집안에 있는 방의 개수를 나타내는 자연수 n(2 ≤ n ≤ 300)과 복도의 개수를 나타내는 자연수 m(1 ≤ m ≤ 5,000)이 공백으로 구분되어 주어진다. 두 번째 줄부터 m개의 줄에 www.acmicpc.net n개의 방과 m개의 복도에 대해, 특정 복도들에 특정 개수의 ..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 10976번 : '피난', 17412번 : '도시 왕복하기 1', 2316번 : '도시 왕복하기 2' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Platinum IV에 해당하며, 문제를 풀이하기 위해 최대 유량 알고리즘에 대한 이해가 필요합니다. 10976번 : 피난 10976번: 피난 어느 날, CC동산에 놀러온 초등학생 석주가 CC동산에 무차별적으로 침을 뱉었다. CC동산 일대에서 열심히 일하던 개미들의 90%가 석주의 침 때문에 몰살당했고, 소수 개미와 1000마리의 여왕개미만 www.acmicpc.net 위의 규칙대로 개미를 보내는 과정은 유량을 보내는 과정과 똑같이 생각할 수 있으므로 적..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 11405번 ~ 11407번 : '책 구매하기 1~3' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Platinum IV에 해당하며, 문제를 풀이하기 위해 최소 비용 최대 유량 알고리즘(MCMF 알고리즘)에 대한 이해가 필요합니다. 11405번 : 책 구매하기 11405번: 책 구매하기 총 N명의 사람이 책을 구매하려고 한다. 각 사람은 1번부터 N번까지 번호가 매겨져 있고, 각 사람이 사려고하는 책의 개수는 A1, A2, ..., AN권이다. 이 책을 판매하는 온라인 서점은 총 M곳이 있다.각 www.acmicpc.net N명의 사람들이 각각 조건에 맞게 책을 구매하려고 하고 배송비가 소모된다고 ..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 2367번 : '파티' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Platinum IV에 해당하며, 문제를 풀이하기 위해 최대 유량 알고리즘(Network Flow)에 대한 이해가 필요합니다. [C++ 알고리즘] 최대 유량 알고리즘 (Network Flow, Ford-Fulkerson, Edmonds-Karp) 이 포스트에서는 최대 유량 알고리즘(Network Flow, Ford-Fulkerson, Edmonds-Karp 알고리즘)에 대한 설명과 코드 구현에 대해 다룹니다. 알고리즘에 대한 적절한 예시를 들기 위해, 프로그래밍 문제 사이트 restudycafe.tistory.com 최대 유량 알고..

이 포스트에서는 최소 비용 최대 유량 알고리즘(MCMF 알고리즘)에 대한 설명과 알고리즘 구현 코드에 대해 다루고 있습니다. 알고리즘에 대한 적절한 예시를 제공하기 위해 프로그래밍 문제 사이트 백준 Online Judge의 11408번 : '열혈강호 5' 문제를 함께 풀이할 것입니다. [C++ 알고리즘] 최대 유량 알고리즘 (Network Flow, Ford-Fulkerson, Edmonds-Karp) 이 포스트에서는 최대 유량 알고리즘(Network Flow, Ford-Fulkerson, Edmonds-Karp 알고리즘)에 대한 설명과 코드 구현에 대해 다룹니다. 알고리즘에 대한 적절한 예시를 들기 위해, 프로그래밍 문제 사이트 restudycafe.tistory.com 최소 비용 최대 유량(MCMF)..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 11377번 : '열혈강호 3', 11378번 : '열혈강호 4' 문제의 풀이 코드와 해설에 대해 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Platinum III에 해당하며, 문제를 풀이하기 위해 최대 유량 알고리즘에 대한 이해가 필요합니다. (다만 일반적인 풀이는 이분 매칭 알고리즘의 응용임을 참고해야 함) 11377번 : 열혈강호 3 11377번: 열혈강호 3 첫째 줄에 직원의 수 N과 일의 개수 M, 일을 2개할 수 있는 직원의 수 K가 주어진다. (1 ≤ N, M ≤ 1,000, 1 ≤ K ≤ N) 둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있 www.acmicpc.net ..

이 포스트에서는 최대 유량 알고리즘(Network Flow, Ford-Fulkerson, Edmonds-Karp 알고리즘)에 대한 설명과 코드 구현에 대해 다룹니다. 알고리즘에 대한 적절한 예시를 들기 위해, 프로그래밍 문제 사이트 백준 Online Judge의 6086번 : '최대 유량' 문제를 풀이하면서 설명하도록 하겠습니다. 6086번 : 최대 유량 6086번: 최대 유량 첫째 줄에 정수 N (1 ≤ N ≤ 700)이 주어진다. 둘째 줄부터 N+1번째 줄까지 파이프의 정보가 주어진다. 첫 번째, 두 번째 위치에 파이프의 이름(알파벳 대문자 또는 소문자)이 주어지고, 세 번째 위 www.acmicpc.net 특정 지점부터 특정 지점까지 흐를 수 있는 다양한 지점들 사이의 최대 유량이 주어졌을 때, A..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 13506번 : '카멜레온 부분 문자열' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Platinum 티어에 해당하며, 문제를 풀이하기 위해 KMP 알고리즘에 대한 이해가 필요합니다. 13506번 : 카멜레온 부분 문자열 입력받은 문자열의 접두사이면서 접미사이면서 문자열 중간에도 등장(이 때 세 위치가 모두 달라야 함)하는 가장 긴 문자열을 출력하는 문제입니다. 당연히 단순 브루트포스 탐색으로는 시간 제한을 통과하지 못하므로, KMP 알고리즘의 Pi 배열을 응용하여 해결하는 문제입니다. #include #include #include using namespace std; vector GetPi(st..