저별이의 초보 코딩

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

앞에 나오는 최소공배수와 최대공약수 구하기 문제는 쉽게 풀었다.

일반적으로 나오는 수학원리에 의해서 말이다.

이 문제는 조금 다르다.

이 문제는 유클리드 호제법을 활용하라고 한다.

먼저 문제를 살펴보자.

3
1 45000
6 10
13 17

45000
30
221

코드 및 설명

이렇게 문제가 제시 되었다.

코드를 보면서 하나 하나 풀어나가보자

cnt=int(input())
def BResult(n1, n2):
    if(n1%n2==0):
        return n2
    else:
        return BResult(n2,n1%n2)
def SResult(n1, n2):
    return int(n1*n2/BResult(n1,n2))
for _ in range(cnt):
    n1,n2=map(int,input().split())
    #if(n1<n2):
    #    n1,n2=n2,n1
    print(SResult(n1,n2))

이 문제를 재귀함수로 풀었다.

처음에 이해가 잘 안되서 다른 사람의 다른 프로그래밍 언어를 보면서 고쳐나간 코드이다.

일단 함수를 두개 선언했다. 최소공배수 문제인데 유클리드 호제법에서는 최대공약수를 바탕으로 최소공배수를 구할 수 있기 때문이다. 최대공약수를 BResult라고 함수를 만들었고 최소공배수를 SResult라고 만들어주었다.

여기서 다른 것 보다는 최대공약수 구하는 과정을 명확히 해야 할 필요가 있다.

유클리드 호제법은 n1,n2가 있다면 n1%n2가 0이 될때까지 무한히 재귀를 해주어야 하는 것이다. 그렇게 해서 n2를 리턴해준다. 그렇지 않는다면 n1의 자리에 n2의 값을 옮겨넣고 n2자리에는 나머지 값인 n1%n2값을 넣어준다.

이렇게 자리이동이 일어나게 된다. 

원리를 알아봤으니 최소 공배수를 구하는 과정을 알아보도록 하자

최소공배수를 유클리드 호제법으로 풀려고 한다면 n1*n2/(n1,n2의 최대공약수)가 식이라고 한다. 그래서 n1,n2와 함께 기존에 만들었던 함수인 BResult를 호출해서 만든 뒤 그 값을 리턴해주는 형태로 만들었다. 

리턴을 할 때 나는 int형으로 바뀌는 것을 포함시켰는데 그 이유는 나누기로 인해 소수점이 표시되었기 때문이다.

출력 예시에서는 int형이기에 이렇게 바꿔주었고 그렇게 리턴한 값을 메인에서 출력하도록 해주었다.

여기서는 유클리드 호제법이 무엇이고 어떻게 풀어나가야 하는지 설계를 하는 것이 중요한 문제인것 같다.

나의 결론은 유클리드 호제법은

n1,n2의 나머지 값이 0이될때까지 반복해서 계산해주는 것

이라고 생각한다. 아직 완벽하게 유클리드 호제법을 이해하지는 못했지만 코드를 짜면서 생각한 결과이다.