11689번: GCD(n, k) = 1 자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 분석 구하고자 하는 오일러 피의 범위만큼 리스트를 자기 자신의 인덱스 값으로 초기화 2부터 시작해 현재 리스트의 값과 인덱스의 값이 같으면(소수) 현재 선택된 숫자k의 배수에 해당하는 수를 리스트에 끝까지 탐색하며 P[i]=P[i]-P[i]/k 연산을 수행 (i는 k의 배수) 리스트의 끝까지 2를 반복하여 오일러 피 함수 완성 풀이 """ 자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오. 첫째 줄에 자연수 n (1 ≤ n ≤ 1012..

1016번: 제곱 ㄴㄴ 수 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수 www.acmicpc.net 분석 min ≤ max ≤ min + 1,000,000 : 일반적인 반복문으로 구하면 시간초과 범위 A~B사이 pow(정수 제곱수)로 떨어지는 수 구함 ➔ checkList[ (A/제곱수 ~ B/제곱수)*제곱수-A]=True Fase 개수 출력 1. 제곱수인 4 0 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 10 j=1 : (4*1)-1=3 (3번 인덱스 제곱수 True) j=2 : (4*2)-1=7 (7번 인덱스 제곱수 T..

1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 풀이 """ 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램을 작성하시오. """ import math n=int(input()) # 에라토스테네스 체 소수구하기 a=[0]*1000..

1456번: 거의 소수 어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다. www.acmicpc.net 분석 에라토스테네스의 체를 이용해 빠르게 소수를 먼저 구함 주어진 소수들의 N제곱값이 A~B 범위안에 존재하는지 판별하며 갯수 체크 풀이 """ 어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력 1 ≤ A ≤ B ≤ 10^14 5324 894739 183 """ import math min,max=map(int, input().split()) a..

10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 분석 N의 최대 개수가 10,000,000으로 매우 큼. 주어지는 숫자의 크기가 10,000보다 작은 자연수 계수 정렬의 시간복잡도 : O(kn) 수열 A : 5 2 3 1 4 2 3 5 1 7 count 배열 0 1 2 3 4 5 6 7 ... 10001 0 2 2 2 1 2 0 1 0 풀이 """ N개의 수가 주어졌을 때, 이를 오름차순으로 정렬 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,00..

1517번: 버블 소트 첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000의 범위에 들어있다. www.acmicpc.net 분석 N(1 ≤ N ≤ 500,000)이므로 nlogn 병합정렬로 풀이 시간복잡도, 시간제한, 빅오(Big-O) 표기법 1초 제한 n으로 구성된 O( )를 계산했을 때의 값이 1억 정도면 1초 정도의 시간이 걸린다고 한다. 예를 들어 N의 최대값이 10만이라고 문제에서 주어진다면 1. O(N) 의 시간복잡도일 경우에 값이 10만 karla.tistory.com 풀이 """ 1517 N개의 수로 이루어진 수열 A[1], A[2], …, A[..