티어 : 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)
티어 : 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')
Computer A에서 Computer B로 100MB의 비디오를 전송하는 경우 Segment 과정이 없다면 사용자는 100MB의 비디오가 모두 로딩된 후 비디오를 볼 수 있다. Segment 과정이 있다면 Segment라는 작은 단위로 나뉘어 비디오 일부분을 미리 볼 수 있다.
연결이 중간에 끊기는 경우 Segmentation을 하지 않으면 큰 Data가 날아가 손실률이 크다.
티어 : 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])
티어 : 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])
티어 : Silver 1 시간 제한 : 2 초 메모리 제한 : 128 MB 알고리즘 분류 : 다이나믹 프로그래밍, 그래프 이론, 다익스트라
문제
매일 아침, 세준이는 학교에 가기 위해서 차를 타고 D킬로미터 길이의 고속도로를 지난다. 이 고속도로는 심각하게 커브가 많아서 정말 운전하기도 힘들다. 어느 날, 세준이는 이 고속도로에 지름길이 존재한다는 것을 알게 되었다. 모든 지름길은 일방통행이고, 고속도로를 역주행할 수는 없다.
세준이가 운전해야 하는 거리의 최솟값을 출력하시오.
입력
첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주어진다. 모든 위치와 길이는 10,000보다 작거나 같은 음이 아닌 정수이다. 지름길의 시작 위치는 도착 위치보다 작다.
출력
세준이가 운전해야하는 거리의 최솟값을 출력하시오.
예제 입출력
Algorithm
dijkstra 알고리즘 - 힙 1. 지름길을 입력 받아 graph 생성 ➝ 도착 지점이 고속도로의 길이보다 큰 경우 graph에 추가하지 않음 2. 지름길이 아닌 길도 graph에 추가 ➝ 중간에 끊겨있는 길도 같이 추가 3. D 위치의 최단 거리 출력
Code
import sys
import heapq
INF = int(1e9)
input = sys.stdin.readline
def dijkstra(start):
queue = []
# 첫 번째 칸으로 가는 최단 경로 0으로 설정
heapq.heappush(queue, (start, 0))
distance[start] = 0
while queue:
# 큐에서 꺼내기
dist, now = heapq.heappop(queue)
# 방문한 노드라면 무시
if distance[now] < dist:
continue
# 인접 노드 확인
for next in graph[now]:
cost = dist + next[1]
# cost가 인접노드까지 가는 데 최소 거리라면 갱신하고 큐에 추가
if cost < distance[next[0]]:
distance[next[0]] = cost
heapq.heappush(queue, (cost, next[0]))
N, D = map(int, input().split())
graph = [[] for _ in range(D+1)]
distance = [INF] * (D+1)
for _ in range(N):
start, end, length = map(int, input().split())
# 도착 지점이 고속도로의 길이보다 큰 경우 graph에 추가하지 않음
if end > D:
continue
graph[start].append((end, length))
# 지름길이 아닌 길도 graph에 추가
if (end, end - start) not in graph[start]:
graph[start].append((end, end - start))
for i in range(D):
# graph의 현재 INDEX에 다음 칸 까지의 거리 추가
graph[i].append((i+1, 1))
dijkstra(0)
print(distance[-1])
<!-- 해당 Collection에 대한 전체 정보 -->
GET /cources
<!-- Document의 정보 조회 -->
GET /cources/front
4.2. Create(생성) - POST
<!-- backend coach 집합에 jjyoung라는 닉네임을 가진 코치 개체 생성 -->
POST /courses/back/coaches
<!-- body에 생성할 내용을 담음 -->
body {nickname: jjyoung}
4.3. Update(수정) - PUT
<!-- frontend coach 집합 중 첫 번째 코치 닉네임을 jjyoung로 수정 -->
PUT /courses/front/coaches
<!-- 수정할 내용을 body에 담음 -->
body {id: 1, nickname: jjyoung}
4.4. Delete(삭제) - DELETE
<!-- frontend crew 집합 중 jjyoung 삭제 -->
DELETE /courses/front/crews/jjyoung
5. REST Arichtecture의 제약 조건
5.1. Client - Server
: Client가 Server에게 Request를 보내고 Server가 Client에게 Response를 보내는 구조로 Server와 Client의 역할이 분리되어있다.
Server : API 제공과 제공된 API를 이용해 비즈니스 로직을 처리하거나 저장
Client : 사용자 인증이나 컨텍스트(세션, 로그인 정보) 등을 관리
5.2. Stateless(무상태성)
: Client와 Server의 통신에는 상태가 없어야하며 모든 요청은 필요한 정보를 담고 있어야 한다.
☞ Client가 두 가지 요청을 보냈을 때 두 번째 요청 시 Server는 Client의 첫 번째 요청의 내용을 모르므로 두 번째 요청시에도 필요한 모든 정보를 담고 있어야 한다.
5.3. Cache
: 일반적인 서비스에서 60 ~ 80% 가량의 Transaction이 Select와 같은 조회성 트랜잭션이며 GET은 얼마든지 호출해도 매번 같은 결과를 만들어내므로(Idempotent) 캐싱이 가능하다.
5.4. Uniform Interface
5.4.1. Identification of Resources : 자원은 유일하게 식별 가능해야하며 Resource가 하나 이상의 유일한 특정 주소인 URI로 식별되어야 한다. ☞ 아직 POST Method로만 Request를 보내기 때문에 URI나 Request Body로 어떤 동작을 할 지 알려줘야 한다.
5.4.2. Manipulation of Resources through Representation : HTTP Method로 표현(CRUD)을 담아야 한다. ☞ 안전한 Operation과 안전하지 않은 Operation 간의 강한 분리를 제공해야 한다.
5.4.4. Hypermedia As the Engine Of Application State(HATEOAS)
: Hyperlink를 통해 Application의 상태가 전이되어야 한다.
☞ HTTP Response에 다음 Action이나 관계되는 Resource에 대한 HTTP Link를 함께 Return한다.
☞ 장점 : 요청 URI가 변경되더라도 Client는 Server에서 동적으로 생성된 URI를 사용함으로써 Client는 URI 수정에 따른 코드를 변경하지 않아도 된다.
5.5. Layered System
: 계층으로 구성이 가능해야 한다.
☞ Server는 다중 계층으로 구성될 수 있으나 Client 입장에서는 계층에 상관 없이 Server만 호출하면 된다.
e.g., 순수 비즈니스 로직을 수행하는 Server, 사용자 인증, 암호화(SSL), 로드 밸런싱 등을 하는 계층을 추가하거나 PROXY, 게이트웨이 같은 중간 매체 사용 가능
5.6. Code-On-Demand(Option)
: Server가 Network를 통해 Client에 Program을 전달하면 그 Program이 Client에서 실행될 수 있어야 한다.
e.g., JavaScript를 사용해 Server에서 Program 전달하면 Client에서 동적으로 실행 가능하다.
6. Richardson Maturity Model
Glory of REST
Level 3 : Hypermedia Controls
Level 2 : HTTP Verbs
Level 1 : Resources
Level 0 : The Swamp of POX
6.1. Level 0 : The Swamp of POX
: POX(Plain Old XML)를 주고받는 단순한 RPC Style System
☞ HTTP를 RPC 기반의 원격 통신을 위한 터널링 Mechanism으로 사용된다.
충족된 제약 조건 : Server-Client, Stateless, Layered System, Manipulation of Resources through Representation
RPC(Remote Procedure Call, 원격 프로시저 호출) : 별도의 원격 제어를 위한 코딩 없이 다른 주소 공간에서 함수나 프로시저를 실행할 수 있게 하는 프로세스 간 통신 기술 (= Client가 Server에 있는 Program을 실행하기 위해 사용하는 통신 기술) ☞ RPC를 이용하면 개발자는 실행 Program이 로컬 위치에 있든 원격 위치에 있든 동일한 코드를 이용할 수 있다.
☞ Client가 Server에게 Message를 보내 Program을 실행시키고 Server에서는 그 Program의 결과를 Client에게 전송
