Algorithm - 최대 부분 증가수열(LIS : Longest Increasing Subsequence)

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[최대 부분 증가수열(LIS)]

 

N개의 자연수로 이루어진 수열이 주어졌을 때, 그 중에서 가장 길게 증가하는(작은 수에서 큰 수로) 원소들의 집합을 찾는 프로그램을 작성하시오. (단, 원수열의 원소 순서는 그대로 유지해야 함)

 

예를 들어, 주어진 수열의 원소가 2, 7, 5, 8, 6, 4, 7, 12, 3 이고 가장 길게 증가하도록 원소들을 차례대로 뽑아내면 2, 5, 6, 7, 12를 뽑아내어 길이가 5인 최대 부분 증가수열을 만들 수 있다.

 

 

*입력 설명

첫 번째 줄에 입력되는 데이터의 수인 자연수 N(2 ≤ N ≤ 1,000)이 주어진다.

두 번째 줄에는 N개의 입력 데이터들이 주어진다.

 

*출력 설명

첫 번째 줄에 부분 증가수열의 최대 길이를 출력한다.

 

 

---

 

 

풀이(Python)

답안

import sys
sys.stdin = open('AA/input_76.txt', 'rt')

n = int(input())
arr = list(map(int, input().split()))
arr.insert(0, 0)
dy = [0] * (n+1)
dy[1] = 1
res = 0

for i in range(2, n+1):
    max = 0
    for j in range(i-1, 0, -1):
        if arr[j] < arr[i] and dy[j] > max:
            max = dy[j]
    dy[i] = max + 1
    if dy[i] > res:
        res = dy[i]
        
print(res)

# 출력 : 4

 

input_76.txt(입력)

8
5 3 7 8 6 2 9 4

 

 

중요내용

1. 해당 문제를 풀 때, 원수열의 원소 순서를 변경해서는 안된다. (원수열의 순서를 유지한 채, 가장 긴 증가수열을 뽑아내는 문제)
2. 따라서, 원수열의 순서가 변경될 수 없기 때문에 dy[1]은 항상 1의 값을 가진다. (해당 값을 미리 선언해둔 이유)
3. dy[i]는 arr[i]의 값이 증가수열의 마지막 항이 될 때 만들 수 있는 가장 긴 수열의 길이를 의미한다.
4. 즉, 리스트 dy에는 원수열에서 추출한 증가수열의 최대길이를 저장한다. 
5. 한편, 리스트 arr의 0번 인덱스에 의도적으로 0값을 넣어줌으로써 리스트의 인덱스 번호와 원수열의 배열 순서를 맞춰줬다.
6. for j in range(i-1, 0, -1): 는 arr[i]를 부분 증가수열의 마지막 항으로 고려할 때, arr[i] 바로 앞의 값(arr[j])부터 뒤에서 앞으로 가면서 수열의 값들을 확인하는 반복문의 코드이다.
7. 변수 res에는 부분 증가수열의 최대 길이값을 저장한다.
8. ' dy[i] = max + 1 ' 에서 max는 arr[i] 앞에 오는 숫자들로 만들 수 있는 부분 증가수열의 최대길이를 의미한다. 
9. 즉, max 값에 1을 더하면 arr[i]로 만들 수 있는 부분 증가수열의 최대길이를 구할 수 있다. (arr[i] 이전의 원소들로 만들 수 있는 최대길이의 증가수열에 1을 더하면 arr[i] 까지 포함해서 만들 수 있는 최대길이의 증가수열을 구할 수 있음)