수열 편집, 재배치, 중첩 문제에서 어떻게 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환원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[] 활용