IT-garden

문제

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

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

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

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

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

입력

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

입력의 종료조건으로 맨 마지막에 점 하나(".")가 들어온다.

출력

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

예제 입력과 출력

알고리즘 분류

문자열 처리 

정답

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

while True:
    a=input()
    st=[]
    if a == '.':
        break

    for i in a:
        if i == '[' or i == '(':
            st.append(i)
        elif i == ']':
            if len(st) != 0 and st[-1] == '[':
                st.pop()
            else:
                st.append(']')
                break
        elif i == ')':
            if len(st) != 0 and st[-1] == '(':
                st.pop()
            else:
                st.append(')')
                break
        
    if len(st) == 0:
        print('yes')
    else:
        print('no')

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

문제

나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다.

재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다.

재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다.

재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 재민이를 도와주자!

입력

첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000)

이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경우 해당 수를 쓴다.

정수가 "0"일 경우에 지울 수 있는 수가 있음을 보장할 수 있다.

출력

재민이가 최종적으로 적어 낸 수의 합을 출력한다. 최종적으로 적어낸 수의 합은 231-1보다 작거나 같은 정수이다.

예제 입력과 출력

정답

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

k=int(input())
st=[]

for i in range(k):
    a=int(input())
    if a == 0:
        st.pop()
    else:
        st.append(a)

print(sum(st))

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

문제

수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.

입력

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

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

출력

첫째 줄에 수열 A의 합이 가장 큰 증가 부분 수열의 합을 출력한다.

예제 입력과 출력

알고리즘 분류

다이나믹 프로그래밍 

정답

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

n=int(input())
a=list(map(int,input().split()))

dp=[1]* n
c=copy.deepcopy(a)

for i in range(n):
    for j in range(i):
        if a[i] > a[j] and dp[i] < dp[j]+1:
            dp[i]= dp[j]+1
            c[i] = max(c[i],c[j]+a[i])
        
print(max(c))

가장 긴 증가하는 부분수열의 알고리즘과 같게 만들고 수열의 합을 기록하는 배열을 하나 추가합니다.
a[i] > a[j] and dp[i] < dp[j]+1 조건이 만족하면 가장 값이 큰 경우를 배열 c에 넣습니다.

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

문제

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.

수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

입력

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

출력

첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

예제 입력과 출력

알고리즘 분류

다이나믹 프로그래밍

정답

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

n=int(input())
a=list(map(int,input().split()))

dp=[1] * n
dp2=[1] * n
for i in range(n): # 앞에서부터 부분 증가수열 개수
    for j in range(i):
        if a[i] > a[j] and dp[i] < dp[j]+1:
            dp[i] = dp[j]+1

for i in range(n-1,-1,-1): # 뒤에서부터 부분 증가수열 개수
    for j in range(n-1,i-1,-1):
        if a[i]> a[j] and dp2[i] < dp2[j]+1:
            dp2[i] = dp2[j]+1

li=[0] * n
for i in range(n):
    li[i]=dp[i]+dp2[i]-1

print(max(li))

가장 긴 부분 수열을 앞에서부터 실행하고 뒤에서부터 실행합니다.
두 배열의 값을 합치고 1을 뺍니다.(자기자신의 길이도 포함하기 때문에)
두 배열의 값을 합친 것 중 가장 큰 값을 출력합니다.

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

문제

수열 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

예제 입력과 출력

알고리즘 분류

다이나믹 프로그래밍 

정답

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

n=int(input())
a=list(map(int,input().split()))

dp=[1]* n

for i in range(n):
    for j in range(i):
        if a[i] > a[j]:
            dp[i]= max(dp[i],dp[j]+1)
            
print(max(dp))

수열 A = {10, 20, 10, 30, 20, 50} 이라면
부분 수열은 {10}, {10, 20}, {10, 20, 30}, {10, 20, 30, 20} 과 같은 것이 있습니다.
이 중 부분수열이 전부 증가하는 요소로 된 것을 증가하는 부분 수열이라 합니다.
가장 긴 증가하는 부분 수열은 부분수열 중 모두 증가하는 요소로 된 길이가 긴 부분수열입니다.

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

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

예제 입력과 출력

알고리즘 분류

그리디 알고리즘 

정답

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

n=int(input())
a=[]

for i in range(n):
    a.append(list(map(int,input().split())))
    
a.sort(key = lambda x: (x[1], x[0]))

c=0 # 회의 개수
t=0 # 회의실 시간

for s,e in a:
    if s >= t:
        t = e
        c += 1

print(c)

리스트 a를 끝나는 시간으로 정렬합니다.
끝나는 시간이 같을 경우 시작하는 시간 순으로 정렬합니다.

3 3
1 3
인 경우 답은 2인데 끝나는 시간으로만 정렬 해놓으면 답이 1로 나오는 것을 방지하기 위해서입니다.

리스트 a에서 처음부터 검사해서 시작시간이 t보다 작거나 같으면 해당 시간에 회의실을 사용한다 생각하고 c를 더해주고 t를 e로 바꿉니다.

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