2023. 신기한 소수
문제
수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다.
7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수이다. 즉, 왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수이다! 수빈이는 이런 숫자를 신기한 소수라고 이름 붙였다.
수빈이는 N자리의 숫자 중에서 어떤 수들이 신기한 소수인지 궁금해졌다. N이 주어졌을 때, 수빈이를 위해 N자리 신기한 소수를 모두 찾아보자.
입력
첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다.
출력
N자리 수 중에서 신기한 소수를 오름차순으로 정렬해서 한 줄에 하나씩 출력한다.
예제 입력 1
4
예제 출력 1
2333
2339
2393
2399
2939
3119
3137
3733
3739
3793
3797
5939
7193
7331
7333
7393
알고리즘 분류
- 수학
- 정수론
- 백트래킹
- 소수 판정
코드 - python3 성공
import sys
input = sys.stdin.readline
# 입력 받기
n = int(input())
# 소수 판별 함수
def isPrime(a):
if (a < 2):
return False
for i in range(2, int(a ** 0.5) + 1):
if (a % i == 0):
return False
return True
# 깊이 우선 탐색 함수
def dfs(num):
# 목표 길이 도달 시 멈춤
if len(str(num)) == n:
print(num)
else:
# 한 자리씩 숫자를 더해가며 탐색
for i in range(10):
temp = num * 10 + i
# 새로 만든 숫자가 소수인지 확인하고, 소수면 재귀적으로 탐색 진행
if isPrime(temp):
dfs(temp)
# 한자리수 소수인 2, 3, 5, 7에서 시작하여, 깊이 우선 탐색을 수행
dfs(2)
dfs(3)
dfs(5)
dfs(7)1504. 특정한 최단 경로
문제
방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.
세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.
입력
첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1) 임의의 두 정점 u와 v사이에는 간선이 최대 1개 존재한다.
출력
첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.
예제 입력 1
4 6
1 2 3
2 3 3
3 4 1
1 3 5
2 4 5
1 4 4
2 3
예제 출력 1
7
알고리즘 분류
- 그래프 이론
- 데이크스트라
- 최단 경로
코드 - python3 성공
import sys
import heapq
input = sys.stdin.readline
# 다익스트라
def solution(start):
visited = [1e9 for _ in range(n + 1)] # 최단거리 테이블
heap = []
heapq.heappush(heap, [0, start])
visited[start] = 0
while heap:
# 가장 최단거리가 짧은 노드에 대한 정보 꺼내기
dist, num = heapq.heappop(heap) # 거리, 정점 번호
# 거리가 해당 정점의 저장된 거리보다 크다면 탐색할 필요없음.
if dist > visited[num]:
continue
# 해당 정점과 인접한 정점의 노드를 확인
for i, j in graph[num]:
cost = dist + j
# 인접한 노드를 거쳐서 이동하는 것이 더 빠른 경우
if cost < visited[i]:
visited[i] = cost
heapq.heappush(heap, [cost, i])
return visited
n, e = map(int, sys.stdin.readline().split()) # 정점개수, 간선개수
graph = [[] for _ in range(n+1)] # 정점 정보와 그 거리
# 양방향 그래프 표시
for i in range(e):
a, b, c = map(int, input().split())
graph[a].append([b, c])
graph[b].append([a, c])
v1, v2 = map(int, input().split())
a = solution(1) # 1부터 n까지 다익스트라
b = solution(v1) # v1부터 n까지 다익스트라
c = solution(v2) # v2부터 n까지 다익스트라
# 1-v1-v2-n 경우와 1-v2-v1-n 경우중 최단 거리를 구한다.
answer = min(a[v1] + b[v2] + c[n], a[v2] + c[v1] + b[n])
if answer >= 1e9:
print(-1)
else:
print(answer)11094. 행렬 곱셈 순서
문제
크기가 N×M인 행렬 A와 M×K인 B를 곱할 때 필요한 곱셈 연산의 수는 총 N×M×K번이다. 행렬 N개를 곱하는데 필요한 곱셈 연산의 수는 행렬을 곱하는 순서에 따라 달라지게 된다.
예를 들어, A의 크기가 5×3이고, B의 크기가 3×2, C의 크기가 2×6인 경우에 행렬의 곱 ABC를 구하는 경우를 생각해보자.
AB를 먼저 곱하고 C를 곱하는 경우 (AB)C에 필요한 곱셈 연산의 수는 5×3×2 + 5×2×6 = 30 + 60 = 90번이다.
BC를 먼저 곱하고 A를 곱하는 경우 A(BC)에 필요한 곱셈 연산의 수는 3×2×6 + 5×3×6 = 36 + 90 = 126번이다.
같은 곱셈이지만, 곱셈을 하는 순서에 따라서 곱셈 연산의 수가 달라진다.
행렬 N개의 크기가 주어졌을 때, 모든 행렬을 곱하는데 필요한 곱셈 연산 횟수의 최솟값을 구하는 프로그램을 작성하시오. 입력으로 주어진 행렬의 순서를 바꾸면 안 된다.
입력
첫째 줄에 행렬의 개수 N(1 ≤ N ≤ 500)이 주어진다.
둘째 줄부터 N개 줄에는 행렬의 크기 r과 c가 주어진다. (1 ≤ r, c ≤ 500)
항상 순서대로 곱셈을 할 수 있는 크기만 입력으로 주어진다.
출력
첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같다.
예제 입력 1
3
5 3
3 2
2 6
예제 출력 1
90
알고리즘 분류
- 다이나믹 프로그래밍
코드 - pypy 성공
import sys
N = int(input())
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
dp = [[0] * (N) for _ in range(N)]
for term in range(1, N):
for start in range(N): # 첫행렬 : i, 끝행렬: i+term
if start + term == N: # 범위를 벗어나면 무시
break
dp[start][start + term] = int(1e9) # 지금 계산할 첫행렬과 끝행렬
for t in range(start, start + term):
dp[start][start + term] = min(dp[start][start + term], # 1 + 2 + 3
dp[start][t] + dp[t + 1][start + term] + arr[start][0] * arr[t][1] * arr[start + term][1])
print(dp[0][N - 1])1727. 커플 만들기
문제
여자친구가 없는 남자 n명과 남자친구가 없는 여자 m명을 불러 모아서 이성 친구를 만들어 주기로 하였다. 하지만 아무렇게나 해줄 수는 없고, 최대한 비슷한 성격의 사람들을 짝 지어 주기로 하였다.
당신은 뭔가 알 수 없는 방법으로 각 사람의 성격을 수치화 하는데 성공하였다. 따라서 각 사람의 성격은 어떤 정수로 표현된다. 이와 같은 성격의 수치가 주어졌을 때, 우선 최대한 많은 커플을 만들고, 각 커플을 이루는 두 사람의 성격의 차이의 합이 최소가 되도록 하려 한다. 남자-여자 커플만 허용된다.
입력
첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 줄에는 n명의 남자들의 성격이 주어진다. 그 다음 줄에는 m명의 여자들의 성격이 주어진다. 성격은 1,000,000이하의 자연수이다.
출력
첫째 줄에 성격의 차이의 합의 최솟값을 출력한다.
예제 입력 1
2 1
10 20
15
예제 출력 1
5
알고리즘 분류
- 알고리즘 분류
- 다이나믹 프로그래밍
- 그리디 알고리즘
- 정렬
코드 - python3 성공
import sys
input = sys.stdin.readline
# 입력 받기
N, M = map(int, input().split())
man = list(map(int, input().split()))
woman = list(map(int, input().split()))
# 남자와 여자의 성격을 오름차순으로 정렬
man.sort()
woman.sort()
# DP 테이블 초기화
d = [[0 for _ in range(M + 1)] for _ in range(N + 1)]
# DP 테이블 갱신
for i in range(1, N + 1):
for j in range(1, M + 1):
# 현재 커플의 성격 차이를 계산하고 이전까지의 누적 차이를 더함
d[i][j] = d[i - 1][j - 1] + abs(man[i - 1] - woman[j - 1])
# i가 j보다 크면 i쪽이 사람이 더 많으므로, i-1쪽과의 차이 중 작은 값을 선택
if i > j:
d[i][j] = min(d[i][j], d[i - 1][j])
# i가 j보다 작으면 j쪽이 사람이 더 많으므로, j-1쪽과의 차이 중 작은 값을 선택
elif i < j:
d[i][j] = min(d[i][j], d[i][j - 1])
# 결과 출력
print(d[N][M])11401. 이항 계수 3
문제
자연수
(N)과 정수
(K)가 주어졌을 때 이항 계수
(\binom{N}{K})를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.
입력
첫째 줄에
(N)과
(K)가 주어진다. (1 ≤
(N) ≤ 4,000,000, 0 ≤
(K) ≤
(N))
출력
(\binom{N}{K})를 1,000,000,007로 나눈 나머지를 출력한다.
예제 입력 1
5 2
예제 출력 1
10
알고리즘 분류
- 수학
- 정수론
- 조합론
- 분할 정복을 이용한 거듭제곱
- 모듈로 곱셈 역원
- 페르마의 소정리
코드 - python3 성공
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
p = 1000000007
# 팩토리얼 값 계산(나머지 연산 적용)
def factorial(N):
n = 1
for i in range(2, N + 1):
n = (n * i) % p
return n
# 거듭제곱 계산(나머지 연산 적용)
def square(n, k):
if k == 0:
return 1
elif k == 1:
return n
tmp = square(n, k // 2)
if k % 2:
return tmp * tmp * n % p
else:
return tmp * tmp % p
# 분자에 해당하는 팩토리얼 계산
top = factorial(N)
# 분모에 해당하는 팩토리얼 계산 및 역원(페르마의 소정리) 적용
bot = factorial(N - K) * factorial(K) % p
# 조합 공식을 페르마의 소정리를 이용하여 구현
result = top * square(bot, p - 2) % p
# 결과 출력
print(result)