졍's 기술 블로그

일곱 난쟁이

티어 : Bronze 2
시간 제한 : 2 초
메모리 제한 : 128 MB
알고리즘 분류 : 브루트포스 알고리즘, 정렬

문제

왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.

아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.

아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.

입력

아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.

출력

예제 입출력

Algorithm

완전 탐색 이용
1. 난쟁이의 키를 리스트로 입력
2. 두 개씩 뺀 후 리스트의 합이 100이 되는지 확인

Code

import sys
input = sys.stdin.readline

heights = [0 for _ in range(9)]
for i in range(9):
    heights[i] = int(input())

# 리스트 오름차순
heights.sort()

# 리스트에서 두개씩 빼어 리스트의 합이 100이 되는지 확인
temp = []
for i in range(len(heights)):
    for j in range(i, len(heights)):
        if sum(heights[:i]+heights[i+1:j]+heights[j+1:]) == 100:
            temp += heights[:i] + heights[i+1:j] + heights[j+1:]
            break
    if len(temp) > 0:
        break
    
answer = ''
for i in temp:
    answer += str(i) + '\n'
print(answer)

메모리: 30860 KB
시간: 68 ms

골드바흐의 추측

티어 : Silver 1
시간 제한 : 1 초
메모리 제한 : 256 MB
알고리즘 분류 : 수학, 정수론, 소수 판정, 에라토스테네스의 체

문제

1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다.

4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.

예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다.

이 추측은 아직도 해결되지 않은 문제이다.

백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오.

입력

입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다. 테스트 케이스의 개수는 100,000개를 넘지 않는다.

각 테스트 케이스는 짝수 정수 n 하나로 이루어져 있다. (6 ≤ n ≤ 1000000)

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 것을 출력한다. 또, 두 홀수 소수의 합으로 n을 나타낼 수 없는 경우에는 "Goldbach's conjecture is wrong."을 출력한다.

예제 입출력

Algorithm

1. 아레토스테네스의 체를 이용해 입력된 값 중 MAX값을 기준으로 소수 리스트 생성
2. 입력받은 값보다 작은 홀수인 소수로 해당 값을 만들 수 있는지 확인

Code

import sys
import math
input = sys.stdin.readline

nums = []
while True:
    num = int(input())
    if num == 0:
        break
    nums.append(num)

# 에라토스테네스의 체를 이용해 MAX(입력값)를 기준으로 소수 리스트 생성
MAX = max(nums)
prime = {}
for i in range(MAX+1):
    prime[i] = True
prime[1] = False
for i in range(2, int(math.sqrt(MAX + 1))):
    if prime[i]:
        for j in range(i*2, MAX, i):
            prime[j] = False

# 입력받은 수보다 작은 홀수 소수로 해당 값을 만들 수 있는지 확인
answer = ''
for i in nums:
    for j in range(i-3, 0, -2):
        if prime[j] and prime[i - j]:
            answer += str(i) + ' = ' + str(i-j) + ' + ' + str(j) + '\n'
            break
    if j == 1:
        answer += 'Goldbach\'s conjecture is wrong.\n'
print(answer)

메모리: 118412 KB
시간: 704 ms

소수 구하기

티어 : Silver 3
시간 제한 : 2 초
메모리 제한 : 256 MB
알고리즘 분류 : 수학, 정수론,소수 판정, 에라토스테네스의 체

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

예제 입출력

Algorithm

1. 1부터 N까지 숫자 리스트 생성
2. 2부터 루트 N까지의 숫자로 리스트 내의 숫자를 순차적으로 나누면서 나누어떨어지는 수 Fasle 표시
3. M부터 N까지의 숫자 중 True 값 갖는 숫자만 출력

Code

import math

# 입력
M, N = map(int, input().split())
# 1부터 N까지 숫자 리스트 생성
nums = [True for _ in range(N+1)]
nums[1] = False # 1은 소수가 아니므로 False 저장

# 2부터 루트 N + 1까지의 숫자로 나눔
for i in range(2, int(math.sqrt(N) + 1)):
    # 현재 숫자가 나누어진 적 없다면
    if nums[i]:
        # i * 2부터 N을 넘지 않을 때까지의 숫자를 모두 Fasle로 저장
        j = 2
        while i*j < N+1:
            nums[i*j] = False
            j += 1

answer = ''
for i in range(M, N+1):
    if nums[i]:
        answer += str(i) + '\n'
print(answer)

메모리: 42080 KB
시간: 684 ms

약수의 합 2

티어 : Silver 2
시간 제한 : 0.5 초 (추가 시간 없음)
메모리 제한 : 512 MB
알고리즘 분류 : 수학, 정수론

문제

두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)로 표현한다.

자연수 N이 주어졌을 때, g(N)을 구해보자.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

출력

첫째 줄에 g(N)를 출력한다.

예제 입출력

Algorithm

N까지의 약수 중 i라는 숫자는 N//i개 존재
-> i가 1부터 N까지 증가하면서 i의 개수 * i 더하기

Code

N = int(input())
sum_ = 0
for i in range(1, N+1):
    sum_ += i * (N//i)
print(sum_)

메모리: 30864 KB
시간: 240 ms

요세푸스 문제

티어 : Silver 4
시간 제한 : 2 초
메모리 제한 : 512 MB
알고리즘 분류 : 구현, 자료 구조, 큐

문제

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)

출력

예제와 같이 요세푸스 순열을 출력한다.

예제 입출력

Algorithm

Queue 구현 - deque library 사용
1. queue에 1부터 N까지 숫자로 채움
2. append(queue[0]), popleft()를 두 번 수행
3. print(queue[0]), popleft() 수행
4. queue가 빌 때까지 반복

Code

from collections import deque
N, K = map(int, input().split())
queue = deque([i for i in range(1, N+1)])
answer = []
while queue:
    # append, popleft 두 번 수행
    for _ in range(K - 1):
        queue.append(queue[0])
        queue.popleft()

    # print, popleft 수행
    answer.append(queue[0])
    queue.popleft()

print('<', end = '')
for i in range(len(answer)):
    if i == len(answer) - 1:
        print(answer[i], end = '>')
    else:
        print(answer[i], end = ', ')

메모리: 32360 KB
시간: 144 ms

카드2

티어 : Silver 2
시간 제한 : 2 초 (추가 시간 없음)
메모리 제한 : 128 MB
알고리즘 분류 : 자료 구조, 큐

문제

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.

이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.

N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N(1 ≤ N ≤ 500,000)이 주어진다.

출력

첫째 줄에 남게 되는 카드의 번호를 출력한다.

예제 입출력

Algorithm

Queue 구현 - deque library 사용
1. queue에 1부터 n까지 숫자로 채움
2. popleft()로 맨 위의 카드 버림
3. append(queue[0])로 맨 위의 카드 맨 마지막으로 보내기
4. popleft()로 맨 위의 카드 버림
5. 카드가 한 장 남을 때까지 반복

Code

from collections import deque

N = int(input())
queue = deque([i for i in range(1, N+1)])

while len(queue) > 1:
    # 맨 위의 카드 버리기
    queue.popleft()
    
    # 그 다음 맨 위의 카드 버리고 캔 아래 카드 아래로 보내기
    queue.append(queue[0])
    queue.popleft()

print(queue[0])

메모리: 53324 KB
시간: 260 ms

큐 2

티어 : Silver 4
시간 제한 : 1 초 (Python 3: 3초)
메모리 제한 : 512 MB
알고리즘 분류 : 자료 구조, 큐

문제

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여섯 가지이다.

• push X: 정수 X를 큐에 넣는 연산이다.
• pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 큐에 들어있는 정수의 개수를 출력한다.
• empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
• front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

예제 입출력

Algorithm

Queue 구현 - deque library 사용
1. 입력받을 때 readline().rstrip()으로 입력
2. push이면 append
3. pop이면 빈 리스트면 -1출력, 비어있지 않으면 del queue[0]
4. size이면 len(queue)
5. empty이면 빈 리스트면 1, 비어있지 않으면 0 출력
6. front이면 빈 리스트면 -1, 비어있지 않으면 print(queue[0])
7. back이면 빈 리스트면 -1, 비어있지 않으면 print(queue[-1])

Code

import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
queue = deque([])

for _ in range(N):
    order = input().rstrip()
    
    # order가 push이면
    if order[:4] == 'push':
        queue.append(int(order[5:]))
    # order가 pop이면
    elif order == 'pop':
        if not queue:
            print(-1)
        else:
            print(queue[0])
            # del queue[0]
            queue.popleft()
    # order가 size이면
    elif order == 'size':
        print(len(queue))
    # order가 empty이면
    elif order == 'empty':
        if queue:
            print(0)
        else:
            print(1)
    # order가 front이면
    elif order == 'front':
        if not queue:
            print(-1)
        else:
            print(queue[0])
    # order가 back이면
    else:
        if not queue:
            print(-1)
        else:
            print(queue[-1])

메모리: 92536 KB
시간: 1764 ms

연결 요소의 개수

티어 : Silver 2
시간 제한 : 3 초
메모리 제한 : 512 MB
알고리즘 분류 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

예제 입출력

Algorithm

DFS 이용
1. 그래프 구성
    ➝ 양방향으로 구성
2. DFS 구현해 덩어리가 하나씩 나올 때마다 COUNT += 1

Code

import sys
input = sys.stdin.readline


def dfs(start):

    # 현재 Node가 이미 방문한 Node라면 False Return
    if visited[start]:
        return False
    
    # 현재 Node 방문 처리
    visited[start] = True

    # 이웃노드 중
    for x in graph[start]:
        # 방문하지 않은 노드만 접근
        if visited[x] == False:
            dfs(x)
            
    return True
    
    
# 입력
N, M = map(int, input().split())
sys.setrecursionlimit(10**9)
graph = [[] for _ in range(N+1)]
visited = [False] * (N+1)

for _ in range(M):
    i, j = map(int, input().split())
    graph[i].append(j)
    graph[j].append(i)

# 노드 하나씩 보면서 덩어리 count
count = 0
for x in range(1, N+1):
    if not visited[x] and dfs(x):
        count += 1
        
print(count)

메모리: 64880 KB
시간: 768 ms