[TIL] 231128_TIL

📌 아래 최대공약수와 최소공배수를 구하는 문제에서 문제를 이해하지 못해 진땀을 뺐다. 수학을 썩 잘하진 않았어서 잘 기억이 안 나 최대공약수, 최소공배수가 무엇인지부터 검색하고 학습했다. 처음에는 값을 받을 제공받은 기본 함수 solusion에 최대공약수, 최소공배수 총 함수 3개를 사용해서 풀었는데 타임아웃처리로 계속 실패가 돼서 최소공배수 함수를 삭제하고 최대공약수를 구한 함수에서 나온 최대공약수의 값으로 solusion함수에서 최소공배수를 바로 구해서 풀었다. 코드를 짤 때 시간복잡도를 고려해서 짜는 습관을 들여야겠다.

📌 새로 알게 된 부분
  ∙ 데이터 타입
  ∙ 연산자, 조건문과 반복문

📌 배움이 필요한 부분
  ∙ 터미널로 여러폴더 한 번에 github push 하기

---

💡 새로 알게 된 부분

  ▶︎ 데이터 타입
  ▶︎ 연산자, 조건문과 반복문

 

---

✖︎ 코딩테스트 풀이

[level 1] Title: 최대공약수와 최소공배수, Time: 0.01 ms, Memory: 16.5 MB -Baekjo… · mirae0312/Programmers_Algorith

 

최대공약수와 최소공배수가 무엇인지 조차 생각이 나지 않아 수학공식을 찾아보는 것부터 공부를 했다. 😂

💡 최대공약수

어떠한 자연수가 있을 경우 해당 수보다 낮은 자연수 중에서 나누었을 때 나머지가 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이 될 때까지 반복한다는 원리.

 

주어진 수를 최대공약수를 유클리드 호제법으로 계산하면 아래와 같음.

 

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 solution(_ n:Int, _ m:Int) -> [Int] {
    var max = 0
    var min = 0
    max = gcd(n, m)
    min = (n * m) / max //최소공배수 = 0아닌 자연수들의 곱 / 최대공약수(max)
    
    return [max, min]
}


func gcd(_ a: Int, _ b: Int) -> Int {
    // 두 수를 비교해 _a 와 _b에 담기
    let _a = a > b ? a : b
    let _b = a < b ? a : b
    let r = _a % _b
    
    // 최대공약수(유클리드호제법) 
    // 큰수 / 작은수 = 나머지가 0이 될때까지 0이 아닌 나머지로 나눔.
    // 연산 종료 해당 식의 몫이 최대공약수
    if r != 0 {
        return gcd(r, _b)
    } else {
        return _b
    }
}