LeetCode 300: Longest Increasing Subsequence

📊 결과

💻 내 코드 (Try 1)

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        int max = 1;
               
        for(int i=1; i<nums.length; i++){
            for(int j=0; j<i; j++){
                if(nums[i]>nums[j]){
                    dp[i]=Math.max(dp[i], dp[j]+1);
                }
            }
            max = Math.max(max, dp[i]);
        }

        return max;
    }
}

📝 평가

✔ 잘한 점

  1. O(N²) DP 정확히 구현
    • dp[i] = i번째까지의 LIS 길이
    • 이전 모든 원소와 비교
  2. 초기화 적절
    • Arrays.fill(dp, 1) - 최소 길이 1
  3. 최댓값 추적
    • 루프 중 max 갱신

✦ 개선점

1. 시간복잡도 O(N²)

현재 방식은 모든 이전 원소를 확인한다. Binary Search로 O(N log N) 가능하다.

2. max 갱신 위치

// ✘ 매 iteration마다 갱신
for(int i=1; i<nums.length; i++){
    // ...
    max = Math.max(max, dp[i]);
}

// ✔ 마지막에 한 번만
return Arrays.stream(dp).max().getAsInt();

✨ 최적화된 풀이

방법 1: O(N log N) - Binary Search

class Solution {
    public int lengthOfLIS(int[] nums) {
        List<Integer> tails = new ArrayList<>();
        
        for(int num : nums){
            int pos = Collections.binarySearch(tails, num);
            if(pos < 0) pos = -(pos + 1);
            
            if(pos == tails.size()){
                tails.add(num);
            } else {
                tails.set(pos, num);
            }
        }
        
        return tails.size();
    }
}

핵심 아이디어:

방법 2: O(N²) 개선

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        
        for(int i=1; i<nums.length; i++){
            for(int j=0; j<i; j++){
                if(nums[i] > nums[j]){
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        
        return Arrays.stream(dp).max().getAsInt();
    }
}

성능 비교

방법 시간복잡도 공간복잡도 Runtime
원본 (DP) O(N²) O(N) 38ms
Binary Search O(N log N) O(N) ~5ms

💡 핵심 인사이트

DP 점화식

dp[i] = max(dp[j] + 1) for all j < i where nums[j] < nums[i]

Binary Search 원리

nums = [10, 9, 2, 5, 3, 7, 101, 18]

tails 변화:
[10]
[9]
[2]
[2, 5]
[2, 3]
[2, 3, 7]
[2, 3, 7, 101]
[2, 3, 7, 18]
→ LIS 길이 = 4

tails는 실제 LIS가 아니라, 각 길이의 최적 후보다.

Collections.binarySearch()

기본 사용법

int pos = Collections.binarySearch(List<T> list, T key);

반환값

양수 (≥0): 찾은 인덱스

List<Integer> list = Arrays.asList(1, 3, 5, 7, 9);
int pos = Collections.binarySearch(list, 5);  // pos = 2

음수 (<0): 못 찾음 → 삽입 위치 계산 필요

int pos = Collections.binarySearch(list, 6);  // pos = -4
int insertPos = -(pos + 1);  // insertPos = 3

삽입 위치 공식

insertPos = -(returnValue + 1)

예시

List<Integer> tails = new ArrayList<>();
// tails = [2, 3, 7]

int pos = Collections.binarySearch(tails, 5);
// pos = -3 (5는 인덱스 2에 들어가야 함)

pos = -(pos + 1);  // pos = 2
tails.set(2, 5);  // [2, 3, 5]

LIS에서 활용

for(int num : nums){
    int pos = Collections.binarySearch(tails, num);
    
    // 못 찾으면 삽입 위치 계산
    if(pos < 0) pos = -(pos + 1);
    
    // 끝에 추가 or 기존 값 교체
    if(pos == tails.size()){
        tails.add(num);
    } else {
        tails.set(pos, num);
    }
}

주의사항

📚 관련 개념

🎓 다음 단계

유사 문제

  1. LeetCode 673: Number of LIS
  2. LeetCode 354: Russian Doll Envelopes
  3. 백준 11053: 가장 긴 증가하는 부분 수열

연습 포인트

🏷️ Keywords

#LeetCode #DP #BinarySearch #LIS #Java #최적화