문제 설명
두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.
제한 사항
- 두 수는 1이상 1000000이하의 자연수입니다.
입출력 예
| n | m | return |
| 3 | 12 | [3, 12] |
| 2 | 5 | [1, 10] |
입출력 예 설명
입출력 예 #1
위의 설명과 같습니다.
입출력 예 #2
자연수 2와 5의 최대공약수는 1, 최소공배수는 10이므로 [1, 10]을 리턴해야 합니다.
✅SOL_1
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
def solution(n, m):
answer = []
temp = 0
if n > m:
temp = n
n = m
m = temp
y = m * n
x = m % n
if x == 0:
answer.append(n)
elif x != 0:
while x != 0:
m = n
n = x
x = m % n
answer.append(n)
answer.append(y/n)
return answer
|
cs |
최대공약수를 구하는 유클리드 호제법 알고리즘을 사용한 코드이다. 처음엔 이 알고리즘을 사용하지 않고 코드를 작성해보려고 고민을 많이 했는데, 쉽지 않았다. 먼저 위의 코드에서 유클리드 호제법을 사용하기 위해 전제가 필요하다. 입력된 두 값 n, m에서 큰 수 와 작은 수를 정해주어야 한다. 문제에서 큰 수가 먼저 입력된다와 같은 조건은 없기 때문에, 함수 내에서 정해주기로 하였다. 순서를 어떻게 해도 상관없지만 나는 n을 작은 수, m을 큰 수로서 정해주기 위해 if문을 사용하였다. temp 변수를 선언하여 if문에서 만약 n이 m보다 크다면 두 수의 위치를 바꿔주기 위해 temp <- n, n <- m, m <- n 와 같이 두 변수의 데이터 값을 바꿔주었다. 그렇게 n이 작은 수, m이 큰 수 임 확정되었으면 n과 m의 곱을 y에, m을 n으로 나눈 나머지를 x에 저장한다. 유클리드 호제법을 사용하면 n과 m에 저장되는 데이터 값이 계속해서 변할 수 있기 때문에 나중에 쓰일 곱과 나머지를 미리 저장해두는 것이다. 이렇게 모든 준비를 마친 후 유클리드 호제법을 사용한다
유클리드 호제법은 이렇다.
2개의 자연수 a, b에서 a를 b로 나눈 나머지를 r이라 하자(단, a>b). a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라 b를 r로 나눈 나머지 r'을 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.
첨부한 메모를 보면 이해가 빠르다. 주황색 화살표처럼 나누는 수를 나눌 수로, 나머지를 나누는 수로 계속해서 내려가다 보면 언젠가 나머지가 0이 나온다. 이때 나누는 수가 a와 b의 최대공약수이다.
따라서 작성한 코드를 보면, if-elif문을 통해 m을 n으로 나눈 나머지, 즉 입력된 값 중 큰수를 작은 수로 나눈 나머지가 0이면 작은 수가 곧 최대 공약수가 되므로 바로 n을 append 한다. 하지만 그 경우가 아니면 elif를 통해(else를 사용해도 됐었다) while문을 작동시킨다. x가 0이 아닐 동안, 즉 x가 0이 되면 반복문은 멈춘다. 이때 x는 큰 수를 작은 수로 나눈 나머지 값을 계속해서 받게 된다. while문에서 먼저 입력된 값 중 작은 수를 나눌 수(m)에 저장하고, 나머지는 나누는 수(n)에 저장하고, 저장된 두 값을 나눈 나머지를 x에 저장한다. 이 과정을 반복하면 결국 x가 0이 되어 반복문이 끝나고 이때의 나누는 수(n)가 최대공약수 이므로 append 한다.
그리고 최소공배수를 append해준다. 최소공배수는 최초의 입력된 값 m과 n의 곱을 유클리트 호제법을 통해 나온 최대공약수로 나누어 구한다. 최대공약수를 구하는 과정에서 최초의 입력된 값이 없어질 수 있기 때문에 위에 변수 y에 두 값의 곱을 저장한 것이다. 따라서 y를 최대공약수 n으로 나눈 값을 append 하면 리스트 answer에는 최대공약수, 최소공배수가 순서대로 저장되어 return 된다.
✅SOL_2
|
1
2
3
4
5
6
7
8
9
10
|
def solution(n, m):
n, m = max(n, m), min(n, m)
x = n % m
y = n * m
while x != 0:
n = m
m = x
x = n % m
return [m, y/m]
|
cs |
SOL_1과 같은 코드이다. 하지만 이 코드에서 if문을 사용하지 않았다. 불필요한 것은 빼고 간단하게 작성 가능한것을 적용하면 이렇게 깔끔한 코드가 나올 수 있다. 먼저 python에는 인수로 받은 자료형 내에서 최댓값, 최솟값을 반환해주는 max와 min함수가 있다. 리스트를 인수로 작성하면 리스트 내에서 최대, 최소 값을 반환하고 위의 코드와 같이 두 값을 인수로 작성하면 두 값 중 최대, 최소 값을 반환한다. 따라서 변수 n과 m에 각각 max(n, m), min(n, m)의 값을 저장하여 n> m임을 확정한다. (위의 SOL_1에서는 m> n로 적용하여 코드를 작성해서 차이가 있다.) 그리고 n과 m의 값이 최초의 입력값에서 바뀔 수 있으므로 x와 y에 나머지와 곱을 각각 저장한다. while문을 통해 x가 0이 아닐 동안, x가 0이 될 때까지 유클리드 호제법 알고리즘을 적용한다. 이때 if문을 통해 최초의 x값이 0 임을 확인하여 따로 저장하지 않은 이유는 한 번에 나머지가 0이 되어도, 유클리드 호제법을 몇 번을 거쳐 나머지가 0이 되어도, 결국 최대공약수는 m으로 지정되기 때문이다. 그렇게 최대공약수가 정해지면 따로 리스트를 선언하지 않아도 위 코드와 같이 return문에서 < [m, y/m] >과 같이 리스트 형태로 반환할 수 있다.
'Python 공부기록' 카테고리의 다른 글
| Python _ 문자열 다루기 기본 (0) | 2021.03.15 |
|---|---|
| Python _ 정수 내림차순으로 배치하기 (1) | 2021.03.11 |
| Python _ 수박수박수박수박수? (0) | 2021.03.09 |
| Python _ 정수 제곱근 판별 (0) | 2021.03.08 |
| Python _ 제일 작은 수 제거하기 (1) | 2021.03.05 |