[백준 2609번] 최대공약수와 최소공배수

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

---

문제 상황

주어지는 두 자연수에 대해

최대공약수와 최소공배수를 순서대로 구해야하는 문제이다.

---

솔루션

1. 최대공약수

2. 최소공배수

하나씩 구해내는 솔루션을 택했다.

 

1. 최대공약수 솔루션

주어진 두 자연수의 약수를 각각 모두 구했다.

약수 중 공통되는 것을 찾아 공약수 리스트를 구하고,

공약수 리스트의 최댓값을 최대공약수로 출력했다.

 

2. 최소공배수 솔루션

주어진 두 자연수 중 하나를 숫자 1부터 배수로 곱하며,

나머지 다른 자연수와 나누어 떨어지면,

"주어진 자연수 중 하나 X 배수" 를 최소공배수로 출력했다.

 

즉, 최대 공약수, 최소공배수를 구하고자
주어진 두 자연수의 모든 약수와 배수를 고려해서

최대 공약수, 최소공배수를 구해냈다.

(브루트포스 알고리즘으로 작성했다. ㅎㅎ..)

---

솔루션 코드 작성

# 최소공약수와 최소공배수

# 두 자연수 입력
num_1, num_2 = map(int, input().split())

# 공약수 리스트
num_1_C = []
num_2_C = []
num_C = []

# 최대 공약수
# 공약수 리스트 채우기
for i in range(1, num_1 + 1):
  if(num_1 % i == 0):
    num_1_C.append(i)

for i in range(1, num_2 + 1):
  if(num_2 % i == 0):
    num_2_C.append(i)

# 최대 공약수 판별
for i in range(len(num_1_C)):
  for z in range(len(num_2_C)):
    if(num_1_C[i] == num_2_C[z]):
      num_C.append(num_1_C[i])

print(max(num_C))



# 최소 공배수

# 배수 변수 초기화
multiple = 1
while True:
  if((num_1 * multiple) % num_2 == 0):
    break
  multiple += 1
  
print(num_1 * multiple)

---

마치며

이번 문제는 "브루트포스 알고리즘"에 기반해 코드를 작성할 수 있었다.

최대공약수, 최소공배수 모두 주어진 두 수의 모든 경우를 고려해 문제를 해결했다.

 

유클리드 호제법으로 문제를 수학적 사고로 접근해 해결할 수 있었다.

int gcd(int a, int b)
{
    while (b > 0)
    {
        int tmp = a;
        a = b;
        b = tmp%b;
    }
    return a;
}

그렇다. 수학적 사고로 접근하면, 최적화된 속도로 문제를 해결해낼 수 있다.

빅오로만 따져보면,

내가 구현한 코드는 O(n^2) 이다.

유클리드 호제법으로 해결한 코드는 O(n)이다.

속도 측면에서 보면, 수학적 사고로 접근한 유클리드 호제법을 활용한 코드가 훨씬 더 우세하다.

 

따라서, 수학적 사고를 활용한 솔루션 코드가

최적화된 결과를 제공한다는 사실을 깨닫게 해준 문제였다.

앞으로, 수학적 사고를 활용해 최적화된 코드를 작성하는 연습을 차근차근해보도록 하겠다!