코드메모장

(1) 문제

• 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 

• 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.
• 토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

(2) 입력

• 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.
• 토마토가 하나 이상 있는 경우만 입력으로 주어진다.

(3) 출력

• 여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

(4) 예제 입력 및 출력

(5) 코드

import sys
import collections

tomato_store = collections.deque()
queue = collections.deque()
visited = collections.deque()

row, col = map(int, sys.stdin.readline().split())

for i in range(col):
   tomato = list(map(int, sys.stdin.readline().split()))
   tomato_store.append(tomato)


for i in range(col):
    for j in range(row):
        if tomato_store[i][j] == 1:
            queue.append([i,j])

max_date = 0

while queue:
    cur_index = queue.popleft()
    # if cur_index not in visited:
    #     visited.append(cur_index)
    cur_row = cur_index[1]
    cur_col = cur_index[0]
    cur_value = tomato_store[cur_col][cur_row]

    #오른쪽
    if cur_row + 1 < row:
        if tomato_store[cur_col][cur_row + 1] == 0:
            tomato_store[cur_col][cur_row + 1] = cur_value + 1
            queue.append([cur_col,cur_row + 1])
    #왼쪽
    if cur_row - 1 > -1:
        if tomato_store[cur_col][cur_row - 1] == 0:
            tomato_store[cur_col][cur_row - 1] = cur_value + 1
            queue.append([cur_col,cur_row - 1])
    #위
    if cur_col - 1 > -1:
        if tomato_store[cur_col - 1][cur_row] == 0:
            tomato_store[cur_col - 1][cur_row] = cur_value + 1
            queue.append([cur_col - 1,cur_row])
    #아래
    if cur_col + 1 < col:
        if tomato_store[cur_col + 1][cur_row] == 0:
            tomato_store[cur_col + 1][cur_row] = cur_value + 1
            queue.append([cur_col + 1,cur_row])
    
    if cur_value > max_date:
        max_date = cur_value

is_0 = False
for i in range(col):
    for j in range(row):
        if tomato_store[i][j] == 0:
            is_0 = True
            break

if is_0:
    print(-1)
else:
    print(max_date - 1)

(6) 실행결과

(1) 문제

• 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.
• 예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

• 어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

(2) 입력

• 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

(3) 출력

• 1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

(4) 예제 입력 및 출력

(5) 코드

import sys
length = int(input())

virus = [False] * length
computer_list = []

for i in range(int(input())):
    computer_list.append(list(map(int,input().split())))

def virus_connet_count(index):
    if virus[index] == True:
        return
    else:
        virus[index] = True
        for computer in computer_list:
            if computer[0] == index + 1:
                virus_connet_count(computer[1] - 1)
            elif computer[1] == index + 1:
                virus_connet_count(computer[0] - 1)


virus_connet_count(0)
print(virus.count(True) - 1)

(6) 실행결과

(1) 문제

• 지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.
• 지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.
  1. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
  2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
  3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.

• 큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.

(2) 입력

• 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.

(3) 출력

• 첫째 줄에 문제의 정답을 출력한다.

(4) 예제 입력 및 출력

(5) 코드

import sys
length, element_count = map(int, sys.stdin.readline().split())

queue = []
target_queue = []
cur_index = 0
count = 0
for i in range(length):
    queue.append(i + 1)

target_queue = list(map(int, sys.stdin.readline().split()))

while target_queue:
    target_index = queue.index(target_queue[0])

    if target_index == cur_index:
        queue.pop(cur_index)
        target_queue.pop(0)   
    else:
        if cur_index < target_index:
            rigth_move = target_index - cur_index
            left_move = -(len(queue) - (target_index - cur_index))
        else:
            rigth_move = len(queue) - (cur_index - target_index)
            left_move = target_index - cur_index
        
        if abs(rigth_move) <= abs(left_move):
            cur_index += rigth_move
            count += abs(rigth_move)
        else:
            cur_index += left_move
            count += abs(left_move)
        
        #계산한 index가 범위 밖일 경우
        if cur_index < 0:
            cur_index += len(queue)
        elif cur_index >= len(queue):
            cur_index -= len(queue)
        
        queue.pop(cur_index)
        target_queue.pop(0)
    
print(count)

(6) 실행결과

(1) 문제

세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.

정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.

문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.

• 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
• 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
• 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
• 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
• 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.

정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.

(2) 입력

• 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다.
• 입력의 종료조건으로 맨 마지막에 점 하나(".")가 들어온다.

(3) 출력

• 각 줄마다 해당 문자열이 균형을 이루고 있으면 "yes"를, 아니면 "no"를 출력한다.

(4) 예제 입력 및 출력

(5) 코드

char_list = [['[', ']'], ['(', ')']]

while True:
    text = input()
    stack = []
    if text == '.':
        break
    
    for char in text:
        if char == '(' or char == '[':
            stack.append(char)
        elif char == ')' or char == ']':
            if len(stack) == 0:
                print('no')
                break
            if char == ')' and stack[-1] == '(' or char == ']' and stack[-1] == '[':
                stack.pop()
            else:
                print('no')
                break
    else:
        if len(stack) == 0:
            print('yes')
        else:
            print('no')

(6) 실행결과

(1) 문제

• 스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.
• 1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

(2) 입력

• 첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.

(3) 출력

• 입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.

(4) 예제 입력 및 출력

(5) 코드

def is_empty(list):
    if not list:
        return True
    else:
        return False

length = int(input())
cur_value = 1

stack = []
queue = []
result = []
is_impossible = False
for i in range(length):
    queue.append(input())

#queue에 값이 없을때 까지
while not is_empty(queue):
    if is_empty(stack):
        stack.append(cur_value)
        result.append('+')
        cur_value += 1
    else:
        if int(stack[-1]) != int(queue[0]):
            stack.append(cur_value)
            result.append('+')
            cur_value += 1
        # elif stack[-1] == queue[0]:
        else:
            stack.pop()
            queue.pop(0)
            result.append('-')
    if cur_value > length + 1:
        is_impossible = True
        break

if is_impossible:
    print('NO')
else:
    for i in result:
        print(i)

(6) 실행결과

(1) 문제

• 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다.
• 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15, 10, 15가 될 것이고, 상근이는 길이가 5인 나무와 2인 나무를 들고 집에 갈 것이다. (총 7미터를 집에 들고 간다) 절단기에 설정할 수 있는 높이는 양의 정수 또는 0이다.
• 상근이는 환경에 매우 관심이 많기 때문에, 나무를 필요한 만큼만 집으로 가져가려고 한다. 이때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

(2) 입력

• 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)
• 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보다 크거나 같기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다. 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.

(3) 출력

• 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

(4) 예제 입력 및 출력

(5) 코드

import sys
import math
tree_count, want_tree = map(int, sys.stdin.readline().split())

tree = list(map(int, sys.stdin.readline().split()))

def binary_search(target, array):
    min_value = 0
    mid_value = 0
    max_value = max(tree)

    while min_value <= max_value:
        mid_value = (min_value + max_value) //2
        rest = 0
        for i in array:
            if i >= mid_value:
                rest += i - mid_value
        
        if rest >= want_tree:
            min_value = mid_value + 1
            
        else:
            max_value = mid_value - 1
            
    return max_value

print(binary_search(want_tree,tree))

(6) 실행결과

(1) 문제

• 2차원 평면 위의 점 N개가 주어진다. 좌표를 y좌표가 증가하는 순으로, y좌표가 같으면 x좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.

(2) 입력

• 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.

(3) 출력

• 첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.

(4) 예제 입력 및 출력

(5) 코드

length = int(input())
point_list = []

for i in range(0,length):
    x,y = input().split()
    point_list.append([int(x),int(y)])

point_list.sort(key=lambda x: (x[1], x[0]))

for i in range(0, len(point_list)):
    print(point_list[i][0], point_list[i][1])

(6) 실행결과

(1) 문제

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.

(2) 입력

• 첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.

(3) 출력

• 첫째 줄에 옮긴 횟수 K를 출력한다.
• 두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

(4) 예제 입력 및 출력

(5) 코드

n = int(input())

results = []
count = 0
def hanoi(N, src, dest, transfer):
    if N == 1:
        return results.append([src, dest])
    hanoi(N-1, src, transfer, dest)
    results.append([src, dest])
    hanoi(N-1, transfer, dest, src)

hanoi(n,1,3,2)

print(len(results))

for result in results:
    print(result[0], result[1])

(6) 실행결과

(1) 문제

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

(2) 입력

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

(3) 출력

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

(4) 예제 입력 및 출력

(5) 코드

import math

#변수를 입력받는 방법
min,max = input().split()
min_number = int(min)
max_number = int(max)

prime = []

for i in range(min_number, max_number + 1):
    prime_check = True
    for j in range(2, int(math.sqrt(i + 1)) + 1):
        if i % j == 0:
            prime_check = False
            break
    if prime_check:
        prime.append(i)

if min_number == 1:
    prime.remove(1)
for i in range(0, len(prime)):
    print(prime[i])

(6) 실행결과

(1) 문제

ACM 호텔 매니저 지우는 손님이 도착하는 대로 빈 방을 배정하고 있다. 고객 설문조사에 따르면 손님들은 호텔 정문으로부터 걸어서 가장 짧은 거리에 있는 방을 선호한다고 한다. 여러분은 지우를 도와 줄 프로그램을 작성하고자 한다. 즉 설문조사 결과 대로 호텔 정문으로부터 걷는 거리가 가장 짧도록 방을 배정하는 프로그램을 작성하고자 한다.

문제를 단순화하기 위해서 호텔은 직사각형 모양이라고 가정하자. 각 층에 W 개의 방이 있는 H 층 건물이라고 가정하자 (1 ≤ H, W ≤ 99). 그리고 엘리베이터는 가장 왼쪽에 있다고 가정하자(그림 1 참고). 이런 형태의 호텔을 H × W 형태 호텔이라고 부른다. 호텔 정문은 일층 엘리베이터 바로 앞에 있는데, 정문에서 엘리베이터까지의 거리는 무시한다. 또 모든 인접한 두 방 사이의 거리는 같은 거리(거리 1)라고 가정하고 호텔의 정면 쪽에만 방이 있다고 가정한다.

그림 1. H = 6 이고 W = 12 인 H × W 호텔을 간략하게 나타낸 그림

방 번호는 YXX 나 YYXX 형태인데 여기서 Y 나 YY 는 층 수를 나타내고 XX 는 엘리베이터에서부터 세었을 때의 번호를 나타낸다. 즉, 그림 1 에서 빗금으로 표시한 방은 305 호가 된다.

손님은 엘리베이터를 타고 이동하는 거리는 신경 쓰지 않는다. 다만 걷는 거리가 같을 때에는 아래층의 방을 더 선호한다. 예를 들면 102 호 방보다는 301 호 방을 더 선호하는데, 102 호는 거리 2 만큼 걸어야 하지만 301 호는 거리 1 만큼만 걸으면 되기 때문이다. 같은 이유로 102 호보다 2101 호를 더 선호한다.

여러분이 작성할 프로그램은 초기에 모든 방이 비어있다고 가정하에 이 정책에 따라 N 번째로 도착한 손님에게 배정될 방 번호를 계산하는 프로그램이다. 첫 번째 손님은 101 호, 두 번째 손님은 201 호 등과 같이 배정한다. 그림 1 의 경우를 예로 들면, H = 6이므로 10 번째 손님은 402 호에 배정해야 한다.

(2) 입력

프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T 개의 테스트 데이터로 이루어져 있는데 T 는 입력의 맨 첫 줄에 주어진다. 각 테스트 데이터는 한 행으로서 H, W, N, 세 정수를 포함하고 있으며 각각 호텔의 층 수, 각 층의 방 수, 몇 번째 손님인지를 나타낸다(1 ≤ H, W ≤ 99, 1 ≤ N ≤ H × W). 

(3) 출력

• 프로그램은 표준 출력에 출력한다. 각 테스트 데이터마다 정확히 한 행을 출력하는데, 내용은 N 번째 손님에게 배정되어야 하는 방 번호를 출력한다.

(4) 예제 입력 및 출력

(5) 코드

import math

#변수를 입력받는 방법
length = int(input())
hotels = []

for i in range(0,length):
     H,W,N = input().split()
     hotels.append([H,W,N])

for i in range(0,len(hotels)):
    hotel_H = int(hotels[i][0])
    hotel_X = int(hotels[i][1])
    client_count = int(hotels[i][2])

    client_x = int(client_count / hotel_H)
    client_y = hotel_H
    

    if client_count % hotel_H != 0:
        client_x += 1
        client_y = client_count % hotel_H    

    if len(str(client_x)) == 1:
        client_x = '0' + str(client_x)

    print(str(client_y) + str(client_x))
    

(6) 실행결과