13241. 최소공배수
Solution
유클리드 호제법 (Euclidean Algorithm)
2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘 중 하나..
1)
def gcd(m, n):
if m < n:
m, n = n, m # m과 n을 바꾼다
if n = 0:
return m
if m % n == 0:
return n
else:
return gcd(n, m%n)2)
def gcd(m, n):
while n != 0:
t = m % n
(m, n) = (n, t)
return abs(m)
3)
def gcd(m, n):
while n != 0:
if m < n:
m, n = n, m
if n == 0:
return m
if m % n == 0
return n
이를 이용해 최소공배수를 구할 수 있음,,
a와 b의 최소공배수는 a와 b의 곱을 a와 b의 최대공약수를 나눈 값과 같다.
def lcm(a, b):
return (a * b) // gcd(a, b)
주의해야 할 점 : Python 에서는 위에서 아래로 Intepreter 가 한 줄씩 읽으므로 함수를 사용하는 경우 선언을 위해서 먼저 해주어야 한다.
1735. 분수 합
A와 B는 모두 자연수라고 가정하고, 두 분수가 주어졌을 때, 그 합을 기약분수 (더 이상 약분되지 않는 분수) 의 형태로 구해라.
Solution
우선, 분모끼리 곱한 후 각자의 분자에 cross 하게 곱해서 더한 후 분자와 분모로 최대공약수를 구해서 출력한다.
import sys
input = sys.stdin.readline
# 유클리드 호제법을 이용한 최대공약수 구하기
def gcd(m, n):
while n != 0:
t = m % n
m, n = n, t
return abs(m)
# 입력 처리
a, b = map(int, input().split()) # b / a 형태의 첫 번째 분수
c, d = map(int, input().split()) # d / c 형태의 두 번째 분수
# 분수 덧셈 처리: 분모의 최소공배수와 분자의 합 계산
high = (d * a) + (b * c) # 분자 계산
low = b * d # 분모 계산
# 분자와 분모의 최대공약수 구하기
g = gcd(high, low)
# 기약분수로 변환
reduced_numerator = high // g
reduced_denominator = low // g
# 결과 출력
print(f"{reduced_numerator} {reduced_denominator}")
2485. 가로수
가로수들이 모두 같은 간격이 되도록 가로수를 추가로 심는 사업을 추진한다.
그래서, 심어져 있는 가로수의 위치가 주어질 때, 모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소는?
Solution
1. 들어오는 가로수의 위치를 List(배열)로 받는다. + gap에 대한 것도 List로 받는다.
2. 들어온 List를 정렬한다 -> 정렬 필요 없었음.
3. 모든 간격의 최대공약수를 구한다.
-> why? 모든 가로수를 일정한 간격으로 배치하기 위해 가장 작은 공통 간격을 찾으려고!
주의!
간격이 2개라면 그 사이의 1개의 나무만 세우면 됨. (So, "간격 - 1"
그렇게 되면 최소한의 나무만 추가로 심을 수 있다.
import sys
input = sys.stdin.readline
def gcd(m, n):
while n != 0:
t = m % n
(m, n) = (n, t)
return abs(m)
n = int(input()) # 이미 심어져 있는 가로수의 수
tree_arr = [] # 가로수의 위치를 저장하는 List
for i in range(n):
tree_arr.append(int(input()))
# 각 가로수의 간격을 저장하는 List
gaps = []
# 각 가로수 간의 간격
for i in range(1, n):
gaps.append(tree_arr[i] - tree_arr[i - 1])
# 간격들의 최대공약수
gcd_value = gaps[0]
for i in range(1, len(gaps)):
gcd_value = gcd(gaps[i], gcd_value)
# 필요한 나무의 수 계산
total_trees_needed = 0
for gap in gaps:
total_trees_needed += (gap // gcd_value) - 1
# 결과 출력
print(total_trees_needed)
4134. 다음 소수
Solution
소수
1보다 큰 정수이며, 1과 자기자신으로만 나뉘어지는 수
에라토스테네스의 체
고대 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법으로, 체로 치듯이 수를 걸러낸다.
그래서, 즉 소수란 1과 자기 자신 이외의 약수를 가지는 합성수이다.
So, 1과 자기 자신 이외의 약수를 가지게 되는 경우를 제거해야 소수가 되기 때문에 1을 예외로 제거하고 2, 3, 5, 7의 배수를 제거하면 남는 것은 소수이다.
에라토스테네스의 체 말고 기본 소수 판별로 진행해보았다.
1. Test case 들을 List에 집어넣는다.
2. 소수를 판별한다.
1️⃣ 2보다 작으면 소수가 아니다. => 2부터 들어온 숫자의 제곱근까지 반복해서 소수 check.. (number % i == 0 : 합성수)
3. 수보다 크거나 같은 가장 작은 소수를 찾는다. (만약 소수가 아니라면 증가)
4. Test case마다 결과를 출력한다.
# n보다 크거나 같은 소수 중 가장 작은 소수를 찾는 Program
import sys
input = sys.stdin.readline
n = int(input()) # 테스트 케이스의 개수
test_cases = [] # 테스트 케이스들을 모아놓는 List
# 테스트 케이스 개수만큼 List 추가
for i in range(n):
test_cases.append(int(input()))
print(test_cases)
# 소수 판별 함수
def isPrime(number):
# 숫자가 2보다 작으면 소수가 아님
if number < 2:
return False
# 2부터 숫자의 제곱근까지 반복해서 소수인지 확인해보기
for i in range(2, int(number ** 0.5) + 1):
if number % i == 0:
return False
return True
# 숫자보다 크거나 같은 가장 작은 소수를 찾는 함수
def find_next_prime(number):
while True:
if isPrime(number):
return number
# 소수가 아니라면 그 다음 수로 증가시킴
number += 1
# 테스트 케이스마다 결과를 출력하는 함수
def prime_list(test_cases):
for number in test_cases:
next_prime = find_next_prime(number)
print(next_prime)
# 결과 출력
prime_list(test_cases)
1929. 소수 구하기
M 이상 N 이하의 소수를 모두 출력하는 문제이다.
Solution
첫 번째 해결 방법은 기존 소수를 판별하는 함수를 이용하는 것이나, 이번에는 에라토스테네스의 체를 사용하였다.
1. M ~ N 사이 List
2. i가 소수면 i의 배수들은 소수가 아니다.
# M이상 N이하의 소수를 모두 출력하는 Program
import sys
input = sys.stdin.readline
M, N = map(int, input().split()) # 자연수 M, N 입력
# 소수를 판별하는 함수
def isPrime(number):
# 숫자가 2보다 작으면 소수가 아님
if number < 2:
return False
# 2부터 제곱근까지 반복
for i in range(2, int(number ** 0.5) + 1):
if number % i == 0:
return False
return True
# M이상 N이하 소수 출력하는 함수
def print_prime(M, N):
for i in range(M, N + 1):
if isPrime(i):
print(i)
print_prime(M, N)# M 이상 N 이하의 소수를 찾는 Program(에라토스테네스의 체 방법 사용)
import sys
input = sys.stdin.readline
M, N = map(int, input().split()) # M, N 자연수 입력
# 에라토스테네스의 체를 이용하여 M 이상 N 이하의 소수를 구하는 함수
def sieve_of_eratosthenes(M, N):
# N까지의 범위에서 소수를 찾기 위한 List
sieve = [True] * (N + 1)
sieve[0] = sieve[1] = False # 0과 1은 소수가 아님
# 2부터 N의 제곱근까지의 수를 기준으로 배수 제거
for i in range(2, int(N ** 0.5) + 1):
if sieve[i]: # i가 소수라면
for j in range(i * i, N + 1, i): # i의 배수들은 소수가 아니다.
sieve[j] = False
# M 이상 N 이하의 소수를 출력
for i in range(M, N + 1):
if sieve[i]:
print(i)
# 결과 출력
sieve_of_eratosthenes(M, N)
4948. 베르트랑 공준
Solution
1. 0이 입력되면 Test case 입력 멈추기
2. 최대 범위까지의 소수를 구한 뒤, 각 범위에 대해 소수만을 출력
3. 소수 출력
# 자연수 n에 대하여 n <= x <= 2n 범위에서 소수인 x를 구하는 Program
import sys
input = sys.stdin.readline
test_cases = [] # 입력을 담을 테스트 케이스 List
while True:
n = int(input())
if n == 0: # 입력 안에 0이 입력되면 종료
break
test_cases.append(n)
# 에라토스테네스의 체를 이용해 소수를 판별하는 함수 (n <= x <= 2n)
def sieve_of_eratosthenes(limit):
sieve = [True] * (limit + 1)
sieve[0] = sieve[1] = False # 0과 1은 소수가 아님
# 2부터 한계의 제곱근까지의 수를 기준으로 배수 제거
for i in range(2, int(limit ** 0.5) + 1):
if sieve[i]:
for j in range(i * i, limit + 1, i):
sieve[j] = False
return sieve
# 주어진 테스트 케이스에 대해 소수를 출력하는 함수
def find_primes_in_range(test_cases):
max_value = max(test_cases) * 2 # 2n 범위까지 소수를 구해야 하므로 가장 큰 n에 대해 2n까지 계산
sieve = sieve_of_eratosthenes(max_value) # 2n까지의 소수 구하기
for number in test_cases:
count = 0
# n <= x <= 2n 범위에서 소수 출력
for i in range(number + 1, 2 * number + 1):
if sieve[i]:
count += 1
print(count)
# 결과 출력
find_primes_in_range(test_cases)
17103. 골드바흐 파티션
Solution
1. 골드바흐 파티션의 수를 넣어놓을 List
2. 에라토스테네스의 체를 사용하여 소수를 구한다.
3. 두 소수의 쌍을 구하는데 중복을 피하기 위해 절반만 확인
4. 가장 큰 Test case를 기준으로 소수 List 생성
# 골드바흐 파티션의 개수 구하기
import sys
input = sys.stdin.readline
T = int(input()) # 테스트 케이스의 개수
test_cases = [] # 골드바흐 파티션의 수를 넣어놓을 List
for i in range(T):
test_cases.append(int(input()))
# 에라토스테네스의 체를 이용하여 소수를 구하는 함수
def sieve_of_eratosthenes(limit):
sieve = [True] * (limit + 1)
sieve[0] = sieve[1] = False # 0과 1은 소수가 아님
# 2부터 주어진 숫자의 제곱근까지 배수를 제거하는 것을 반복
for i in range(2, int(limit ** 0.5) + 1):
if sieve[i]:
for j in range(i * i, limit + 1, i):
sieve[j] = False
return sieve
# 골드바흐 파티션의 개수를 구하는 함수
def count_goldbach_partititons(n, primes):
count = 0
for i in range(2, (n // 2) + 1): # 두 소수의 쌍을 구하는데 중복을 피하기 위해 절반만 확인
if primes[i] and primes[n - i]:
count += 1
return count
# 가장 큰 테스트 케이스를 기준으로 소수 리스트 생성
max_value = max(test_cases)
primes = sieve_of_eratosthenes(max_value)
# 각 테스트 케이스에 대해 결과 출력
for n in test_cases:
result = count_goldbach_partititons(n, primes)
print(result)
13909. 창문 닫기
Solution
각 창문이 몇 번의 사람에 의해 변경되느냐는 해당 창문의 번호의 약수의 개수에 따라 결정된다는 것.
-> 어떤 창문이 열려 있는지 여부는 그 창문번호가 약수가 홀수 개인지에 따라 달라진다.
즉, 제곱수의 창문만이 홀수 번 열고 닫히므로, 마지막에 열려있게 된다.
1. 각 사람의 순서대로 창문을 열거나 닫는 작업 -> (메모리 초과됨)
2. 제곱수의 창문만 마지막에 열려 있으므로 제곱수의 개수만 계산
# n번째 사람은 n의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다.
# N번째 사람까지 진행한 후 열려 있는 창문의 개수를 구하는 Program (단, 처음에 모든 창문은 닫혀있음)
import sys
input = sys.stdin.readline
n = int(input()) # 창문의 개수와 사람의 수
# 창문을 열려 있는지 여부를 나타내는 List (처음엔 모두 닫혀있음)
windows = [False] * (n + 1) # 1번부터 n번까지의 창문
# 각 사람의 순서대로 창문을 열거나 닫는 작업
for person in range(1, n+1):
for window in range(person, n + 1, person):
windows[window] = not windows[window] # 창문을 열거나 닫음
# 열려 있는 창문의 개수 카운트
open_windows_count = sum(windows)
print(open_windows_count)
# 메모리 초과# n번째 사람은 n의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다.
# N번째 사람까지 진행한 후 열려 있는 창문의 개수를 구하는 Program (단, 처음에 모든 창문은 닫혀있음)
import math
n = int(input())
# 1부터 n까지의 제곱수의 개수
open_windows_count = int(math.sqrt(n))
print(open_windows_count)'Algorithm' 카테고리의 다른 글
| Coding-Test Day 1 (0) | 2025.08.19 |
|---|---|
| Greedy (0) | 2025.03.18 |
| Baekjoon - 집합과 맵 (5) | 2024.10.03 |
| Baekjoon - 정렬 (1) | 2024.10.01 |
| Baekjoon - Brute-Force (5) | 2024.09.18 |