IT-garden

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

예제 입력과 출력

알고리즘 분류

BFS

DFS

정답

from collections import deque

n,m,v=map(int,input().split())

a=[[] for i in range(n+1)]

for i in range(m):
    x, y=map(int,input().split())
    a[x].append(y)
    a[y].append(x)

for i in a:
    i.sort()

def dfs(node):
    ch[node]=1
    print(node, end=' ')

    for i in a[node]:
        if ch[i] != 1:
            dfs(i)

ch=[0]*(n+1)
dfs(v)

print()

def bfs(start):
    de=deque()
    de.append(start)
    che[start]=1

    while len(de) != 0:
        now=de.popleft()
        print(now, end=' ')
        
        for i in a[now]:
            if che[i] != 1:
                che[i]=1
                de.append(i)
    
che=[0]*(n+1)
bfs(v)

queue를 사용하면 런타임 에러가 나서 deque를 사용했습니다.

queue가 많이 느려서 그렇다고 하는데 정확하지는 않습니다.

백준 알고리즘 1260번 : www.acmicpc.net/problem/1260

문제

정수를 저장하는 덱(Deque)를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여덟 가지이다.

• push_front X: 정수 X를 덱의 앞에 넣는다.
• push_back X: 정수 X를 덱의 뒤에 넣는다.
• pop_front: 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• pop_back: 덱의 가장 뒤에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 덱에 들어있는 정수의 개수를 출력한다.
• empty: 덱이 비어있으면 1을, 아니면 0을 출력한다.
• front: 덱의 가장 앞에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• back: 덱의 가장 뒤에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

예제 입력과 출력

알고리즘 분류

덱

정답

import sys
from collections import deque
input= lambda :sys.stdin.readline().strip()

n=int(input())
d=deque()

for i in range(n):
    a, *b = input().split()
    if a == 'push_front':
        d.appendleft(int(b[0]))
    elif a == 'push_back':
        d.append(int(b[0]))
    elif a == 'pop_front':
        print(d.popleft() if len(d) != 0 else -1)   
    elif a == 'pop_back':
        print(d.pop() if len(d) != 0 else -1)
    elif a == 'size':
        print(len(d))
    elif a == 'empty':
        print(1 if len(d) == 0 else 0)
    elif a == 'front':
        print(d[0] if len(d) != 0 else -1)
    elif a == 'back':
        print(d[-1] if  len(d) != 0 else -1)

백준 알고리즘 10866번 : www.acmicpc.net/problem/10866

문제

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여섯 가지이다.

• push X: 정수 X를 큐에 넣는 연산이다.
• pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 큐에 들어있는 정수의 개수를 출력한다.
• empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
• front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

예제 입력과 출력

알고리즘 분류

큐

정답

import sys

def push(c):
    b.append(c)

def pop():
    if len(b) == 0:
        print(-1)
    else:
        print(b.pop(0))

def size():
    print(len(b))

def empty():
    if len(b) == 0:
        print(1)
    else:
        print(0)
        
def front():
    if len(b) == 0:
        print(-1)
    else:
        print(b[0])

def back():
    if len(b) == 0:
        print(-1)
    else:
        print(b[-1])

n=int(input())
b=[]
    
for i in range(n):
    c=sys.stdin.readline().strip()
    a=c.split(' ')

    if a[0] == 'push':
        push(a[1])
    elif a[0] == 'pop':
        pop()
    elif a[0] == 'size':
        size()
    elif a[0] == 'empty':
        empty()
    elif a[0] == 'front':
        front()
    elif a[0] == 'back':
        back()

백준 알고리즘 10845번 : www.acmicpc.net/problem/10845

문제

여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저의 배치는 다음 조건을 만족한다.

• 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다.
• 각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다.
• 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다.

아래 그림은 위 조건을 만족하는 예를 보여준다. 수평으로 그려진 굵은 실선은 쇠막대기이고, 점은 레이저의 위치, 수직으로 그려진 점선 화살표는 레이저의 발사 방향이다.

이러한 레이저와 쇠막대기의 배치는 다음과 같이 괄호를 이용하여 왼쪽부터 순서대로 표현할 수 있다.

1. 레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 ‘( ) ’ 으로 표현된다. 또한, 모든 ‘( ) ’는 반드시 레이저를 표현한다.
2. 쇠막대기의 왼쪽 끝은 여는 괄호 ‘ ( ’ 로, 오른쪽 끝은 닫힌 괄호 ‘) ’ 로 표현된다.

위 예의 괄호 표현은 그림 위에 주어져 있다.

쇠막대기는 레이저에 의해 몇 개의 조각으로 잘려지는데, 위 예에서 가장 위에 있는 두 개의 쇠막대기는 각각 3개와 2개의 조각으로 잘려지고, 이와 같은 방식으로 주어진 쇠막대기들은 총 17개의 조각으로 잘려진다.

쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 주어졌을 때, 잘려진 쇠막대기 조각의 총 개수를 구하는 프로그램을 작성하시오.

입력

한 줄에 쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 공백없이 주어진다. 괄호 문자의 개수는 최대 100,000이다. 

출력

잘려진 조각의 총 개수를 나타내는 정수를 한 줄에 출력한다.

예제 입력과 출력

알고리즘 분류

스택

정답

a=list(input())
s=[]
b=0

for i in range(len(a)):
    if a[i] == '(':
        s.append('(')
        
    else:
        if a[i-1] == '(':
            s.pop()
            b=b+len(s)
        
        else:
            s.pop()
            b=b+1

print(b)

(이 나오면 스택에 넣습니다.

()이 나오면 현재 스택에 있는 ( 수만큼 정답에 더해줍니다.

)이 나오면 스택의 (를 pop하고 정답에 1을 더해줍니다.

백준 알고리즘 10799번 : www.acmicpc.net/problem/10799

문제

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다.

여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다.

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다. 

출력

출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다. 

예제 입력과 출력

알고리즘 분류

스택

정답

t=int(input())
b=list()

for i in range(t):
    a=input()
    b.clear()

    if len(a) % 2 == 1:
        print('NO')
        continue

    for j in range(len(a)):
        if a[j] == '(':
            b.append('(')
            
        elif a[j] == ')':
            if j== len(a)-1 and len(b)==1:
                print('YES')
                
            if len(b) == 0:
                print('NO')
                break

            if b[-1] == '(':
                b.pop()
            else:
                print('NO')

    if len(b) != 0:
        print('NO')

백준 알고리즘 9012번 : www.acmicpc.net/problem/9012

문제

정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 다섯 가지이다.

• push X: 정수 X를 스택에 넣는 연산이다.
• pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 스택에 들어있는 정수의 개수를 출력한다.
• empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
• top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

예제 입력과 출력

알고리즘 분류

스택

정답

import sys

def push(c):
    b.append(c)

def pop():
    if len(b) == 0:
        print(-1)
    else:
        print(b.pop())

def size():
    print(len(b))

def empty():
    if len(b) == 0:
        print(1)
    else:
        print(0)
        
def top():
    if len(b) == 0:
        print(-1)
    else:
        print(b[-1])

n=int(input())
b=[]
    
for i in range(n):
    c=sys.stdin.readline().strip()
    a=c.split(' ')

    if a[0] == 'push':
        push(a[1])
    elif a[0] == 'pop':
        pop()
    elif a[0] == 'size':
        size()
    elif a[0] == 'empty':
        empty()
    elif a[0] == 'top':
        top()

백준 알고리즘 10828번 : www.acmicpc.net/problem/10828