스파르타 내배캠 Unity 3기 11일차

피곤하고... 어렵고... 아이고...

 

 

 

오늘은 5주차 알고리즘 과제 중에서 3번 문제였던 최장 증가 부분 수열(LIS) 에 대해 알아보고자 한다.

 

※ 최장 증가 부분 수열 (Longest Increasing Subsquance) 란?

 

n개의 원소를 가진 배열의 일부분으로 만든 부분 수열 중,

각 원소가 이전 원소보다 크다는 조건을 만족하면서 그 길이가 가장 긴 부분 수열 이라고한다.

 

예)  배열 { 3, 2, 4, 5, 1, 10, 6, 8 } 있다고 치자.

부분수열 => { 3, 4, 5 },  { 2, 4, 5 }, { 1, 6, 8 }, { 3, 4, 5, 10 } 등등

부분 부분으로 잘라서 수열을 만들 수 있지만 그 중 "증가 하며 가장 긴 수열" 은

{ 3, 4, 5, 6, 8 } 또는 { 2, 4, 5, 6, 8 } 이며 이를 (최장 증가 부분 수열) 이라고 한다.

 

LIS의 길이를 구하는 방법에는 두 가지 방법이 있다고 한다.

1. DP를 활용한 LIS의 길이를 구하는 방법.

2. 이분탐색을 활용한 LIS의 길이를 구하는 방법.

 

DP를 활용한 방법은 시간복잡도가 O(n^2)

이분탐색을 활용한 방법은 시간복잡도가 O(n log n)

이라고 한다.

 

둘 다 공부하고 이해 하도록 해보자.

 

---

 

DP를 활용한 LIS의 길이 구하기 : O(n^2)

 

 

배열 int[] nums 가 주어졌다고 할 때 다음과 같은 코드를 쓸 수 있다.

예시로 { 3, 2, 4, 5, 1, 10, 6, 8 } 를 쓰도록 하겠다.

int LengthOfLIS(int[] nums)
        {
            if (nums == null || nums.Length == 0)
                return 0;

            int[] dp = new int[nums.Length];
            Array.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 dp.Max();
        }

 

 

주어진 배열 nums의 길이를 가진 새로운 int 배열 dp를 만들어준다.

dp는 nums 각 원소가 자신이 마지막 부분 수열의 원소일 때 길이를 저장하는 배열이다.

 

먼저 dp의 모든 원소를 1로 채워준다. (nums의 각 원소가 마지막일 때 길이가 1 이므로)

 

 

 

이중 for문을 돌아야 하는데, i = 1 ~ nums.Length - 1 까지 / j = 0 ~ i - 1 까지 루프하며

nums[ i ] > nums[ j ] 이라면 dp[ i ] 를 기존의 dp [ i ] 값 또는 dp[ j ] + 1 값 중 더 큰 쪽을 저장한다.

 

이를 풀어 설명하자면 이렇다.

 

1. i 는 부분수열의 마지막 원소의 값이 있는 위치를 나타낸다.
2. j 는 nums[ i ] 가 마지막 원소일 때, nums[ i ] 보다 앞에 위치한 원소들을 전부 순회한다.
3. 증가 수열이기 위해선 nums[ j ] 는 반드시 nums[ i ] 보다 작아야 하며, 조건이 성립하면 부분수열의 길이 dp[ i ]는 기존의 dp[ i ] 또는 dp[ j ] + 1 중 큰 값을 dp[ i ] 로 저장한다.

 

그림으로 보도록 하자.

 

012345678910

[슬라이드] 차례대로 루프를 돌았을 때의 결과이다. (중간과정 생략)

 

 

결과와 일치한다.

 

이렇게 nums[ i ] 가 마지막 원소일 때 부분수열의 길이배열 dp를 구하였다.

"최장" 길이를 구해야 하므로

 

return dp.Max() 로 최대값을 반환하자.

그러므로 배열 { 3, 2, 4, 5, 1, 10, 6, 8 } 의 LIS는 ( 5 ) 이다.

 

 

---

 

이분 탐색을 활용한 LIS의 길이 구하기 : O(n log n)

 

 

같은 배열 nums를 쓴다고 하였을 때, 다음과 같은 코드를 작성할 수 있다.

int LengthOfLIS(int[] nums)
        {
            // LIS의 길이를 담을 리스트
            List<int> lis = new List<int>();

            // 배열 nums의 각 원소를 lis의 어느 자리에 저장할지 검사
            foreach (int num in nums)
            {
                int index = BinarySearch(lis, num);
                
                if (index == lis.Count)
                    lis.Add(num);
                else
                    lis[index] = num;
            }            

            return lis.Count;
        }

int BinarySearch(List<int> lis, int target)
        {
            // 0 ~ 현재 lis의 개수 - 1 을 초기값으로 while 반복
            int left = 0;
            int right = lis.Count;
            
            // 탐색범위가 완전히 좁혀질 때 까지 반복
            while (left < right)
            {
                // 탐색 중간값인 mid를 해당 식으로 구한다.                
                int mid = left + (right - left) / 2;

                // lis의 중간값이 target 보다 작으면 탐색 범위를 뒤로 좁혀준다.
                if (lis[mid] < target)
                    left = mid + 1;
                // lis의 중간값이 target 보다 크면 탐색 범위를 앞으로 좁혀준다.
                else
                    right = mid;                
            }

            return left;
        }

 

리스트 lis 는 부분수열이 들어갈 리스트이며 최종적으로 lis.Count 가 최장증가부분수열의 길이가 된다.

 

배열 nums의 각 원소를 BinarySearch 메서드의 target 값으로 전달한다.

BinarySearch 메서드는 0 ~ lis.Count - 1 만큼 while문으로 순환하며

target 값이 lis의 어느 위치에 저장될지에 대한 최적값을 반환해준다.

 

여기서 right는 lis의 개수, left는 0부터 시작한다.

left < right 이라면 그 중간값인 mid를 구해
index를 구하는 시간을 줄여준다.

 

간단하게 설명하면

num의 값이 lis의 모든 값보다 크면 추가

num의 값이 lis의 값 보다 작은값이 처음 나오는 자리에 num을 치환

하는 것이다.

 

 

 

1. num = 3 은 비교할 대상이 없으므로 추가.
2. num = 2 는 3 보다 작으므로 lis[0] 자리에 2를 저장
3. num = 4 는 2 보다 크므로 추가.
4. num = 5 는 2, 4 보다 크므로 추가.

 

 

이런식으로 반복해 나가면 foreach 문이 모두 루프했을 때, lis에 추가된 원소의 개수가 LIS가 된다.

 

다만, 이 방식으로는 수열을 구할 순 없고 길이만 구할 수 있다고 한다.