컴퓨터하는 kimmessi

https://euler.synap.co.kr/problem=11 11번 문제 20×20 격자에서 연속된 네 수의 곱 중 최댓값 euler.synap.co.kr 문제 해결 알고리즘 브루트 포스 알고리즘으로 푼다. 세로, 가로 대각선 2개 4개의 곱을 전부 비교해서 최댓값을 출력한다. 소스 코드 #include using namespace std; long max_result = 0; long arr[20][20]; int main(){ for(int i=0;i arr[i][j]; } } for(int i=0;i

https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 문제 해결 알고리즘 모든 노드에서 시작하는 DFS를 활용해서 문제를 풀어준다. 이 때 n이 1이면 런타임 에러가 나니 예외처리를 해주어야한다. 소스 코드 #include using namespace std; vector tree[100002]; vector resultArr; int maxValue = 0, result = 0; bool visited[100002]; void ..

https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 문제 해결 알고리즘 위의 문제대로 3가지로 방식대로 bfs를 해주는데 이 때, visited배열을 선언해주어서 만약 방문한 수가 visited배열에서 true값을 나타내면 그 수의 탐색을 하지 않는 식으로하면 시간 초과를 피할 수 있다. 소스 코드 #include using namespace std; bool visited[1000001]; typedef struct CT{ vector v; int result; }ct; void bfs(int N){ vector v; v.push_back(N); qu..

https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 문제 해결 알고리즘 DFS를 활용해 백트래킹 기법으로 모든 도시들을 탐색한 후에 가장 적은 비용을 출력해준다. 소스 코드 #include using namespace std; int N; int W[11][11]; bool visited[11]; int result = 99999999; bool visitedCheck(){ for(int i=2;i N;..

https://euler.synap.co.kr/problem=3 3번 문제 가장 큰 소인수 구하기 euler.synap.co.kr 문제 해결 알고리즘 2부터 N까지 모든 수들을 나눠준다. 이 때 또 그 수로 나눌 수 있다면 나눈다. 나눌 때마다 나눈 수를 출력한다. 소스 코드 #include using namespace std; int main(){ int N; cin >> N; if(N == 1) return 0; for(int i=2;i

https://euler.synap.co.kr/problem=2 2번 문제 피보나치 수열에서 4백만 이하이면서 짝수인 항의 합 euler.synap.co.kr 문제 해결 알고리즘 브루트 포스로 구해준다. 소스 코드 #include using namespace std; long long result = 0; int main(){ int fibo[10001]; fibo[0] = 1; fibo[1] = 2; for(int i=2;i

https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 문제 해결 알고리즘 각각의 사람들의 몸무게와 키를 전부 직접 비교해서 등수를 매긴다. 소스 코드 #include using namespace std; int main(){ int N; cin >> N; vector v(N); vector result(N); for(int i=0;i> v[i].first >> v[i].second; } for(int i=0;i

https://www.acmicpc.net/problem/3684 3684번: 어려운 문제 지난 acmicpc.net 대회에는 매우 어려워서 아무도 푼 사람이 없는 문제가 나왔었다. 그 문제의 데이터를 만드느라 엄청나게 고생한 백준이는 푼 사람이 없는 것을 보고 큰 좌절에 빠졌다. 백준이는 www.acmicpc.net 문제 해결 알고리즘 1. a와 b를 이중 for문으로 통해 0부터 10000까지 완전 탐색을 진행 하면서 배열에 입력 받은 값을 아래의 식에 두번 대입하면서 다음 값이 나오는지 확인한다. $$ x_i = (a x_{i-1} + b)\; \mathrm{mod} \; 10001 $$ 2. 모든 값이 전부 맞게 나온다면 이중 for문에서 나오고 그에 해당하는 a와 b값을 식에 대입해서 $x_2,..

www.acmicpc.net/problem/1747 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 문제 해결 알고리즘 이 문제는 간단한 브루트 포스 문제로 주어진 수(N)이상의 수가 팰린드롬 수이면서 소수인 수를 출력하면 되는 문제이다. check_1 함수는 소수 판정 함수인데 빠른 탐색을 위해 판정하는 수의 루트를 씌워준 값까지 나머지가 있는지 탐색한다. 이 방식을 이용하면 더 빠른 탐색이 가능하고, 탐색 중 나머지가 0이거나 마지막에 1은 소수가 아니므로 판정하는 수..

www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 문제 해결 알고리즘 문제에서 원하는 입력 값들을 전부 받은 후에 0 ~ 1000000까지의 수를 전부 조사한다. 결괏값은 초기에는 적당히 큰 수로 설정해준다. 1. 조사할 때, 그 수에 들어가면 안되는 숫자가 있는지, 이 수가 몇자리 수인지를 조사한다. 이 수를 num이라 하자. 2. 만약 이 수에 들어가면 안되는 숫자가 없으면 결괏값과 (num의 자릿수 + (N - num)의 절댓값)을 비교해..