증가하는 부분 수열 (LIS: Longest Increasing Subsequence)

---

1. 문제 정의

• 수열이 주어졌을 때, 해당 수열에서 일부 원소를 골라 만든 증가하는 부분 수열 중 가장 긴 것의 길이를 구하는 문제이다.
  • 즉, 원소들의 상대적인 순서를 유지하면서 오름차순이 되도록 선택한 부분 수열 중 가장 길게 만들 수 있는 경우를 찾는 것이다.

 

1.1 DP를 활용한 LIS 풀이 방법

1.1.1 핵심 아이디어

• 각 원소를 마지막 원소로 가지는 LIS의 길이를 구하여 전체 최댓값을 구한다.
  • 이때, 이전 원소들과 비교하여 자신보다 작은 값이 있다면 그 값까지의 LIS 길이에 1을 더하여 갱신한다.

 

1.1.2 점화식

• dp[i] = max(dp[j] + 1) (단, 0 <= j < i 이고 arr[j] < arr[i] 인 경우)
  • 즉, i번째 원소를 끝으로 하는 LIS 길이는, 그 이전까지 중 자신보다 작은 값을 가지는 모든 인덱스 j에 대해 dp[j] + 1의 최대값이 된다.

 

1.1.3 초기화

• 모든 위치에 대해 dp[i] = 1로 초기화한다.
• (자기 자신 하나만으로 구성된 LIS는 항상 가능하므로 최소 길이는 1이다.)

 

1.1.4 알고리즘 구현 예시 (Python)

def LIS(arr):
    n = len(arr)
    dp = [1] * n  # 모든 위치는 최소 1의 LIS를 가짐

    for i in range(n):
        for j in range(i):
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)  # 전체 LIS 길이의 최댓값

 

 

1.2 예제 분석

1.2.1 예제 입력

arr = [10, 20, 10, 30, 20, 50]

 

1.2.2 DP 배열 상태 변화

0	10	초기값 1	1
1	20	10 < 20 → dp[1] = max(1, dp[0]+1)	2
2	10	모든 j에 대해 arr[j] ≥ 10 → 변화 없음	1
3	30	10, 20, 10 < 30 → dp[3] = max(1, 2+1)	3
4	20	10, 10 < 20 → dp[4] = max(1, 1+1)	2
5	50	10, 20, 10, 30, 20 < 50 → dp[5] = 4	4

• 최종 dp = [1, 2, 1, 3, 2, 4]
• 결과: max(dp) = 4

 

 

1.3 시간 복잡도 분석

• 이중 루프 구조이므로 시간 복잡도는 O(N²) 이다.
• 수열의 길이가 크지 않다면 충분히 적용 가능하다.