파이썬 알고리즘 백준 2609

파이썬 알고리즘 백준 2609

https://www.acmicpc.net/problem/2609

2609번: 최대공약수와 최소공배수

import sys
input = sys.stdin.readline

num_list = list(map(int, input().split()))
# 여기에 num_list = num_list2 이런식으로 해버리면
# 동일한 메모리값을 가지기 떄문에 num_list가 바뀐만큼 num_list2도 바뀐다.
num_list2 = num_list[:]
# [:] 말고 copy()도 가능함.
num_list.sort()
num_list2.sort()
# 처음에 sort를 하여 계산할 준비를 한다.

while True:
    if num_list[1] % num_list[0] == 0: # 최대 공약수
        print(num_list[0])
        # 나눠서 0으로 떨어지면 작은 수가 최대 공약수 이기 때문
        target_number = num_list[0] #최대 공약수 넣은 것

        #if문으로 최대 공약수를 구했을 경우
        #for문으로 들어와 최소 공배수를 구한다.
        for i in num_list2:
            #처음에 그대 저장되어있던 list2를 for문으로 돌리고,
            target_number = target_number * int(i/num_list[0])
            # num_list가 이미 최대공약수이기 때문에 처음에 적은
            # 두 수 를 최대공약수로 나누고, 그게 a, b라 가정하면
            # a x b x 최대공약수 = 최대공배수
            # 이기 때문에 저장되어있던 num_list2를 가지고와 최대공약수로 각각 나눈 후
            # 최대공약수와 각각의 i를 곱한다.
        print(target_number) # 최소 공배수 출력
        break #최대공약수를 이용한 최소 공배수까지 구했다면 while문 탈출

    else :
        num_list[1] = num_list[1] % num_list[0]
    num_list.sort()
    #sort 하여 다시 나눌 수 있게 한다.

유클리드 호제법으로 풀면 쉽게 풀 수 있다.

 

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

유클리드 호제법

최대 공약수

: a와 b의 최대 공약수를 구하려면

b > a

: b%a를 구한 후, 0으로 떨어지면

: a는 최대 공약수

: 만약 안 떨어지면 b%a % a를 한다.

이렇게 계속 반복해서 0으로 떨어질 경우, 그게 최대 공약수

 

최소 공배수

: 최대공약수 x a/최대공약수 x b/최대공약수

 

num_list = num_list2 = list(map(int, input().split()))

처음에 리스트를 이런 식으로 1과 2를 각각 저장했는데,

 

당연히 각각의 리스트값이 유지될 줄 알았지만,

 

동일한 메모리를 가르키고 있어서, num_list가 바뀌면 num_list2도 바뀐다.

 

그래서

 

num_list2 = num_list로 바꾸었는데도, 똑같았다.

 

처음에 받은 리스트값을 각각 유지시키고 싶으면

 

.copy(0) 나 리스트인 경우는 [:]를 붙여서 해결할 수 있다.