[프로그래머스_Lv1] 최대공약수와 최소공배수
최대공약수와 최소공배수
- 나의 풀이
def solution(n, m):
answer = []
for i in range(min(n, m), 0, -1):
if n % i == 0 and m % i == 0:
print(i)
break
for j in range(max(n, m), (n * m) + 1):
if j % n == 0 and j % m == 0:
print(j)
break
answer = [i, j]
return answer
- 최대공약수 : 자연수 n, m중 작은 수 부터 1까지 1씩 감소하는 범위를 갖는 for 반복문을 진행하였고, 자연수 n, m 모두 i로 나누었을때 나머지가 0이 될때의 i 값이 최대공약수이다.
- 최소공배수 : 자연수 n, m중 큰 수부터 n*m 값까지의 범위를 갖는 for 반복문을 진행하였고, 자연수 n, m 각각을 j로 나누었을때 나머지가 0이 될때의 j 값이 최소공배수이다.
- i(최대공약수), j(최소공배수) 값을 answer 변수에 할당하여 return!
- 다른사람의 풀이
def gcdlcm(a, b):
c, d = max(a, b), min(a, b)
t = 1
while t > 0:
t = c % d
c, d = d, t
answer = [c, int(a*b/c)]
return answer
- 유클리드 호제법으로 풀이한 코드이다. max, min함수를 이용하여 변수를 재할당하였고 while 반복문을 이용하여 비교적 간단하게 유클리드 호제법을 표현한 것을 볼 수 있다. 유클리드 호제법에 대한 간략한 설명은 아래와 같다.
유클리드 호제법
-
유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다.
(출처 : 위키백과) -
코드 작성을 위해 좀 더 쉽게 설명하자면,
자연수 a를 b로 나눈 나머지와 b의 최대공약수는 a, b의 최대공약수와 같다는 원리가 핵심이다. 따라서 나눗셈만 반복하여 최대공약수 값을 구할 수 있다. -
자연수 a, b가 주어졌을때, a를 b로 나누어 나머지를 구한다. 그리고 b를 a위치에, a%b(a를 b로 나눈 나머지 값) 값을 b위치에 할당하여 b값이 0이 될 때까지 반복한다.
이를 코드로 작성하면 아래와 같다.
def GCD(a, b):
while b > 0:
a, b = b, a % b
return a
Author And Source
이 문제에 관하여([프로그래머스_Lv1] 최대공약수와 최소공배수), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@lck0827/프로그래머스Lv1-최대공약수와-최소공배수저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)