Future is now

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번째 사람을 출력한 후 큐에서 제거합니다. 이를 큐가 비게 될 때까지 반복해주면 됩니다. 또한 문제의 출력 형식에 맞추기 위해 큐에 데이터가 있는 경우에만 콤..