[Python/파이썬] 프로그래머스 Lv2 - 숫자 나누기 (유클리드호제법)

문제 설명 제한사항 입출력 예 Solution.py 첫 번째, 두 번째 조건을 보면 철수가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고 영희가 가진 카드들에 적힌 모든 숫자들 중에 하나도 나눌수 없는 양의 정수 a => 철수가 가진 카드들의 최대 공약수 영희가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고 철수가 가진 카드들에 적힌 모든 숫자들 중에 하나도 나눌수 없는 양의 정수 a => 영희가 가진 카드들의 최대 공약수 로 해석할 수 있습니다. 유클리드 호제법을 사용해 철수와 영희의 카드뭉치 최대공약수를 구하기 구한 최대공약수로 두 조건들을 적용 두 최대공약수 중 가장 큰 값을 반환 정답 코드 def solution(arrayA, arrayB): answer = 0 # array의 첫 번째 값이 최대..

• format_list_bulleted ◼ 코딩테스트/구현 (Implementation)
• · 2023. 4. 4.
• textsms

[알고리즘] 유클리드 호제법 - 최소공배수, 최대공약수 구하기

유클리드 호제법 유클리드 호제법이란, 두 개의 수가 주어졌을 때, 최대공약수를 구하는 알고리즘입니다. 최소공배수는 주어진 두 개의 수를 곱한 값을, 그 두 개의 수의 최대공약수로 나누어 구할 수 있습니다. 최대공약수 : GCD(greatest common divisor) 최소공배수 : LCM(largest common multiple) 유클리드 호제법으로 최대공약수를 구하는 원리 1980과 168의 최소공배수를 유클리드 호제법을 이용하면 다음과 같은 과정을 거치게 됩니다. 1. 1980을 168로 나눕니다. 2. 1980을 168로 나눈 나머지 132와 168을 다시 나눕니다. 3. 168을 132로 나눈 나머지 36과 132를 다시 나눕니다. 4. 나머지가 0이 될때까지 반복합니다. 5. 나머지가 0이..

• format_list_bulleted ◼ CS 기초 지식/[알고리즘]
• · 2022. 10. 30.
• textsms