C++ 검색 결과
55 개의 검색 결과가 있습니다.
코딩/백준 (C++)

백준 2316번: 도시 왕복하기 2 (C++)

접근 https://www.acmicpc.net/problem/2316 2316번: 도시 왕복하기 2 N개의 도시가 P개의 양방향 길로 연결되어 있다. 이석원은 1번 도시와 2번 도시 사이를 오가며 워해머를 한다. 성실한 이석원은 두 도시 사이를 최대한 많이 왔다 갔다 하려 하는데, 이때 한 번 방 www.acmicpc.net 네트워크 플로우에서 에드몬드카프 알고리즘을 이용하여 푸는 문제임은 알았으나 도시에 한번만 방문하게 하기 위한 방법을 찾기 위해 visited 배열 등 갖가지 방법을 다 쓰다가 못풀어 다른 분의 풀이를 참고하게 되었다. 핵심은 한개의 마을을 2개의 정점, in 정점과 out 정점으로 나누고 이 둘을 capacity 1로 주는 것이다. 이렇게 된다면 여러 마을에서 in 정점으로 여러번..

2022. 6. 15. 23:37
코딩/백준 (C++)

백준 11378번: 열혈강호 4 (C++)

접근 https://www.acmicpc.net/problem/11378 11378번: 열혈강호 4 첫째 줄에 직원의 수 N과 일의 개수 M, 지난달에 받은 벌점의 합 K가 주어진다. (1 ≤ N, M ≤ 1,000, 1 ≤ K ≤ N) 둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있는 www.acmicpc.net 이전 열혈강호 문제들과 마찬가지로 이분매칭을 이용하여 문제를 해결하였다. 이전 문제와 다른 점은 각 직원들에게 해당하는 일의 수가 벌점에 의해 바뀔 수 있으며, 이 벌점은 전체 직원의 총점만 정해져있고, 어떤 직원에게 몇 점의 벌점을 주어 일의 갯수를 다르게 할지를 결정해야한다. 문제 해결은 아래와 같이 진행하였다. 각 직원들의 기본 일의 수 1개까지는 ..

2022. 6. 15. 22:32
코딩/백준 (C++)

백준 17412번: 도시 왕복하기 1 (C++)

접근 https://www.acmicpc.net/problem/17412 17412번: 도시 왕복하기 1 첫째 줄에 두 정수 N(3 ≤ N ≤ 400), P(1 ≤ P ≤ 10,000)이 주어진다. 다음 P개의 줄에는 각 길이 연결하는 출발 도시와 도착 도시의 번호가 주어지며, 두 번호는 다르다. www.acmicpc.net 네트워크 플로우의 에드몬드카프 알고리즘에서 flow의 최대치를 1로 두었을 때의 결과를 표시하면 되는 문제였다. 네트워크 플로우에 대한 자세한 설명은 아래 글을 참조하였다. https://yjg-lab.tistory.com/198 [알고리즘] 네트워크 플로우 (Network Flow) - 에드몬드 카프 알고리즘 (Edmonds-Karp) 네트워크 플로우 (Network Flow) -..

2022. 6. 11. 22:49
코딩/백준 (C++)

백준 11376번: 열혈강호 2 (C++)

접근 https://www.acmicpc.net/problem/11376 11376번: 열혈강호 2 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 최대 두 개의 일을 할 수 있고, www.acmicpc.net 열혈강호 1번 문제와 동일하게 직원에게 일을 배정하는 문제이지만 한 직원이 2개의 일을 할 수 있다는 점만 다르다. 이전 문제와 동일하게 네트워크 플로우의 최대 이분 매칭을 이용하여 문제를 풀 수 있고, 한 사람당 일을 2개 할 수 있는 점은 직원 수를 2배로 늘리는 방법을 이용하여 문제를 해결하였다. https://ca.ramel.be/249 백준 11375번: 열혈강호 (C++..

2022. 6. 6. 17:24
코딩/백준 (C++)

백준 11375번: 열혈강호 (C++)

접근 https://www.acmicpc.net/problem/11375 11375번: 열혈강호 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 한 개의 일만 할 수 있고, 각각 www.acmicpc.net 이전에 풀었던 돌멩이 제거하는 문제와 같은 방식의 네트워크플로우 최대이분매칭을 이용한 문제였다. https://ca.ramel.be/248 백준 1867번: 돌멩이 제거 (C++) 접근 https://www.acmicpc.net/problem/1867 1867번: 돌멩이 제거 첫째 줄에 n과 k가 주어진다. (1 ≤ n ≤ 500, 1 ≤ k ≤ 10,000) 이후 k개의 줄에는 돌멩..

2022. 6. 6. 16:31
코딩/백준 (C++)

백준 1867번: 돌멩이 제거 (C++)

접근 https://www.acmicpc.net/problem/1867 1867번: 돌멩이 제거 첫째 줄에 n과 k가 주어진다. (1 ≤ n ≤ 500, 1 ≤ k ≤ 10,000) 이후 k개의 줄에는 돌멩이의 위치가 한 줄에 하나씩 주어진다. 줄마다 첫 번째 숫자는 행 번호, 두 번째 숫자는 열 번호를 나타낸다. 입 www.acmicpc.net 각 줄의 돌의 수를 찾아 가장 많은 돌을 가진 줄부터 삭제하는 방향의 그리디 알고리즘으로 먼저 풀어보았다가 예상대로 틀렸다. 푸는 방향을 못찾아 다른 분의 풀이를 참고하였고, 네트워크 플로우의 한 종류인 최대 이분 매칭 알고리즘을 이용하여 푼다는 것을 확인했다. 알고리즘에 대한 이해는 아래 글을 참고하였다. https://cocoon1787.tistory.com..

2022. 6. 5. 23:17
반응형