2018. 08. 14 백준 저지 알고리즘 정리(파이썬)

문제 2156번 - 포도주 시식

링크 - https://www.acmicpc.net/problem/2156

소스코드

import sys

wine = []

num = int(sys.stdin.readline())

for i in range(num):
    wine.append(int(sys.stdin.readline()))


T = [[0 for i in range(2)] for j in range(num+1)]

for i in range(1, num+1):
    T[i][0] = max(T[i-1])
    if i > 1:
        T[i][1] = max(T[i-2][0] + wine[i-1] + wine[i-2], T[i-1][0] + wine[i-1])
    else:
        T[i][1] = wine[i-1]

sys.stdout.write(str(max(T[num])))

코멘트

다이나믹 프로그래밍은 역시 종이에 써서 규칙을 찾아내는게 제일 좋은 방법인 것 같다. 이것 또한 "골랐을 때" 와 "고르지 않았을 때" 두 가지로 분리해서 기록을 한 다음, 2수 앞의 고르지 않았을 때 + 와인 두잔과 1수 앞에서 고르지 않았을 때 와인 한잔의 가치를 비교하면 된다. 여기까진 쉬웠는데.. 후...

문제 11053번 - 가장 긴 증가하는 부분 수열

링크 - https://www.acmicpc.net/problem/11053

소스코드

import sys


num = int(sys.stdin.readline())

T = [1 for i in range(num)]
arr = list(map(int, sys.stdin.readline().rstrip().split()))


for i in range(len(T)):
    T[i] = 1
    for j in range(i, -1, -1):
        if arr[j] < arr[i] and T[j] >= T[i]:
            T[i] = T[j] + 1


sys.stdout.write(str(max(T)))

코멘트

언제나 그렇지만, 보통 알고리즘 테스트에서 틀렸다고 나오면 컴파일러 문제보단 내 문제일 확률이 99.99% 정도 된다. 처음엔 각 수열의 마지막 값만 따로 저장해서 그 값과 단순 비교를 해가며 갱신해가는 방식으로 했었다. "이게 다이나믹 프로그래밍이라고?" 라고까지 생각하면서 돌려봤는데 아니나 다를까 틀렸었다.

반례가 뭘지 몰라서 질문게시판을 좀 찾아보니 처음에 짠 코드로 했다간 10 20 30 11 12 13 14 15 같은 경우를 해결하지 못한다는 것을 알았다. 결국 찾아낸 방법은 i번째 인덱스까지 이어지는 수열의 최대 길이를 지속적으로 갱신하는 방법. 처음엔 코드를 짠 나조차도 "엥 이게 정답이네" 라고 생각이 들 정도로 이해가 안 갔지만, 찬찬히 뜯어보니 알것 같았다. 다이나믹 프로그래밍이 현재 나한테는 제일 취약한 분야인 듯.

문제 11055번 - 가장 큰 증가하는 부분 수열

링크 - https://www.acmicpc.net/problem/11055

소스 코드

import sys


num = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().rstrip().split()))

D = [0 for i in range(num)]

for i in range(num):
    D[i] = arr[i]

for i in range(num):
    for j in range(i, -1, -1):
        if arr[j] < arr[i] and D[j] > D[i] - arr[i]:
            D[i] = D[j] + arr[i]

sys.stdout.write(str(max(D)))

코멘트

위 문제 변형에 불과한데, 멍청하게도 D를 비교할 때 arr의 값도 합산해서 계산해야한다는 것을 간과했다. 덕분에 3번 틀리고 4번만에 성공.

문제 11722번 - 가장 긴 감소하는 부분 수열

링크 - https://www.acmicpc.net/problem/11722

소스 코드

import sys


num = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().rstrip().split()))

D = [1 for i in range(num)]

for i in range(num):
    for j in range(i, -1, -1):
        if arr[j] > arr[i] and D[j] >= D[i]:
            D[i] = D[j] + 1

sys.stdout.write(str(max(D)))

코멘트

딱히 없음. 반복문의 순서만 조심하면 된다. 순서를 바꿔 적으면 다이나믹 프로그래밍이 성립되지 않는다.

문제 11054 - 가장 긴 바이토닉 부분 수열

링크 - https://www.acmicpc.net/problem/11054

소스 코드

import sys


num = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().rstrip().split()))

D = [[1, 1] for i in range(num)]

for i in range(num):
    for j in range(i):
        if arr[j] < arr[i] and D[j][0] >= D[i][0]:
            D[i][0] = D[j][0] + 1
#        if arr[num-1 - j] < arr[num-1 - i] and D[num-1 - j][0] >= D[num-1 - i][0]:
#            D[num-1 - i][1] = D[num-1 - j][1] + 1

for i in range(num-1, -1, -1):
    for j in range(num-1, i-1, -1):
        if arr[j] < arr[i] and D[j][1] >= D[i][1]:
            D[i][1] = D[j][1] + 1

max_value = 0

for i in range(num):
    max_value = max(max_value, sum(D[i]) - 1)

sys.stdout.write(str(max_value))

코멘트

주석 친 부분대로 하면 틀렸다고 나온다. 반복문 두번 적는걸 줄이려고 억지로 우겨넣었더니 뭔가 문제가 있는 듯. 아마 계산을 잘못한 듯 싶으니 나중에 다시 생각해 봐야겠다.

아, 다이나믹 너무 어렵다.