최대공약수

멀쩡한 사각형 (최대공약수)

https://school.programmers.co.kr/learn/courses/30/lessons/62048 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 분석 1. 가로 세로 최대공약수 구하기 2. 작은 직사각형 가로 세로 구하기 : 가로/최대공약수, 세로/최대공약수 2. 작은 직삭각형 빈칸 크기 : 작은 직사각형 가로 + 작은 직사각형 세로 - 1 전체 직사각형 빈칸 크기 : 작은 직사각형 빈칸 크기 * 최대공약수 3. 전체 크기에서 빈칸 크기 빼기 가로 8, 세로 12 1. 가로 세로 최대공약수 : 4 2. 작은 직사각형 가로 : 8/4 = 2..

숫자 카드 나누기 (최대공약수)

https://school.programmers.co.kr/learn/courses/30/lessons/135807 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 분석 1. 각 배열의 최대공약수 구하기 2. 최대공약수로 다른 배열의 숫자가 나눠지는지 확인하기 3. 최대값 리턴 풀이 import sys,math def solution(arrayA, arrayB): def find(array): #최대공약수 GCD = 0 for i in range(len(array)): GCD = math.gcd(GCD, array[i]) return GCD def chec..

[9613] GCD 합 (조합)

9613번: GCD 합 첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진 www.acmicpc.net 풀이 """ 양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오. 첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진다. 입력으로 주어지는 수는 1,000,000을 넘지 않는다. """ import sys input=sys.stdin...

확장 유클리드 알고리즘

확장 유클리드 호제법 유클리드 호제법 : 두 수의 최대 공약수 구하기 확장 유클리드 호제법 : 방정식의 해 구하기 베주 항등식 (Bezout's Identity) 의 명제를 기반으로 해를 구하는 알고리즘 베주 항등식 (Bezout's Identity) ax + by = d 를 만족하는 (x, y) 정수해는 d 의 값이 gcd(a, b) 의 배수일 때 존재하며, 이 존재하는 경우 나오는 값들만 (x, y) 의 정수해가 될 수 있다. 즉, d % gcd(a, b) == 0 인 경우이다. 만약 4x + 3y = 2 이라는 방적식이 있다고 하자. 이 때 (x, y)의 정수해는 ... ,(-1, 2), (2, -2), (5, -6), ... 등이 된다. 4, 3 의 최대공약수는 1이며 우변의 2는 1의 배수이기 ..

[10934] 최소공배수 (유클리드 호제법)

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] 최대공약수 (유클리드 호제법)

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