self.winter.(08). 정수론 및 조합론(이항정리), 진수, 요세푸스 문제(deque) _ 백준[2609, 1676, 2004, 11051, 2981, 2877, 1158]

🧐 백준 2609 (최대공약수, 최소공배수)

🤫 해결의 실마리 

🤔 최대공약수, 최소공배수는 math 내장 라이브러리에 있는 gcd, lcm 함수를 이용하자!  

from math import gcd, lcm

🤫  solution_2609

from math import gcd, lcm
x, y = map(int, input().split())
print(gcd(x,y), lcm(x,y), sep = "\n")

 

 

🧐 백준 1676 (factorial)

🤫 해결의 실마리 

🤔 팩토리얼은 math 내장 라이브러리에 있는 factorial 함수를 이용하자!

from math import factorial

🤔 문자열이나 리스트에 대한 뒤에서의 접근은 reversed를 애용하자!

for i in reversed(ans):

🤫  solution_1676

from math import factorial
ans = str(factorial(int(input())))
cnt = 0
for i in reversed(ans):
    if i == '0':
        cnt += 1
    else:
        break
print(cnt)

 

 

🧐 백준 2004 (combination_조합)

🤫 해결의 실마리 

🤔 조합론의 원리, 즉 본질의 파악이 우선이다!

0의 개수 = 
min{
(M!이 가지는 2의 개수 - N!이 가지는 2의 개수 - (M-N)!이 갖는 2의 개수) 
                             /
(M!이 가지는 5의 개수 - N!이 가지는 5의 개수 - (M-N)!이 갖는 5의 개수)
}

🤫  solution_2004 (시간초과)

from math import factorial

def combination(n, m):
    return factorial(n) // (factorial(m) * factorial(n-m))

n, m = map(int, input().split())
num = str(combination(n,m))

cnt = 0
for i in reversed(num):
    if i == '0':
        cnt += 1
    else:
        break
print(cnt)

🤫  solution_2004

M, N = map(int, input().split())
def countNum(N, num):
    cnt = 0
    divNum = num
    while(N >= divNum):
        cnt = cnt + (N // divNum)
        divNum *= num
    return cnt

# 0의 개수 = min(M!이 가지는 2의 개수 - N!이 가지는 2의 개수 - (M-N)!이 갖는 2의 개수  /  M!이 가지는 5의 개수 - N!이 가지는 5의 개수 - (M-N)!이 갖는 5의 개수)
print(min(countNum(M, 5) - countNum(N, 5) - countNum(M-N, 5), countNum(M, 2) - countNum(N, 2) - countNum(M-N, 2)))

 

 

🧐 백준 11051 (이항정리)

🤫  solution_2004

from math import factorial
n, k = map(int, input().split())
print((factorial(n) // (factorial(k) * factorial(n - k))) % 10007)

조합의 경우 n! / k! (n-k)! 으로 표현이 가능하기에 위와 같이 표현할 수 있다.

 

 

🧐 백준 2981 (combination_조합)  Gold IV

🤫 해결의 실마리 _ 유클리드 호제법

 

🤔 Algorithm
나눗셈에서 몫과 나머지가 어떻게 나오는지, 본질의 파악이 우선이다!
위의 예제입력 2의 일부를 예로 들어 알고리즘 과정을 설명해 보겠다.

# 17 = 5*(3) + '2'
# 83 = 27*(3) + '2'

# 3 = (number - 'rest')*몫
# 즉, 숫자 2개를 빼주면? => ()괄호 값을 인수로 갖는 숫자가 나옴
# ex) 83-17 = 66의 공약수 = 2 3 6 11 22 33 66
# ex) 17- 5 = 12의 공약수 = 2 3 4 6 12
# ex) 17-14 = 3의 공약수 = 3
# 즉, 최종적으로 위의 리스트들의 공약수는 3이므로 3을 출력하면 됨.

🤔Algorithm 과정
위에서 설명한 바와 같은 방식으로 진행할 것이다.
1. 입력된 num간의 차이를 저장하는 num_interval 리스트를 생성해주고 저장한다.
2. ans는 num_interval의 최대공약수를 구하여 넣어주기 위한 리스트이다.
3. gcd(*num_interval)을 통해 모든 num_interval의 원소들을 비교, 최대공약수를 구해준다.
4. ans에 저장된 1을 제외한 약수가 답이 되므로 약수를 구하기 위한 divisor함수를 선언해준다.
5. divisor함수에서는 2부터 n까지를 돌면서 나머지가 0이 될 때, i값을 append해준다.
6. 이렇게 모인 answer 리스트가 바로 1을 제외한 약수가 저장되있는 리스트이다.
7. 이 함수에 ans에 저장된 최대공약수의 원소를 넣어주고 함수로 도출된 리스트의 원소를 뽑아준다.

🤫  solution_2981

from math import gcd

N = int(input())
num = [int(input()) for _ in range(N)]

num_interval = []
ans = []
for i in range(1, N):
    num_interval.append(abs(num[i] - num[i-1]))
ans.append(gcd(*num_interval))

def divisor(n):
    answer = []
    for i in range(2, n+1):
        if n%i == 0:
            answer.append(i)
    return answer

print(*divisor(*ans))

 

 

🧐 백준 2877 (2진수) Gold V

🤫 해결의 실마리 _  format() 

>>> format(42, 'b') # 2진수
'101010'
>>> format(42, 'o') # 8진수
'52'
>>> format(42, 'x') # 16진수
'2a

🤔 Algorithm 

🤫  solution_ 2877

n = format(int(input()) + 1, 'b') # k+1 숫자를 2진수('b')로 변환
print(n[1:].replace('0', '4').replace('1', '7'))

 

 

 

 

 

🧐 백준 1158 (요세푸스 문제)

🤫 해결의 실마리 _  deque 

🤔 collections의 deque를 이용하자!  

from collections import deque
dq = deque()

# dq의 뒤(오른쪽)에 값 추가, 삭제
dq.append(num)
dq.pop()

# dq의 앞(왼쪽)에 값 추가
dq.appendleft(num)
dq.popleft()

# dq안의 값들 회전 (원형 큐를 이용)
dq.rotate(양수)  = 양수 칸씩 오른쪽으로 밀린다.
dq.rotate(음수)  = 음수 칸씩 왼쪽으로 밀린다.

print(dq)  # deque([1, 2, 3, 4, 5])

dq.rotate(1)
print(dq)  # deque([5, 1, 2, 3, 4])

dq.rotate(-1)
print(dq)  # deque([1, 2, 3, 4, 5])

dq.rotate(-1)
print(dq)  # deque([2, 3, 4, 5, 1])

 

🤫  solution_1158

from collections import deque

n, k = map(int, input().split())
dq = deque([i for i in range(1, n+1)])

ans = []
while dq:
    dq.rotate(-k+1)
    ans.append(dq.popleft())  # popleft: 덱의 앞(왼쪽)값 삭제후 반환

print("<" + ", ".join(map(str, ans)) + ">")