알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/15591 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 그래프 탐색을 이용해 푸는 문제였습니다. 시작점을 큐에 넣고 탐색을 시작하지 않는 것이 중요했습니다. 시작점이 아닌 시작점과 연결된 점들을 큐에 넣은 뒤 탐색을 시작해, 최단 거리를 구해주면 됐습니다. 자세한 것은 코드를 참고해주세요 #define _CRT_SECURE_NO_WARNINGS #include #include #in..

문제 링크입니다. https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net BFS 혹은 DFS를 통해 푸는 문제였습니다. 물통의 물을 옮겨 C물통의 경우를 구하는 문제입니다. 물통을 옮기는 경우를 생각하면 문제 풀기가 쉬워집니다. 1. A에서 B 2. A에서 C 3. B에서 A 4. B에서 C 5. C에서 A 6. C에서 B 이렇게 6가지입니다. 하지만 경우마다 2가지로 나눠서 생각해야합니다. 1. X물통을 Y에 옮겨도 Y물통이 전부..

문제 링크입니다. https://www.acmicpc.net/problem/16197 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net 그래프 탐색을 통해 푸는 문제입니다. 두 동전을 상하좌우 4방향으로 움직여 한 동전만 떨어뜨리는 문제입니다. 두 동전이 모두 떨어지는 상황만 나오거나, 10번보다 많이 움직이면 -1를 출력해주면 됩니다. 먼저 두 동전의 위치에서 시작합니다. 두 동전은 4방향 전부 움직일 수 있으니, 상하좌우를 모두 탐색해줘야합니다. 탐색을 할 때는 이동한 좌표를 통해 판별을 하는데, 1. 두 ..

문제 링크입니다. https://www.acmicpc.net/problem/2660 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net BFS를 이용한 문제입니다. 친구 사이가 얼마나 떨어져있나에 따라 점수가 달라집니다. 모든 사람과 친구 사이이면 1점, 친구의 친구 사이가 있다면 2점, 친구의 친구의 친구 사이가 있다면 3점이 됩니다. 즉, BFS 탐색을 할 때, 탐색의 깊이만큼 사람의 점수가 된다는 의미입니다. 1번 사람부터 N번 사람까지 각각 탐색을 해줘야합니다. 그러면, 1~N번 사람까지 자신의 점수가 구..

문제 링크입니다. https://www.acmicpc.net/problem/6118 6118번: 숨바꼭질 재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다. 농장에는 헛간이 많이 널려있고 재서기는 그 중에 하나에 숨어야 한다. 헛간의 개수는 N(2 y; connect[x].push_back(y); connect[y].push_back(x); } solve(); return 0; } 질문 및 조언은 댓글을 남겨주세요

문제 링크입니다. https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 백트래킹과 BFS를 이용한 문제였습니다. N개의 정점이 주어질 때, 이들을 적절하게 나눠 인구수 차이를 가장 적게 만드는 문제였습니다. 해당 문제를 풀려면 구햔해야 하는 것들이 있습니다. 1. 선거구를 나누는 방법 2. 나뉜 선거구가 연결되는 지 확인 3. 선거구의 인구차를 확인 이와 같이 3개를 구현하면 풀 수 있었습니다. 먼저 1번부터 확인해보겠습니다. 1. 선거구를 나누는 방법 인구수를 최소로 ..

문제 링크입니다. https://www.acmicpc.net/problem/18404 18404번: 현명한 나이트 첫째 줄에 N과 M이 공백을 기준으로 구분되어 자연수로 주어진다. (1 ≤ N ≤ 500, 1 ≤ M ≤ 1,000) 둘째 줄에 나이트의 위치 (X, Y)를 의미하는 X와 Y가 공백을 기준으로 구분되어 자연수로 주어진다. ( www.acmicpc.net BFS를 이용해 푸는 문제입니다. 일반적인 상하좌우 4방향 탐색이 아닌, 나이트 이동인 8방향으로 탐색하는 문제입니다. 자세한 것은 코드를 참고해주세요 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #define INF ..

문제 링크입니다. https://www.acmicpc.net/problem/14433 14433번: 한조 대기 중 첫째 줄에 한 팀에 속한 플레이어의 수 N(1 ≤ N ≤ 300)과 트롤픽의 수 M(1 ≤ M ≤ 300), 각 팀의 팀원들이 원하는 트롤픽의 수 K1, K2(1 ≤ K1, K2 ≤ 500)가 주어진다. 다음 K1개의 줄에 걸쳐 두 수 i, j(1 ≤ www.acmicpc.net 이분 매칭을 이용하는 문제입니다. 해당 문제와 같은 방법으로 푸는 문제입니다. 자세한 설명은 링크를 참고해주세요 https://junseok.tistory.com/339 백준 11375 - 열혈강호(C++) 문제 링크입니다. https://www.acmicpc.net/problem/11375 11375번: 열혈강호 ..

문제 링크입니다. https://www.acmicpc.net/problem/18138 18138번: 리유나는 세일러복을 좋아해 너비가 3인 티셔츠와 너비가 2인 세일러 카라를 붙이고, 너비가 5인 티셔츠에 너비가 5인 세일러 카라를 붙이고 너비가 7인 티셔츠에 너비가 4인 세일러 카라를 붙이고 너비가 10인 티셔츠에 너비 www.acmicpc.net 이분 매칭을 이용해 푸는 문제입니다. 이분 그래프에서 두 그룹을 X, Y그룹이라고 할 때, 모든 경로의 방향이 X -> Y인 그래프의 최대 유량을 구하는 것이 이분 매칭입니다. 문제에서 볼 수 있듯이, 이분 매칭을 통해 구하고자 하는 것은 최대 매칭 수입니다. 이때 매칭한다는 것은 1대 1함수와 같이 하나의 정점이 다른 그룹의 하나의 정점만을 점유하고 있는 ..

문제 링크입니다. https://www.acmicpc.net/problem/25083 25083번: 새싹 아래 예제와 같이 새싹을 출력하시오. www.acmicpc.net 그래도 출력하는 문제입니다. 자세한 것은 코드를 참고해주세요 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #define INF 987654321 using namespace std; char a1, a2; double ans; int main() { cin.tie(0); cout.tie(0); printf(" "); printf(",r\'\"7\n"); printf("r`-_ ,\' ,\/\n"); printf(..

문제 링크입니다. https://www.acmicpc.net/problem/2754 2754번: 학점계산 어떤 사람의 C언어 성적이 주어졌을 때, 평점은 몇 점인지 출력하는 프로그램을 작성하시오. A+: 4.3, A0: 4.0, A-: 3.7 B+: 3.3, B0: 3.0, B-: 2.7 C+: 2.3, C0: 2.0, C-: 1.7 D+: 1.3, D0: 1.0, D-: 0.7 F: 0.0 www.acmicpc.net 조건문을 사용하는 문제입니다. 성적을 입력받아 해당하는 성적을 출력하는 문제입니다. 저는 A,B,C,D,F 와 +,0,-를 나눠서 입력받았습니다 자세한 것은 코드를 참고해주세요 #define _CRT_SECURE_NO_WARNINGS #include #include #include #in..

문제 링크입니다. https://www.acmicpc.net/problem/17481 17481번: 최애 정하기 1번 친구가 SOOJIN, 2번 친구가 SOYEON, 3번 친구가 YUQI, 4번 친구가 SHUHUA, 5번 친구가 MIYEON을 최애 멤버로 정하면 친구들이 최대로 좋아할 수 있는 멤버 수는 5명이 된다. www.acmicpc.net 이분 매칭으로 쉽게 풀 수 있는 문제입니다. 이분 그래프에서 두 그룹을 X, Y그룹이라고 할 때, 모든 경로의 방향이 X -> Y인 그래프의 최대 유량을 구하는 것이 이분 매칭입니다. 문제에서 볼 수 있듯이, 이분 매칭을 통해 구하고자 하는 것은 최대 매칭 수입니다. 이때 매칭한다는 것은 1대 1함수와 같이 하나의 정점이 다른 그룹의 하나의 정점만을 점유하고 있..