Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

Python으로 길이가 k인 엄격하게 증가하는 부분 수열의 개수 구하기

문제 이해하기

숫자로 이루어진 리스트 nums와 정수 k가 주어졌을 때, 길이가 정확히 k이면서 엄격하게(strictly) 증가하는 부분 수열의 개수를 구하는 프로그램을 작성해 보겠습니다.

여기서 '엄격하게 증가한다'는 것은 부분 수열 내에서 앞의 원소가 항상 뒤의 원소보다 작아야 한다는 의미입니다. 만약 정답이 매우 커질 수 있다면, 결과를 10^9 + 7로 나눈 나머지를 반환해야 합니다.

예를 들어 입력이 다음과 같다고 가정해 봅시다.

  • nums = [2, 3, 4, 1]
  • k = 2

이 경우 길이가 2인 증가 부분 수열은 [2, 3], [3, 4], [2, 4]의 세 가지이므로 출력은 3이 됩니다.

풀이 접근 방식: 동적 계획법(DP)

이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 각 원소를 부분 수열의 마지막 원소로 삼는 경우의 수를 단계별로 누적해 나가는 방식입니다.

구체적인 알고리즘 단계는 다음과 같습니다.

  • 모듈러 값 m := 10^9 + 7로 설정합니다.
  • dp := nums와 같은 크기의 리스트를 만들고 모든 값을 1로 초기화합니다. (각 원소 하나만으로 이루어진 길이 1짜리 수열을 의미)
  • 다음 과정을 k번 반복합니다.
    • j를 dp의 마지막 인덱스부터 0까지 거꾸로 순회하며:
      • dp[j] := 0으로 초기화한 뒤,
      • i를 0부터 j-1까지 순회하면서 nums[i] < nums[j]를 만족하면 dp[j]에 dp[i]를 더해 누적합니다.
  • 최종적으로 dp 리스트의 모든 원소의 합을 m으로 나눈 나머지를 반환합니다.

바깥 반복문을 k번 돌리는 이유는, DP 배열을 한 번 갱신할 때마다 부분 수열의 길이가 1씩 늘어나기 때문입니다. 따라서 k번째 반복이 끝난 시점의 dp[j]에는 'j번째 원소로 끝나는 길이 k의 증가 부분 수열의 개수'가 저장됩니다.

Python 구현 예제

아래 코드를 통해 실제 구현을 확인해 보겠습니다.

class Solution:
    def solve(self, nums, k):
        m = 10 ** 9 + 7
        dp = [1] * len(nums)
        for _ in range(k - 1):
            for j in range(len(dp) - 1, -1, -1):
                dp[j] = 0
                for i in range(j):
                    if nums[i] < nums[j]:
                        dp[j] += dp[i]
    return sum(dp) % m

ob = Solution()
nums = [2, 3, 4, 1]
k = 2
print(ob.solve(nums, k))

입력

[2, 3, 4, 1], 2

출력

3

동작 과정 살펴보기

입력 nums = [2, 3, 4, 1], k = 2일 때 코드의 실행 흐름을 단계별로 확인해 보겠습니다.

  1. 초기 상태: dp = [1, 1, 1, 1] (길이 1짜리 부분 수열)
  2. 첫 번째 갱신(k=2를 위해 k-1=1회 실행):
    • j=3: nums[3]=1보다 작은 앞 원소가 없으므로 dp[3]=0
    • j=2: nums[0]=2, nums[1]=3이 4보다 작으므로 dp[2]=dp[0]+dp[1]=2
    • j=1: nums[0]=2가 3보다 작으므로 dp[1]=dp[0]=1
    • j=0: 앞 원소가 없으므로 dp[0]=0
  3. 갱신 후 dp = [0, 1, 2, 0], 합계는 3

결과적으로 3이 출력되며, 이는 [2, 3], [3, 4], [2, 4] 세 가지 부분 수열과 정확히 일치합니다.

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 O(n² × k)입니다. 바깥 루프가 k번 실행되고, 각 반복마다 두 개의 중첩 루프(i, j)가 n²번 연산을 수행하기 때문입니다. 공간 복잡도는 dp 배열 하나만 사용하므로 O(n)입니다.

n이 수천 수준이라면 충분히 빠르게 동작하지만, n이 매우 크다면 펜윅 트리(Fenwick Tree) 등을 활용한 최적화를 고려할 수 있습니다.