4/28 동적 프로그래밍 2일차

동적 프로그래밍

어제는 동적 프로그래밍을 활용한 난이도가 쉬운 문제를 몇 가지 풀어봤습니다
문제를 풀어보면서 어느 부분에 동적 프로그래밍을 활용해야 하는지 생각해 내는 게 쉽지 않아서 문제를 더 풀어보며 익숙해지자고 생각했습니다

문제 링크

LCS

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
0.1 초 (하단 참고) 256 MB 68999 28056 20587 40.230%

문제
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력
첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력
첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

예제 입력 1
ACAYKP
CAPCAK

예제 출력 1
4

이 문제는 이차원 배열을 이용해 리스트를 만든 뒤, 두 문자열의 길이를 활용해 문자를 비교하고 같은 문자가 나오면 CHACK 리스트에 카운트를 올려 같은 문자가 몇 개가 있는지 체크하고 출력하는 방식을 이용했습니다

import sys
input = sys.stdin.readline

d1 = list(input().strip())
d2 = list(input().strip())
x, y, z = len(d1), len(d2)

# LCS 길이를 저장하기 위한 이차원 리스트를 생성합니다.
# 행은 d2의 문자열을, 열은 d1의 문자열을 나타냅니다.
# 각 요소는 0으로 초기화됩니다.
chack = [[0] * (y+1) for _ in range(x+1)]
# d1과 d2의 각 문자를 비교하면서 LCS 길이를 구합니다.
for i in range(1, x + 1):
    for j in range(1, y + 1):
        # 현재 비교하는 문자가 같다면
        if d1[i - 1] == d2[j - 1]:
            # 이전까지 구한 LCS 길이에 1을 더하여 저장합니다.
            chack[i][j] = chack[i - 1][j - 1] + 1
        # 현재 비교하는 문자가 다르다면    
        else:
            # 현재 비교하는 문자가 다르다면
            chack[i][j] = max(chack[i][j-1], chack[i-1][j])

# 최종적으로, chack[x][y]에 저장된 값이 최장 공통 부분 수열의 길이가 됩니다.
print(chack[x][y])

이 문제는 LCS 2번, LCS 3번 문제가 존재하는데, 2번 같은 경우는 출력이 LCS의 길이에서 문자열을 출력하는 문제를 바뀐 것이라 별로 다르지 않을 거라 생각하고 풀었다가 많이 헤맨 문제입니다..ㅎㅎ
코드는 비슷해서 출력 부분에 추가되는 부분만 올리겠습니다

문제 링크

i = x
j = y
lcs = "" # 빈 수를 선언하고
while i != 0 and j != 0:
    if d1[i - 1] == d2[j - 1]: # 각 리스트의 끝 문자가 같으면
        lcs = d1[i - 1] + lcs #lcs 변수의 끝부터 채움
        i -= 1 # 대각선으로 이동하기 위해 i, j를 -1
        j -= 1
    else: # 같은 값이 아니면
        if chack[i][j - 1] > chack[i - 1][j]: # chack리스트의 -j, -i중에 큰 곳으로 이동
            j -= 1
        else:
            i -= 1

print(lcs)

3번 문제의 경우 1번 문제에서 리스트가 하나 추가된 3차원 배열의 문제라 그렇게 어렵지 않게 풀었습니다.

문제 링크

import sys
input = sys.stdin.readline

d1 = list(input().strip())
d2 = list(input().strip())
d3 = list(input().strip())
x, y, z = len(d1), len(d2), len(d3)

# LCS 길이를 저장하기 위한 이차원 리스트를 생성합니다.
# 행은 d2의 문자열을, 열은 d1의 문자열을 나타냅니다.
# 각 요소는 0으로 초기화됩니다.
chack = [[[0] * (z+1) for _ in range(y + 1)] for _ in range(x + 1)]
# d1과 d2의 각 문자를 비교하면서 LCS 길이를 구합니다.
for i in range(1, x + 1):
    for j in range(1, y + 1):
        for k in range(1, z + 1):
        # 현재 비교하는 문자가 같다면
            if d1[i - 1] == d2[j - 1] == d3[k - 1]:
                # 이전까지 구한 LCS 길이에 1을 더하여 저장합니다.
                chack[i][j][k] = chack[i - 1][j - 1][k - 1] + 1
            # 현재 비교하는 문자가 다르다면    
            else:
                # 현재 비교하는 문자가 다르다면
                chack[i][j][k] = max(chack[i][j][k - 1], chack[i][j - 1][k], chack[i - 1][j][k])

# 최종적으로, chack[x][y]에 저장된 값이 최장 공통 부분 수열의 길이가 됩니다.
print(chack[x][y][z])

위에 3문제와 몇 가지 문제를 더 풀어봤지만, 아직 점화식을 찾는 게 어렵고 방식을 생각해 낸다고 하여도 코드로 옮기는 게 익숙하지 않은 거 같습니다
크래프톤 정글에서는 알고리즘 공부를 1~4주차까지만 공부하는 거로 알고 있어서, 4주차가 끝난 뒤에도 하루에 한 문제 정도 시간으로 꾸준히 공부해봐야겠습니다.
내일은 동적 프로그래밍을 활용한 문제 중 유명한 Fraction Knapsack에 관해 공부해보겠습니다