수열 편집, 재배치, 중첩 문제에서 어떻게 LIS를 활용하는가?

LIS(Longest Increasing Subsequence)는 알고르짐 입문자에게는 필수지만,

실전 코딩테스트나 알고르짐 경시에서는 단순 LIS 문제가 거의 출제되지 않습니다.

 

대신, LIS를 응용하거나 변형해서 풀어야 하는 문제가 다양하게 등장합니다.

예를 들어:

• 수열을 최소 횟수로 정렬하는 법
• 정렬을 방해하는 "장애물 수열" 탐지
• 여러 수열을 동시에 중첩 배치하는 문제
• 문자열, 트리 구조, LCS 문제를 LIS로 환원하는 문제 등

---

실전에서 자주 등장하는 변형 유형 5가지

유형	키워드	핵심 로직
정렬 최소 편집	정렬을 위해 제거해야 할 최소 원소 수	n - LIS
수열 재배치 최적화	재배치 횟수 최소화	LIS 활용
두 수열 매핑	LCS 문제를 LIS로 변환	위치 배열 매핑
장애물/포함 관계 처리	중첩 가능한 상자/사람/건물 수 최대	정렬 + LIS
LIS 복수 추적	경로 개수 구하기	DP + count 테이블

---

변형 유형 1 – 정렬을 위한 최소 편집

정렬되지 않은 수열을 정렬하려면 어떤 원소들을 "빼야" 하는가?

 

arr = [3, 7, 5, 2, 6, 1, 4]
→ LIS = [3, 5, 6] → 길이 3
→ 정렬 위해 제거해야 할 최소 수 = len(arr) - LIS = 7 - 3 = 4

활용 문제

• 백준 18353 병사 배치하기 (감소하는 수열 정렬 → LDS 사용)

 

변형 유형 2 – 수열 재배치 최적화

예: 한 줄로 세운 사람의 키가 입력됨

최대로 줄 세울 수 있는 사람 수는?

그 외의 사람은 재배치하거나 제거해야 함

 

핵심은:

• 증가 수열을 만들기 위해  필요한 최소 작업 수
  • 전체 수 - LIS 길이

 

변형 유형 3 – 두 수열 매핑 문제 (LCS → LIS 환원)

두 수열의 공통 부분을 유지하면서 최대 정렬 형태를 만들고 싶을 때

예: LCS 문제를 LIS 문제로 바꾸는 전략

예제 문제: 백준 13711

• 두 수열 A, B가 주어짐
• A의 원소 순서를 유지하며, B와의 공통 부분 수열을 최장으로 만들고 싶다

해결 전략:

1. B의 원소를 인덱스로 매핑
2. A에서 B에 포함된 원소들의 인덱스 시퀀스를 만든 후
3. 그 인덱스 배열에 대해 LIS를 구함

# 예:
A = [3, 1, 2, 4]
B = [1, 2, 3, 4]

→ B 인덱스 매핑: {1:0, 2:1, 3:2, 4:3}
→ A 매핑: [2, 0, 1, 3]
→ LIS([2, 0, 1, 3]) = 3

 

 

변형 유형 4 – 중첩 구조: 상자/사람/건물 포함 최대

예시:

• 상자들이 (가로, 세로) 형태로 주어짐
• 한 상자가 다른 상자에 들어가려면 두 차원 모두 작아야 함

핵심 아이디어:

1. 한쪽 차원 기준 정렬
2. 나머지 차원에 대해 LIS 적용

boxes = [(5,4), (6,4), (6,7), (2,3)]
→ 너비 오름차순, 높이 내림차순 정렬 → [(2,3), (5,4), (6,7), (6,4)]
→ LIS on 높이: [3, 4, 7]

 

활용 문제

• 백준 1965: 상자 넣기

 

변형 유형 5 – LIS 경로의 개수 구하기

LIS의 길이만이 아니라, 그 가능한 경로 수까지 구해야 하는 경우

접근 방식:

• dp[ i ] : i를 마지막으로 하는 LIS의 길이
• Count[ i ] : 해당 길이로 끝나는 LIS 경로 수

→ 전체 max(dp[ i ]) 길이에 대해, count[ i ] 를 더하면 됨

 

---

실전 문제에 어떻게 접근할 것인가?

문제 형태	접근 방식
수열 길이만 필요한 경우	기본 LIS (DP or 이분 탐색)
경로 복원	prev[] 추적 or 역추적 구현
제거 횟수 최소화	n - LIS 공식 적용
두 수열 비교	인덱스 매핑 + LIS
2D 구조 포함 문제	정렬 + LIS

---

요약

• 실전에서는 LIS 자체보다 응용/변형이 훨씬 자주 등장
• 정렬/재배치 문제 → n - LIS
• 이중 수열/중첩 구조 → 정렬 + LIS 조합
• 두 수열 비교 문제 → 인덱스 매핑 후 LIS
• 수열 복원 or 경로 수 계산 → prev[] or count[] 활용