LCS(Longest Common Subsequence), Knapsack

LCS(Longest Common Subsequence, 최장 공통 부분 수열)는 두 시퀀스(예: 문자열, 리스트 등)에서 순서를 변경하지 않고 양쪽 시퀀스에서 모두 찾아낼 수 있는 가장 긴 부분 수열을 찾는 문제다. 이 문제는 다이나믹 프로그래밍(dynamic programming) 기법을 이용하여 효율적으로 해결할 수 있다.

 

LCS 문제를 해결하는 기본 아이디어는 두 시퀀스의 각 위치에 대해, 해당 위치까지의 최장 공통 부분 수열의 길이를 저장하는 2차원 배열(또는 테이블)을 만드는 것이다. 이 배열을 dp라 할 때, dp[i][j]는 첫 번째 시퀀스의 i번째 원소와 두 번째 시퀀스의 j번째 원소까지 고려했을 때의 최장 공통 부분 수열의 길이를 나타낸다.

 

dp 배열의 모든 값을 0으로 초기화한다. 여기서 dp[0][j]와 dp[i][0]은 첫 번째 시퀀스 또는 두 번째 시퀀스의 원소가 하나도 없을 때를 의미하므로, 공통 부분 수열의 길이는 0이다.

 

• 만약 현재 위치의 원소가 같다면, dp[i][j] = dp[i-1][j-1] + 1로 설정한다. 이는 현재 원소가 공통 부분 수열에 포함되므로, 이전 위치까지의 최장 길이에 1을 추가한 것이다.
• 만약 현재 위치의 원소가 다르다면, dp[i][j] = max(dp[i-1][j], dp[i][j-1])로 설정한다. 이는 현재 원소를 제외하고, 이전 위치에서의 최장 공통 부분 수열의 길이를 가져오는 것이다.

dp 배열의 마지막 원소인 dp[n][m]이 두 시퀀스의 최장 공통 부분 수열의 길이를 나타낸다. 여기서 n과 m은 각각 두 시퀀스의 길이다.

LCS 문제는 컴퓨터 과학뿐만 아니라, 생물 정보학에서 유전자 시퀀스 비교나 텍스트 편집 거리 계산 등 다양한 분야에서 응용된다.

def lcs(X, Y):
    # 두 문자열의 길이 계산
    m, n = len(X), len(Y)

    # dp 테이블 초기화 (m+1)x(n+1) 크기
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # dp 테이블 채우기
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i-1] == Y[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[m][n]  # 테이블의 마지막 값이 최장 공통 부분 수열의 길이

X = "GXTXAYB"
Y = "AGGTAB"
print(f"LCS length: {lcs(X, Y)}")

#출력
#LCS length: 4
#(GTAB로 4이기 때문)

 

Knapsack 문제는 조합 최적화(Combinatorial Optimization)의 대표적인 예로, 특정한 제약 조건 하에서 최적의 해를 찾는 문제다. 이 문제는 배낭에 넣을 수 있는 물건들이 주어졌을 때, 물건의 무게 제한을 초과하지 않으면서 가치의 합을 최대화하는 방법을 찾는 것이다. Knapsack 문제에는 여러 변형이 있지만, 가장 널리 알려진 형태는 0-1 Knapsack 문제와 Fractional Knapsack(분할 가능 배낭) 문제다.

 

0-1 배낭 문제에서는 각 물건을 통째로 넣거나 아예 넣지 않아야 한다.(분할 불가)

• n개의 아이템이 있으며, 각 아이템은 가치(value)와 무게(weight)를 가진다.
• 최대 무게가 W인 배낭이 있다.
• 배낭의 무게 한도를 초과하지 않으면서 가치의 합을 최대화하려면 어떤 아이템을 배낭에 넣어야 하는가?

분할 가능 배낭 문제에서는 물건을 부분적으로 나누어 넣을 수 있다. 이는 그리디 알고리즘을 사용해 해결할 수 있으며, 아이템의 가치 대비 무게(가치/무게 비율)를 기준으로 선택한다.

 

0-1 배낭 문제는 다이나믹 프로그래밍을 사용해 효율적으로 해결할 수 있다. 핵심 아이디어는 두 가지 선택지가 있을 때 최적의 선택을 결정하는 것이다: 아이템을 배낭에 추가하거나 추가하지 않는다. 다이나믹 프로그래밍 접근 방식에서는 이러한 결정을 기반으로 값을 메모하여, 반복 계산을 줄인다.

1. (n+1)x(W+1) 크기의 테이블을 0으로 초기화한다. 여기서 n은 아이템 수, W는 배낭의 최대 무게다.
2. 각 아이템에 대해, 가능한 모든 무게에 대해 최대 가치를 계산하여 dp 테이블을 채운다.
3. dp 테이블의 마지막 값(dp[n][W])은 주어진 무게 한도에서 얻을 수 있는 최대 가치다.

예를 들어, 배낭의 최대 무게가 50이고, 다음 3개의 아이템이 있을 때의 최적의 해를 찾는다고 가정하자.

• 아이템 1: 무게 10, 가치 60
• 아이템 2: 무게 20, 가치 100
• 아이템 3: 무게 30, 가치 120

0-1 배낭 문제의 해결책은 이 아이템들 중에서 선택하여 최대 가치를 얻는 조합을 찾는 것이다.

Knapsack 문제는 그 해결 방법이 명확하고, 다양한 실생활 문제에 응용될 수 있는 대표적인 최적화 문제 중 하나다.

def knapsack(W, wt, val, n):
    """
    :param W: int 배낭의 최대 무게
    :param wt: list 아이템의 무게 리스트
    :param val: list 아이템의 가치 리스트
    :param n: int 아이템의 총 개수
    :return: int 최대 가치
    """
    # 기본적으로 0으로 초기화된 DP 테이블 생성
    K = [[0 for x in range(W + 1)] for x in range(n + 1)]
    
    # DP 테이블을 채워나감
    for i in range(n + 1):
        for w in range(W + 1):
            if i == 0 or w == 0:
                K[i][w] = 0
            elif wt[i-1] <= w:
                # i번째 아이템을 포함시킬 경우와 포함시키지 않을 경우 중 최대 가치 선택
                K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w])
            else:
                # i번째 아이템을 포함시킬 수 없는 경우
                K[i][w] = K[i-1][w]

    return K[n][W]  # 최대 가치 반환

# 예시 데이터
val = [60, 100, 120]  # 아이템의 가치
wt = [10, 20, 30]  # 아이템의 무게
W = 50  # 배낭의 최대 무게
n = len(val)  # 아이템 개수

# 최대 가치 계산
print(knapsack(W, wt, val, n))

# 출력
# 220