코드메모장

(1) 문제

• 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 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)

(6) 실행결과

(1) 문제

• <그림 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)

(6) 실행결과

(1) 문제

• 수열 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)

(6) 실행결과