[Leetcode 아주 상세한 문제풀이] 300. Longest Increasing Subsequence – 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 300번 문제 Longest Increasing Subsequence 다.

우선 문제를 살펴보자.

 

리트코드 300번 문제 Longest Increasing Subsequence 링크

Longest Increasing Subsequence - LeetCode

Longest Increasing Subsequence - LeetCode

 

 

Given an integer array nums, return the length of the longest strictly increasing subsequence.

Example 1:
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2:
Input: nums = [0,1,0,3,2,3]
Output: 4

Example 3:
Input: nums = [7,7,7,7,7,7,7]
Output: 1
 
Constraints:
1 <= nums.length <= 2500
-104 <= nums[i] <= 104

 

 

문제 설명

문제를 간략히 살펴보자. 인풋으로 정수로 이루어진 배열이 주어진다. 이때 '엄격하게' 오름차순인 subsequence 중 길이가 가장 긴 것을 찾아 그 길이를 리턴하라는 문제다. 문제 예시 1번을 보면 인풋으로 [10,9,2,5,3,7,101,18] 배열이 주어졌다. 이 배열에서 만들 수 있는 오름차순 subsequence은 여러가지다. 이 중에서 우선 오름차순은 subsequence를 찾아야 한다. 그리고 그 subsequence 중 길이가 가장 긴 것을 찾아 그 길이를 리턴해야 한다. 이 경우 subsequence 중 2, 3, 7, 101을 (혹은 2, 3, 7, 18)을 선택하면 엄격하게 오름차순인 subsequence가 성립된다. 따라서 이때 subsequence의 길이를 4를 리턴하면 된다. 문제를 이해하는데 어렵지 않으므로 곧바로 문제를 풀어보자.

 

 

문제 접근법

이 문제를 해결하기 위해 우리는 dynamic programming을 이용할 것이다.

우리는 dp라는 배열을 만들 것인데 이때 dp[i]는 index i에 해당하는 element로 끝나는 가장 긴 오름차순 subseqeunce의 길이 의미한다.

좀 더 구체적으로 우리는 다음과 같이 접근할 것이다.

1) dp 배열을 입력받은 인풋 배열과 같은 길이로 만들어 1로 초기화한다. 가장 짧은 subsequence 길이가 1이기 때문이다.

2) 주어진 인풋 배열을 탐색한다. 탐색하는 element에 대하여 그 이전에 탐색했던 element를 가지고 오름차순 배열을 만들 수 있는지 확인한다.

3) 탐색을 마치고 나면 dp[i]에 해당 index의 element로 끝나는 가장 긴 오름차순 subsequence의 길이를 업데이트 한다.

4) 주어진 인풋 배열의 모든 element를 탐색 후 dp 배열에서 가장 큰 값을 리턴한다. dp 배열에서 각 element로 끝나는 가장 긴 오름차순 subsequence의 길이가 업데이트 되어 있다. 따라서 그 중 가장 큰 값이 인풋 배열에서 만들 수 있는 가장 긴 오름차순 subsequence의 길이가 된다.

이제 코드로 한 번 살펴보자

 

 

문제 풀이

인풋 배열을 입력받을 함수를 정의해 준다. (line 1)

만약 입력받은 인풋 배열이 비어있다면 0을 리턴하고 종료한다. (line 2-3)

이 경우 가장 긴 오름차순 subsequence가 존재하지 않기 때문이다.

앞서 설명한대로 인풋 배열 길이만큼 dp 배열을 만들어준다. (line 5)

이때 dp 배열은 1로 초기화해준다.

우리는 인풋 배열의 1번 인덱스부터 for loop를 이용해 탐색한다. (line 7)

0번 인덱스 부터 탐색하면 그 element 하나밖에 존재하기 않기 때문에 dp의 초기값과 같아지기 때문이다.

그 후 해당 인덱스 이전에 탐색했던 element 들을 for loop를 이용하여 탐색한다. (line 8)

만약 현재 탐색하고 있는 element가 이전에 탐색했던 element 보다 큰 경우 우리가 찾고있는 경우다. (line 9)

따라서 이 경우 dp 배열의 해당 인덱스를 업데이트 해준다. (line 10)

이때 우리는 i) 해당 인덱스의 element를 마지막으로 하는 최대 길이 subsequence (dp[i])와 ii) 이전 인덱스의 element를 마지막으로 하는 최대 길이 subsequence (dp[j]))에 1을 더한 (현재 탐색하는 (i 인덱스) element를 포함한 subsequence 길이 중 더 큰 값을 선택한다.

이 모든 과정을 마치고 나면 dp 배열의 각 인덱스에 해당 인덱스의 element를 마지막으로 하는 가장 긴 오름차순 subsequence의 길이가 업데이트 되어있다.

따라서 우리는 전체 인풋 배열에서 만들 수 있는 가장 긴 오름차순 subsequence를 찾는 것이므로 dp 중 가장 큰 값을 리턴하고 종료한다. (line 12)

 

 

문제 풀이 코드

def lengthOfLIS(nums):
    if not nums:
        return 0
 
    dp = [1] * len(nums)
 
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
 
    return max(dp)
 
# Test the function with the provided examples
print(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]))  # Output: 4
print(lengthOfLIS([0, 1, 0, 3, 2, 3]))            # Output: 4
print(lengthOfLIS([7, 7, 7, 7, 7, 7, 7]))         # Output: 1
 

 

 

관련 문제

리트코드 55번 Jump game 문제 풀이 링크

리트코드 62번 Unique paths 문제 풀이 링크

리트코드 70번 Climing stairs 문제 풀이 링크

리트코드 91번 Decode ways 문제 풀이 링크

리트코드 139번 Work break problem 문제 풀이 링크

리트코드 198번 House robber 문제 풀이 링크

리트코드 213번 House robber II 문제 풀이 링크

리트코드 322번 Coin change 문제 풀이 링크

리트코드 1143번 Largest Common Subsequence 문제 풀이 링크

 

300.&nbsp;Longest Increasing Subsequence