1031-TIL(knapsack, LCS)

knapsack

import sys
input = sys.stdin.readline

num_stuffs, max_weight = map(int, input().split())
stuffs = []

for i in range(num_stuffs):
    weight, value = map(int, input().split())
    stuffs.append((weight, value))

def find_max(cursor, current_weight, current_value):
    global max_wieght
    if current_weight > max_weight:
        return float("-inf")
    
    if current_weight == max_weight:
        return current_value
    
    if cursor >= num_stuffs:
        return float("-inf")
    
    _max = -1
    _max = max(find_max(cursor + 1,
                        current_weight + stuffs[cursor][0], 
                        current_value + stuffs[cursor][1]), 
                find_max(cursor + 1, current_weight, current_value))
    
    return _max

def find_max2(cursor, current_weight):
    global max_wieght
    if current_weight > max_weight:
        return float("-inf")
    
    if current_weight == max_weight:
        return 0
    
    if cursor >= num_stuffs:
        return float("-inf")
    
    _max = -1
    _max = max(find_max2(cursor + 1,
                        current_weight + stuffs[cursor][0]) + stuffs[cursor][1], 
                find_max2(cursor + 1, current_weight))
    
    return _max

dp = [[-1 for _ in range(max_weight)] for _ in range(num_stuffs)]
def find_max3(cursor, current_weight):
    global max_wieght
    if current_weight > max_weight:
        return float("-inf")
    
    if current_weight == max_weight:
        return 0
    
    if cursor == num_stuffs:
        return 0 
    
    if dp[cursor][current_weight] != -1: # 이미 계산한 값은 계산 안하게 바로 리턴
        return dp[cursor][current_weight]
    
    _max = -1
    _max = max(find_max3(cursor + 1,
                        current_weight + stuffs[cursor][0]) + stuffs[cursor][1], 
                find_max3(cursor + 1, current_weight))
    
    dp[cursor][current_weight] = _max
    return dp[cursor][current_weight]
print(find_max3(0, 0))

LCS

import sys

string_a = sys.stdin.readline().rstrip().upper()
string_b = sys.stdin.readline().rstrip().upper()

len_a = len(string_a)
len_b = len(string_b)

dp = [[0] * (len_b+1) for _ in range(len_a+1)]


def lcs(i,j):
    for i in range(1, len_a + 1):
        for j in range(1, len_b +1):
            if string_a[i-1] == string_b[j-1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[i][j]     
print(lcs((len_a-1), (len_b-1)))

마지막에
return dp[i][j]
print(lcs((len_a-1), (len_b-1)))

부분에서 이렇게 안하고
print(dp[i-1][j-1])

이렇게 하는 방법도 있는데 이렇게 하는 것보다 디피 테이블에 저장을 하고 나서 그 데이터를 가져오는 방식이 더 낫다고 생각한다. 왜냐하면 함수 자체가 lcs 라면 마지막에 업데이트 된 lcs 정보를 리턴하는게 맞는것 같다.

외판원 순회