[알고리즘 기초 1/2] 수학 1

1934번: 최소공배수

참고 여부: X

둘 중에 작은 것에 자기 자신을 더해줌. 반복하다 보면 둘이 같이 지는 순간이 오는데 그게 최소공배수

t = int(input())
def func(a, b) :
    num1 = a
    num2 = b

    while num1 != num2 :
        if (num1 > num2) :
            num2 += b
        elif (num1 < num2) :
            num1 += a

    return num1

for i in range(t) :
    a, b = list(map(int, input().split(' ')))
    print(func(a, b))

2004번: 조합 0의 개수

참고 여부: O

주석처리 되어있는 count_two 함수는 내가 처음에 만든 함수이다. 팩토리얼을 곱하지 않으면서 2와 5의 개수를 세어준다는 아이디어는 맞았으나, 더 나은 방법이 있었다.

아래의 주석으로 설명을 해놓았는데, 나눠떨어지는 수를 카운트하는 방법으로 팩토리얼의 2, 5가 몇번 제곱 되었는지 카운트 할 수 있다.

import sys
input = sys.stdin.readline

# def count_two(n) :
#     answer = 0
#     if n < 2 :
#         return answer

#     for i in range(1, n + 1) :
#         tmp_i = i
#         while tmp_i % 2 == 0 :
#             tmp_i //= 2
#             answer += 1
#     return answer


def count_five(n):
    """
    예시) n = 25인 경우,
    25 이하에서 5로 나눠 떨어지는 수 : 5개
    25 이하에서 5^2으로 나눠 떨어지는 수 : 1개

    총 6개!
    """
    answer = 0
    while n != 0:
        n = n // 5
        answer += n
    return answer

def count_two(n):
    answer = 0
    while n != 0:
        n = n // 2
        answer += n
    return answer

n, r = list(map(int, input().split()))

count2 = count_two(n) - count_two(n - r) - count_two(r)
count5 = count_five(n) - count_five(n - r) - count_five(r)
print(min(count2, count5))

7489번: 팩토리얼

참고 여부: O

아이디어 자체는 똑같았는데, answer를 mod해주는 수를 너무 작게 잡았었다.

def factorial(n) :
    answer = 1
    for i in range(1, n + 1) :
        answer *= i
        answer %= 10000000000
        while answer % 10 == 0 :
            answer /= 10
    return (answer % 10)

t = int(input())
for i in range(t) :
    n = int(input())
    fact = factorial(n)
    print(int(fact))

1373번: 2진수 8진수

참고 여부: X

이건 진수 변환을 42에서 엄청 했기 때문에..
진수 변환 꿀팁
2->8진수인 경우, 2진수 3자리를 8진수 하나로 매칭하면 된다.
11001100 -> 11 / 001 / 100 -> 3 / 1 / 4
이런 식이다. 반대의 경우도 통과

2->16진수면 2진수 4자리를 하나로 매칭하면 된다.

import sys, math
input = sys.stdin.readline

s = input().split()
s = s[0]

repeat = math.ceil(len(s) / 3)
num = 0
answer = []
for i in range(repeat) :
    if ((i * 3 + 1) <= len(s)) :
        num += int(s[-(i * 3 + 1)]) * 1
    if ((i * 3 + 2) <= len(s)) :
        num += int(s[-(i * 3 + 2)]) * 2
    if ((i * 3 + 3) <= len(s)) :
        num += int(s[-(i * 3 + 3)]) * 4
    answer.append(num)
    num = 0
answer.reverse()
print(*answer, sep='')

17087번: 숨바꼭질 6

참고 여부: X

거리들의 최대공약수를 판단해서 푸는 문제였다.
수빈이는 숨바꼭질을 너무 많이 하는 것 같다.. 동생도 참 많고..

import sys, math
input = sys.stdin.readline

def GCD(a, b) :
    while b != 0 :
        a, b = b, a % b
    return a

n, s = list(map(int, input().split()))
arr = list(map(int, input().split()))
arr.append(s)

arr.sort()

if n == 1 :
    print(arr[1] - arr[0])
else :
    distance = []
    for i in range(1, n + 1) :
        distance.append(arr[i] - arr[i - 1])

    gcd = distance[0]
    for i in range(1, len(distance)) :
        gcd = GCD(distance[i], gcd)

    print(gcd)

2089번: -2진수

처음엔 bfs 개념으로 접근했다. 그러나 메모리 초과..

n = int(input())

from collections import deque

stack = deque()

stack.append([1, '1'])
stack.append([0, '0'])


while True and n != 1 :
    first, str = stack.popleft()
    num2 = 1
    for i in range(len(str)) :
        num2 *= -2
    
    if (first == n) :
        str = str + '0'
        print(str[::-1])
        break

    if (first + num2 == n) :
        str = str + '1'
        print(str[::-1])
        break
    stack.append([first, str + '0'])
    stack.append([first + num2, str + '1'])

if n == 1 :
    print("1")

-2진수라고 당황하지 말자. 속지말자.
다른 n진수법과 다를바가 없다.
ㄴ자 그어서 나눠주는 걸로 계산해보니까 똑같았다.

n = int(input())
if (n == 0) :
    print('0')
else :
    answer = ''
    while n != 0 :
        mod = n % -2
        if not (mod == 0 or mod == 1) :
            mod = 1
            n -= 1
        n = n // -2

        answer += str(mod)
    print(answer[::-1])