알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/9576 9576번: 책 나눠주기 백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의 www.acmicpc.net 이분 매칭을 이용해 푸는 문제입니다. 자세한 것은 코드를 참고해주세요 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #include #include #include #define LL long long #define pp pair #define ..

문제 링크입니다. https://www.acmicpc.net/problem/11377 11377번: 열혈강호 3 첫째 줄에 직원의 수 N과 일의 개수 M, 일을 2개할 수 있는 직원의 수 K가 주어진다. (1 ≤ N, M ≤ 1,000, 1 ≤ K ≤ N) 둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있 www.acmicpc.net 이분 매칭을 이용한 문제입니다. 해당 문제에서 응용된 문제입니다. https://junseok.tistory.com/339 백준 11375 - 열혈강호(C++) 문제 링크입니다. https://www.acmicpc.net/problem/11375 11375번: 열혈강호 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원..

문제 링크입니다. https://www.acmicpc.net/problem/11376 11376번: 열혈강호 2 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 최대 두 개의 일을 할 수 있고, www.acmicpc.net 이분 매칭을 이용하는 문제입니다. 해당 문제에서 응용된 문제입니다. https://junseok.tistory.com/339 백준 11375 - 열혈강호(C++) 문제 링크입니다. https://www.acmicpc.net/problem/11375 11375번: 열혈강호 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매..

문제 링크입니다. https://www.acmicpc.net/problem/2188 2188번: 축사 배정 농부 존은 소 축사를 완성하였다. 축사 환경을 쾌적하게 유지하기 위해서, 존은 축사를 M개의 칸으로 구분하고, 한 칸에는 최대 한 마리의 소만 들어가게 계획했다. 첫 주에는 소를 임의 배정해 www.acmicpc.net 이분 매칭을 이용하는 문제입니다. 이분 매칭이라는 알고리즘 설명이 잘나와있는 블로그입니다. 참고해주세요. https://yjg-lab.tistory.com/209 [알고리즘] 이분 매칭 알고리즘 (Bipartite Matching) 이분 매칭 알고리즘 (Bipartite Matching) 두 개의 정점 그룹이 존재할 때 모든 간선(경로)의 용량이 1이면서 양쪽 정점이 서로 다른 그룹..

문제 링크입니다. https://www.acmicpc.net/problem/11375 11375번: 열혈강호 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 한 개의 일만 할 수 있고, 각각 www.acmicpc.net 이분 매칭을 사용하는 문제입니다. 이분 그래프에서 두 그룹을 X, Y그룹이라고 할 때, 모든 경로의 방향이 X -> Y인 그래프의 최대 유량을 구하는 것이 이분 매칭입니다. 문제에서 볼 수 있듯이, 이분 매칭을 통해 구하고자 하는 것은 최대 매칭 수입니다. 이때 매칭한다는 것은 1대 1함수와 같이 하나의 정점이 다른 그룹의 하나의 정점만을 점유하고 있는 상태를 말합니다. ..

문제 링크입니다. https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net upper, lower_bound를 사용하는 문제였습니다. 배열 A와 B 중, 하나 이상을 선택해 합이 T를 만드는 부분 수열의 갯수를 구하는 문제입니다. N과 M값이 1,000이기에 이중 for문을 통해서 모든 부분 수열의 합을 구합니다. A 부분 수열과 B 부분 수열의 합을 구하는 것이기에, 배열..

문제 링크입니다.https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 비트마스킹과 Dp를 사용하는 문제입니다. 생각하는게 어려웠던 문제입니다. 0~9를 모두 포함하는 계단 수를 세는 문제입니다. 0~9를 사용했는지 배열을 이용해서 구하는 방법은 너무 어려워집니다. 따라서 변수 하나를 통해 0~9를 사용했는지 저장할 것입니다. -> 비트마스킹 방법을 사용하면 됩니다. 문제에 사용된 비트마스킹은 다음과 같습니다. 9 8 7 6 5 4 3 2 1 0 1 1 1 1 0 0 0 0 0 0 예를 들어, 계단 수가 10206789 라고 하면, (6, 7, 8, 9)가 계단수가 됩니다...

문제 링크입니다. https://www.acmicpc.net/problem/9086 9086번: 문자열 입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 한 줄에 하나의 문자열이 주어진다. 문자열은 알파벳 A~Z 대문자로 이루어지며 알파벳 사이에 공백은 없으 www.acmicpc.net 문자열을 사용하는 간단한 문제입니다. N개의 문자열을 입력받고, 문자열의 처음과 끝 문자를 출력하는 문제입니다. String을 사용하면 쉽게 풀 수 있었습니다. 자세한 것은 코드를 참고해주세요 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include..

문제 링크입니다. https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 비트마스킹을 사용한 구현 문제였습니다. 비트마스킹이라는 방법을 사용하는 문제였습니다. int 형 변수를 비트연산자처럼 사용하는 방법인데, 0과 1을 이용해 원하는 데이터 값을 저장합니다. 예를 들어, 문제에서 열쇠를 a, c, f를 가지고 있다면, 10101로 나타내 해당 위치의 열쇠를 가지고 있는지 저장합니다. 그렇다면 새로운 열쇠를 얻었을 때, ..

문제 링크입니다. https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 유명한 문제인 외판원 순회입니다. 외판원 문제에 대한 설명이 잘나와있습니다. 해당 블로그를 참고해주세요! 더보기 https://velog.io/@jxlhe46/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%99%B8%ED%8C%90%EC%9B%90-%EC%88%9C%ED%9A%8C-%EB%AC%B8%EC%A0%9C ..

문제 링크입니다. https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 까다로운 그리디 문제였습니다. 보석을 어떤 순으로 담아야 되는지 생각했어야 했습니다. N과 K의 범위가 300,000 이기에 가방 한개마다 모든 보석을 확인하기에는 문제가 있습니다. 따라서 우선순위 큐를 사용했습니다. 우선순위 큐를 사용하면 조건에 따라 가장 작은 or 가장 큰 값이 루트에 있기에 이를 가져오기만 하면 ..

문제 링크입니다. https://www.acmicpc.net/problem/2420 2420번: 사파리월드 첫째 줄에 두 도메인의 유명도 N과 M이 주어진다. (-2,000,000,000 ≤ N, M ≤ 2,000,000,000) www.acmicpc.net If문을 이용한 간단한 문제였습니다. 큰 수에서 작은 수를 뺀 값에 절댓값을 씌워주면 되는 문제입니다. 조건문을 사용한다면, 큰 수를 먼저 찾은 뒤, 작은 수를 빼주고, 연산한 수를 출력해주면 됩니다. 저는 abs() 라는 절댓값을 출력해주는 것을 사용해 간단하게 풀었습니다. 작자세한 것은 코드를 참고해주세요 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #i..