졍's 기술 블로그

큐 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 3
시간 제한 : 2 초
메모리 제한 : 128 MB
알고리즘 분류 : 자료 구조, 스택

문제

스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

입력

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

출력

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

예제 입출력

힌트

1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다.

Algorithm

Stack 이용
1. 수열의 현재 숫자와 Stack의 마지막 값 비교
-> 수열의 현재 숫자까지 push()
-> 수열의 현재 숫자 == stack[-1]이면 pop()
-> 그외의 상황은 NO 출력

Code

import sys
input = sys.stdin.readline

n = int(input())
list_ = []
for _ in range(n):
    list_.append(int(input()))
    
pop_dict = {}
pop_dict = [False for _ in range(n+1)]

stack = []
flag = False # 불가능한 경우 True
answer = []
i = 0
num = 1
while i < len(list_):
    # stack 비어있으면 현재 값 append
    if not stack:
        stack.append(num)
        
    for j in range(num, list_[i] + 1):
        # pop dict에 없는 원소만 추가
        if not pop_dict[j]:
            stack.append(j)
            answer.append('+')
            num += 1

    if list_[i] == stack[-1]:
        pop_dict[stack[-1]] = True
        stack.pop()
        answer.append('-')
        i += 1
    else:
        flag = True
        break

# 출력
if flag:
    print('NO')
else:
    for i in answer:
        print(i)

메모리: 37084 KB
시간: 280 ms

균형잡힌 세상

티어 : Silver 4
시간 제한 : 1 초
메모리 제한 : 128 MB
알고리즘 분류 : 자료 구조, 문자열, 스택

문제

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

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

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

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

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

입력

하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다.

출력

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

예제 입출력

힌트

7번째의 " ."와 같이 괄호가 하나도 없는 경우도 균형잡힌 문자열로 간주할 수 있다.

Algorithm

Stack 이용
1. Stack을 생성
2. 문자가 ( 이거나 [ 인 경우 Stack에 추가, ) 이거나 ] 인 경우 stack의 마지막 원소가 ( 이거나 [ 인지 확인하고 맞으면 POP()
3. pop할 때 짝이 맞지 않으면 no
4. 스택에 원소가 남아있으면 no

Code

import sys
input = sys.stdin.readline

while True:
    words = input().rstrip()
    # 입력이 .이면 종료
    if words == '.':
        break
    
    stack = []
    flag = False # 균형이 맞으면 False, 균형이 맞지 않으면 True
    for word in words:
        # 문자가 (인 경우 소괄호 stack에 추가
        if word == '(':
            stack.append(word)
        elif word == ')': # 문자가 )인 경우 소괄호 stack에서 pop
            # stack의 마지막 원소와 짝이 맞으면 pop
            if stack and stack[-1] == '(': 
                stack.pop()
            # stack 비어있으면 no 출력
            else:
                flag = True
                break
                
        elif word == '[': # 문자가 [인 경우 대괄호 stack에 추가
            stack.append(word)
        elif word == ']': # 문자가 ]인 경우 대괄호 stack에서 pop
            # stack의 마지막 원소와 짝이 맞으면 pop
            if stack and stack[-1] == '[':
                stack.pop()
            # 대괄호 stack 비어있으면 no 출력
            else:
                flag = True
                break

    # flag가 True이거나 소괄호 stack과 대괄호 stack 중 비어있지 않은 리스트가 있으면 균형을 이루지 않는 문자열
    if flag or stack:
        print('no')
    # 소괄호 stack과 대괄호 stack에 아무것도 없으면 균형을 이루는 문자열
    elif not stack:
        print('yes')

메모리: 30864 KB
시간: 112 ms

최소비용 구하기

티어 : Gold 5
시간 제한 : 0.5 초
메모리 제한 : 128 MB
알고리즘 분류 : 그래프 이론, 다익스트라

문제

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다.

입력

첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.

그리고 M+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다. 출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.

예제 입출력

Algorithm

dijkstra 알고리즘 - 힙
1. 입력으로 graph 구성
2. 다익스트라 알고리즘을 이용해 최단 경로 구하기

Code

import sys
import heapq

def dijkstra(start):
    queue = []
    
    # 첫 번째 위치 큐에 추가
    heapq.heappush(queue, (0, start))
    distance[start] = 0
    
    while queue:
        # queue에서 꺼내기
        dist, now = heapq.heappop(queue)
        
        # 이미 방문한 적 있는 도시이면 무시
        if distance[now] < dist:
            continue
        
        # 인접 노드 확인
        for next in graph[now]:
            # cost 계산 : 현재 node의 누적 거리 + 현재 노드에서 다음 노드까지의 거리
            cost = dist + next[0]
            # cost가 distance에 저장된 값보다 작으면 갱신
            if cost < distance[next[1]]:
                distance[next[1]] = cost
                heapq.heappush(queue, (cost, next[1]))
                
input = sys.stdin.readline
INF = 1e9

# 입력
N = int(input())
M = int(input())
graph = [[] for _ in range(N+1)]
distance = [INF] * (N+1)
for _ in range(M):
    start, end, cost = map(int, input().split())
    graph[start].append((cost, end))
start, end = map(int, input().split())

dijkstra(start)
print(distance[end])

메모리: 56088 KB
시간: 352 ms

최단경로

티어 : Gold 5
시간 제한 : 1 초
메모리 제한 : 256 MB
알고리즘 분류 : 그래프 이론, 다익스트라

문제

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

입력

첫째 줄에 정점의 개수 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 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

출력

첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

예제 입출력

Algorithm

dijkstra 알고리즘 - 힙
1. 입력으로 graph 구성
2. 다익스트라 알고리즘을 이용해 최단 경로 구하기

Code

import sys
import heapq

def dijkstra(start):
    queue = []
    # 첫 번째 노드 큐에 추가
    heapq.heappush(queue, (0, start))
    distance[start] = 0
    
    while queue:
        # 큐에서 꺼내기
        dist, now = heapq.heappop(queue)
        
        # 이미 방문한 노드는 무시
        if distance[now] < dist:
            continue
        
        # 인접 노드 확인
        for next in graph[now]:
            # cost 계산 = 현재 node의 거리 + 다음 node까지의 거리
            cost = dist + next[1]
            if cost < distance[next[0]]:
                distance[next[0]] = cost
                # 큐에 추가
                heapq.heappush(queue, (cost, next[0]))

INF = int(1e9)
input = sys.stdin.readline

V, E = map(int, input().split())
start = int(input())
graph = [[] for _ in range(V+1)]
distance = [INF] * (V+1)
for _ in range(E):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))

dijkstra(start)
for i in range(1, V+1):
    if distance[i] == INF:
        print('INF')
    else:
        print(distance[i])

메모리: 66936 KB
시간: 700 ms

1

티어 : Silver 3
시간 제한 : 1 초
메모리 제한 : 128 MB
알고리즘 분류 : 수학, 브루트포스 알고리즘, 정수론

문제

2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, n이 주어진다.

출력

1로 이루어진 n의 배수 중 가장 작은 수의 자리수를 출력한다.

예제 입출력

Code

while True:
  try:
    n = int(input())
    num = 1
    while True:
      if int('1'*num) % n == 0:
        print(len('1'*num))
        break
      num += 1
  except:
    break

메모리: 30860 KB
시간: 2240 ms

가장 긴 감소하는 부분 수열

티어 : Silver 2
시간 제한 : 1 초
메모리 제한 : 256 MB
알고리즘 분류 : 다이나믹 프로그래밍

문제

수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10}  이고, 길이는 3이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 감소하는 부분 수열의 길이를 출력한다.

예제 입출력

Algorithm

가장 긴 감소하는 부분 수열은 가장 긴 증가하는 부분 수열을 이용
dp[i] : i번째 원소를 마지막으로 하는 부분 증가수열의 길이
1. 입력 받는 수열을 reverse
2. 가장 긴 증가하는 부분 수열 찾기

Code

N = int(input())
A = list(map(int, input().split()))

# 수열 reverse
A.reverse()

dp = [1] * N

for i in range(1, N):
  for j in range(i):
    if A[j] < A[i]:
      dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))

메모리: 30864 KB
시간: 196 ms

가장 긴 증가하는 부분 수열

티어 : Silver 2
시간 제한 : 1 초
메모리 제한 : 256 MB
알고리즘 분류 : 다이나믹 프로그래밍

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

예제 입출력

Algorithm

dp[i] : i 번째 원소를 마지막으로 하는 부분 증가 수열의 최대 길이
1. 리스트를 이중 for문으로 돌면서 자신보다 작은 index에 값이 작은 수가 몇 개 있는지 확인
    ➝ i : 1 ~ N-1, j : 0 ~ i
2. j번째 원소가 i번째 원소보다 작으면 i번째 dp Table의 값과 j번째 dp Table의 값 + 1 중 큰 값으로 dp Table 갱신

Code

N = int(input())
A = list(map(int, input().split()))

dp = [1] * N

for i in range(1, N):
  for j in range(i):
    if A[j] < A[i]:
      dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))

메모리: 30860 KB
시간: 200 ms