99클럽 코테 스터디 _ 22일차 TIL (동적 계획법, 이분 탐색)

 

< 문제 >

[백준] 11053. 가장 긴 증가하는 부분 수열 / 실버2

---

< 풀이 >

Dynamic Programming
시간복잡도 : O(N^2)

 

 

코드 변수 정의

• l : 수열의 길이
• A : 정수로 이루어진 수열

def lis(l, A):
    # dp[i]: A[i]를 마지막 원소로 가지는 최장 증가 부분 수열의 길이
    dp = [1] * l  # 모든 원소는 최소 1개의 길이를 가짐

    # 모든 i에 대해 이전 원소들과 비교
    for i in range(1, l):
        for j in range(i):
            # A[j]가 A[i]보다 작다면, A[i]를 A[j] 뒤에 붙일 수 있음
            if A[i] > A[j]:
                dp[i] = max(dp[i], dp[j] + 1)  # 더 긴 길이 선택

    return max(dp)  # 최장 증가 부분 수열의 길이 반환

def main():
    l = int(input())
    A = list(map(int, input().split()))
    print(lis(l, A))

if __name__ == "__main__":
    main()

 

 

 

풀이 방식

 

최장 증가 부분 수열(Longest Increasing Subsequence, LIS)의 길이를 찾는 문제로 DP 알고리즘으로 구현

예시 ) A = [10, 20, 10, 30, 20, 50] 인 경우, LIS는 [10, 20, 30, 50] 이며 길이는 4 이다.

 

1. dp 테이블 초기화
   • dp[i]는 A[i]를 마지막 원소로 하는 LIS의 길이를 저장한다.
   • dp[i] 초기값은 1로 설정한다. (각 원소는 최소한 자기 자신 하나로 구성된 부분 수열이 가능하기 때문에)
2. dp 테이블 갱신
   • 이중 반복문을 사용하여 A[i] 앞의 원소 A[j] ( j < i )와 비교한다.
   • A[i] > A[j] 인 경우, A[j]를 포함한 증가 부분 수열을 만들 수 있다.
   • dp[i]는 max(dp[i], dp[j] + 1) 로 갱신한다.
     • 예시
     • dp = [1, 1, 1, 1, 1, 1]
       

       • i	A[i]	j 값 비교 (A[j])	갱신 여부	dp 변화
         1	20	10 (j=0)	O	[1, 2, 1, 1, 1, 1]
         2	10	10 (j=0), 20 (j=1)	X	[1, 2, 1, 1, 1, 1]
         3	30	10 (j=0), 20 (j=1), 10 (j=2)	O O	[1, 2, 1, 3, 1, 1]
         4	20	10 (j=0), 20 (j=1), 10 (j=2), 30 (j=3)	O X O	[1, 2, 1, 3, 2, 1]
         5	50	10 (j=0), 20 (j=1), 10 (j=2), 30 (j=3), 20 (j=4)	O O O O	[1, 2, 1, 3, 2, 4]

3. 최댓값 반환
   • 모든 dp 값 중 최댓값이 전체 수열의 최장 증가 부분 수열의 길이가 된다.

 

---

< 회고 >

 

이진 탐색으로 시간 복잡도를 줄일 수 있다.

• bisect 모듈을 활용하여 LIS를 구성하는 배열을 유지하며 최적의 위치를 찾는 방식

 

Bisect
시간 복잡도 : O(N logN)

from bisect import bisect_left

def lis_optimized(l, A):
    sub = []  # LIS를 유지하는 배열

    for num in A:
        idx = bisect_left(sub, num)  # num이 들어갈 위치 탐색

        if idx == len(sub):
            sub.append(num)  # num이 LIS의 가장 큰 값이면 추가
        else:
            sub[idx] = num  # LIS 내 적절한 위치의 값을 num으로 대체

    return len(sub)  # LIS의 길이 반환

def main():
    l = int(input())
    A = list(map(int, input().split()))
    print(lis_optimized(l, A))

if __name__ == "__main__":
    main()

 

실행 과정

 

예시) l = 6, A = [10, 20, 10, 30, 20, 50]

1. 초기 sub = []
2. 10 추가  →   [10]
3. 20 추가  →   [10, 20]
4. 10 대체  →   [10, 20]  (기존 10은 10으로 대체)
5. 30 추가  →   [10, 20, 30]
6. 20 대체  →   [10, 20, 30]  (기존 20은 20으로 대체)
7. 50 추가  →   [10, 20, 30, 50]

LIS 길이 = 4