복습 정리 노트

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 10786번 : 'Catering' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 출처는 ACM-ICPC World Finals 2015 C번이며, 문제 난이도는 Solved.ac 기준 Platinum II에 해당합니다. 10786번 : Catering 10786번: Catering Paul owns a catering company and business is booming. The company has k catering teams, each in charge of one set of catering equipment. Every week, the company accepts n catering requests for ..

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 3938번 : 'Concert Hall Scheduling' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Platinum II에 해당하며, 문제를 풀이하기 위해 최소 비용 최대 유량(MCMF) 알고리즘에 대한 이해가 필요합니다. 3938번 : Concert Hall Scheduling 3938번: Concert Hall Scheduling You are appointed director of a famous concert hall, to save it from bankruptcy. The hall is very popular, and receives many requests to use its..

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge의 3640번 : '제독' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Platinum II에 해당하며, 문제를 풀이하기 위해 최소 비용 최대 유량 알고리즘(MCMF)에 대한 이해가 필요합니다. 3640번 : 제독 3640번: 제독 두 함선(빨강, 파랑)은 1에서 시작해서 6에서 만난다. 빨간 함선은 1 → 3 → 6 (총 33개 포탄)으로 이동하고, 파란 함선은 1 → 2 → 5 → 4 → 6 (총 53개 포탄)으로 이동한다. 두 경로에서 출발 www.acmicpc.net 시작 노드와 도착 노드만 동일하고 나머지 노드는 겹치지 않는 두 경로를 잡을 때, 두 경로의 비용이 최소가 되는 합을 구하는 문제입니..

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 2311번 : '왕복 여행' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Platinum II에 해당하며, 문제를 풀이하기 위해 최대 유량 알고리즘(Network Flow)와 최소 비용 최대 유량 알고리즘에 대한 이해가 필요합니다. 2311번 : 왕복 여행 1번 나라에서 N번 나라에 방문한 후 다시 1번 나라로 돌아올 때 걸리는 최소 비용을 구하는 문제입니다. 단순 최소 비용 최대 유량 알고리즘으로는 해결할 수 없는 것이, MCMF 알고리즘에서는 Cost[i][j] = -Cost[j][i]로 설정함으로써 알고리즘이 작동하였는데 여기서는 간선이 양방향 간선이므로 그러한 조건의 설정이 불가능합니다..

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 1658번 : '돼지 잡기' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Platinum II에 해당하며, 문제를 풀이하기 위해 최대 유량 알고리즘(Network Flow)에 대한 이해가 필요합니다. 1658번 : 돼지 잡기 손님 N명이 순서대로 도착해서 각각이 가지고 있는 특정 번호들의 열쇠로 우리를 열고 돼지를 원하는 마릿수 이하로 가져간 뒤, 최근에 열린 우리 사이의 돼지들을 적절히 이동시킬 수 있다고 할 때 모든 사람들의 최대로 가져갈 수 있는 돼지의 합을 구하는 문제입니다. 이 문제의 핵심은 A, B번 사람이 같은 우리의 키를 가지고 있는 경우 B가 돼지를 더 많이 살 수 있도록 하기..

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 1420번 : '학교 가지마!' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Platinum II에 해당하며, 문제를 풀이하기 위해 최대 유량 알고리즘(Network Flow)와 최대 유량 최소 컷 정리(MFMC)에 대한 이해가 필요합니다. 1420번 : 학교 가지마! 1420번: 학교 가지마! 첫째 줄에 도시의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 100) 둘째 줄부터 N개의 줄에 도시의 모양이 주어진다. 비어있으면 점('.'), 벽은 '#', 도현이의 위치는 K, 학교의 위치는 H이다. www.acmicpc.net N형 M열의 지도가 주어졌을 때, K가 H까지 이..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 "맞았습니다" 또는 정답 코드를 추출하여 따로 저장하는, 정답 코드 모음 만드는 방법을 다루고 있습니다. 깃허브에 자신의 코드를 정리해서 올리고 싶거나 또는 정답 코드만 따로 모아두고 싶을 때 Python 코드를 이용하여 이를 자동화시키는 방법이 있습니다. 다른 분이 깃허브에 크롤링 하는 프로그램을 간단하게 작성하여 올리신 것이 있어 이를 공유하고, 사용 방법을 알리고자 합니다. GitHub - pgh268400/BaekJoon-Code-Extractor: 지금까지 제출한 백준 "맞았습니다" 코드를 추출하는 프로그램 지금까지 제출한 백준 "맞았습니다" 코드를 추출하는 프로그램 입니다. Contribute to pgh268400..

이 포스트에서는 알고리즘의 일종인 '최대 유량 최소 컷 정리'에 대해 다루고 있습니다. 알고리즘에 대한 적절한 적용 상황을 제시하기 위해 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 14286번 : '간선 끊어가기 2' 문제의 풀이 코드와 해설을 함께 다룹니다. 최대 유량 최소 컷 정리 컷이란 그래프의 노드들을 두 개의 덩어리로 나누는 것을 의미합니다. (무향 그래프에서는 두 그룹 사이에 어떠한 간선도 존재하지 않아야 하지만, 유향 그래프의 경우에는 Sink에서 Sour로 이동이 가능해도 Sour에서 Sink로 이동이 불가능하기만 하다면 역시 컷에 해당합니다.) 이 때, 그래프를 나누기 위해 간선을 끊으면서 그 간선의 비용을 계산한다고 할 때, 컷(그래프를 두 개로 나누는 과정)의 비용..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 9413번 : '제주도 관광' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Platinum III에 해당하며, 문제를 풀이하기 위해 최소 비용 최대 유량(MCMF) 알고리즘에 대한 이해가 필요합니다. 9413번 : 제주도 관광 두 그룹이 주어진 입력대로 연결된 교차로들을 지나며 교차로가 겹치지 않게 동선을 짜려고 할 때, 두 동선의 교차로 수의 합의 최대치를 구하는 문제입니다. 우선 각 intersection들은 노드에 해당하기 때문에 노드를 방문하는 조건이 붙은 문제는 노드를 두 개로 분할하여 그 사이에 용량이 1인 간선을 추가함으로써 해결이 가능합니다. 그리고 두 팀이 출발한다고 하였기..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 5997번 : 'Who Brings the Cookies?', 2679번 : '맨체스터의 도로' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Platinum III에 해당하며, 문제를 풀이하기 위해 최대 유량 알고리즘에 대한 이해가 필요합니다. 5997번 : Who Brings the Cookies? 5997번: Who Brings the Cookies? Farmer John's N (1