LeetCode - 300(동적 프로그래밍)

처음 이 문제를 본뒤 많이 익숙한 문제라는 생각이 들어 dp를 이용하여 해결해 보았다.

public class Solution {
    public int LengthOfLIS(int[] nums) {
         int[] dp = new int[nums.Length];
            int maxAns = 1;
            dp[0] = 1;

            for (int i = 1; i < nums.Length; i++)
            {
                int maxCount = 0;
                for (int j = 0; j < i; j++)
                {
                    if(nums[i] > nums[j])
                    {
                        maxCount = Math.Max(maxCount, dp[j]);
                    }
                }
                dp[i] = maxCount + 1;
                maxAns = Math.Max(dp[i], maxAns);
            }
            Console.WriteLine(maxAns);
            return maxAns;
    }
}

 

dp를 이용하여 해결한 뒤 가장 시간이 적게 걸린 코드를 살펴 보았는데

적절하게 이진탐색을 접목시킨 것이 상당히 인상적이여서 이 코드를 파해쳐 보는데 30분정도 소비하였다.

public class Solution
{
    public int LengthOfLIS(int[] nums)
    {
        var sequence = new int[nums.Length];
        var result = 0;

        foreach (var number in nums)
        {
            var leftBound = BinarySearch(sequence, result, number);

            sequence[leftBound] = number;
            // 부분수열에 더 추가가 된다면
            // 부분수열의 길이를 갱신해 준다
            if (leftBound == result)
            {
                result++;
            }
        }

        return result;
    }

    private int BinarySearch(int[] sequence, int rightBound, int number)
    {
        var leftBound = 0;

        while (leftBound != rightBound)
        {
            var middleIndex = (leftBound + rightBound) / 2;

            if (sequence[middleIndex] < number)
            {
                leftBound = middleIndex + 1;
            }
            else
            {
                rightBound = middleIndex;
            }
        }

        return leftBound;
    }
}

 

어떻게 이러한 생각이 나올 수 있는지 정말 놀라운 코드였고 나도 추후에는 이러한 아름다운 코드를 작성 할 수 있지 않을까 생각해 보았다.