Future is now

https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 문제에서 주어진 수열의 순서는 변경이 없고, 주어진 연산자들의 순서만 바꿀 수 있습니다. 또한 연산사 우선순위를 따지지 않고 앞에서부터 계산하는데, 그때 가능한 최대값과 최소값을 구하는 문제입니다. 연산자를 +, -, *, / 의 순서대로 배열에 저장합니다. 배열에 저장할 때는 덧셈부터 차례대로 0, 1, 2, 3이 되며, 덧셈이 두개라면 0..

https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 이번 로또 문제는 주어진 k개의 수들 중에 6개의 수를 골라서 출력하는 문제입니다. k가 8이라고 했을 때 k개 중에 6개를 고른다는 것은 k개 중에 2개를 고르는 것과 같습니다. 골랐다는 의미를 1이라고 하고, 고르지 않았음을 0이라고 했을 때, 골라야 하는 수의 개수는 6개이므로 고르지 않은 수는 k-6개입니다. 새로운 순열을 하나 만드는데, 0을 k-6개, 1을 6개 넣은 배열을 ..

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 외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 유명한 문제 중 하나입니다. 모든 도시를 거쳐가는 순서들 중 가장 적은 비용을 들이는 외판원의 순회 경로를 구하는 것인데요. 한번 갔던 도시로는 다시 갈 수 없고, 모든 도시를 거친 후 다시 원래의 도시로 돌아와야 합니다. 세부 문제 내용은 위 링크..

https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 배열에 들어있는 정수의 순서를 적절히 바꿔서 문제에서 주어진 식의 최대값을 구해야 합니다. 수의 개수 제한이 N (3 ≤ N ≤ 8) 이므로 최대 8개의 수를 일렬로 나열하는 경우의 수는 \(8!\)이 됩니다. \(8! = 40,320\)가지이므로 4만여정도는 모든 경우의 수를 다 계산해보아도 무리가 없습니다. (1억가지의 수가 대략 1초 소요) 모든 경우의 수를 찾아보기 위해 순열을 이용하는 브루트포스 알고리..

https://www.acmicpc.net/problem/10972 10972번: 다음 순열 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 순열이란 서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 선택하는 혹은 나열하는 것을 순열(permutation)이라고 합니다. (나무위키 순열 정의 참조) 예를 들어 1 2 3 수들을 순열로 나열해보면, 1 2 3 (오름차순) 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 (내림차순) 이러한 형태가 나타납니다. 여기서 특징은 첫 순열은 항상 오름차순, 마지막 순열을 항상 내림차순 형태를 띄게 됩니다. 또한 부분 순열을 살펴봤을 때에도 부..

https://www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타 www.acmicpc.net 이 문제는 두가지 방법으로 풀어보았습니다. 그러나 맥락은 결국 같은 방법인데, 모든 경우의 수를 다해보는 것입니다. 모든 경우의 수를 다 따져보는 것을 브루트 포스(Brute force) 알고리즘이라고 합니다. [코드1] 첫번째 방법은 E, S, M을 계속 증가시켜보면서 입력으로 주어진 e, s, m과 일치하는 경우 그때의 년도(i)를 출력하는 것입니다. 최대 년도는 문제에서 주어진 e, s, m의 제..

https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 소수는 약수를 1과 자기 자신만 갖는 수입니다. 하나의 소수를 찾는 방법은 간단한데요. 어떤 수 n이 소수인지 아닌지 판단하기 위해서는 2부터 n 직전의 수까지 전부 나누어보면서 한번이라도 나누어 떨어지게 되면 소수가 아니게 되죠. (어떤 수의 약수를 찾는 방법과 동일) 아래 코드의 prime 함수에서 for문의 조건문 i * i input; if(prime(input)) cnt++; } cout m >> n; for (int i = 2; i * i

https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 1. 최대공약수(Greatest Common Divisor) 구하기 유클리드 호제법(Euclidean algorithm)을 이용하는 방법입니다. * 유클리드 호제법 a를 b로 나눈 나머지를 r이라고 할 때, GCD(a,b) = GCD(b,r) 이다. r이 0이면 그 때의 b가 최대공약수가 됩니다. 세 수의 최대공약수를 구해야할 때는 GCD(a,b,c) = GCD(GCD(a,b),c) 로 구할 수 있습니다. 즉, 먼저 두 수의 최대공약수를 구한 값과 c와의 최대공약..

https://www.acmicpc.net/problem/10430 10430번: 나머지 첫째 줄에 A, B, C가 순서대로 주어진다. (2 ≤ A, B, C ≤ 10000) www.acmicpc.net 종종 문제에서 구하는 정답의 크기가 너무 클 경우 정수로 저장할 수 있는 범위에 한계가 있기 때문에 결과를 X로 나눈 나머지를 구하라고 하기도 합니다. 이 문제에서는 단순히 두 식의 결과값이 동일한지를 값을 출력만 하면 됩니다. 1. (A+B)%C는 ((A%C) + (B%C))%C 와 같을까? 2. (A×B)%C는 ((A%C) × (B%C))%C 와 같을까? 질문의 정답은 둘다 YES입니다. +과 x 연산에서는 %를 분배법칙처럼 각각의 수에 연산해준 다음 다시 전체를 C로 나누더라도 동일한 값이 출력됩니..

https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 1부터 n명까지의 사람이 원형으로 있다고 생각해보면, k번째 사람을 제거하는 것인데 제거하고 난 후에도 사람이 0명이 될 때까지 계속 k번째 사람을 제거하고, 제거되는 차례대로 출력하는 문제입니다. 큐의 성질을 이용하여 요세푸스 문제를 풀어보았습니다. k번째 사람을 제거해야 하므로 k-1번째까지의 사람은 빼서 다시 큐에 넣어주고, k번째 사람을 출력한 후 큐에서 제거합니다. 이를 큐가 비게 될 때까지 반복해주면 됩니다. 또한 문제의 출력 형식에 맞추기 위해 큐에 데이터가 있는 경우에만 콤..