- 새롭게 배운 내용
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)9) 1010번 다리놓기
이 문제는 정의역과 공역이 주어질 때 1:1 매칭으로 나올 수 있는 치역에 조건이 붙은 상황이다.
조건은 x1 < x2 이면 f(x1) < f(x2) 이다.
쉽게 생각하면 치역을 정의역의 개수만큼 뽑아 순서대로 매칭시키면 된다.
따라서 mCn의 조합이 정답이 된다.
import sys
T = int(input())
for i in range(T):
N, M = map(int, sys.stdin.readline().split())
val = 0
def factorial(n):
ans = n
while True:
if n <= 2:
return ans
break
ans *= (n-1)
n -= 1
if N == M:
val = 1
else:
val = factorial(M)//(factorial(N)*factorial(M-N))
print(val)11) 9375번 패션왕 신해빈
같은 종류끼리 정렬하여 종류 별 개수(n)를 리스트에 저장했다.
종류 별로 안입거나 n개 중 하나를 선택하므로 (n+1)개이다.
따라서 모든 종류 별 개수 + 1을 곱해준 뒤 알몸의 경우 1을 빼준다.
import sys
T = int(input())
# 전체 옷의 이름과 종류를 저장하는 리스트
clothes = []
for i in range(T):
N = int(sys.stdin.readline())
if N == 0:
print(N)
continue
for j in range(N):
nm, cg = map(str, sys.stdin.readline().split())
# 2차원 배열로 [종류, 이름]을 넣어준다.
clothes.append([cg, nm])
#종류를 기준으로 정렬해준다.
clothes.sort(key=lambda x:(x[0]))
first = clothes[0][0]
cnt_list = []
cnt = 0
# 종류 별 개수를 카운트하여 저장해준다.
for k in range(len(clothes)):
if clothes[k][0] == first:
cnt += 1
first = clothes[k][0]
if k == (len(clothes) -1):
cnt_list.append(cnt)
else:
cnt_list.append(cnt)
cnt = 1
first = clothes[k][0]
if k == (len(clothes) -1):
cnt_list.append(cnt)
# 종류 별 개수 + 1씩 곱해주고 마지막에 알몸의 경우 1을 빼준다.
ans = 1
for t in cnt_list:
ans *= (t+1)
ans -= 1
print(ans)
# 개수 리스트와 옷 리스트는 케이스 종료 시 초기화 해준다.
cnt_list.clear()
clothes.clear()12) 1676번 팩토리얼 0의 개수
입력값의 팩토리얼 값의 뒤에서 부터 0이 나올 때 까지 0이 몇개인가를 계산
팩토리얼 값을 구해 str로 형변환해주고 리스트에 담아 역순으로 다시 저장
그 후 첫 번째 0의 인덱스를 구해 zeroCnt를 계산해주는 코드를 작성했다.
def factorial(n):
ans = n
while True:
if n <= 2:
return ans
break
ans *= (n - 1)
n -= 1
N = int(input())
NFac = factorial(N)
NFacList = list(str(NFac))
ReverseNFacList = list(reversed(NFacList))
reverseFirstIdx = 0
# .index()는 해당하는 원소가 첫번 째로 나타나는 인덱스를 표출하므로
# 아래 반복문을 대체하여 쓸 수 있다고 생각한다.
for i in range(len(ReverseNFacList)):
if ReverseNFacList[i] != '0':
reverseFirstIdx = i
break
ZeroCount = 0
for j in range(len(ReverseNFacList)):
if j == reverseFirstIdx:
print(ZeroCount)
break
else:
if ReverseNFacList[j] == '0':
ZeroCount += 113) 2004번 조합 0의 개수
❌❌❌ <1회차 최종 실패! -> DP 단원 배우고 다시 시도해보기!>
처음 시도에서 어렴풋이 배웠던 DP 이론을 활용하여 딕셔너리에 저장한 값을 불러오는 조합 계산 함수를 작성했으나, n,m은 20억 까지도 가능한 조건 때문에 Recursion error를 직감하고 멈추었다.
n, m = map(int, input().split())
# 딕셔너리의 키값에는 mutable한 list가 들어갈 수 없다. 따라서 튜플을 활용해야 한다. 키값에는 튜플 (n,m)을 넣고 밸류에 해당 조합 값을 저장.
com_dict = {(1,0): 1, (1,1): 1}
def combination(n,m):
if m == 0 or m == n:
if com_dict.get((n,m), -1) != -1:
return com_dict[(n,m)]
else:
com_dict[(n,m)] = 1
return com_dict[(n, m)]
elif com_dict.get((n,m), -1) != -1:
return com_dict[(n,m)]
else:
if com_dict.get((n-1,m-1), -1) != -1 and com_dict.get((n-1,m), -1) != -1:
com_dict[(n,m)] = com_dict[(n-1, m-1)] + com_dict[(n-1, m)]
return com_dict[(n,m)]
else:
return combination(n-1, m-1) + combination(n-1, m)
print(combination(n,m))+) 끝자리 0의 연속된 개수는 2*5의 n제곱에 의해 결정된다는 점을 활용한 코드
출처: https://somjang.tistory.com/entry/BaeKJoon-2004%EB%B2%88-%EC%A1%B0%ED%95%A9-0%EC%9D%98-%EA%B0%9C%EC%88%98-Python
def countNum(N, num):
count = 0
divNum = num
# 순서대로 5 혹은 2의 1승, 2승, 3승, 4승 등을 카운트에 추가해주기..
while(N >= divNum):
count = count + (N // divNum)
divNum = divNum * num
return count
m,n = map(int, input().split())
print(min(countNum(m,5) - countNum(n,5) - countNum(m-n,5), countNum(m,2) - countNum(n,2) - countNum(m-n,2)))