IT-garden

문제

KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다.

예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 모든 탑에서는 주어진 탑 순서의 반대 방향(왼쪽 방향)으로 동시에 레이저 신호를 발사한다고 하자. 그러면, 높이가 4인 다섯 번째 탑에서 발사한 레이저 신호는 높이가 7인 네 번째 탑이 수신을 하고, 높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신을 한다. 높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 어떤 탑에서도 수신을 하지 못한다.

탑들의 개수 N과 탑들의 높이가 주어질 때, 각각의 탑에서 발사한 레이저 신호를 어느 탑에서 수신하는지를 알아내는 프로그램을 작성하라.

입력

첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 이상 100,000,000 이하의 정수이다.

출력

첫째 줄에 주어진 탑들의 순서대로 각각의 탑들에서 발사한 레이저 신호를 수신한 탑들의 번호를 하나의 빈칸을 사이에 두고 출력한다. 만약 레이저 신호를 수신하는 탑이 존재하지 않으면 0을 출력한다.

예제 입력과 출력

알고리즘 분류

스택

정답

from collections import deque

n=int(input())
a=list(map(int,input().split()))
li=deque()
r=[]

for i in range(n):
    while li:
        if li[-1][1] > a[i]:
            r.append(li[-1][0] + 1)
            break
        li.pop()

    if not li:
        r.append(0)

    li.append([i, a[i]])
    
for i in range(n):
    print(r[i], end=' ')

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

문제

4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다.

1. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다.
2. 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다.
3. X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다.

예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다.

1. ‘()’ 인 괄호열의 값은 2이다.
2. ‘[]’ 인 괄호열의 값은 3이다.
3. ‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.
4. ‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.
5. 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.

예를 들어 ‘(()[[]])([])’ 의 괄호값을 구해보자. ‘()[[]]’ 의 괄호값이 2 + 3×3=11 이므로 ‘(()[[ ]])’의 괄호값은 2×11=22 이다. 그리고 ‘([])’의 값은 2×3=6 이므로 전체 괄호열의 값은 22 + 6 = 28 이다.

여러분이 풀어야 할 문제는 주어진 괄호열을 읽고 그 괄호값을 앞에서 정의한대로 계산하여 출력하는 것이다.

입력

첫째 줄에 괄호열을 나타내는 문자열(스트링)이 주어진다. 단 그 길이는 1 이상, 30 이하이다.

출력

첫째 줄에 그 괄호열의 값을 나타내는 정수를 출력한다. 만일 입력이 올바르지 못한 괄호열이면 반드시 0을 출력해야 한다. 

예제 입력과 출력

알고리즘 분류

스택

정답

s = list(input())
stack = []
c = 0

for i in s:
    if i == ')':
        t = 0
        while len(stack) != 0:
            top = stack.pop()
            if top == '(':
                if t == 0:
                    stack.append(2)
                else:
                    stack.append(2 * t)
                break
            elif top == '[':
                print(0)
                exit(0)
            else:
                t = t + int(top)
 
    elif i == ']':
        t = 0
        while len(stack) != 0:
            top = stack.pop()
            if top == '[':
                if t == 0:
                    stack.append(3)
                else:
                    stack.append(3 * t)
                break
            elif top == '(':
                print(0)
                exit(0)
            else:
                t = t + int(top)
 
    else:
        stack.append(i)
 
for i in stack:
    if i == '(' or i == '[':
        print(0)
        exit(0)
    else:
        c += i
 
print(c)

1. '('와 '[' 가 들어오면 스택에 넣습니다.
2. ')'와 ']'인 경우를 나눠 생각합니다.
3. 각 경우 스택이 1 이상인 경우 스택의 맨 위 요소를 뽑아 '('나 '['인지 확인합니다.
바로 맨 위가 '('나 '['이면 2나 3을 넣고 앞에 숫자들이 있는 경우 그 숫자들의 합을 구해 합에 2나 3을 곱합니다.
4. 각 경우 짝이 맞지 않는 괄호가 오면 0을 출력하고 프로그램을 종료합니다.
5. 문자열에 대한 for문이 끝나고 괄호가 남아있으면 0을 출력하고 그렇지 않으면 숫자들의 합을 구해 출력합니다.

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

문제

상근이의 상상의 친구 외계인은 손가락을 수십억개 가지고 있다. 어느 날 외계인은 기타가 치고 싶었고, 인터넷에서 간단한 멜로디를 검색했다. 이제 이 기타를 치려고 한다.

보통 기타는 1번 줄부터 6번 줄까지 총 6개의 줄이 있고, 각 줄은 P개의 프렛으로 나누어져 있다. 프렛의 번호도 1번부터 P번까지 나누어져 있다.

멜로디는 음의 연속이고, 각 음은 줄에서 해당하는 프렛을 누르고 줄을 튕기면 연주할 수 있다. 예를 들면, 4번 줄의 8번 프렛을 누르고 튕길 수 있다. 만약, 어떤 줄의 프렛을 여러 개 누르고 있다면, 가장 높은 프렛의 음이 발생한다.

예를 들어, 3번 줄의 5번 프렛을 이미 누르고 있다고 하자. 이때, 7번 프렛을 누른 음을 연주하려면, 5번 프렛을 누르는 손을 떼지 않고 다른 손가락으로 7번 프렛을 누르고 줄을 튕기면 된다. 여기서 2번 프렛의 음을 연주하려고 한다면, 5번과 7번을 누르던 손가락을 뗀 다음에 2번 프렛을 누르고 연주해야 한다.

이렇게 손가락으로 프렛을 한 번 누르거나 떼는 것을 손가락을 한 번 움직였다고 한다. 어떤 멜로디가 주어졌을 때, 손가락의 가장 적게 움직이는 회수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 멜로디에 포함되어 있는 음의 수 N과 한 줄에 있는 프렛의 수 P가 주어진다. (N ≤ 500,000, 2 ≤ P ≤ 300,000)

다음 N개 줄에는 멜로디의 한 음을 나타내는 두 정수가 주어진다. 첫 번째 정수는 줄의 번호이고 두 번째 정수는 그 줄에서 눌러야 하는 프렛의 번호이다. 입력으로 주어진 음의 순서대로 기타를 연주해야 한다.

출력

첫째 줄에 멜로디를 연주하는데 필요한 최소 손가락 움직임을 출력한다.

예제 입력과 출력

알고리즘 분류

스택

정답

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

n, p=map(int,input().split())
a=[list(map(int,input().split())) for i in range(n)]

c=0
ch=[[] for i in range(7)]

for i,j in a:
    if len(ch[i]) == 0:
        ch[i].append(j)
        c +=1
        
    else:
        if j > ch[i][-1]:
            ch[i].append(j)
            c += 1
        elif j == ch[i][-1]: # 이미 있는 경우
            continue
        else: 
            while len(ch[i]) != 0 and j < ch[i][-1]:
                ch[i].pop()
                c += 1
            if len(ch[i]) != 0 and ch[i][-1] == j:
                continue
            ch[i].append(j)
            c += 1

print(c)

1. 기타의 각 줄에 대해 스택을 사용합니다.
2. i 줄의 스택이 비어있으면 값을 추가합니다.
3. i 줄의 스택이 비어있지 않은 경우 스택안의 값과 j 값을 비교합니다.
3-1. j가 스택의 값보다 더 큰 경우 스택에 값을 추가합니다.
3-2. j와 스택의 값이 같은 경우 추가사항 없이 넘어갑니다.
3-3. j가 스택의 값보다 작은 경우 스택의 끝에서부터 j보다 큰 값들을 모두 삭제합니다.
큰 값들을 모두 삭제하고 스택의 값과 j의 값이 같으면 추가사항 없이 넘어가고 그렇지 않으면
스택에 j를 추가합니다.
4. 각 과정마다 손가락 움직인 횟수를 더해 출력합니다.

예제 설명
1 5 : 1 스택의 5 누르기
2 3 : 2 스택의 3 누르기
2 5 : 2 스택의 5 누르기
2 7 : 2 스택의 7 누르기
2 4 : 2 스택의 7 떼기, 2 스택의 5 떼기, 2 스택의 4 누르기
1 5 : 넘어가기(1 스택에 5 있어서)
1 3 : 1 스택의 5 떼기, 1 스택의 3 떼기

따라서 필요한 손가락 움직임의 최소 횟수는 9입니다.

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

문제

이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 깨고 말았다. 안타깝게도 자는 동안 키보드가 잘못 눌려서 보고서의 모든 글자가 A와 B로 바뀌어 버렸다! 그래서 평석이는 보고서 작성을 때려치우고 보고서에서 '좋은 단어'나 세보기로 마음 먹었다.

평석이는 단어 위로 아치형 곡선을 그어 같은 글자끼리(A는 A끼리, B는 B끼리) 쌍을 짓기로 하였다. 만약 선끼리 교차하지 않으면서 각 글자를 정확히 한 개의 다른 위치에 있는 같은 글자와 짝 지을수 있다면, 그 단어는 '좋은 단어'이다. 평석이가 '좋은 단어' 개수를 세는 것을 도와주자.

입력

첫째 줄에 단어의 수 N이 주어진다. (1 ≤ N ≤ 100)

다음 N개 줄에는 A와 B로만 이루어진 단어가 한 줄에 하나씩 주어진다. 단어의 길이는 2와 100,000사이이며, 모든 단어 길이의 합은 1,000,000을 넘지 않는다.

출력

첫째 줄에 좋은 단어의 수를 출력한다.

예제 입력과 출력

알고리즘 분류

스택
문자열 처리

정답

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

n=int(input())
a=[list(input()) for i in range(n)]
c= 0
for i in a:
    li=deque()
    for j in i:
        if len(li) == 0:
            li.append(j)
        elif len(li) >= 1:
            if li[-1] == j:
                li.pop()
            else:
                li.append(j)
    
    if len(li) == 0:
        c +=1
        
print(c)

1. 첫번째 알파벳을 덱 li에 넣습니다.
2. 스택 맨 위의 알파벳과 넣을 알파벳이 같으면 pop을 하고 같지 않으면 push 합니다.
3. 덱의 길이가 0이면 좋은 단어 개수를 하나 올려줍니다.
4. 좋은 단어 개수를 출력합니다.

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

문제

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

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

입력

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

출력

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

예제 입력과 출력

알고리즘 분류

스택

정답

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

def push(i):
    s.append(i)
    li.append('+')
    
def popp():
    li.append('-')
    s.pop()

n=int(input())
a=[int(input()) for i in range(n)]
s=deque()
li=deque()
p='Y'
for i in range(1,a[0]+1):
    push(i)

m=max(s)
popp()

for i in range(1,n):
    if a[i] < a[i-1]:
        if s[-1] == a[i]:
            popp()
        else:
            p='NO'
            break
        
    elif a[i] > a[i-1]:
        for j in range(m+1,a[i]+1):
            push(j)

        m=max(s)
        popp()

if p == 'NO':
    print(p)
else:
    for i in li:
        print(i)

1. 첫번째 수까지 push하고 pop을 합니다.
2. 두번째부터 n번째까지 스택을 이용해 수열을 만들 수 있는지 확인합니다.
3. 리스트의 앞자리와 뒷자리의 수를 비교합니다.
3-1. 앞자리가 더 큰 경우 스택의 마지막 값과 뒷자리의 수가 같으면 pop을 합니다.
3-2. 뒷자리가 더 큰 경우 스택에 해당 수까지 push 합니다.
4. 각 단계마다 리스트 li에 push에는 '+'를, pop에는 '-'를 추가하여 출력합니다.

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

문제

n×n 바둑판 모양으로 총 n2개의 방이 있다. 일부분은 검은 방이고 나머지는 모두 흰 방이다. 검은 방은 사면이 벽으로 싸여 있어 들어갈 수 없다. 서로 붙어 있는 두 개의 흰 방 사이에는 문이 있어서 지나다닐 수 있다. 윗줄 맨 왼쪽 방은 시작방으로서 항상 흰 방이고, 아랫줄 맨 오른쪽 방은 끝방으로서 역시 흰 방이다.

시작방에서 출발하여 길을 찾아서 끝방으로 가는 것이 목적인데, 아래 그림의 경우에는 시작방에서 끝 방으로 갈 수가 없다. 부득이 검은 방 몇 개를 흰 방으로 바꾸어야 하는데 되도록 적은 수의 방의 색을 바꾸고 싶다.

아래 그림은 n=8인 경우의 한 예이다.

위 그림에서는 두 개의 검은 방(예를 들어 (4,4)의 방과 (7,8)의 방)을 흰 방으로 바꾸면, 시작방에서 끝방으로 갈 수 있지만, 어느 검은 방 하나만을 흰 방으로 바꾸어서는 불가능하다. 검은 방에서 흰 방으로 바꾸어야 할 최소의 수를 구하는 프로그램을 작성하시오.

단, 검은 방을 하나도 흰방으로 바꾸지 않아도 되는 경우는 0이 답이다.

입력

첫 줄에는 한 줄에 들어가는 방의 수 n(1≤n≤50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다.

출력

첫 줄에 흰 방으로 바꾸어야 할 최소의 검은 방의 수를 출력한다.

예제 입력과 출력

정답

from collections import deque

n=int(input())
a=[list(map(int,input())) for i in range(n)]
ch=[[-1] * n for i in range(n)]

dx=[-1,0,1,0]
dy=[0,1,0,-1]

def bfs():
    de=deque()
    de.append([0,0])
    ch[0][0]=0 

    while de:
        x,y=de.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < n:
                if ch[nx][ny] == -1:
                    if a[nx][ny] == 0:
                        ch[nx][ny]= ch[x][y] + 1
                        de.append([nx,ny])
                    else:
                        ch[nx][ny]= ch[x][y]
                        de.appendleft([nx,ny])
                       
bfs()
print(ch[n-1][n-1])

흰방에 도착하면 이동거리는 이전과 같고 먼저 흰방을 방문하기 위해 appendleft를 사용합니다.
검은방에 도착하면 이동거리는 이전에서 +1해주고 append를 사용합니다.

백준 1261 알고스팟과 똑같은 문제입니다.

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