1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있 www.acmicpc.net 분석 최소공배수 = A * B / 최대공약수 풀이 """ 두 자연수 A와 B가 주어졌을 때, A와 B의 최소공배수를 구하는 프로그램을 작성하시오. 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 둘째 줄부터 T개의 줄에 걸쳐서 A와 B가 주어진다. (1 ≤ A, B ≤ 45,000) """ def gcd(a,b): if b==0: return a else: return gcd(b,a%b) T=int(input()) ..

1850번: 최대공약수 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A www.acmicpc.net 유클리드 호제법 두 수의 최대 공약수를 구하는 알고리즘 큰 수를 작은 수로 나누는 MOD 연산을 수행한다. 앞 단계에서 작은 수와 MOD 연산 결과값(나머지)으로 MOD 연산을 수행한다. 단계 2를 반복하다가 나머지가 0이되는 순간의 작은 수를 최대 공약수로 선택한다. 풀이 """ 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가..

1033번: 칵테일 august14는 세상에서 가장 맛있는 칵테일이다. 이 칵테일을 만드는 정확한 방법은 아직 세상에 공개되지 않았지만, 들어가는 재료 N개는 공개되어 있다. 경근이는 인터넷 검색을 통해서 재료 쌍 N www.acmicpc.net 분석 사이클이 없는 트리 구조이므로 임의의 노드에서 DFS를 진행하면서 해결 DFS 과정에서 유클리드 호제법을 사용해 비율들의 최소공배수와 최대공약수를 구하고, 재료의 최소 질량을 구하는데 사용 풀이 """ 칵테일에 들어가는 재료 N개는 공개되어 있다. 총 재료 쌍 N-1개의 비율이 입력으로 주어진다. 칵테일을 만드는데 필요한 각 재료의 양 이때, 필요한 재료의 질량을 모두 더한 값이 최소가 되어야 한다. a b p q : a번 재료의 질량을 b번 재료의 질량으..

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..