9.7 문제 : k번째 최대 증가 부분 수열(Python)

문제 출처 : algospot.com :: KLIS

algospot.com :: KLIS

---

1. 문제 분석

• 이전의 예제와 문제(8.4절 참고)들을 통해서 최대 증가 부분 수열 중 가장 긴 것을 찾아낸 경험이 있다.
• 이를 바탕으로 위 문제를 해결하기 위해서는 다음의 과정을 거쳐야 한다.

 

• 1. 바탕이 되는 최적화 문제를 푼다.
• 2. 최적화 문제의 최적해를 세는 문제를 푼다.
• 3. 답의 수를 기반으로 답안을 재구성한다.

---

2. LIS의 개수 세기

(1) 함수 설계하기

• 수열의 i번째에서 시작하는 LIS의 수를 반환하는 경우를 생각해보자.
• 예를 들어, 전체 수열이 S = [1, 4, 3, 2]인 경우 0번 인덱스의 값인 1에서 시작하는 LIS는 [1, 4], [1, 3], [1, 2]로 총 3개다.
• 그러나 1, 2, 3번 인덱스에서 부터 LIS를 만들 경우 LIS의 길이는 모두 1인 LIS를 1개씩만 갖는다.
• (i < j)이고 어떤 수열 S에 대해서 S[i] < S[j] 인 경우 i번째 위치에서 시작하는 LIS의 수를 반환하는 함수 count( i )는 다음과 같이 정의할 수 있다.

next(i)는 i번째 숫자 뒤에 올 수 있는 인덱스의 목록

• 그리고 한 가지, i번 인덱스에서 부터 만든 LIS의 길이는 j번 인덱스에서 부터 만든 LIS의 길이에 1을 더한 것과 같은 조건이 성립해야 한다.

(2) 코드 구현

MAX = int(2e9)+1

# S[start]에서 시작하는 증가 부분 수열 중 최대 길이를 반환한다.
def lis(start):
    # 메모이제이션
    # start + 1을 사용하는 이유는 S[-1]이 있다고 가정하고 0번 인덱스부터 cache에 담기 위해(?)
    if cacheLen[start + 1] != -1:
        return cacheLen[start + 1]

    cacheLen[start + 1] = 1 # LIS에 항상 S[start + 1]는 있기 때문에 길이는 최하 1

    for next in range(start+1, n):
        if start == -1 or S[start] < S[next]:
            cacheLen[start + 1] = max(cacheLen[start + 1], lis(next) + 1)

    return cacheLen[start + 1]

# S[start]에서 시작하는 최대 증가 부분 수열의 수를 반환
def count(start):
    # 기저 사례 : LIS의 길이가 1인 경우
    if lis(start) == 1:
        return 1
    
    # 메모이제이션
    if cacheCnt[start + 1] != -1:
        return cacheCnt[start + 1]

    cacheCnt[start + 1] = 0
    for next in range(start+1, n):
        if (start == -1 or S[start] < S[next]) and (lis(start) == lis(next) + 1):
            cacheCnt[start + 1] = min(MAX, cacheCnt[start + 1] + count(next))

    return cacheCnt[start + 1]

• 기존의 LIS 문제들 처럼 S[-1]의 존재를 가정하고 시작한다.(특정 인덱스에서 시작하는 LIS를 찾는게 아니라 전체 수열에서 LIS를 찾기 위함)
• lis( ) 함수의 경우 i번째 인덱스에서 시작할 때의 LIS의 최대 길이를 구한다. -> 바탕이 되는 최적해를 푼다.
• count( ) 함수의 경우 LIS의 i번째 인덱스에서 시작할 때의 LIS의 개수를 구한다. -> 최적화 문제의 최적해를 세는 문제를 푼다.
• 길이와 개수를 구하는 차이가 있지만 두 함수의 구조가 상당히 유사함을 알 수 있다.
• 위에서 설명한 'i번 인덱스에서 부터 만든 LIS의 길이는 j번 인덱스에서 부터 만든 LIS의 길이에 1을 더한 것과 같다.'는 조건이 count( ) 함수 내의 조건문에서 lis(start) == lis(next) + 1 으로 표현되었다.

---

3. LIS의 재구성

(1) 함수 설계하기

• 맨 처음 설명한 3가지 과정 중 2가지 과정을 해결했으니 이제 3번째 과정을 해결해야 할 차례이다.
• k번째 답을 찾기 위해 직전의 9.6 예제와 마찬가지로 skip = k-1로 초기화 하고 시작한다.

 

• S = [5, 1, 6, 4, 3, 2, 8, 7], k=6을 예를 들어 설명하면 다음과 같다.
• S에서 만들 수 있는 최대 길이의 LIS는 길이가 3으로 각각 S[0]과 S[1]에서 시작했을 때 만들 수 있다.
• 그리고 S[0]에서 부터 만들 수 있는 길이가 3인 LIS의 수는 2개, S[1]에서 만들 수 있는 길이가 3인 LIS의 수는 8개가 존재한다.
• 이렇게 총 10개의 길이가 3인 LIS들을 사전순으로 정렬하면 S[0]=5 > S[1]=1 이므로 S[1]에서 시작하는 LIS가 앞에 위치한다.
• skip = k-1에 따라 skip = 5이고, S[1]에서 만들 수 있는 LIS의 수는 8개이기 때문에 우리가 찾는 k번째 LIS는 S[1]에서 시작하는 LIS 중에 존재한다.
• S[1]에서 시작하는 LIS는 모두 1이기 때문에 우리는 LIS의 두 번째 부터의 값을 확인하면서 k(=6)번째를 찾아야 한다.

 

• 이 과정을 프로그램으로 옮기면 다음과 같이 4가지 동작을 하는 코드로 구현할 수 있다.
• 1. S[start]를 LIS에 추가 : S[start]에서 시작하는 LIS의 첫 번째 원소는 항상 S[start]
• 2. LIS에서 S[start] 다음에 올 수 있는 숫자들의 목록을 작성 : S[start] 뒤에 위치(=next)하면서 S[start]보다 크고 lis(start) = lis(next) + 1를 만족하는 모든 S[next]를 찾아 이를 숫자가 증가하는 순서대로 정렬하여 저장한다. (그냥 저장하는 것이 아니라 Python의 경우 튜플 자료형을 사용하여 저장한다.)
• 3. 목록 중 k번째 LIS에 포함되는 숫자를 찾기 : 정렬한 숫자들을 순서대로 검토하면서 이 숫자에서 시작하는 LIS의 수가 skip보다 작은지 확인한다. 답의 수가 skip을 초과한다면 k번째 LIS가 이 숫자를 사용한다는 의미다. 아니라면 skip에서 해당 숫자가 포함된 LIS의 수를 빼면 된다.
• 4. LIS의 나머지 부분 계산하기 : k번째 LIS는 정해진 숫자에서 시작하는 LIS 중 skip개를 빼고 가장 앞에 있으므로 이를 재귀 호출을 통해 해결한다.

(2) 코드 구현

1) reconstruct( )

# S[start]에서 시작하는 LIS 중 사전순으로 skip개 건너뛴 수열을 lis에 저장
def reconstruct(start, skip, lis_array):
    # S[start]는 항상 lis에 포함된다.
    if start != -1:
        lis_array.append(S[start])
    
    # 뒤에 올 수 있는 숫자들의 인덱스 목록을 만듦
    # (숫자, 숫자의 인덱스)형태로 저장
    followers = []
    # range(start + 1, n)을 그냥 (start + 1, n)로 적는 대참사 발생...
    for next in range(start + 1, n):
        if (start == -1 or S[start] < S[next]) and lis(start) == lis(next)+1:
            followers.append((S[next], next))
    
    followers.sort() # 숫자가 증가하는 순서대로 정렬

    # k번째 LIS의 다음 숫자를 찾는다.
    for i in range(len(followers)):
        # i번째 숫자를 S[start]뒤에 붙였을 때 만들 수 있는 LIS의 개수를 확인한다.
        idx = followers[i][1]
        cnt = count(idx)

        # 나올 수 있는 LIS의 수가 skip보다 적기 때문에 skip에서 해당 수 만큼 제외
        if cnt <= skip:
            skip -= cnt

        # 나올 수 있는 LIS의 수가 skip보다 많다면 k번(skip+1)째 LIS를 재귀 호출을 통해 구한다.
        # 또한, k번째 LIS에서 start 뒤에 올 원소는 idx임을 알 수 있다. 
        else:
            reconstruct(idx, skip, lis_array)
            break

• 먼저, k번째 LIS의 원소들은 리스트 lis_array에 저장된다.
• followers라는 리스트에 LIS 원소들을 튜플을 통해 (값, 인덱스) 형식으로 후보군을 저장하고 정렬한다.
• 후보군의 원소들을 count( )함수를 통해 해당 원소에서 만들어지는 LIS의 개수를 확인한다.
• LIS의 개수가 skip보다 작다거나 같다면 해당 원소는 생략하고 skip의 값을 줄인다.
• LIS의 개수가 skip보다 크다면 재귀 호출을 통해 해당 후보군의 원소를 lis_array에 저장한다.
• 위 과정을 거쳐 k번째 LIS를 확인할 수 있다.

 

• 이 함수는 한 번 호출될 때마다 현재 인덱스 뒤에 있는 숫자들을 모두 한 번 순회하고, 이를 정렬한 뒤 다음 숫자를 정한다.
• 이 중 가장 시간이 오래 걸리는 것은 O(n*logn)이 걸리는 정렬 과정이고, 재귀 호출의 깊이는 LIS의 길이와 같으므로 최대 O(n)이다.
• 따라서, 해당 함수의 시간 복잡도는 O(n^2*logn)이라고 말할 수 있다.

 

• 별도로 위 함수에서 유의할 점은 별도의 기저 사례가 없다는 점이다.
• 보통은 LIS의 길이가 1이면 곧장 종료하도록 구현할 수 있지만 LIS의 길이가 1이라면 뒤에 올 숫자가 없고 followers 리스트에 아무런 값이 저장되지 않아 함수가 자동으로 종료하게 된다.

2) 문제 입출력

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

    S = list(map(int, input().split()))

    cacheLen = [-1] * (n + 2) # i번째 인덱스에서 만들 수 있는 LIS의 최대 길이를 저장
    cacheCnt = [-1] * (n + 2) # i번째 인덱스에서 만들 수 있는 LIS의 최대 개수를 저장

    lis_array = []
    reconstruct(-1, k-1, lis_array)

    print(len(lis_array))
    print(lis_array)

• LIS의 길이를 저장하는 cache와 LIS의 개수를 저장하는 cache, 2 개의 메모이제이션 공간이 필요하다.
• 그리고 k번째 LIS를 저장할 lis_array 리스트를 별도로 만들었다.

---

4. 후기

  갈수록 산 넘어 산이다. 그냥 천천히 여러번 문제를 훑어보는 방법밖에 답이 없다고 생각된다. 그렇게 하면 이해가 된다. 문제를 처음 접할 때 한 2번정도 그리고 블로그에 올리면서 다시 2번 정도해서 적어도 4번 정도는 다시 읽어보긴 하는데 확실히 조금씩 조금씩 이해가 되긴한다. 문제는 이해는 되는데 머릿속에 정리가 잘 안되고, 응용이 안되는게 문제다 ㅋㅋㅋㅋ...

  그래도 이 책을 읽으면서 사고의 방법이 달라지고 있다. 기존의 k번째 답안을 찾으라고 한다면 무조건 모든 답을 구해서 정렬 후 k번째 답안을 찾았을 텐데, 이전 문제와 이번 문제에서 소개하는 건너뛰는 방법은 많은 참고자료가 될 것 같다. 그러나 문제가 있다면 큰 그림은 설계할 수 있겠는데 재귀호출을 하는 방법이나 어디서 건너뛰어야 하는지 등의 방법은 고안하기 어렵다고 느껴진다. 특히 재구성하는 함수 같은 경우 유사한 문제들을 많이 풀어야 겠다는 생각이 들었다. 못 풀면 뭐 그냥 블로그에 올린 글들 참고해서 해결하면 어떻게든 되지 않을까?

---

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

LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies