내일은 알고리즘

https://school.programmers.co.kr/learn/courses/30/lessons/136798

약수를 구하는 아이디어만 떠올리면 쉽게 풀리는 구현 문제입니다.

간단히 1부터 n까지 수가 가지는 약수를 카운트 해주고, 주어진 limit보다 큰 경우 limit로 갱신해서 누적합을 만들어 주면 됩니다. 단, 약수를 구할 때는 시간초과를 고려해야합니다. 

n의 약수를 구할 때 1부터 n까지 모든 자연수 x에 대해 1부터 x/2까지 일일히 나누어 떨어지는치를 체크한다면 이 문제의 n이 10만이기때문에 10만 x 5만 = 50억이라는 어마어마한 연산이 필요합니다.

약수를 나누어 구하는 대신 1부터 n까지 모든 자연수 x에 대해 자신의 배수들을 모두 찾으면 거꾸로 그 배수는 자신의 약수가 몇개인지를 알 수 있습니다. 이 경우엔 10만개의 수에 대해 10만 ÷ x번 연산을 하게 되고 이 값은 대략 1152620이라고 합니다. (해당 연산이 조화급수로 챗 gpt의 도움을 빌렸습니다.) 위에서 필요했던 50억번의 연산에 비해 0.02%에 불과한 매우 작은 연산입니다.

간단히 작성한 코드는 아래와 같습니다. 1 ... n으로 x를 키워가며 x의 배수들마다 1씩 더해주면 그 수들은 x로 나누어 떨어지는 수입니다. 

def solution(number, limit, power):
    answer = 0
    arr = [1] * (number + 1)
    
    for i in range(2, number + 1):
        d = i
        while d <= number:
            arr[d] += 1
            d += i
    
    for i in range(1, number + 1):
        if arr[i] <= limit:
            answer += arr[i]
        else:
            answer += power
            
    return answer

리스트 컴프리헨션을 이용해 코드를 좀 더 줄일 수도 있습니다.

def solution(number, limit, power):
    answer = 0
    arr = [1] * (number + 1)
    
    for i in range(2, number + 1):
        d = i
        while d <= number:
            arr[d] += 1
            d += i

    return sum([arr[i] if arr[i] <= limit else power for i in range(1, number + 1)])

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

최대 공약수와 최소 공배수를 구하는 문제입니다.

GCD를 이용해서 최대 공약수는 쉽고 빠르게 구할 수 있습니다.

최대 공약수를 구했다면, 최소 공배수는 N * M을 최대 공약수로 나눈 값입니다.

예를 들어 N과 M이 24, 36이라면

GCD(24, 36)

GCD(36, 24)

GCD(24, 12)

GCD(12, 0) -> 최대 공약수가 12

N * M = 864이고 864를 12로 나누면 최소 공배수인 72가 됩니다.

def solution(n, m):
    md = gcd(n, m)

    answer = [md, n * m / md]
    return answer


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

https://school.programmers.co.kr/learn/courses/30/lessons/82612

간단한 수학 문제입니다.

1에서 N까지를 더하면 그 합은 N (N + 1) / 2가 됩니다. 이를 이용해 전체 요금을 계산하고, 가지고 있는 금액에서 빼 음ㅇ수라면 -1을 곱해준 값을, 0 또는 양의 정수라면 0을 return 하면 됩니다.

def solution(price, money, count):
    
    gap = money - ((count * (count + 1)) // 2 ) * price

    return -gap if gap < 0 else 0

https://school.programmers.co.kr/learn/courses/30/lessons/68935

3진법으로 변환하는 방법만 알면 간단하게 구현 가능한 문제입니다.

나머지를 List에 저장해 reverse로 뒤집어줘도 되지만 저는 앞뒤로 출납이 가능한 deque자료구조를 활용해 구현했습니다.

from collections import deque

def solution(n):
    answer = 0
    deq = deque()
    
    while n > 0:
        remain = n % 3
        n = n // 3
        
        deq.append(remain)
    
    while len(deq) > 0:
        answer *= 3
        answer += deq.popleft()
    
    return answer