알고리즘 모음(C++)

문제 링크입니다. 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함수와 같이 하나의 정점이 다른 그룹의 하나의 정점만을 점유하고 있..

문제 링크입니다. https://www.acmicpc.net/problem/14939 14939번: 불 끄기 전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄 www.acmicpc.net 비트마스킹을 이용한 문제입니다. 구현하는 방법을 떠올리는게 어려웠던 문제입니다. 한 곳의 불을 끄면 해당 위치부터 상하좌우의 값이 바뀌게 됩니다. 가로, 세로가 모두 10의 크기이기에 모든 경우를 확인하여면 2^100인 경우가 나오게 됩니다. -> 시간 초과가 생깁니다. 이 문제를 풀기 위해선 2가지를 생각해야하는데, 1. 한 번 누르면 다시 누를 필요가 없다. -> ..

문제 링크입니다. https://www.acmicpc.net/problem/2738 2738번: 행렬 덧셈 첫째 줄에 행렬의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 차례대로 주어진다. 이어서 N개의 줄에 행렬 B의 원소 M개가 차례대로 주어진다. N과 M은 100보다 작거나 같 www.acmicpc.net 배열을 이용한 간단한 문제입니다. 2차원 배열 2개를 이용해 행렬을 입력 받은 뒤, 합을 출력하는 간단한 문제입니다. 자세한 것은 코드를 참고해주세요 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include using namespace std; int N..

문제 링크입니다. https://www.acmicpc.net/problem/2744 2744번: 대소문자 바꾸기 영어 소문자와 대문자로 이루어진 단어를 입력받은 뒤, 대문자는 소문자로, 소문자는 대문자로 바꾸어 출력하는 프로그램을 작성하시오. www.acmicpc.net 문자열을 사용하는 문제입니다. 문자열에 속해있는 알파벳의 대소문자를 바꾸는 문제입니다. string을 통해 문자열을 입력 받은 뒤, 문자 하나씩 확인하면서 소문자인지 대문자인지를 구합니다. 1. 소문자일 경우 -> a[i] - 'a' + 'A' 2. 대문자일 경우 -> a[i] - 'A' + 'a' 다음과 같은 연산을 통해 문자열에서 알파벳이 몇번째 순서인지 구하고, 필요한 알파벳을 더해주면서 원하는 알파벳을 찾을 수 있습니다. 자세한 ..

문제 링크입니다. https://www.acmicpc.net/problem/1298 1298번: 노트북의 주인을 찾아서 어느 날 모든 학생들은 한 명이 한개의 노트북을 가지고 공부하던 도중, 자리를 바꾸다가 그만 노트북이 뒤섞이고 말았다. 대다수의 학생들은 자신의 노트북을 잘 알고 있어서 자신의 노트북을 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..