복습 정리 노트

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 17481번 : '최애 정하기', 1574번 : '룩 어택' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Platinum IV에 해당하며, 문제를 풀이하기 위해 이분 매칭 알고리즘에 대한 이해가 필요합니다. 17481번 : 최애 정하기 17481번: 최애 정하기 1번 친구가 SOOJIN, 2번 친구가 SOYEON, 3번 친구가 YUQI, 4번 친구가 SHUHUA, 5번 친구가 MIYEON을 최애 멤버로 정하면 친구들이 최대로 좋아할 수 있는 멤버 수는 5명이 된다. www.acmicpc.net N명의 친구들이 M명의 멤버들 중에 좋아하는 멤버들이 있을 때 최애 멤버를 겹치지 않도록 최대 매..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 14433번 : '한조 대기 중', 15271번 : '친구 팰린드롬 2' 문제의 풀이 코드와 해설에 대해서 다룹니다. 문제 난이도는 Solved.ac 기준 Platinum IV에 해당하며, 문제를 풀이하기 위해 이분 매칭 알고리즘에 대한 이해가 필요합니다. 14433번 : 한조 대기 중 14433번: 한조 대기 중 첫째 줄에 한 팀에 속한 플레이어의 수 N(1 ≤ N ≤ 300)과 트롤픽의 수 M(1 ≤ M ≤ 300), 각 팀의 팀원들이 원하는 트롤픽의 수 K1, K2(1 ≤ K1, K2 ≤ 500)가 주어진다. 다음 K1개의 줄에 걸쳐 두 수 i, j(1 ≤ www.acmicpc.net 트롤픽을 원하는 팀원의 번호와 트롤픽..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 11376번 : '열혈강호 2', 1671번 : '상어의 저녁식사' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Platinum에 해당하며, 문제를 풀이하기 위해 이분 매칭 알고리즘에 대한 이해가 필요합니다. 11376번 : 열혈강호 2 11376번: 열혈강호 2 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 최대 두 개의 일을 할 수 있고, www.acmicpc.net N개의 직원에 대해 M개의 일을 적절히 연결시켜서 할 수 있는 일의 최대 개수를 구하는, 전형적인 이분..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 1298번 : '노트북의 주인을 찾아서', 11375번 : '열혈강호' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Platinum 티어에 해당하며, 문제를 풀이하기 위해 이분 매칭 알고리즘에 대한 이해가 필요합니다. [C++ 알고리즘] 이분 매칭 (Bipartite Matching) (BOJ 2188번 : 축사 매칭) 이 포스트에서는 프로그래밍 알고리즘의 일종인 이분 매칭(Bipartite Matching)의 원리와 설명을 다룹니다. 또한 알고리즘의 적용을 효과적으로 설명하기 위해 프로그래밍 문제 사이트 백준 Online Judg restudycafe.tistory.com ↑ 이분 매칭 ..

이 포스트에서는 프로그래밍 알고리즘의 일종인 이분 매칭(Bipartite Matching)의 원리와 설명을 다룹니다. 또한 알고리즘의 적용을 효과적으로 설명하기 위해 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 2188번 : '축사 배정' 문제의 풀이 코드와 해설을 함께 다룹니다. 이분 매칭 알고리즘이란, 두 그룹 사이의 최대한 많은 일대일 대응을 구하는 알고리즘입니다. 이전에 다루었던 최대 유량 = 네트워크 플로우(Network Flow) 알고리즘의 특수한 상황을 다루는 알고리즘으로, 그래프의 노드를 두 그룹으로 나누어 연결을 지어야 하고 사이의 간선 용량이 모두 1인 상황에서만 적용이 가능합니다. 사용할 수 있는 조건이 더 강해진다는 단점이 있지만, 대신 조건만 맞는다면 O(VE^2..

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 11122번 : 'Train Tickets' 문제에 대한 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Diamond V에 해당하며, 문제를 풀이하기 위해 최소 비용 최대 유량(MCMF) 알고리즘에 대한 이해가 필요합니다. 11122번 : Train Tickets 11122번: Train Tickets The first line of input contains a single number T, the number of test cases to follow. Each test case begins with a line containing two numbers, N and P, the number of s..

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 17633번 : '제곱수의 합' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Diamond IV에 해당하며, 문제를 풀이하기 위해 각종 제곱수 관련 정리와 폴라드 로 인수분해 알고리즘에 대한 이해가 필요합니다. 17633번 : 제곱수의 합 (More Huge) 17633번: 제곱수의 합 (More Huge) 입력은 표준입력을 사용한다. 입력은 자연수 n을 포함하는 한 줄로 구성된다. 여기서, 1 ≤ n ≤ 1,000,000,000,000,000,000이다. www.acmicpc.net 10^18 이하의 자연수가 입력되었을 때, 이 자연수를 최소 몇 개의 제곱수들의 합으로 나타낼 수 있는지를 출..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 3933번 : '라그랑주의 네 제곱수 정리' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Gold V에 해당하며, 문제를 풀이하기 위해 브루트포스(완전탐색) 알고리즘에 대한 이해가 있으면 좋습니다. (사실 이 문제는 지금 Diamond IV 티어를 배정받은 정수론 문제를 풀고 있는데 그 문제를 푸는 데 도움이 될까 해서 같이 풀어보고 있는 문제입니다.) 3933번 : 라그랑주의 네 제곱수 정리 3933번: 라그랑주의 네 제곱수 정리 입력은 최대 255줄이다. 각 줄에는 215보다 작은 양의 정수가 하나씩 주어진다. 마지막 줄에는 0이 하나 있고, 입력 데이터가 아니다. www.acmicpc.net ..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 1770번 : '배수와 약수의 개수' 문제의 풀이 코드와 해설을 다룹니다. 문제 난이도는 Solved.ac 기준 Diamond IV이며, 문제를 풀이하기 위해 밀러-라빈 소수 판별법과 폴라드 로 인수분해 알고리즘에 대한 이해가 필요합니다. 1770번 : 배수와 약수의 개수 1770번: 배수와 약수의 개수 각각의 테스트 케이스마다 문제 조건을 만족하는 양의 정수 X의 개수를 한 줄에 하나씩 출력한다. 만약, 조건을 만족하는 정수의 개수가 무한대인 경우 -1을 출력한다. www.acmicpc.net 단순 폴라드 로 인수분해 문제인줄 알고 접근했다가 큰 낭패를 본 문제입니다. (https://hapby9921.tistory.com/..

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 13926번 : 'gcd(n, k) = 1' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Diamond V에 해당하며, 문제를 풀이하기 위해 밀러-라빈 소수 판정법 알고리즘, 폴라드 로 인수분해 알고리즘, 그리고 서로소의 개수를 구하는 공식에 대한 이해가 필요합니다. (굳이 필요는 없지만 더 나아가서는 오일러 Phi 함수에 대한 배경지식도 있으면 좋음) [백준/BOJ C++][Diamond V] 10854번 : Divisions (폴라드 로 알고리즘) 이 포스트는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 10854번 : 'Divisions' 문제의 풀이 코드와 해설을 다루..