LIS 알고리즘 - 이분탐색

LIS 알고리즘 - DP(동적계획법)

LIS 알고리즘 - DP(동적계획법)

 

저번에 이어 LIS알고리즘을 이용하여 가장 갈게 증가하는 부분 수열을 찾는 알고리즘 중 이분 탐색을 이용한 방법을 알아보자

 

1.LIS 알고리즘-이분탐색

 

이분탐색의 경우 시간 복잡도는 O(nlog⁡n)을 가진다. 이분탐색을 이용하는 경우에는 실제 LIS가 아닌 LIS의 길이를 구하는데 중점을 두는  알고리즘이다.

이분탐색은 배열이 정렬되었다는 특징을 이용하여 탐색 범위를 절반씩 줄여가며 찾고자 하는 값을 빠르게 검색할 수 있다.

이분탐색의 핵심은 탐색 범위의 중간값을 확인한 뒤, 찾고자 하는 값이 중간값보다 크면 오른쪽 절반으로, 작으면 왼쪽 절반으로 범위를 줄여가는 것이다.

 

LIS 이분탐색은 길이를 구하는데 초점을 맞추며, 실제 LIS 수열을 구하는 방법과는 약간 다르다.

이 방법의 핵심은 LIS를 구성할 수 있는 후보 숫자들을 유지하는 배열  lis를 생성하고, 각 수자에 대해 이 배열에서 이분탐색을 수행하여 적절한 위치에 삽입하거나 교체하는 것이다.

 

먼저 간단하게 설명하면 다음과 같다.

1. 새로운 숫자를 추가할 때, lis 배열에서 그 숫자가 들어갈 적절한 위치를 이분 탐색으로 찾는다.
2. 해당 위치에 있는 값을 새로운 숫자로 대체한다.
   (이미 존재하는 값보다는  작은 값으로 대체하므로 길이는 유지되며 LIS 수열을 위한 더 나은 값으로 수정된다)
3. 만약 lis 배열의 끝보다 큰 숫자라면,  lis qodufdptj tntwkfmf cnrkgksek.

이분탐색을 적용한 코드는 다음과 같다.

public class LISWithBinarySearch {
    
    public static int lengthOfLIS(int[] nums) {
        // LIS의 후보 값을 저장할 리스트
        List<Integer> lis = new ArrayList<>();

        // 배열의 각 숫자를 순회
        for (int num : nums) {
            // 현재 숫자가 들어갈 위치를 찾음 (이분 탐색)
            int pos = binarySearch(lis, num);
            
            // 이 위치가 lis 길이와 같다면 리스트에 추가 (새로운 길이 증가)
            if (pos == lis.size()) {
                lis.add(num);
            } else {
                // 이미 위치가 존재하면 그 위치의 값을 num으로 대체
                lis.set(pos, num);
            }
        }

        // LIS의 길이를 반환
        return lis.size();
    }

    // 이분 탐색 메소드: 목표 숫자가 들어갈 위치를 반환
    private static int binarySearch(List<Integer> lis, int target) {
        int left = 0, right = lis.size() - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (lis.get(mid) == target) {
                return mid;
            } else if (lis.get(mid) < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return left;  // 목표 위치 반환
    }
}

위의 코드를 통해 단계별로 확인해보면 다음과 같다.

1. 초기화
   • lis리스트를 생성하여 LIS 후보 숫자들을 저장한다.
2. 각 숫자에 대해 위치 찾기
   • 배열 nums의 각 숫자  num을 순회한다.
   • num이 lis 배열에서 어디에 들어가야할지 이분 탐색을 통해 찾는다. binarySearch 메소드를 사용하여 num이 삽입될 위치를 pos에 저장한다.
3. 이분 탐색을 통한 위치 결정
   • binarySearch 메소드는 이분 탐색을 통해 target이 들어갈 위치를 찾는다.
   • target보다 큰 값이 lis에 처음 등장하는 위치를 반환하며 이는 lis 리스트에서 target을 대체하거나 추가할 위치이다.
4. 위치에 따라 숫자 추가 또는 대체
   
   • pos가 lis의 길이와 같다면, 이는 num이 lis에서 가장 큰 값이므로 lis의 끝에 추가한다.
   • 그렇지 않다면, lis의 pos위치에 num을 대체한다. 이는 lis의 크기를 변화시키지 않고, LIS를 유지하면서 더 작은 값으로 대체하여 다음 숫자가 더 쉽게 추가될 수 있도록 한다.
5. 최종 길이 반환
   • lis 리스트의 길이를 반환한다. 이는 nums의 가장 긴 증가 부분 수열의 길이와 같다.

입력 배열이 {10, 9, 2, 5, 3, 7, 101, 18}인 경우를 살펴보자

1. num =10 : lis 리스트가 비었으므로 10을 추가. lis=[10]
2. num = 9 : 9의 위치는 0이므로 10을 9로 대체. lis=[9]
3. num = 2 : 2의 위치는 0이므로 9를 2로 대체. lis=[2]
4. num = 5 : 5는 2다음에 오므로 끝에 추가. lis=[2, 5]
5. num = 3 : 3의 위치는 1이므로 5를 3으로 대체. lis=[2,3]
6. num = 7 : 7은 3다음에 오므로 끝에 추가. lis=[2, 3, 7]
7. num = 101 : 101은 7 다음에 오므로 끝에 추가. lis=[2, 3, 7, 101]
8. num = 18 : 18의 위치는 3이므로 101을  18로 대체.

최종 lis 리스트 길이는 4가 된다.