TIL 2023.04.25

알고리즘 문제를 풀던 중 새롭게 알게된 것들이다.

 

최대공약수와 최소공배수

def solution(n, m):
    big = max(n, m)
    small = min(n, m)
    gcd = 0
    for i in range(1, small+1):
        if big % i == 0 and small % i == 0:
            gcd = i

    lcm = n * m / gcd

    return [gcd, lcm]

최대공약수는 영어로 GCD(Greatest Common Divisor) 라고 한다.

1 부터 주어진 두 수 중 작은 수까지 순회하면서

두 수 모두 나누어 떨어지는 수 중 가장 큰 수(마지막 수)를 구하면 된다.

 

최소공배수는 영어로 LCM(Least Common Multiple/Lowest Common Multiple) 이라고 한다.

최대공약수를 구했다면 최소공배수를 구하는 건 간단하다.

주어진 두 수를 곱한 값을 최대공약수로 나눠주면 최소공배수를 구할 수 있다.

 

 

n진수 변환법

def solution(n):
    ternary = ''
    while n > 0:
        ternary += str(n % 3)
        n //= 3
    ternary = ternary[::-1]
    return ternary

3진수를 예로 들었다.

먼저 삼진수 라는 문자열을 초기화해준다

와일 반복문으로 주어진 수를 n이라고 할때 n이 0이 될 때까지 반복한다.

n을 3으로 나눈 나머지를 삼진수 문자열에 넣어준다.

n에는 다시 n을 3으로 나눈 몫으로 선언해준다.

이를 반복한다.

 

n진수 모든 경우에 적용되며(3으로 된 부분만 바꿔주면 됨)

거꾸로 저장하기 때문에 뒤집어주는 과정이 필요하다.