컴굥일지

문제 https://school.programmers.co.kr/learn/courses/30/lessons/86971 문제 내용 N개의 송전탑과 이를 연결하는 N-1개의 전선이 있다. 입력으로 주어지는 송전탑들의 관계는, N-1개의 전선으로 모두 이어져있다. 이때, 전선 1개를 끊어서 송전탑을 2 부류로 나눈다. 양측의 탑의 개수의 차를 최소화 했을 때의 차이를 구하면 된다. 문제 풀이 주어진 N-1개의 전선을 한번씩 끊어보면 된다. 끊고 bfs를 돌리면 탑들이 2부류로 나뉘게 된다. 이때의 차를 구하는 것은 어렵지 않다. 코드 #include #include #include #include using namespace std; int divideTowerAndCalcNum(vectorarr[], in..

문제 https://www.acmicpc.net/problem/14500 문제 내용 위의 도형 5가지는 회전시키거나 뒤집을 수 있다. 각 칸에 정수가 적힌 배열을 입력받고, 그 배열에 위 도형 중 하나를 올려놓는다. 올려진 부분의 정수를 모두 더한 값이 최대가 되도록 하면 된다. 문제 풀이 브루트포스로 문제를 해결할 수 있다. 도형이 차지할 수 있는 범위를 모두 적어두고, 반복문을 전부 돌려보면 된다. 코드 #include #include using namespace std; int n, m; int arr[500][500]; vector puzzle = {{{true, true, true, true}}, {{true}, {true}, {true}, {true}}, {{true, true}, {true,..

문제 https://www.acmicpc.net/problem/21608 문제 내용 N*N명의 학생이 N*N 크기의 격자에 아래 방법대로 앉는다. (격자는 (1,1)부터 (N,N)까지이다.) 각 학생별로 그 학생이 좋아하는 학생들 4명이 입력으로 주어진다. |r1 - r2| + |c1 - c2| = 1을 만족하는 두 칸이 (r1, c1)과 (r2, c2)를 인접하다고 한다. 1. 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다. 2. 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다. 3. 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42842 문제 내용 위의 사진과 같이 안쪽에 노란색 칸들이 있고, 이를 1줄로 감싼 갈색 칸들이 있다. 갈색 칸의 개수와 노란색 칸의 개수가 주어질 때, 전체 카펫의 가로, 세로 길이를 구하면 된다. 문제 풀이 문제의 상황을 그림 그려보면 위와 같다. 우리는 a와 b에 어떤 값이 들어가면 되는지를 찾으면 쉽게 문제를 해결할 수 있다. 이때 갈색 격자의 수는 8~5,000, 노란 격자의 수는 1~2,000,000라고 한다. 즉 2a*2b+4

문제 https://www.acmicpc.net/problem/1436 문제 내용 666이 들어간 숫자 중에서 n번째 숫자를 출력하면 되는 문제이다. n=1이면 666, n=2이면 1666, n=3이면 2666 이런 식으로 진행된다. 문제 풀이 완전탐색으로 문제를 풀었다. 숫자의 크기를 1씩 키워가며 666이 들어있는지를 확인했는데, 이를 위해 숫자를 문자열로 변환하는 과정이 필요하다. 코드 #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //입력 int n; cin >> n; //문제 해결 int num = 666; string tmp; whil..

문제 https://www.acmicpc.net/problem/7568 문제 내용 전체 사람들의 몸무게와 키를 입력받아, 덩치 등수를 순서대로 출력하면 된다. 덩치 등수는 자신보다 몸무게와 키 모두 큰 사람의 수 + 1 을 하면 된다. 문제 풀이 완전탐색으로 문제를 해결할 수 있다. pair로 몸무게와 키를 입력받는다. 이후, 반복문을 돌며, 자신보다 몸무게와 키가 모두 큰 사람의 수를 count 하고, 출력하면 된다. 코드 #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //입력 int n; cin >> n; vectorarr; int w, h;..

문제 https://www.acmicpc.net/problem/2798 문제 내용 카드 n개를 입력받아 3장을 뽑는다. 뽑은 카드를 다 합했을 때, m보다는 작거나 같으면서 만들 수 있는 최대의 값을 만들면 된다. 문제 풀이 완전 탐색으로 문제를 풀면 된다. 3장의 합이 m보다 작을 때, mmax의 값을 계속 갱신해가면서 확인하면 된다. 코드 #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //입력 int n, m; cin >> n >> m; vectorarr(n); for (int i = 0; i > arr[i]; //..

문제 https://www.acmicpc.net/problem/2309 문제 내용 9명의 키가 주어지고, 이들 중 2명을 제외하여 키의 합을 100으로 맞추는 문제이다. 문제 풀이 전형적인 완전 탐색 문제이다. 일단 입력받은 키들의 합을 구하고, 이중 for문을 돌며 두 명을 골라 제외시키며 키의 합이 100이 되는지 아닌지를 확인하면 된다. 만약 키의 합이 100이 되면, 나머지 수들을 바로 출력해주고 프로그램을 종료하면 된다. 코드 #include #include #include //accumulate() 들어있다. using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //입력 int arr[9]..

문제 https://www.acmicpc.net/problem/2231 문제 내용 자연수 N을 입력받아, N의 가장 작은 생성자를 구하는 문제이다. 즉, 우리의 결과값의 분해합을 구하였을 때 N이 만들어지면 된다. 문제 풀이 이 문제의 경우, 완전탐색 알고리즘(brute force)을 사용하여 문제를 해결했다. 이 문제의 결과값은 항상 1 이상, N 미만이다. (생성자가 없는 경우는 0) 따라서 for 반목문을 1~N-1까지 돌면서 각 숫자의 분해합을 구해보면 된다. 만들어진 분해합이 N과 같으면 종료하면 되고, for문이 끝날 때까지 결과가 나오지 않는다면 생성자가 없는 경우이므로 0을 출력하면 된다. 특정 숫자의 분해합을 구하는 과정은 while문을 통해 구현했다. 10으로 나누었을 때의 나머지를 차..

문제 https://www.acmicpc.net/problem/8892 문제 내용 입력받은 문자열들 중 2개를 골라 연결했을 때, 팰린드롬인지 아닌지 확인하는 내용이다. 가능한 팰린드롬들 중에 1가지만 출력하면 되며, 만들 수 없을 경우 0을 출력하면 된다. 문제 풀이 1. check_palindrome(string str) 함수 매개 인자로 전달받은 문자열이 팰린드롬인지 아닌지를 확인하는 함수이다. 문자열의 양 끝에서부터 가운데로 진행하며, 대칭인지 아닌지를 확인하면 된다. 2. solution() 함수 함수 안에서 먼저 주어지는 단어의 개수와, 단어들을 입력받는다. 이중 for문을 돌며, 단어 두 개를 골라 결합하여 check_palindrome()에 넘긴다. 반환된 값이 false이면 새로 단어를 ..