방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.
(2) 입력
첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.
(3) 출력
첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.
(4) 예제 입력 및 출력
(5) 코드
import heapq
import sys
point_count, line_count = sys.stdin.readline().split()
point_count = int(point_count)
line_count = int(line_count)
start_point = int(sys.stdin.readline())
line_dic = {}
for i in range(point_count):
line_dic[i + 1] = []
for i in range(line_count):
u, v, w = sys.stdin.readline().split()
line_dic[int(u)].append((int(v),int(w)))
def dijkstra(graph, start):
distances = {node + 1: float('inf') for node in range(point_count)}
distances[start] = 0
queue = []
heapq.heappush(queue, [distances[start], start])
while queue:
# print(f'distances = {distances}')
# print(f'queue = {queue}')
current_distance, current_node = heapq.heappop(queue)
if distances[current_node] < current_distance:
continue
for line in graph[current_node]:
adjacent = line[0]
weight = line[1]
distance = current_distance + weight
if distance < distances[adjacent]:
distances[adjacent] = distance
heapq.heappush(queue, [distance, adjacent])
return distances
distance_dic = dijkstra(line_dic, start_point)
for value in distance_dic.values():
if value == float('inf'):
print('INF')
else:
print(value)
<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.
(2) 입력
첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.
(3) 출력
첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.
(4) 예제 입력 및 출력
(5) 코드
import sys
def DFS(x,y):
global count
if f'{x},{y}' in check_dictionary:
return count
else:
check_dictionary[f'{x},{y}'] = True
if square_list[x][y] == 1:
count += 1
#위
if y > 0:
DFS(x,y - 1)
#아래
if y < length - 1:
DFS(x,y + 1)
#오른쪽
if x < length - 1:
DFS(x + 1, y)
#왼쪽
if x > 0:
DFS(x - 1, y)
return count
length = int(sys.stdin.readline())
square_list = []
check_dictionary = {
}
for i in range(length):
string = sys.stdin.readline().rstrip('\n');
temp_list = []
for char in string:
temp_list.append(int(char))
square_list.append(temp_list)
count_list = []
for i in range(length):
for j in range(length):
count = 0
count = DFS(i, j)
if count > 0:
count_list.append(count)
count_list.sort()
print(len(count_list))
for count in count_list:
print(count)
수열 S가 어떤 수 Sk를 기준으로 S1< S2< ... Sk-1< Sk> Sk+1> ... SN-1> SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.
예를 들어, {10, 20,30, 25, 20}과 {10, 20, 30,40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.
수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.
(2) 입력
첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai≤ 1,000)
(3) 출력
첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.
(4) 예제 입력 및 출력
(5) 코드
import sys
length = int(sys.stdin.readline())
sequence_list = list(map(int, sys.stdin.readline().split()))
asc_list = [0] * length
desc_list = [0] * length
for i in range(length):
for j in range(i):
if (sequence_list[i] > sequence_list[j] and asc_list[i] < asc_list[j]):
asc_list[i] = asc_list[j]
asc_list[i] += 1
for i in range(length - 1, -1, -1):
for j in range(length - 1, i, -1):
if (sequence_list[i] > sequence_list[j] and desc_list[i] < desc_list[j]):
desc_list[i] = desc_list[j]
desc_list[i] += 1
max_count = 0
for i in range(length):
max_count = max(max_count,asc_list[i] + desc_list[i])
print(max_count - 1)
흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다.
주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다
위 그림에서 왼쪽의 영상은 오른쪽의 배열과 같이 숫자로 주어지며, 이 영상을 쿼드 트리 구조를 이용하여 압축하면 "(0(0011)(0(0111)01)1)"로 표현된다. N ×N 크기의 영상이 주어질 때, 이 영상을 압축한 결과를 출력하는 프로그램을 작성하시오.
(2) 입력
첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.
(3) 출력
영상을 압축한 결과를 출력한다.
(4) 예제 입력 및 출력
(5) 코드
import sys
import math
square_length = int(sys.stdin.readline())
square_list = []
square_store = []
def DFS(square_arrow_list):
square = square_arrow_list
half_size = len(square) // 2
square_left_up_list = []
square_rigth_up_list = []
square_left_down_list = []
square_right_down_list = []
for i in range(half_size):
temp_left_up_list = []
temp_rigth_up_list = []
temp_left_down_list = []
temp_right_down_list = []
for j in range(half_size):
# 왼쪽 위
temp_left_up_list.append(square[i][j])
# 오른쪽 위
temp_rigth_up_list.append(square[i][j + half_size])
# 왼쪽 아래
temp_left_down_list.append(square[i + half_size][j])
# 오른쪽 아래
temp_right_down_list.append(square[i + half_size][j + half_size])
square_left_up_list.append(temp_left_up_list)
square_rigth_up_list.append(temp_rigth_up_list)
square_left_down_list.append(temp_left_down_list)
square_right_down_list.append(temp_right_down_list)
print('(', end='')
is_zero_one(square_store, square_left_up_list)
is_zero_one(square_store, square_rigth_up_list)
is_zero_one(square_store, square_left_down_list)
is_zero_one(square_store, square_right_down_list)
print(')', end='')
def is_zero_one(square_store, square_arrow_list):
is_zero = False
is_one = False
for row in square_arrow_list:
if not is_one or not is_zero:
if 1 in row:
is_one = True
if 0 in row:
is_zero = True
else:
break
if is_one and is_zero:
DFS(square_arrow_list)
square_store.append(square_arrow_list)
elif not is_zero:
print(1, end='')
else:
print(0, end='')
for i in range(square_length):
string = sys.stdin.readline().rstrip('\n');
temp_list = []
for char in string:
temp_list.append(int(char))
square_list.append(temp_list)
is_zero_one(square_store, square_list)
1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.
N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.
(2) 입력
첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.
(3) 출력
예제와 같이 요세푸스 순열을 출력한다.
(4) 예제 입력 및 출력
(5) 코드
import sys
N, K = map(int,sys.stdin.readline().split())
player_list = []
for i in range(N):
player_list.append(i + 1)
cur_index = 0
print('<', end='')
while True:
cur_index = (cur_index + K - 1) % len(player_list)
print(player_list.pop(cur_index), end= '')
if not player_list:
break
print(', ',end='')
print('>')
어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다.
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
고른 수열은 오름차순이어야 한다.
(2) 입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
(3) 출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
(4) 예제 입력 및 출력
(5) 코드
import itertools
import sys
N, M = map(int,sys.stdin.readline().split())
N_list = []
for i in range(N):
N_list.append(str(i + 1))
for i in list(map(' '.join, itertools.combinations(N_list, M))):
print(i)
