[프로그래머스 Level1] 최대공약수와 최소공배수
📃 문제 설명
최대공약수와 최소공배수
👨💻 해결 방법
나는 단순하게
n과 m의 최대공약수를 구할 때
1부터 n,m 중 더 큰 수까지 반복문을 돌면서
둘 다 나누어 떨어지는 수 중 가장 큰 수를 구했다.
그리고 최소공배수를 구할 때는
n,m중 더 큰 수를 기준으로 *2,3,4....
이렇게 곱해나가면서 나머지 수로 나누어 떨어지는 가장 작은 수를 최소공배수로 했다.
그런데
최대공약수를 구할 때 유클리드 호제법을 이용하면 더 간단하게 풀 수 있었다.
유클리드 호제법
2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
이 성질에 따라, b를 r로 나눈 나머지 r’를 구하고, 다시 r을 r’로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.
자세한 것은 유클리드 호제법 정리
유클리드 호제법에 대해 정리할 수 있는 좋은 날이었다.
👨💻 소스 코드
def solution(n, m):
answer = [0]
temp = 1
while temp <= max(n, m):
if n % temp == 0 and m % temp == 0:
answer[0] = temp
temp += 1
temp = m
while temp % n != 0:
temp += m
answer.append(temp)
return answer
유클리드 호제법 이용
def solution(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
Author And Source
이 문제에 관하여([프로그래머스 Level1] 최대공약수와 최소공배수), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@choiyunh/프로그래머스-Level1-최대공약수와-최소공배수
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
최대공약수와 최소공배수
나는 단순하게
n과 m의 최대공약수를 구할 때
1부터 n,m 중 더 큰 수까지 반복문을 돌면서
둘 다 나누어 떨어지는 수 중 가장 큰 수를 구했다.그리고 최소공배수를 구할 때는
n,m중 더 큰 수를 기준으로 *2,3,4....
이렇게 곱해나가면서 나머지 수로 나누어 떨어지는 가장 작은 수를 최소공배수로 했다.그런데
최대공약수를 구할 때 유클리드 호제법을 이용하면 더 간단하게 풀 수 있었다.유클리드 호제법
2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
이 성질에 따라, b를 r로 나눈 나머지 r’를 구하고, 다시 r을 r’로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.
자세한 것은 유클리드 호제법 정리
유클리드 호제법에 대해 정리할 수 있는 좋은 날이었다.
👨💻 소스 코드
def solution(n, m):
answer = [0]
temp = 1
while temp <= max(n, m):
if n % temp == 0 and m % temp == 0:
answer[0] = temp
temp += 1
temp = m
while temp % n != 0:
temp += m
answer.append(temp)
return answer
유클리드 호제법 이용
def solution(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
Author And Source
이 문제에 관하여([프로그래머스 Level1] 최대공약수와 최소공배수), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@choiyunh/프로그래머스-Level1-최대공약수와-최소공배수
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
def solution(n, m):
answer = [0]
temp = 1
while temp <= max(n, m):
if n % temp == 0 and m % temp == 0:
answer[0] = temp
temp += 1
temp = m
while temp % n != 0:
temp += m
answer.append(temp)
return answer
유클리드 호제법 이용
def solution(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
Author And Source
이 문제에 관하여([프로그래머스 Level1] 최대공약수와 최소공배수), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@choiyunh/프로그래머스-Level1-최대공약수와-최소공배수저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)