9.1 예제_최적화 문제의 실제 답 계산하기_최대 증가 부분 수열 실제로 출력하기(Python)

1. 최대 증가 부분 수열 실제로 출력하기

• 이전에 주어진 수열의 최대 증가 부분 수열(LIS)의 길이를 구하는 문제를 해결한 적이 있다.
• 그러나 단순히 길이만 알고 실제 LIS가 어떤 원소들로 구성되는지는 알 수가 없다.
• 예를 들어 S=[4, 7, 6, 9, 8, 10]의 LIS의 길이는 4라는 사실은 알 수 있지만, 실제 부분 수열을 알 수는 없었다.
• 그렇다면 S의 LIS인 [4, 6, 9, 10] 혹은 [4, 7, 9, 10]은 어떻게 알 수 있을까?

(1) 문제 분석 및 설계

• 맨 처음 방법은 기존에 구현했던 lis() 함수가 LIS의 길이 대신 실제 LIS의 원소들을 담는 배열을 반환하도록 하는 것이다.
• 직관적이라는 장점이 있지만 모든 부분 문제마다 최적해를 저장해 메모리를 많이 차지하는 번거로운 문제가 발생한다.
• 때문에 보통 실제 답을 계산하는 과정을 별도로 구현할 필요가 있다.

 

• 보통 부분 문제가 주어질 때 그 중 첫 번째 조각을 어떤 선택지로 채울지 하나 하나 시도하면서 최적해를 찾는다.
• 실제 답을 계산하기 위해서는 각 부분 문제마다 어떤 선택지를 골랐을 때 최적해을 얻는지 기록하고 별도의 재귀 함수를 이용해 각 조각에서 한 선택을 되짚어 가면서 최적해를 생성하면 된다.

(2) 코드 - 문제풀이 해설 방법

1) lis4(start) : S[start]에서 시작하는 증가 부분 수열 중 최대 길이를 반환해서 choices에 저장한다.

# S[start]에서 시작하는 증가 부분 수열 중 최대 길이를 반환해서 choices에 저장한다.
def lis4(start):
    if cache[start+1] != -1:
        return cache[start+1]
    
    cache[start + 1] = 1 # 항상 S[start]는 있기 때문에 길이는 1
    bestNext = -1

    # 최대 증가 부분 수열의 길이 구하기
    for next in range(start+1, n):
        if start == -1 or S[start] < S[next]:
            cand = lis4(next) + 1

            # 재귀 호출을 통해 기존에 cache에 저장된 값보다 부분 수열의 길이가 긴 경우를 발견하면 cache 갱신
            if cand > cache[start + 1]:
                cache[start + 1] = cand
                bestNext = next # 어떤 숫자를 다음 숫자로 선택해야 전체 증가 부분 수열의 길이를 최대화 할지 저장
    
    choices[start + 1] = bestNext # choices에 이를 기록하고 이후에 실제 원소들을 나열할 때 사용
    return cache[start + 1]

• 주의해야 할 점은 이전에 LIS문제를 풀때와 비슷하게 -1 인덱스의 존재를 가정하는 것이다.
• 따라서 cache에서 실제로는 존재하지 않는 -1 인덱스 때문에 발생할 수 있는 문제를 'start + 1'을 통해 cache에 대해서는 0번 인덱스에 대해 정상 작동할 수 있도록 한다.
• 리스트 choices를 통해 해당 인덱스부터 LIS를 만들기 시작할 때 최적해가 나오는 실제 원소의 인덱스를 저장한다.

2) reconstuct(start, seq) : LIS의 원소들을 구해 리스트 seq에 저장한다.

# 최대 길이의 증가하는 부분 수열의 원소들을 구하는 함수
# 해당 원소를 seq 리스트에 저장함
def reconstruct(start, seq):
    if start != -1:
        seq.append(S[start])
    
    next = choices[start + 1]

    if next != -1:
        reconstruct(next, seq)

• start에서 시작하는 LIS의 실제 원소들을 리스트 seq에 저장한다.
• choice에는 최적화된 LIS의 원소들의 인덱스가 저장되어 있기 때문에 이를 바탕으로 seq에 실제 원소를 저장한다.
• 사실 reconstruct() 함수는 꼭 재귀적으로 구현할 필요는 없다.
• 하지만 추후에 다른 문제에서 답을 재구성하는(이 경우에는 실제 원소들을 저장하는) 과정에서 구조가 현재 사용한 재귀적 호출의 구조와 비슷하게 진행되기 때문에 위와 같이 구현했다고 한다.

3) 입-출력

S = [4, 7, 6, 9, 8, 10] # 주어진 수열 S
n = len(S) # 수열 S의 길이

cache = [-1] * 101 # cache[start+1] : start에서 시작하는 LIS의 최대 길이를 저장
choices = [-1] * 101 # start에서 시작하는 LIS의 실제 원소의 인덱스를 저장

seq = [] # choices에서 저장된 인덱스를 바탕으로 reconstruct() 에서 인덱스에 해당되는 원소들을 저장

lis4(-1) # 0번 인덱스부터 시작하는 LIS의 최대 길이와 최적화된 원소들의 인덱스를 choice에 저장
reconstruct(-1, seq) # 0번 인덱스부터 시작하는 LIS의 실제 원소들을 seq에 저장

print(seq) # 수열 S의 LIS출력

---

2. 최적화 문제 답 계산하기 레시피

• 1. 재귀 호출의 각 단계에서 최적해를 만들었던 선택을 별도의 배열(ex. choices)에 저장한다.
• 2. 별도의 재귀 함수를 이용해 이 선택을 따라가며 각 선택지를 저장하거나 출력한다.

---

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

LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies