본문 바로가기
카테고리 없음

최장 증가 부분 수열(LIS) 알고리즘 (O(N^2) vs O(NlogN) 성능 비교)

by tech-korea 2026. 2. 23.

배열 내부의 데이터 흐름을 분석하는 코딩 테스트 문제 중, '최장 증가 부분 수열(Longest Increasing Subsequence, 이하 LIS)'은 출제 빈도가 매우 높은 알고리즘입니다. "어지럽게 꼬인 전깃줄을 엉키지 않게 최소한으로 잘라내기", "순서대로 배치된 상자들 중 크기가 점점 커지도록 상자를 가장 많이 고르기" 같은 문제들이 겉모습만 다를 뿐 모두 이 LIS 알고리즘의 본질을 묻고 있습니다. LIS를 해결하는 방법은 크게 두 가지로 나뉘는데, 데이터가 적을 때 사용하는 동적 계획법(DP) 기반의 O(N^2) 방식과, 대용량 데이터 환경에서 이진 탐색(Binary Search)을 결합하여 속도를 극대화한 O(N log N) 방식이 있습니다. 이 두 가지 방식의 논리적 전개 과정을 완벽히 비교 분석해 드립니다.

1. 최장 증가 부분 수열(LIS)의 정확한 개념

주어진 배열에서 '일부 원소를 자유롭게 지워버리고 남은 원소들이 순서를 유지하면서 오름차순으로 점점 커지는(증가하는) 수열'을 증가 부분 수열이라고 합니다. 그중에서도 길이가 가장 긴 것을 LIS라고 부릅니다.

예를 들어 배열 [10, 20, 10, 30, 20, 50]이 주어졌다고 가정해 봅시다. 여기서 10, 20, 30, 50을 고르면 뒤로 갈수록 값이 점점 커지며, 길이는 4가 됩니다. 이것보다 더 길게 오름차순으로 원소를 뽑아낼 방법은 없으므로, 이 배열의 LIS 길이는 4가 되는 것입니다.

2. 기초적인 접근: 동적 계획법 (시간 복잡도 O(N^2))

가장 직관적이고 구현이 쉬운 방법은 1차원 DP 테이블을 활용하는 것입니다. dp[i]를 "i번째 인덱스의 숫자를 마지막으로 하는 가장 긴 증가 수열의 길이"라고 정의합니다.

2-1. 이중 반복문을 활용한 점화식

로직은 단순합니다. 현재 위치(i)의 숫자가 그보다 앞에 있는 숫자들(j)보다 크다면, 앞선 숫자가 만들어놓은 수열의 뒤에 현재 숫자를 이어 붙일 자격이 생깁니다. 따라서 내 앞에 있는 모든 숫자들을 하나하나 검사하면서 나보다 작은 놈들을 찾고, 그중에서 가장 길이가 긴 수열에 나 자신(+1)을 편입시키는 것입니다.


int[] dp = new int[N];
int maxLIS = 1;

for (int i = 0; i < N; i++) {
  dp[i] = 1; // 자기 자신만 있는 수열, 최소 길이는 1
  for (int j = 0; j < i; j++) {
  	// 내 앞의 숫자가 나보다 작다면 이어 붙일 수 있음
    if (arr[j] < arr[i]) {
   		dp[i] = Math.max(dp[i], dp[j] + 1);
    }
  }
  maxLIS = Math.max(maxLIS, dp[i]);
}

이 방식은 코드가 짧고 논리가 아주 명확합니다. 하지만 바깥쪽 루프(N)와 안쪽 루프(N)가 이중으로 돌아가기 때문에 O(N^2)의 시간이 소요됩니다. 만약 주어진 숫자가 10만 개라면 연산 횟수가 100억 번에 달해 가차 없이 시간 초과(Time Limit Exceeded)를 맞이하게 됩니다.

3. 극한의 최적화: 이진 탐색 결합 (시간 복잡도 O(N log N))

데이터가 10만 개, 100만 개 단위로 주어지는 극한의 환경에서는 이중 반복문을 사용할 수 없습니다. 속도를 획기적으로 줄이기 위해 '증가하는 수열을 직접 유지하는 새로운 배열(List)'을 하나 만들고, 이진 탐색(Binary Search) 기법을 도입해야 합니다.

3-1. 자리를 대체(Replace)하는 마법의 로직

새로운 배열 LIS_list를 빈 상태로 준비합니다. 원본 배열을 순회하면서 다음 규칙을 적용합니다.

  1. 현재 숫자가 LIS_list의 맨 마지막 숫자보다 크다면: 기분 좋게 LIS_list의 맨 뒤에 이어 붙여 수열의 길이를 늘립니다.
  2. 현재 숫자가 LIS_list의 맨 마지막 숫자보다 작거나 같다면: 여기서 이진 탐색이 들어갑니다. LIS_list 안에서 현재 숫자보다 크거나 같은 놈 중 가장 왼쪽에 있는 놈(Lower Bound)을 찾아서, 그 자리를 현재 숫자로 바꿔치기(대체) 해버립니다.

왜 멀쩡한 숫자를 더 작은 숫자로 바꿔치기할까요? 수열의 끝부분(혹은 중간 부분) 값을 최대한 작게 유지해야만, 나중에 뒤에서 더 많은 숫자들을 쉽게 이어 붙일 수 있는 '잠재력'이 커지기 때문입니다.

이진 탐색을 통해 들어갈 자리를 찾는 데 O(log N)이 걸리고, 이를 N번 반복하므로 최종 시간 복잡도는 O(N log N)이라는 경이로운 수치가 됩니다. 주의할 점은, 이 방식으로 구한 LIS_list의 길이가 실제 정답 길이는 맞지만, 그 안에 들어있는 숫자의 나열 자체가 실제 LIS의 원소들과 100% 일치하지는 않는다는 사실(대체 과정 때문에 순서가 꼬일 수 있음)을 반드시 기억해야 합니다.

[핵심 요약] 1. 최장 증가 부분 수열(LIS)은 순서를 유지하며 오름차순으로 길게 이어지는 부분 수열을 찾는 대표적인 알고리즘입니다. 2. 기본적으로 1차원 DP 배열과 이중 반복문을 사용하여 O(N^2)의 속도로 직관적으로 풀이할 수 있습니다. 3. 데이터 크기가 방대할 때는 수열을 작게 유지하는 치환 기법과 이진 탐색(Lower Bound)을 결합하여 O(N log N)의 속도로 최적화해야 합니다.

티스토리툴바