기록방

👉 문제링크 11689번: GCD(n, k) = 1 자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 🔸 문제 분석 🔸 1부터 자연수 n까지의 범위에서, 최대공약수(GCD)가 1인 자연수의 개수를 구하는 문제이다. 다시 말하면 서로소의 개수를 구하는 문제이다. 🔸 문제 풀이 🔸 서로소 개수를 구하는 공식으로 오일러의 피 함수(Euler product formula; 오일러 곱 공식)을 사용한다. n의 소인수로 P[i] = P[i] - P[i]/K (i는 K의 배수) 연산을 반복한다. n이 소수이거나, n이 지수가 1인 소인수를 가지는 경우, 오일러 피 함수를 1회 더 적용한다. 🔸 코드 🔸 impo..

👉 문제링크 1016번: 제곱 ㄴㄴ 수 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수 www.acmicpc.net 🔸 문제 분석 🔸 주어진 범위에서 1보다 큰 수의 제곱수로 나누어 떨어지지 않는 수의 개수를 출력한다. 최소값이 1부터 1조, 최대값은 최소값부터 100만을 더한 값까지 주어진다. 🔸 문제 풀이 🔸 min과 max의 값이 1조까지 크게 주어지므로 long으로 받야아 한다. 제곱수를 확인하기 위해 에라토스테네스의 체 알고리즘을 사용한다. 배열의 크기를 max-min+1 만큼 차이로 선언한다. 제곱수의 배수를 max까지 계산하며 에라토스..

👉 문제링크 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 🔸 문제 분석 🔸 소수를 구한 후 오름차순으로 팰린드롬을 찾아 출력한다. 🔸 문제 풀이 🔸 N이 100만까지 입력되는데, 여유있게 1000만까지 소수를 구한다. 팰린드롬은 수를 char배열로 변환한 뒤 투포인터로 판단한다. 🔸 코드 🔸 import java.io.*; public class Main { public static void main(String[] args) throws IOException { Bu..

👉 문제링크 1456번: 거의 소수 어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다. www.acmicpc.net 🔸 문제 분석 🔸 어떤 소수의 N제곱 (N>2)의 수를 거의 소수라고 한다. A이상 B이하의 거의 소수의 개수를 출력한다. (1

👉 문제링크 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 🔸 문제 분석 🔸 피보나치 수열을 구현하는데 n이 1,000,000,000,000,000,000 으로 매우 큰 수가 주어진다. 🔸 문제 풀이 🔸 피보나치 수열을 구현하는데 반복문, 재귀, 동적 계획법을 사용할 수 있지만, 매우 큰 n에 대해서는 분할 정복을 이용한 거듭제곱을 이용해야한다. 행렬 곱셈을 이용한다. n번째 피보나치수는 (n/2-1)번째 피보나치 수[k1]와 (n/2)번째 피보나치 수[k2], (n/2+1)번째 피보나치 수[k3], (n/2+2)번째 피보나치 수[k4]로 나타낼 수 있다. EX ) 0, 1, 1, 2,..