[Problem Solving] 정수론 및 조합론 백준 예제/Python

해당 게시글은 비전공자이자 쌩초보 개발자 지망생이 작성한 글로 정확하지 않을 수 있으니 참고해주시길 바랍니다! 

피드백과 정보 정정 댓글은 환영입니다 :)

 

이번에 해결해 본 단계는 기하1에 이어서 정수론 및 조합론이다! 해당 단계에서 사용하는 주된 수학적 개념은 배수/약수/조합이었다. 그래서인지 기하1과 마찬가지로 그렇게 어려운 논리를 포함한 문제들은 아니라는 생각이 아주 조심스럽게 들었다. 이제 하나씩 문제들과 해결 코드를 살펴보자!

 

# 백준 1934번 최소공배수 Python3
#유클리드 호제법 사용

import sys

T = int(sys.stdin.readline())

for _ in range(T):
    A, B = map(int, sys.stdin.readline().split())
    n1 = max(A,B)
    n2 = min(A,B)
    left = n1%n2
    
    while left != 0:
        n1 = n2
        n2 = left
        left = n1%n2

    #n2 는 최대공약수

    print(int(A*B/n2))

# 백준 1934번 최소공배수 Python3

 

아무런 배경지식 없이 두 수의 최소 공배수를 구하기 위해서는 노가다가 필요했다. (물론 컴퓨터가 해주는 노가다^^) n과 m, 이 두 수의 최소 공배수를 구하기 위해 우선 최대공약수를 구해야 하는데, 이는 for i in range(n, 0, -1): 으로 시작하여 if n%i == 0 and m%i ==0 의 조건에 맞으면 for 문을 탈출할 수 있게끔 구현하면 된다. 하지만 이는 숫자가 커지면 시간초과의 문제가 발생할 수 있기 때문에 다른 방법을 생각해야 한다. 시간을 단축시킬 수 있는 법이 바로 유클리드 호제법인데, 이는 위키백과에 검색하면 나오는 내용이기에 그 내용을 그대로 구현하였다. https://ko.wikipedia.org/wiki/유클리드_호제법 해당 링크를 참고해보자!

 

# 백준 2981번 검문 Python3

def uclid(A, B):	#유클리드 호제법을 활용한 최대공약수 구하기
    n1 = max(A,B)
    n2 = min(A,B)
    left = n1%n2

    while left != 0:
        n1 = n2
        n2 = left
        left = n1%n2

    return n2
    
import sys

N = int(sys.stdin.readline())
nums = [0] * N

for i in range(N):
    nums[i] = int(sys.stdin.readline())

nums.sort()

A = nums[1] - nums[0] #초기 A값 지정
    
for i in range(2, N): #for문을 통해 각 원소에서 가장 작은 값이었던 nums[0]을 빼주고, 그 수와 A의 최대공약수를 구하게끔 한다
    B = nums[i]-nums[0]
    A = uclid(A,B)

result = set()

for j in range(2, int(A**0.5)+1): #출력 시간 단축
    if (A%j == 0):
        result.add(j)
        result.add(A//j)
        
result.add(A)
print(*sorted(list(result)))

# 백준 2981번 검문 Python3

 

한번에 풀었다면 거짓말이다. 일단 논리 자체는 쉽게 생각을 했지만 시간 초과에서 에러가 떠 고생했다. 입력으로 받는 원소들 중, 가장 작은 값을 minimum이라고 하자. 해당 원소들을 특정 숫자로 나누었을 때 모두 같은 나머지를 갖게 하는 수는 각각의 원소들에서 minimum을 뺀 값들의 최대공약수의 약수들이라고 할 수 있다. 이러한 생각을 갖고 구현했으나 76퍼에서 시간초과가 났다. 처음에는 유클리드 호제법이 시간초과를 불러일으키거나 sort 메서드 때문이라고 생각하였는데, 다른 분들의 코드를 참고하니 출력에서 시간을 많이 잡아먹고 있음을 깨달았다. 본래 풀이에서는 for 문을 이용해 모든 수들을 검토하였는데 이는 시간 낭비였다! 예로, 100의 약수를 구하기 위해서서 우리는 51까지의 수들로만 100을 나누면 된다. 2를 나눴을 때 나누어 떨어진다면 자동으로 100의 약수에는 50도 포함되기 때문이다. 그래서 출력 방식을 위와 같이 변경하였고, 1은 해당 문제에서는 답에 포함이 안 되기 때문에 자기 자신을 마지막에 따로 빼서 add 해주었다. 이후 출력하면 끝!

 

# 백준 3036번 링 Python3

import sys

def uclid(A, B):
    n1 = max(A,B)
    n2 = min(A,B)
    left = n1%n2

    while left != 0:
        n1 = n2
        n2 = left
        left = n1%n2

    return n2

N = int(sys.stdin.readline())
rings = list(map(int, sys.stdin.readline().split()))

for i in range(1,N):
    num = uclid(rings[0], rings[i])
    print(f'{int(rings[0]/num)}/{int(rings[i]/num)}')

# 백준 3036번 링 Python3

 

주어지는 수들의 최대공약수로 입력을 모두 나누어준 값을 작성하면 된다. 요즘 구독하고 있는 IT 뉴스레터에서 문자열을 합쳐서 출력할 때 + 보다 f-string을 사용하면 더 효율적이라고 해서 작성해보았다.

 

# 백준 11051번 이항계수2 Python3

import sys

def binary(N, K):
    if (N, K) in dp or (N, N-K) in dp: 
        try:
            return dp[(N,K)]
        except:
            return dp[(N, N-K)]
    
    if K == 1 or K == N-1:
        dp[(N,K)] = N
        return N

    if N == K or K == 0:
        dp[(N,K)] = 1
        return 1

    dp[(N,K)] = binary(N-1, K-1) + binary(N-1, K)
    return dp[(N,K)]
 
N, K = map(int, sys.stdin.readline().split())
dp = {}
binary(N,K)
print(dp[(N,K)]%10007)

# 백준 11051번 이항계수2 Python3

 

이 문제도 꽤나 골치 아픈 문제였다. 해줄 거 다 했는데 왜 시간 초과가 났는지... 싶었다. 해답은 binary 함수에서의 if 문의 순서에 있었다. 처음 코드에서는 if (N, K) in dp or (N, N-K) in dp: 가 맨 윗 줄에 있지 않았다. 그래서 코드의 순서를 바꾸어주니 시간 초과가 해결됐다. 왜인지는 긴가민가 한데,,, 아마 답이 있으면 바로 return 해야 하는데 다른 조건들 거치고 오면 출력이 늦어져서 일까 싶기도? 공부해보자... 

 

# 백준 9375번 패션왕 신해빈 Python3

import sys

T = int(sys.stdin.readline())

for i in range(T):
    closet = {}
    clothes = int(sys.stdin.readline())
    
    for j in range(clothes):
        clothe, types = sys.stdin.readline().split()

        try:
            closet[types].append(clothe)
        except:
            closet[types] = [clothe]

    lengths = [len(k) for k in closet.values()]
    result = 1

    for j in lengths:
        result = result * (j+1)

    print(result-1)

# 백준 9375번 패션왕 신해빈 Python3

 

이름이 참으로 귀여운 문제이다! 해당 문제는 경우의 수를 가지고 풀면 된다. 종류별로 옷들을 분리하고 종류마다 옷의 개수를 센 후 여기에 1을 더한 값을 모두 곱해버리면 된다. 상의 3개, 하의 2개가 있을 때 (상의를 고르는 경우 3 + 안 고르는 경우 1 )*(하의를 고르는 경우 2 + 안 고르는 경우 1) - (둘 다 아무것도 안 입는 경우 1) 이런 식으로 구해야 하기 때문에 1을 각각 더해주고 최종 결과에서 다시 1을 빼주어야 한다.

 

# 백준 2004번 조합 0의 개수 Python3

import sys

def five(n):
    cnt = 0
    while n != 0:
        n = n//5
        cnt += n
    return cnt

def two(n):
    cnt = 0
    while n != 0:
        n = n//2
        cnt += n
    return cnt
    
N, K = map(int, sys.stdin.readline().split())
fson = five(N)
fmom = five(N-K)+five(K)
tson = two(N)
tmom = two(N-K)+two(K)

fives = fson-fmom
twos = tson-tmom

print(min(fives,twos))

# 백준 2004번 조합 0의 개수 Python3

 

^^ 이 문제.. 직접 조합 계산했다가 재귀오류 떠서 한참 고민했다! 직접 계산하지 않고 각각 분자와 분모 (5C2 의 경우 5!/3!*2! 계산) 가 10을 몇 개 지니고 있는지 구하고, 분자에서의 10의 개수 - 분모에서의 10의 개수 해주면 된다. 그러기 위해서 각각 분모 분자에서 2와 5의 개수를 세주기! 

 

느낀 점

오늘은 패스. 솔직히 이 게시물 알바 끝나고 적은거라 비몽사몽 말 이상하게 썼을까봐 걱정된다... 나중에 수정하러 와야지... 내일도 과외 알바 화잉팅