백준 알고리즘 13단계 (정수론 및 조합론)

• 새롭게 배운 내용

1) 5086번 배수와 약수

import sys

while True:
    a, b = list(map(int, sys.stdin.readline().split()))
    if a == 0 and b == 0:
        break

    if a % b == 0 and a > b:
        print('multiple')
    elif b % a == 0 and b > a:
        print('factor')
    else:
        print('neither')

2) 1037번 약수

특정 값 N의 약수의 개수와, 진짜 약수들을 입력해준다.
약수들은 오름차순 정렬되어있을 때 대칭구조로 이루어지는 점을 활용했다.
따라서 정렬된 약수리스트의 첫번째 원소와 마지막 원소를 곱하여 N값을 구했다.

N = int(input())
nums = list(map(int, input().split()))
nums.sort()

ans = nums[0] * nums[-1]
print(ans)

3) 1609번 최대공약수(gcd)와 최소공배수(lcm)

최대 공약수와 최소 공배수를 구하는 방법들을 검색해보던 중, 파이썬의 math모듈에 이미 구현된 함수가 있다고하여 바로 사용해봤다.

import math

a, b = list(map(int, input().split()))

# 최대 공약수 math 모듈의 gcd() Greatest Common Divisor

# 최소 공배수 math 모듈의 lcm() Least Common Multiple
# 최소 공배수는 두 수의 곱을 최대 공약수로 나눠준 값과 동일하다.

print(math.gcd(a, b))
print(math.lcm(a, b))

하지만 공부하는 입장이니, 얻은 힌트로 일반 코드도 작성해봤다.
아래 코드는 입력값 중 작은 값의 범위만큼 반복문을 돌며 최대 공약수를 구한다. 최대 공약수가 1인 경우도 고려하여 1부터 시작!

import math

a, b = list(map(int, input().split()))
gcd = 0
lcm = 0

# b의 범위에서 반복문을 돌며 a를 나눠봄으로써 최대 공약수 구하기.
if a > b:
    for i in range(1, b+1):
        if a % i == 0 and b % i == 0:
            gcd = i
else:
    for i in range(1, a+1):
        if a % i == 0 and b % i == 0:
            gcd = i

# 최소 공배수는 두 수의 곱을 최대공약수로 나눈 값이다.
# 따라서 몫을 구하는 // 연산자
lcm = a * b // gcd

print(gcd)
print(lcm)

4) 1934번 최소 공배수 (유클리드 호제법)

유클리드 호제법이란?

숫자 a와 b가 있을때 a%b(a를 b로 나눈 나머지)와 b의 최대공약수는 a와 b의 최대공약수와 같다는 것이다.
이에 따라 반복문을 통해 a에는 b값을 넣어주고, b에는 a%b값을 넣어주며 b가 0이 될 때 까지 이를 반복하여 0이됐을 경우의 a값이 최대공약수가 된다.
나아가 최소공배수는 두 수의 곱을 최대공약수로 나눈것이므로 간단한 연산으로 구할 수 있게된다.
위 3번에 내가 작성한 풀이는 불필요한 약수까지 따지게 되어 시간복잡도가 증가하지만, 유클리드 호제법의 이론을 활용하면 복잡도를 상당수 낮출 수 있게된다.

import sys

# 유클리드 호제법 활용!
def getGcd(a, b):
    # b가 0이 될 때 까지 (0은 false이기 때문에 자동 종료)
    while b:
        a, b = b, a%b
    return a

T = int(input())
for i in range(T):
    a, b = map(int, sys.stdin.readline().split())

    gcdVal = getGcd(a, b)
    lcmVal = a * b // gcdVal

    print(lcmVal)

5) 2981번 검문

❌❌❌ <1회차 최종 실패! -> 코드 리뷰 및 이해에 초점>

참고: https://tmdrl5779.tistory.com/94
약간의 수학적 지식이 요구되는 문제이다.
입력 받는 값을 아래와 같이 분리하여 M을 타겟팅해야 한다.
A = M a + R
B = M b + R
C = M * c + R
여기에서 R을 소거한다면
A - B = M ( a - b )
B - C = M ( b - c )
와 같은 식이 나오므로, M은 해당 요소들의 차이값의 약수임을 알 수 있다.
따라서 차이값 리스트를 만든 후 반복을 돌며 해당 요소들의 최대 공약수를 찾고, 최대공약수의 약수를 출력한다.
이 때, 최대공약수의 약수를 구할 때도
18 % 2 = 0 ( 2 = 약수)
18 // 2 = 9 ( 9 = 약수)
위와 같이 두개씩 추가해준다. 복잡도를 제곱근만큼 줄일 수 있다..!!

from math import gcd
from math import sqrt

n = int(input())
ns = list(int(input()) for _ in range(n))
ns.sort()
interval = list()
ans = list()

# 입력값들의 차이값을 저장하는 리스트
for i in range(1, n):
    interval.append(ns[i] - ns[i - 1])

# 차이값 리스트를 돌며 이전 원소와의 최대공약수(gcd)를 구함
prev = interval[0]
for i in range(1, len(interval)):
    prev = gcd(prev, interval[i])

# 마지막으로 출력된 최종 최대공약수의 약수를 구한다.
# 이 때 제곱근 까지만 검색하여, i뿐만 아니라 몫도 저장하는 것이 포인트!
for i in range(2, int(sqrt(prev)) + 1): #제곱근까지만 탐색
    if prev % i == 0:
        ans.append(i)
        ans.append(prev//i)
ans.append(prev)
ans = list(set(ans)) #중복이 있을수 있으니 제거
ans.sort()
print(*ans)

6) 3036번 링

처음 주어진 원의 반지름과 나머지 원들의 반지름 간의 각 최대 공약수를 찾아 기약분수 형태로 나타내준다.

from math import gcd

N = int(input())
nums = list(map(int, input().split()))

first = nums[0]
for i in range(1, N):
    gcdVal = gcd(first, nums[i])
    print(str(first//gcdVal) + '/' + str(nums[i]//gcdVal))

7) 11050번 이항계수 1

처음에 재귀함수를 통해 팩토리얼을 구현했으나 recursion error가 발생했다. BOJ 채점 시 재귀가 1000번으로 제한되어있다고 한다.
따라서 재귀함수가 아닌 반복문으로 팩토리얼을 구현했다.

N, K = map(int, input().split())

def factorial(n):
    ans = n
    while True:
        if n <= 2:
            return ans
            break
        ans *= (n-1)
        n -= 1

# nCn과 nC0은 1로 약속
if N == K or K == 0:
    print(1)
else:
	# 이항계수 구하는 식
    print(factorial(N)//(factorial(K)*factorial(N-K)))

8) 11051번 이항계수 2

위와 동일한 코드를 사용했다. 즉, DP 이론을 활용하지 않은 코드

N, K = map(int, input().split())

val = 0
def factorial(n):
    ans = n
    while True:
        if n <= 2:
            return ans
            break
        ans *= (n-1)
        n -= 1

if N == K or K == 0:
    val = 1
else:
    val = factorial(N)//(factorial(K)*factorial(N-K))

print(val % 10007)

+) 동적 계획법 DP(Dynamic Programming)

소분류에 동적계획법이 적혀있어 DP에 대해 공부했다.
동적 계획법의 대표적인 예제는 피보나치 수열이다.
피보나치 수열은 재귀함수로 구현될 때, 특정 차수의 값들이 반복적으로 쓰여 계속 함수를 호출하게 된다.
이를 막고자 값을 저장하는 배열을 만들어 이미 호출된 값을 재귀함수가 아닌 배열에서 가져옴으로써 성능을 높이는 방법이다.
아래 코드는 2차원 배열을 생성하여 파스칼의 삼각형 값을 저장하는 코드이다.
이를 통해 nCk = n-1Ck-1 + n-1Ck 를 구현하여 연산 속도를 높일 수 있다.

n, k = map(int, input().split())
# dynamic programming -> 중복 호출하는 값들을 배열에 저장함으로써 효율 up!
dp = [[0] * 1 for i in range(1001)]
dp[1].append(1)
for i in range(2, 1001):
    for j in range(1, i + 1):
        if j == 1:
            dp[i].append(1)
        elif j == i:
            dp[i].append(1)
        else:
            dp[i].append(dp[i - 1][j - 1] + dp[i - 1][j])
print(dp[n + 1][k + 1] % 10007)