8.5 문제 : 합친 LIS(Python)

문제 출처 : algospot.com :: JLIS

algospot.com :: JLIS

---

1. 문제를 해결하기 전 알아둬야 하는 이론

(1) 최적 부분 구조

• 최적 부분 구조(Optimal substructure) : 어떤 문제에 대해서 분할 방식에 성립하는 조건으로 각 부분 문제의 최척해를 통해 전체 문제의 최적해를 얻어낼 수 있는 경우 최적 부분 구조가 성립한다고 말한다. 즉, 각 부분 문제의 최적해가 전체의 최적해로 이어지는 경우를 말한다.
• 반대로 작은 부분 문제의 최적해만으로 전체 문제의 최적해를 구할 수 없다면 최적 부분 구조가 존재하지 않는다고 말한다.

(2) 증가하는 부분 수열

• 증가하는 부분 수열(LIS) : 정수 수열 S에서 0개 이상의 숫자를 지우고 남은 수열 중 부분 수열에 포함된 숫자들이 순 증가하면 이 부분 수열을 증가하는 부분 수열이라고 말한다.
• 예를 들어, 수열 S가 '1 3 4 2 4'라면 '1 2 4'는 S의 증가하는 부분 수열이지만 '1 4 4'는 그렇지 못하다.

---

2. 해설 풀이 방법

(1) 문제 분석

• jlis(indexA, indexB) = A[indexA]와 B[indexB]에서 시작하는 합친 증가 부분 수열의 최대 길이
• A[indexA]와 B[indexB]중 더 작은 값이 앞에 온다고 가정한다.
• 다음에 올 수열은 A[indexA+1]과 B[index+1]이후의 수열 중 max(A[indexA], B[indexB])보다 큰 수 중 하나가 된다.
• 만일, A[nextA]를 다음 숫자로 선택했을 경우, 합친 증가하는 부분 수열의 최대 길이는 jlis(indexA, indexB) + 1이 된다.
• B[nextB]를 선택할 수도 있는데 재귀 호출을 통해 nextA를 선택했을 때와 nextB를 선택했을 경우 결과적으로 더 길이가 큰 경우를 선택해야 한다.

(2) 코드

def jlis(indexA, indexB):
    # 이미 계산된 결과가 있는 경우 해당 값 반환
    if cache[indexA + 1][indexB + 1] != -1:
        return cache[indexA + 1][indexB + 1]

    # indexA와 indexB의 최초 값은 -1부터 시작하기 때문에 cache에 접근할 때는 +1을 해줘야 정상적인 인덱스 접근이 가능하다.
    # cache[indexA + 1][indexB + 1] = 2 # JLIS 내부에는 적어도 A[indexA]와 B[indexB]가 들어있기 때문에 2를 초기 값으로 지정(?)
    cache[indexA + 1][indexB + 1] = 0
    
    # indexA와 indexB가 -1인 설정이 있어야 두 배열 내 가장 작은 원소를 기준으로 하는 증가하는 부분 수열을 탐색한다.
    tempA = -int(10e9) if indexA == -1 else a[indexA]
    tempB = -int(10e9) if indexB == -1 else b[indexB]
    maxElement = max(tempA, tempB) # 다음에 들어올 수 있는 원소에 대한 기준을 설정

    # 다음에 들어올 원소를 찾음
    # 기준값보다 큰 원소를 추가하여 증가하는 부분 수열을 재귀적으로 만들어 보고 기존의 값과 비교하여 나오는 최대 길이를 반환한다.
    # 원소가 추가되면 합친 LIS의 길이는 1씩 증가되는 것을 반영한다.
    for nextA in range(indexA + 1, n):
        if maxElement < a[nextA]:
            cache[indexA + 1][indexB + 1] = max(cache[indexA + 1][indexB + 1], jlis(nextA, indexB) + 1)
    
    for nextB in range(indexB + 1, m):
        if maxElement < b[nextB]:
            cache[indexA + 1][indexB + 1] = max(cache[indexA + 1][indexB + 1], jlis(indexA, nextB) + 1)

    return cache[indexA + 1][indexB + 1]

• 먼저 두 배열 A와 B에 대해서 0번 인덱스가 아닌 -1 인덱스가 존재한다고 가정한다.(두 배열의 0번 인덱스부터 순회하면서 검사하기 필요한 과정이다.)
• 만일, -1 인덱스를 가정하지 않는다면 A = [10, 20, 30, 1, 2], B = [10, 20, 30]인 경우 a의 원소 1, 2는 증가하는 부분수열에 고려하지 않는 문제가 발생한다.
• -1 인덱스부터 순회하기 때문에 cache에 접근할 때에는 찾고자 하는 인덱스의 값에 +1을 해야 정상적으로 접근할 수 있다.
• 이로 인해, cache의 크기도 1씩 증가한다.
• 단, 배열의 인덱스는 그 자체로 접근 가능하다.
• 중간 주석 코드에 cache[indexA + 1][indexB + 1] = 2로 초기화 하는 부분이 있는데, jlis함수가 동작할 때 기존에 A[indexA]와 B[indexB]가 들어있으므로 최소 길이는 2부터 시작한다는 것을 의미한다.
• 그러나 이렇게 작성할 경우 마지막 출력 값에 -2를 해야 정상적인 답이 나오기 때문에 애초에 그냥 0으로 초기화하였다.
• 위 점화식에 나와있는 것과 코드를 비교할 때, max(max(jlis(nextA, indexB) + 1, max(jlis(indexA, nextB) + 1) 구현을 반복문 2개를 통해 구현을 했는데 어차피 둘 중 최댓값을 찾는 이유기 때문에 동시에 비교할 필요가 없었음을 유의할 필요가 있었다.

# 문제 입출력
for tc in range(int(input())):
    n, m = map(int, input().split())

    a = list(map(int, input().split()))
    b = list(map(int, input().split()))

    # cache를 통해 두 배열의 각 특정 인덱스에서 나올 수 있는 합친 LIS의 최대 길이를 저장
    # cache 배열의 마지막 부터(재귀 호출할 때 제일 깊숙히 들어가서 서서히 반환하기 때문?) 최적 부분 구조로 인한 최적화 결과가 누적되어 cache의 맨 처음에 저장
    cache = [[-1] * (m + 1) for _ in range(n + 1)]

    print(jlis(-1, -1))

• a와 b 두 배열의 0번 인덱스부터 순차적으로 순회하기 위해 jlis(-1, -1)로 인자를 넘겼음에 유의해야 한다.
• 또한, -1 인덱스의 가정으로 인해 cache의 크기가 배열의 크기에 대해서 1씩 증가했다.

---

3. 후기

  사실 이번 문제는 책의 내용을 보면서 무엇인가 뚜렷하게 이해햐지 못한 부분이 많다. 이 부분을 몇 번 다시 보긴 했지만 결국 '그냥 그런갑다'하고 넘어가게 되었다... 매번 하는 이야기지만 문제 해결을 위한 설계 과정을 떠올리기가 정말 쉽지가 않다. 그런데 보통의 경우 설계된 과정을 보면 이해가 되었는데 이 문제는 점화식을 보고도 왜 이렇게 할까 라는 의문이 많이 들었다.

  증가하는 부분 수열의 경우 다른 코딩테스트 책에서 봤었다. 그러나 다른 책에서는 실제 증가하는 부분 수열을 구하는 문제였고 이 문제의 경우 증가하는 부분 수열의 최대 길이를 구하는 차이점이 있었다. 그리고 최대 길이를 구하기 위해서 일종의 -1 인덱스를 처음 접했는데 이 부분을 이해하기 위해서 테스트 코드를 만들어 실험해서 그 이유를 알 수 있었다. 그러나 남에게 설명해보라 하면 내 스스로도 어렴풋이 이해햔 것이기 때문에 남들이 듣기에 납득이 되지 않을 거 같아 구체적으로 설명은 하지 않았다. 아마 후일에 몇 번 더 복습하다 보면 그래도 이해할 수 있을 것이라 자신한다.

---

github :  Algorithmic_Problem_Soving_Strategies/q2_0.py at main · LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies (github.com)

LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies