알고리듬/Math

문제 1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 바로 이전에 오는 순열을 구하는 프로그램을 작성하시오. 사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다. N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다. 1, 2, 3 1, 3, 2 2, 1, 3 2, 3, 1 3, 1, 2 3, 2, 1 입력 첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 순열이 주어진다. 출력 첫째 줄에 입력으로 주어진 순열의 이전에 오는 순열을 출력한다. 만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력한다. 풀이 앞서 풀었던 다음 순열과 비슷하게 접근하여 풀면 될 것 같다 먼저 이전 순열을 구하기..

문제 1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 다음에 오는 순열을 구하는 프로그램을 작성하시오. 사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다. N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다. 1, 2, 3 1, 3, 2 2, 1, 3 2, 3, 1 3, 1, 2 3, 2, 1 입력 첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 순열이 주어진다. 출력 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. 풀이 처음에 문제를 보고 재귀를 통한 완전탐색으로 비교를 통해 입력받은 순열을 찾고 다음 순열을 출..

조합 nCm의 값 중 끝에 오는 0의 개수를 구하는 문제이다 nCm = n! / (n-m)!*m! 공식을 사용하여 팩토리얼을 계산하고 0의 개수를 세어줄 수 있겠지만 정수 n,m의 범위를 보았을 때 시간 초과가 날 것을 고려하여 소인수분해를 사용하였다 nCm을 소인수분해 하였을 때 2와 5가 한 쌍이 되어 하나의 0이 만들어지기에(2*5 = 10) 5의 개수가 더 작을 것이라 생각하고 5의 개수를 구하였다 5 = 5 25 = 5*5 125 = 5*5*5 와 같은 패턴을 적용하여 소인수분해 하고자 하는 limit내의 지수 5의 개수를 구하였다 제출 결과는 틀렸으며 지수 2의 개수가 5의 개수보다 적은 경우도 존재한다는 것을 알았다 지수 2와 5의 개수를 모두 구하기 위해 함수를 만들고 def CountZe..

문제 1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다. 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다. 예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다. 이 추측은 아직도 해결되지 않은 문제이다. 백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오. 입력 입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다. 테스트 케이스의 개수는 100,000개를 넘지 않는다. 각 테스트 케이스는 짝수 정수 n 하나로 이루어져 있다. (6 ≤ n ..

두 개의 자연수를 입력받고 최대 공약수와 최소 공배수를 출력하는 간단한 문제이다. 최대 공약수는 greatest common divisor의 약자를 사용해서 GCD로 줄여 부르며 최소 공배수는 largest common multiple로 LCM으로 줄여 부른다 GCD와 LCM을 구하는 방법은 다양하다 GCD를 구하는 직관적인 방법으로 1씩 증가시키며 두 수에 모두 나누어 떨어지는지 확인하여 가장 큰 수를 찾아내는 방법이 있다. for i in range(1,min(x,y)+1): if x%i==0 and y%i==0: res = i 이 방법은 O(n)의 시간복잡도를 갖는다 시간 복잡도 측면에서 효율적인 방법으로는 유클리드 호제법이 있다 x,y의 최대 공약수를 구할 때 유클리드 호제법을 사용하면 큰 수를 ..