IT-garden

문제

수열 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

문제

월드컵 축구의 응원을 위한 모임에서 회장을 선출하려고 한다. 이 모임은 만들어진지 얼마 되지 않았기 때문에 회원 사이에 서로 모르는 사람도 있지만, 몇 사람을 통하면 모두가 서로 알 수 있다. 각 회원은 다른 회원들과 가까운 정도에 따라 점수를 받게 된다.

예를 들어 어느 회원이 다른 모든 회원과 친구이면, 이 회원의 점수는 1점이다. 어느 회원의 점수가 2점이면, 다른 모든 회원이 친구이거나 친구의 친구임을 말한다. 또한 어느 회원의 점수가 3점이면, 다른 모든 회원이 친구이거나, 친구의 친구이거나, 친구의 친구의 친구임을 말한다.

4점, 5점 등은 같은 방법으로 정해진다. 각 회원의 점수를 정할 때 주의할 점은 어떤 두 회원이 친구사이이면서 동시에 친구의 친구사이이면, 이 두사람은 친구사이라고 본다.

회장은 회원들 중에서 점수가 가장 작은 사람이 된다. 회장의 점수와 회장이 될 수 있는 모든 사람을 찾는 프로그램을 작성하시오.

입력

입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 회원의 수만큼 붙어 있다. 마지막 줄에는 -1이 두 개 들어있다.

출력

첫째 줄에는 회장 후보의 점수와 후보의 수를 출력하고, 두 번째 줄에는 회장 후보를 오름차순으로 모두 출력한다.

예제 입력과 출력

알고리즘 분류

플로이드 와샬 알고리즘 

정답

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

INF=sys.maxsize

n=int(input())
a=[[INF]*(n+1) for i in range(n+1)]

while True:
    s1,s2=map(int,input().split())
    
    if s1 == -1 and s2 == -1:
        break
    a[s1][s2] = 1
    a[s2][s1] = 1

for i in range(1,n+1): # 자기자신의 경로
    a[i][i] = 0

for k in range(1,n+1): # 거치는 거
    for i in range(1,n+1):
        for j in range(1,n+1):
            if a[i][j] == 1 or a[i][j] == 0:
                continue
            elif a[i][j] > a[i][k] + a[k][j]:
                a[i][j] = a[i][k] + a[k][j]     

r=[]
for i in range(1,n+1):
    r.append(max(a[i][1:]))

m=min(r)
print(m, r.count(m))
for i,v in enumerate(r):
    if v == m:
        print(i+1,end=' ')

전체 배열을 INF로 하고 자기자신으로 가는 경로는 0으로 설정합니다.
플로이드 와샬 알고리즘을 적용하고 각 행에서 가장 큰 값을 각 회원의 점수로 매깁니다.
점수들 중 가장 작은 값을 회장 후보의 점수로 삼고 후보의 수와 회장 후보를 출력합니다.

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

문제

효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오.

예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.

입력

첫째 줄에 포도주 잔의 개수 n이 주어진다. (1≤n≤10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.

출력

첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다.

예제 입력과 출력

알고리즘 분류

다이나믹 프로그래밍

정답

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

n=int(input())
a=[0]*(n+1)

for i in range(1,n+1):
    a[i]=int(input())

dp=[0]*(n+1)
dp[1]=a[1]

if n == 2:
    dp[2]=dp[1]+a[2]
elif n > 2:
    dp[2]=dp[1]+a[2]
    for i in range(3,n+1):
        dp[i]=max(dp[i-3]+a[i-1], dp[i-2]) + a[i]
        dp[i]=max(dp[i-1], dp[i])

print(dp[n])

dp[i-3] + a[i-1] + a[i] : 전 와인 먹고 다음에 와인 먹기
dp[i-2] + a[i] : 전전 와인 먹고 한 칸 뛰고 다음 와인 먹기

max(dp[i-1], dp[i]): 현재의 와인 먹을지 말지 결정(와인을 무조건 마셔야 하는 것은 아니기 때문에!)

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