본문 바로가기
반응형

개발👩‍💻

 (72)
백준 js 6913: GCD 합 문제 양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진다. 입력으로 주어지는 수는 1,000,000을 넘지 않는다. 출력 각 테스트 케이스마다 가능한 모든 쌍의 GCD의 합을 출력한다. 예제 입력 1 3 4 10 20 30 40 3 7 5 12 3 125 15 25 예제 출력 1 70 3 35 풀이 1번째 줄에 총 몇개의 테스트 케이스가 주어지는 지가 나와있고, 1번째 줄 제외 모든 줄 맨 앞에는 각 몇개의 수가 올지 나와있다. 그렇기 때문..
백준 js 2004: 조합 0의 개수 풀이 nCm(조합)에서 끝자리 0의 개수를 구하면 된다. 조합 공식은 n! / m! (n-m)! 이다. 만약 저 조합의 값을 구하고 0을 구하려고 한다면 원하는 답이 나오지도 않을 뿐 더러 시간 초과 걸릴 것이다. 위 값을 구하려고 한다면 Number 범위를 넘어버린다. 그렇기 때문에 각 팩토리얼 당 0의 개수를 구해서 더하고 빼주면 된다. 0의 개수를 구하기 위해서는 소인수 분해해서 5의 개수와 2의 개수를 알아야한다. 팩토리얼은 2의 개수가 항상 5보다 많거나 적기 때문에 5의 개수만 구하면 됐지만, 조합은 알 수 없기 때문에 2와 5를 모두 구해야 한다. n! / m! (n-m)!이기 때문에 n!의 2와 5의 개수를 구하고 그 값에서 m!의 2와 5의 개수를 빼고 (n-m)!의 2와 5의 개수를 빼..
백준 js 1676: 팩토리얼 0의 개수 문제 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500) 출력 첫째 줄에 구한 0의 개수를 출력한다. 예제 입력 1 10 예제 출력 1 2 예제 입력 2 3 예제 출력 2 0 풀이 0이 올 수 있는 것은 10^n 인 수에서 가능하다. 예를 들어 100라는 수가 있다면, 100 = [10^2] = [[5*2]^2] = [5*2 * 5*2]로 표현이 가능하고, 이러한 수의 개수를 찾기위해서는 이렇게 5*2를 만들 수 있는 5가 몇개 있는지 찾아보면 된다. (x! 에서 2는 항상 5보다 많거나 같기 때문) 예를 들어 10!이라는 수가 있다고 해보자 10! = 1 * 2 * ... * 5 * ... *10 이..
백준 js 10872: 팩토리얼 const input =주어진 값 const getFactorial = (n) => { let result = 1; for (let i = 1; i { if (n { let result = 1; for (let i = 1; i
백준 js 6588: 골드바흐의 추측 문제 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 ..
백준 js 1920: 소수 구하기 문제 M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. 출력 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다. 예제 입력 1 3 16 예제 출력 1 3 5 7 11 13 풀이 에라토스테니스의 체를 이용해서 소수를 구하는 문제 2부터 n까지의 수를 배열에 넣고 루프를 돌리면서 해당 수가 소수가 아니면 지워간다. check 배열을 통해 소수가 아닌 것은 true로 바꾸고, false로 남은 것들만 소수가 된다. 2부터 출발하는데, 2는 소수니까 소수 배열에 넣고, 2의 배수는 모두 소수가 아니니까 체크한다. 3이되고, 3은 소수니..
백준 js 1978: 소수 찾기 문제 주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오. 입력 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. 출력 주어진 수들 중 소수의 개수를 출력한다. 예제 입력 1 4 1 3 5 7 예제 출력 1 3 풀이 소수를 찾는 방법을 알면 쉽게 풀 수 있다. 소수는 2이상의 수 중, 나누어 지는 수(약수)가 자신과 1밖에 없는 수를 말한다. 그러면 해당 수를 n라고 하고, n가 소수인지 찾기 위해 루프문 내에서 하나씩 비교해보면 된다. 그렇게 되면 O(n)이 된다. 그러나 n = a * b (a √n => a * b > n a = b 이면 소수가 아니게 된다 (√n라는 수로 나누어지므로) 반대로 얘기하..
백준 js 17299: 오등큰수 문제 크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오등큰수 NGF(i)를 구하려고 한다. Ai가 수열 A에서 등장한 횟수를 F(Ai)라고 했을 때, Ai의 오등큰수는 오른쪽에 있으면서 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오등큰수는 -1이다. 예를 들어, A = [1, 1, 2, 3, 4, 2, 1]인 경우 F(1) = 3, F(2) = 2, F(3) = 1, F(4) = 1이다. A1의 오른쪽에 있으면서 등장한 횟수가 3보다 큰 수는 없기 때문에, NGF(1) = -1이다. A3의 경우에는 A7이 오른쪽에 있으면서 F(A3=2) < F(A7=1) 이기 때문에, NGF(3) = 1..

티스토리툴바