레야몬

아직 풀지는 못했고 언젠가는 정수론을 공부해야한다고 생각하기 때문에 정수론을 공부하고나서 풀어보려고 한다. 정수론 책 pdf https://blog.naver.com/PostView.nhn?blogId=mindo1103&logNo=221340552620&from=search&redirect=Log&widgetTypeCall=true&directAccess=false 정수론의 기초 https://divyanshkumarsblog.wordpress.com/2017/05/30/number-theory-i/ 그래서 결론은? https://divyanshkumarsblog.wordpress.com/2017/05/30/number-theory-ii-advanced-modular-arithmetic/ 중국인의 나머지..

1. 문제 소가 자신이 희망하는 몇 개의 축사에만 들어가고자 할 때 최대한 많은 수의 소가 축사에 들어갈 수 있도록 하는 프로그램을 작성하시오. 축사의 번호는 1~M번으로 매겨져 있다. -1- 소의 수 N, 축사의 수 M \((1 \leq N, M \leq 200)\) -2~N- 각 소가 들어가기 원하는 축사에 대한 정보가 주어진다. i번째 소가 들어가기 원하는 축사의 수 \(S_{i}(0 \leq S_{i} \leq M)\). \(S_{i}\)개의 축사 번호가 주어진다. 같은 축사 번호가 두 번 이상 주어지는 경우는 없다. -1- 축사에 들어갈 수 있는 소의 최댓값을 출력하라 2. 재정의 이분 매칭 최대 수를 구하시오. 3. 해결 방법 이분 매칭 알고리즘(dfs)를 이용하여 해결한다. 4. 실수한 점,..

1. 문제 직원이 N명, 해야 할 일이 M개가 있다. 직원은 1~N번까지 번호가 매겨져 있고 일은 1~M번까지 번호가 매겨져 있다. 각 직원은 한 개의 일만 할 수 있고, 각 일을 담당하는 사람은 1명이어야 한다. 각각의 직원이 할 수 있는 일의 목록이 주어졌을 때, M개의 일 중에서 최대 몇 개를 할 수 있는지를 구하여라 -1- 직원의 수 N, 일의 수 M \((1 \leq N, M \leq 1000)\) -2~N- i번째 직원이 할 수 있는 일의 개수, 일의 번호 강호내 회사에서 할 수 있는 최대 일의 개수를 출력 2. 재정의 직원과 일이 일대일 매칭일 때 할 수 있는 일의 최대 개수를 구하여라. 3. 해결 방법 sour = 0, sink = N+M+1 0 -> (1~N)번 연결하기 i번 직원과 할 ..

1. 문제 N*M 크기의 도시는 빈칸 또는 벽이다. 도현이와 학교는 빈칸에 있고 도현이는 상하좌우로 인접한 칸으로 이동해 학교에 가려고 한다. 이때, 벽이 있는 칸으로는 이동할 수 없고, 도시를 벗어날 수 없을 때 도현이가 학교에 가지 못하게 빈칸을 벽으로 바꾸려고 한다. 도현이와 학교가 있는 곳은 벽으로 바꿀 수 없을 때 바꿔야 하는 횟수의 최솟값을 구하시오. -1- 도시의 세로 크기 N, 가로 크기 M \(M(1 \leq N, M \leq 100)\) M개의 줄 도시의 모양이 주어진다. 빈칸: '.', 벽: '#', 도현이의 위치: 'K', 학교의 위치: 'H'. K와 H는 하나만 주어진다. 바뀌는 벽의 최솟값을 출력하라. 만약 벽을 세워도 막을 수 없다면 -1을 출력하라. 2. 재정의 바뀌는 벽의 ..

1. 문제 정점 n개, 간선 m개로 이루어진 가중치가 있는 무방향 그래프가 주어진다. 특정 정점 s, t가 비연결되도록 간선을 제거하는데, 제거한 간선의 가중치의 합의 최솟값을 구하시오. -1- 정점의 개수 n, 간선의 수 m이 주어짐 \((2 \leq n \leq 500, 1 \leq m \leq 10,000)\) m줄 a와 b사이 가중치 c \((1 \leq a, b \leq n, 1 \leq c \leq 100, a \neq b)\) -m+2- 두 정점 s, t \((1 \leq s, t \leq n, s \neq t)\) 제거한 간선의 가중치 합의 최솟값 출력 2. 재정의 최소컷을 구하시오. 3. 해결 방법 최대 유량 최소 컷 정리에 따라 최소컷은 최대 유량과 같다. 따라서 최대 유량 알고리즘을 ..

도시 왕복하기 2를 풀면서 같이 푼 문제라서 함께 풀이합니다. 1. 문제 도시 왕복하기 2: N개의 도시가 P개의 양방향 길로 연결되어 있다. 1번 도시와 2번 도시 사이에는 길이 없을 때 이석원은 1번 도시와 2번 도시를 최대한 많이 왔다 갔다 하는데 한 번 방문한 도시는 두 번 이상 방문할 수 없다. 이때 왔다 갔다 할 수 있는 최대 횟수를 구하여라. 도시 왕복하기 1: N개의 도시가 P개의 방향 길로 연결되어 있다. 1번 도시와 2번 도시 사이에는 길이 없을 때 이석원은 1번 도시와 2번 도시를 최대한 많이 왔다 갔다 하는데 한 번 지난 길은 다시 지날 수 없다. 이때 왔다 갔다 할 수 있는 최대 횟수를 구하여라. -1- \(N(3 \leq N \leq 400)\), \(P(1 \leq P \leq..

도시 왕복하기 2를 풀면서 같이 푼 문제라서 함께 풀이합니다. 1. 문제 도시 왕복하기 2: N개의 도시가 P개의 양방향 길로 연결되어 있다. 1번 도시와 2번 도시 사이에는 길이 없을 때 이석원은 1번 도시와 2번 도시를 최대한 많이 왔다 갔다 하는데 한 번 방문한 도시는 두 번 이상 방문할 수 없다. 이때 왔다 갔다 할 수 있는 최대 횟수를 구하여라. 도시 왕복하기 1: N개의 도시가 P개의 방향 길로 연결되어 있다. 1번 도시와 2번 도시 사이에는 길이 없을 때 이석원은 1번 도시와 2번 도시를 최대한 많이 왔다 갔다 하는데 한 번 지난 길은 다시 지날 수 없다. 이때 왔다 갔다 할 수 있는 최대 횟수를 구하여라. -1- \(N(3 \leq N \leq 400)\), \(P(1 \leq P \leq..

1. 문제 N개의 정사각형 블록을 쌓아 두 개의 탑을 만드는데 이때 두 탑의 높이는 같다. 각 탑은 적어도 한 개의 블록을 포함해야 할 때 탑의 높이는 같다. 적어도 한 개의 블록을 포함해야 할 때 탑의 높이의 최댓값을 구하여라. -1- 조각의 개수 \(N(1 \leq N \leq 50)\) -2- 각 조각의 높이가 주어짐 \(H(1 \leq H \leq 500,000)\) 모든 조각의 합은 500,000보다 작다 문제의 정답을 출력하며, 불가능할 때는 -1을 출력한다. 2. 재정의 수열의 서로 겹치지 않는 두 부분 집합의 합이 같도록 하는 집합의 합의 최댓값을 구하시오 3. 해결방법 max[i][k] = max(max[i-1][k+num[i]], max[i-1][abs(num[i]-k])) 차이가 k인..