99클럽 코테 스터디 29일차 TIL , Longest Increasing Subsequence

문제

풀이

입력으로 정수 배열이 주어지면 왼쪽에서 오른쪽으로 갈 때 증가하는 수의 개수가 가장 큰 것을 출력하는 것이다.

예를 들어,

nums = {10,9,2,5,3,7,101,18}

이면 (2,5,7,101), (2,3,7,101), (2,5,7,18), (2,3,7,18)의 경우가 가장 긴 경우들이고 길이니까 4가 나와야 한다.

제출 1 - 정답

class Solution {
    public static int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int maxLength = 1;

        for (int i = 0; i < n; i++) {
            dp[i] = 1;
        }

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }

            maxLength = Math.max(maxLength, dp[i]);
        }

        return maxLength;
    }
}

 

dp를 nums의 길이만큼 배열로 선언해 주고 첫 길이는 1로 설정해 준다.

모든 dp의 값을 첫 길이만큼 1로 변경해 준다.

dp의 길이를 nums의 길이만큼 만들어 준 이유는 각 위치에서 만들어지는 개수를 구하기 위해서다. 설명은 뒤에서 하고 반복문을 보면 1부터 시작해서 안에 있는 반복문은 j가 i전까지만 돌면서 nums [j]가 nums[i]보다 작을 경우에 값을 갱신해 주는 방법을 사용하고 있다. 과정을 살펴보자

nums = {10, 9, 2, 5, 3, 7, 101, 18 };

dp = {1,1,1,1,1,1,1,1}

maxLength = 1;

i = 1일 경우, j=0 일 경우 작지 않아서 pass

i = 2일 경우, j=0 일 경우 작지 않아서 pass

                     j=1 일 경우 작지 않아서 pass

i = 3일 경우, j=0 일 경우 작지 않아서 pass

                     j=1 일 경우 작지 않아서 pass

                     j=2 일 경우 작기 때문에 dp[i], dp[j]+1 비교해서 넣어줌

dp = {1,1,1,2,1,1,1,1}

maxLength = 2;

i = 4 일 경우, j=0 일 경우 작지 않아서 pass

                      j=1 일 경우 작지 않아서 pass

                      j=2 일 경우 작기 때문에 dp[i], dp[j]+1 비교해서 넣어줌

                      j=3 일 경우 작지 않아서 pass

dp = {1,1,1,2,2,1,1,1}

maxLength = 2;

i = 5 일 경우, j=0 일 경우 작지 않아서 pass

                      j=1 일 경우 작지 않아서 pass

                      j=2 일 경우 작기 때문에 dp[i], dp[j]+1 비교해서 넣어줌

                      j=3 일 경우 작기 때문에 dp[i], dp[j]+1 비교해서 넣어줌

                      j=4 일 경우 작기 때문에 dp[i], dp[j]+1 비교해서 넣어줌 (3으로 동일해서 바뀌지 않음)

dp = {1,1,1,2,2,3,1,1}

maxLength = 3;

i = 6 일 경우, j=0 일 경우 작기 때문에 dp[i], dp[j]+1 비교해서 넣어줌

                      j=1 일 경우 작기 때문에 dp[i], dp[j]+1 비교해서 넣어줌 (2로 동일해서 바뀌지 않음)

                      j=2 일 경우 작기 때문에 dp[i], dp[j]+1 비교해서 넣어줌 (2로 동일해서 바뀌지 않음)

                      j=3 일 경우 작기 때문에 dp[i], dp[j]+1 비교해서 넣어줌

                      j=4 일 경우 작기 때문에 dp[i], dp[j]+1 비교해서 넣어줌 (3으로 동일해서 바뀌지 않음)

                      j=5 일 경우 작기 때문에 dp[i], dp[j]+1 비교해서 넣어줌

dp = {1,1,1,2,2,3,4,1}

maxLength = 4;

i = 7 일 경우, j=0 일 경우 작기 때문에 dp[i], dp[j]+1 비교해서 넣어줌

                      j=1 일 경우 작기 때문에 dp[i], dp[j]+1 비교해서 넣어줌 (2로 동일해서 바뀌지 않음)

                      j=2 일 경우 작기 때문에 dp[i], dp[j]+1 비교해서 넣어줌 (2로 동일해서 바뀌지 않음)

                      j=3 일 경우 작기 때문에 dp[i], dp[j]+1 비교해서 넣어줌

                      j=4 일 경우 작기 때문에 dp[i], dp[j]+1 비교해서 넣어줌 (3으로 동일해서 바뀌지 않음)

                      j=5 일 경우 작기 때문에 dp[i], dp[j]+1 비교해서 넣어줌

                      j=6 일 경우 작기 때문에 dp[i], dp[j]+1 비교해서 넣어줌 (4로 동일해서 바뀌지 않음)

 

정답 : 4

 

이러식으로 앞에서 올 때 내 자리에서는 몇 개가 가능한지 넣어주는 방식이다.

 

다른 풀이 - 클럽장님 코드

class Solution {
    public static int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        // dp 배열은 LIS의 현재 길이를 저장
        int[] dp = new int[nums.length];
        int length = 0;  // 현재 LIS의 길이

        for (int num : nums) {
            // 이분 탐색을 사용하여 num이 dp 배열에서 적절한 위치를 찾기
            int left = 0, right = length;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (dp[mid] < num) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            // left는 num이 들어가야 할 위치
            dp[left] = num;

            // length는 dp 배열의 현재 유효 길이
            if (left == length) {
                length++;
            }
        }
        return length;
    }

}

 

이해하기 굉장히 어려웠다. 이해 안 가면 직접 디버깅해 보는 것을 추천한다.

일단 위에서는 dp를 반복문을 전체를 다 돌면서 확인했다. 위는 한 번의 반복문을 돌면서 이분탐색을 통해 자리를 찾아나가는 방법이다.

dp의 크기는 최대 길이인 nums의 length로 하고, 만들어진 길이는 0으로 초기화한다.

이제 전체 nums를 하나씩 돌면서 자리를 찾아나간다.

left에는 시작인 0, right에는 현재 만들어진 길이를 넣고 left가 right보다 작을 동안 반복문을 돌린다. 

직접 디버깅해 보는 것을 추천한다.. 

TIL

• 이분탐색의 새로운 방법을 알았다.