[Swift] 프로그래머스 연습 문제(Level 1) : 최대공약수와 최소공배수

실제 코딩테스트의 문제를 통하여 알고리즘 분석과 코딩 능력을 향상시킵니다.

 

 

#. 구독 대상

• 기본 알고리즘을 코딩 테스트 문제를 통하여 학습하고 싶으신 분
• 취업 및 이직을 준비하고 계신 개발자
• Swift를 통하여 코딩 테스트 문제를 살펴보고 이해를 하고 싶으신 분
• 코딩 테스트에 대한 거부감을 없애기 위하여 기초부터 하나씩 공부해보고 싶으신 분
• 기타 알고리즘과 문제 해결 능력에 대해서 관심이 있는 모든 개발자분

참고 사항

본 코딩 테스트 문제에 대한 설명 및 해결 방안은 최적의 답이 아닐 수 있습니다.

본 강의에서 지향하는 목표는 바로 특정 문제에 대한 최적의 해결 방법을 찾기보다는 특정한 문제에 대해서 충분히 이해할 수 있고 다양한 방법을 통하여 해결하는 방법을 찾고 향상시키는데 그 목적이 있습니다.

좀 더 좋은 알고리즘 및 코드가 있으시다면 언제든지 본 게시물의 댓글을 통해서 제시해주시면 감사하겠습니다.

 

 

 

---

 

 

 

코딩 테스트 문제

 

먼저 오늘 살펴볼 문제에 대해서 먼저 살펴보겠습니다.

 

https://programmers.co.kr/learn/courses/30/lessons/12940

코딩테스트 연습 - 최대공약수와 최소공배수

 

 

 

---

 

 

 

문제 설명

 

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

 

 

 

 

---

 

 

 

제한 조건

 

• 두 수는 1이상 1000000이하의 자연수입니다.

 

 

 

 

---

 

 

 

 

입출력 예

n	m	return
3	12	[3, 12]
2	5	[1, 10]

 

 

 

 

---

 

 

문제 분석

 

오늘 문제는 입력되는 두 정수에 대해서 최대공약수와 최소공배수를 구하여 각각 반환하는 문제입니다.

오늘의 문제를 풀기위해서는 최대공약수와 최소공배수의 개념을 먼저 파악할 필요가 있습니다.

 

 

 

 

최대공약수?

 

어떠한 자연수가 있을 경우 해당 수보다 낮은 자연수 중에서 나누었을 때 나머지가 0으로 떨어지는 모든 수들을 바로 약수라고 합니다.

그리고 자연수 2개가 있을 경우 각 자연수들의 약수를 나열하였을 때 두 자연수가 가지는 공통의 약수를 공약수라고 합니다.

 

여기서 최대공약수란, 공통의 약수 중 큰 자연수를 의미합니다.

 

 

 

예) 16과 20의 최대공약수는 16의 약수이면서 20의 약수인 수 가장 큰 수입니다.

 

16의 약수 : 1, 2, 4, 8, 16

20의 약수 : 1, 2, 4, 5, 10, 20

 

이 두 수의 공통된 약수는 1, 2, 4이며 그 중 가장 큰 수가 4이므로 두 수의 최대공약수는 바로 4입니다.

 

최대공약수를 수학적 표현으로 표현하면 아래와 같습니다. 

 

gcd(16, 20) = 4

 

 

문제는 주어진 자연수가 작을 경우는 약수와 최대공약수를 하나씩 수를 대입하면서 구할 수 있겠지만 수가 클 경우는 그렇게 하기에는 다소 힘들 수 있습니다.

 

따라서 우리는 최대공약수를 구하는 효율적인 알고리즘이 필요합니다. 대표적으로 최대공약수를 구하는 방벙에는 소인수분해, 유클리드 호제법 등 여러 방법이 있습니다. 여기서 우리는 유클리드 호제법이라는 방법을 통하여 한번 최대공약수를 구해보도록 하겠습니다.

 

 

 

 

유클리드 호제법 :

기원전 300년경에 발견된 가장 오래된 알고리즘으로서 유클리드(Euclid) 라는 사람이 발명한 공식입니다.
해당 알고리즘의 큰 개념은 큰 수에서 작은 수로 나누어 나머지 구하고 나눈 몫을 또 계속 나누어 나머지가 0이 될때까지 반복한다는 원리입니다.

 

위에서 제시된 16과 20을 예시로 한번 최대공약수를 유클리드 호제법으로 구해보도록 하겠습니다.

 

20 / 16 = 1(나머지 4)

16 / 4 = 4(나머지 0), 연산 종료 해당 식에서의 몫이 바로 최대공약수

 

따라서 최대공약수(gcd) = 4임을 알 수 있습니다.

 

 

조금 큰 수를 예를 들어 한번 다시 최대공약수를 구해보겠습니다.

 

gcd(192, 72) = 24

 

192 / 72 = 2(나머지 48)

72 / 48 = 1(나머지 24)

48 / 24 = 2(나머지 0)

 

따라서 최종적으로 192와 72의 최대공약수는 24임을 알 수 있습니다.

 

 

 

 

최소공배수란?

 

최대공약수와 반대로 주어진 특정 자연수에 대하여 서로 공통으로 존재하는 공배수 중 가장 작은 수를 뜻합니다.

배수와 공배수 의미를 알기쉽게 예를 들어 한번 살펴보겠습니다.

 

8의 배수 : 8, 16, 24, 32, 40, 48, 56, 64, 72, 80, ...

10의 배수 : 19, 20, 30, 40, 50, 60, 70, 80, 90, 100, ...

 

위의 예제에서 알 수 있듯이 8과 10의 공배수는 두 자연수가 가지는 공통의 배수로서 40, 80 등이 있음을 알 수 있습니다.

그 중 가장 작은 공배수를 바로 최소공배수라 하며 8과 10의 최소공배수는 40임을 알 수 있습니다.

 

이를 수학적 표현으로 표현하면 lcm(8, 10) = 40으로 표현할 수 있습니다.

 

 

최소공배수를 구하는 방법은 위의 예제처럼 배수를 모두 나열하여 가장 작은 공배수를 찾으면 될 수 있으나 우리는 간단하게 최소공배수를 찾을 수 있는 한가지 방법을 사용하겠습니다.

 

바로 위에서 구한 최대공약수를 활요하는 방법으로서 해당 공식은 아래와 같습니다.

 

 

최소공배수(lcm) = 0이 아닌 자연수들의 곱 / 최대공약수(gcd)

 

8의 약수 : 1, 2, 4, 8

10의 약수 : 1, 2, 5, 10

 

8과 10의 최대공약수(gcd) = 2

 

 

8과 10의 최소공배수(lcm) = 8 * 10 / 2

                                          = 80 / 2

                                          = 40

 

 

최대공약수를 활용하여 바로 최소공배수를 빠르게 찾았습니다.

 

 

 

 

 

---

 

 

 

알고리즘

 

그렇다면 본 문제를 해결하기 위한 알고리즘을 하나씩 살펴보면 아래와 같습니다.

 

 

• 주어진 자연수들의 최대공약수를 구한다. 
• 최대공약수 값을 활용하여 최소공배수 값을 구한다.
• 최종 결과값이 최대공약수와 최소공배수값을 반환한다.

 

 

 

 

 

---

 

 

 

코드 설명

 

그렇다면 위의 알고리즘에 대해서 하나씩 살펴보면서 코드로 작성을 해보도록 하겠습니다.

 

 

• 주어진 자연수들의 최대공약수를 구한다.

func gcd(_ a: Int, _ b: Int) -> Int {
  let r = a % b
    
  if r != 0 {
    return gcd(b, r)
  } else {
    return b
  }
}

 

 

• 최대공약수 값을 활용하여 최소공배수 값을 구한다.

func lcm(_ a: Int, _ b: Int) -> Int {
  let r = a * b / gcd(a, b)

  return r
}

 

 

• 최종 결과값이 최대공약수와 최소공배수값을 반환한다.

let g = gcd(n, m)
let l = lcm(n, m)
    
return [g, l]

 

 

 

위의 코드들을 모두 조합하여 최종 코드를 완성하면 아래와 같습니다.

 

 

최종 코드

func solution(_ n:Int, _ m:Int) -> [Int] {
    let g = gcd(n, m)
    let l = lcm(n, m)
    
    return [g, l]
}

func gcd(_ a: Int, _ b: Int) -> Int {
  let r = a % b
    
  if r != 0 {
    return gcd(b, r)
  } else {
    return b
  }
}

func lcm(_ a: Int, _ b: Int) -> Int {
  let r = a * b / gcd(a, b)

  return r
}

 

 

 

 

---

 

 

 

이상으로 오늘 제시한 문제에 대해서 분석 및 코드를 작성해 보았습니다.

 

감사합니다.

 

 

 

 

---

[참고 자료(References)]

 

 

[1] 프로그래머스 - 최대공약수와 최소공배수 : https://programmers.co.kr/learn/courses/30/lessons/12940

[2] 소인수분해로 최대공약수 구하기 (개념+수학문제) : https://calcproject.tistory.com/225

[3] 최소공배수 (초등5학년 1학기 1단원) 복습 : https://ko.khanacademy.org/math/cc-sixth-grade-math/cc-6th-factors-and-multiples/cc-6th-lcm/a/least-common-multiple-review