LIS

LIS, 즉 '최장 증가 부분 수열' 알고리즘에 대해 명확하게 이해하는 시간을 가졌습니다. 처음에는 그저 '중간을 건너뛰는 증가 수열' 정도로만 막연하게 생각했지만, 코드를 깊이 파고들면서 LIS가 왜 일반적인 DP와 다른지, 그리고 제 코드와는 어떤 구조적인 차이가 있는지를 명확하게 구분할 수 있었습니다.

학습 주제

• 오늘 공부한 주제: LIS (Longest Increasing Subsequence, 최장 증가 부분 수열) 알고리즘의 원리와 C++ DP 구현 방식
• 대화 제목: LIS
• 학습 날짜: 2026년 2월 12일

질문과 탐구

제 머릿속에는 항상 LIS에 대한 질문이 맴돌았습니다.

• "LIS가 왜 일반적인 DP 문제와 다른 걸까?"
• "내 코드는 왜 LIS가 아니라 연속 증가 부분배열 길이만 구할까?"
• "LIS에서 '중간 원소를 건너뛴다'는 게 정확히 어떤 의미일까?"
• "LIS의 DP 점화식은 왜 그렇게 복잡해 보이는 걸까?"

이러한 궁금증들을 ChatGPT에게 던지며, LIS의 근본적인 정의부터 올바른 DP 구조, 그리고 제 코드와의 결정적인 차이점을 파헤치기 시작했습니다.

핵심 학습 내용

LIS를 이해하기 위해 가장 중요했던 내용은 다음 두 가지였습니다.

1. LIS의 정의: LIS는 주어진 수열에서 순서를 유지하되, 중간 원소를 마음대로 건너뛰어서 만들 수 있는 가장 긴 증가 수열의 길이를 의미합니다. 여기서 '건너뛴다'는 것은 원소를 실제로 선택하지 않는다는 것을 뜻합니다.
2. DP의 정의와 구조:
   • 제 코드의 DP: dp[i]는 1부터 i까지 봤을 때 '연속 증가 최대 길이'를 의미합니다. 이는 과거의 정보를 요약하여 정보 손실이 발생하는 '선형 누적' 방식입니다.
   • LIS의 DP: dp[i]는 'i번째 원소를 마지막으로 하는 LIS의 길이'를 의미합니다. 이는 과거의 모든 원소를 고려하여 최적의 경로를 찾는 'DAG(Directed Acyclic Graph) DP' 구조입니다.

핵심은 LIS가 dp[i] = dp[i-1] + 1 또는 dp[i] = dp[i-1]과 같은 선형적인 전개가 아니라, dp[i] = max(dp[j] + 1) (단, j < i 이고 v[j] < v[i]) 와 같이 과거의 모든 가능성을 열어두고 탐색해야 한다는 것입니다.

// LIS의 핵심 DP 구조 (O(N^2))
for (int i = 1; i <= n; i++) {
    dp[i] = 1; // 자기 자신 하나로 이루어진 LIS는 길이가 1
    for (int j = 1; j < i; j++) { // i보다 앞에 있는 모든 원소 j를 탐색
        if (v[j] < v[i]) { // v[j]가 v[i]보다 작다면, v[j] 뒤에 v[i]를 붙일 수 있음
            dp[i] = max(dp[i], dp[j] + 1); // j에서 끝나는 LIS에 v[i]를 붙였을 때의 길이와 현재 dp[i]를 비교하여 더 큰 값으로 갱신
        }
    }
}

위 코드는 dp[i]를 계산하기 위해 1부터 i-1까지 모든 j를 탐색하며 v[j] < v[i] 조건을 만족하는 경우 dp[j] + 1 값들을 비교하여 dp[i]를 갱신합니다. 이것이 바로 '중간 원소를 건너뛰어 과거의 다른 원소와 연결'하는 LIS의 핵심입니다.

이해한 내용

이번 대화를 통해 LIS에 대한 막연했던 개념들이 명확하게 정리되었습니다.

• 새로 알게 된 것: LIS에서 '건너뛰기'는 단순히 연산을 스킵하는 것이 아니라, 해당 원소를 선택지에서 제외하고 다른 과거 원소와 연결하는 행위라는 점입니다. 또한, LIS DP는 dp[i]가 'i에서 끝나는' 지역 최적값이 모여 전체 최적값을 이루는 구조라는 것을 이해했습니다.
• 이전 몰랐던 것과의 연결: 이전에 LIS 문제를 풀 때 왜 DP를 잘못 적용하는지 명확히 알지 못했는데, 이는 제가 DP의 '상태 정의'를 잘못하고 '연속성'에만 초점을 맞췄기 때문임을 깨달았습니다. LIS는 '순서'와 '증가'라는 두 가지 조건만 만족하면 중간 건너뛰기가 자유로운 '부분수열(subsequence)' 문제였던 것입니다.
• 개념 정리:
  • Subarray: 연속적인 부분 배열 (예: 1 2 3 에서 2 3)
  • Subsequence: 순서는 유지하되 중간 건너뛰기 가능한 부분 수열 (예: 1 2 3 4 5 에서 1 3 5)
  • LIS는 Subsequence 문제이며, 일반적인 DP는 Subarray 문제를 푸는 데 더 적합하다는 것을 알게 되었습니다.

실전 적용

배운 LIS 알고리즘은 다양한 최적화 문제에 적용될 수 있습니다.

• 적용 가능 분야:
  • 주식 가격 예측에서 특정 기간 동안의 최대 상승률 계산 (단, 순서 유지 및 증가 조건 적용 시)
  • 게임에서 캐릭터의 능력치 상승 경로 최적화
  • 데이터 압축이나 시퀀스 정렬 문제
• 실습 계획:
  • 백준 등 알고리즘 문제 풀이 사이트에서 LIS 관련 문제들을 풀어볼 예정입니다. (예: 11053번, 14002번 등)
  • O(N log N) 시간 복잡도를 가지는 LIS 최적화 알고리즘도 공부해 볼 계획입니다.
• 응용 아이디어: LIS의 원리를 활용하여 특정 조건 하에서 가장 긴 '동시 접속자 수 증가 구간'을 찾는 로직을 구현해 볼 수 있습니다.

추가 학습 계획

• 더 깊이 공부하고 싶은 부분:
  • LIS 알고리즘의 O(N log N) 최적화 기법 (이분 탐색 활용)
  • LIS와 관련된 다른 DP 문제들 (LCS, 편집 거리 등)과의 관계
• 관련 자료 찾기:
  • "이것이 취업을 위한 코딩 테스트다 with Python" 등 검증된 알고리즘 서적의 LIS 챕터
  • GeeksforGeeks, LeetCode 등의 LIS 관련 튜토리얼 및 해설
• 다음 학습 주제: LIS의 O(N log N) 최적화 알고리즘을 공부하고, 이를 실제 코드로 구현해보는 것입니다.

참고 자료

• ChatGPT와의 대화 내용 전체 (2026년 2월 12일)
• LIS 알고리즘 관련 온라인 문서 및 튜토리얼 (ChatGPT가 추천한 내용 포함)