Algorithm/CH 5. 응용 문제

1. 백준 11053

bellmake 2025. 1. 4. 10:52

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

 

아래에서는 가장 긴 증가하는 부분 수열(LIS; Longest Increasing Subsequence)을 구하는 전형적인 동적 프로그래밍(DP) 풀이 방법(O(N^2) 접근)과 그 과정에 대해 상세히 설명하고, 이어서 파이썬 예시 코드를 제시하겠습니다.

1. 문제 이해

  • 가장 긴 증가하는 부분 수열이란, 주어진 수열에서 일부 항을 골라내어 만든 부분 수열 중, 그 항들이 엄격하게 증가하는(뒤에 나오는 원소가 앞의 원소보다 항상 큰) 부분 수열 중 가장 긴 것의 길이를 의미합니다.
  • 예시: A = [10, 20, 10, 30, 20, 50]
    • 길이가 4인 가장 긴 증가하는 부분 수열은 [10, 20, 30, 50] 등이 있습니다(여러 개가 존재할 수 있지만 길이는 동일).

2. 해결 아이디어 (동적 프로그래밍 O(N^2) 방법)

  1. 길이가 N인 1차원 배열 dp를 준비합니다.
    • dp[i]는 **"A[i]로 끝나는 가장 긴 증가하는 부분 수열의 길이"**를 저장합니다.
    • 초기에 모든 dp[i]를 1로 초기화하는데, 이는 최소한 자기 자신만 뽑았을 때 부분 수열의 길이는 1이기 때문입니다.
  2. dp[i]를 구하기 위해서는, i보다 앞에 있는 모든 인덱스 j(0 ≤ j < i)에 대해 다음을 확인합니다.
    • 만약 A[j] < A[i]라면, A[j] 뒤에 A[i]를 붙여서 부분 수열을 만들 수 있으므로, dp[i]=max⁡(dp[i], dp[j]+1) dp[i] = \max(dp[i],\ dp[j] + 1)
    • 이 과정을 통해 dp[i]를 최대로 갱신할 수 있습니다.
  3. 모든 i(0부터 N-1까지)에 대해 위 과정을 마치면, dp 배열 중 최댓값이 곧 가장 긴 증가하는 부분 수열의 길이가 됩니다.

2.1 예시로 살펴보기

  • A = [10, 20, 10, 30, 20, 50]
    초기 상태: dp = [1, 1, 1, 1, 1, 1] (각 원소가 자기 자신만 포함하는 부분 수열 길이는 1)
  1. i = 0
    • 앞에 원소가 없으므로 dp[0] = 1
  2. i = 1 (A[1] = 20)
    • j = 0 (A[0] = 10)
      • A[0] < A[1] → 10 < 20
        • dp[1] = max(dp[1], dp[0] + 1) = max(1, 1+1) = 2
    • 결과: dp = [1, 2, 1, 1, 1, 1]
  3. i = 2 (A[2] = 10)
    • j = 0 (A[0] = 10) → 10 < 10 (거짓)
    • j = 1 (A[1] = 20) → 20 < 10 (거짓)
    • 아무 업데이트 없음.
    • 결과: dp = [1, 2, 1, 1, 1, 1]
  4. i = 3 (A[3] = 30)
    • j = 0 (A[0] = 10) → 10 < 30
      • dp[3] = max(dp[3], dp[0] + 1) = max(1, 1+1) = 2
    • j = 1 (A[1] = 20) → 20 < 30
      • dp[3] = max(dp[3], dp[1] + 1) = max(2, 2+1) = 3
    • j = 2 (A[2] = 10) → 10 < 30
      • dp[3] = max(dp[3], dp[2] + 1) = max(3, 1+1) = 3 (이미 3이 큼)
    • 결과: dp = [1, 2, 1, 3, 1, 1]
  5. i = 4 (A[4] = 20)
    • j = 0 (A[0] = 10) → 10 < 20
      • dp[4] = max(dp[4], dp[0] + 1) = max(1, 1+1) = 2
    • j = 1 (A[1] = 20) → 20 < 20 (거짓)
    • j = 2 (A[2] = 10) → 10 < 20
      • dp[4] = max(dp[4], dp[2] + 1) = max(2, 1+1) = 2 (동일)
    • j = 3 (A[3] = 30) → 30 < 20 (거짓)
    • 결과: dp = [1, 2, 1, 3, 2, 1]
  6. i = 5 (A[5] = 50)
    • j = 0 (10 < 50) → dp[5] = max(1, dp[0]+1) = 2
    • j = 1 (20 < 50) → dp[5] = max(2, dp[1]+1) = max(2, 2+1) = 3
    • j = 2 (10 < 50) → dp[5] = max(3, dp[2]+1) = max(3, 1+1) = 3
    • j = 3 (30 < 50) → dp[5] = max(3, dp[3]+1) = max(3, 3+1) = 4
    • j = 4 (20 < 50) → dp[5] = max(4, dp[4]+1) = max(4, 2+1) = 4
    • 결과: dp = [1, 2, 1, 3, 2, 4]
  • 최종 dp 배열은 [1, 2, 1, 3, 2, 4]이고, 이 중 최댓값은 4입니다.

3. 파이썬 코드 구현 (O(N^2) 풀이)

 
def lis_length(sequence):
    N = len(sequence)
    dp = [1] * N  # 각 위치에서의 LIS 길이를 저장할 배열

    for i in range(N):
        for j in range(i):
            if sequence[j] < sequence[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    
    return max(dp)

# 메인 함수 역할
if __name__ == "__main__":
    N = int(input().strip())
    A = list(map(int, input().split()))
    
    print(lis_length(A))

코드 설명

  1. dp = [1] * N
    • 각 인덱스 i에 대해, 수열 A[i] 하나만 있는 부분 수열은 항상 길이 1이므로 초기값을 1로 설정합니다.
  2. 2중 for문으로 i와 j를 순회하며 업데이트
    • for i in range(N):
      • for j in range(i):
        • 조건: 만약 sequence[j] < sequence[i]라면, 즉 증가 관계를 만족한다면
          • dp[i] = max(dp[i], dp[j] + 1)
        • 이전 인덱스 j에서의 가장 긴 증가하는 부분 수열에 자기 자신(인덱스 i 원소)을 이어붙일 수 있으므로 길이 갱신을 해줍니다.
  3. 최종적으로 max(dp) 값을 구하면, 가장 긴 증가하는 부분 수열의 길이가 됩니다.

4. 시간 복잡도

  • 이중 반복문을 사용하므로, O(N2)\mathcal{O}(N^2)의 시간 복잡도를 가집니다.
  • N의 최대 크기가 1,000이므로, O(1,0002)=O(1,000,000)\mathcal{O}(1,000^2) = \mathcal{O}(1,000,000) 정도는 충분히 계산 가능합니다.

5. 정리

  • 가장 긴 증가하는 부분 수열(LIS) 문제는 동적 프로그래밍으로 쉽게 접근 가능하며, 문제에서 요구하는 N의 최대 범위(1,000)에서는 O(N2)\mathcal{O}(N^2) 방식으로도 충분히 풀 수 있습니다.
  • 만약 N의 범위가 매우 커진다면, 이진 탐색을 활용한 O(Nlog⁡N)\mathcal{O}(N \log N) 방법을 추가로 공부하시는 것이 좋습니다.