[BOJ] Python 백준 11053번 가장 긴 증가 부분 수열 실버 2

https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

문제 풀이

---

동적 계획법(Dynamic Programming, 이하 DP)을 활용하는 문제였다.

 

DP란 정해진 방식이 있는 게 아니라 큰 문제를 해결하기 위해 문제를 세분화시키고 각각 작은 문제를 해결하여 나온 값들을 이용하는 방식을 총체적으로 지칭하는 알고리즘이다.

 

따라서 이미 연산한 값을 이용함으로써 불필요한 연산을 줄일 수 있다.

 

이것의 대표적인 예시가 피보나치 수열이다.

 

매번 필요한 값을 연산하도록 구현할 수 있지만 DP를 활용하게 되면 획기적으로 연산 횟수가 줄어들기 때문에 더 많은 수열을 구할 수 있다.

 

다시 문제로 돌아와서 문제는 A란 수열에서 원소가 증가하는 부분 수열을 찾는 것이며 각 원소는 연속하지 않아도 된다.

 

해당 문제는 최장 증가 수열(Least Increasing Subsequence) 알고리즘으로 알려져 있으며 DP를 활용하는 기법이기도 하다.

 

문제의 조건은 다음과 같다.

 

1. 수열 A의 크기는 1000 이하다.
2. 각 원소도 1000 이하의 자연수이다.

수열 A의 크기는 1000 이하이므로 O(n^2)의 시간 복잡도도 충분히 연산이 가능하다.

 

바로 전체 코드를 통해 어떻게 DP를 활용했는지 확인해 보자.

 

n=int(input())
sequence=list(map(int,input().split()))
res=[0 for i in range(n)]
res[0]=1
for i in range(1,n):
    cnt=0
    for j in range(0,i):
        if sequence[j]<sequence[i] and cnt<res[j]:
            cnt=res[j]
    res[i]=cnt+1
print(max(res))

 

3번째 줄 res란 리스트가 DP를 활용하는 리스트이기 때문에 핵심 포인트이다.

 

sequence는 원래의 수열 A를 뜻하고 res는 각 원소가 부분 수열의 몇 번째에 해당하는지를 나타낸다.

 

따라서 n만큼 수열의 길이를 입력받으므로 res를 n의 길이만큼 초기화시키고 res의 0번째 인덱스를 1로 한 이유는 0번째 인덱스의 원소가 부분 수열의 첫 번째 원소가 된다는 의미이다.

 

5번째 줄부터 중첩 for문을 사용하는데 버블 정렬과 원리는 비슷하다.

 

첫 번째 for문에서는 1번째 원소부터 n-1번째 원소까지 반복하는데 매번 카운트를 0으로 초기화하고 두 번째 for문에서는 i번째 원소보다 작으면서 카운트보다 res의 원소가 더 크다면 카운트를 갱신한다.

 

즉 해당 원소보다 작은 원소들이 최대한 몇 개 포함될 수 있는지 계산하는 방식이다.

 

두 번째 for문이 끝나면 res의 i번째를 카운트+1로 갱신한다.

 

예를 들어 카운트가 2라면 i번째 인덱스는 3이 되고 i번째 원소보다 작은 원소가 두 개, i번째 원소는 부분 수열의 3번째 원소가 될 수 있다는 의미이다.

 

이렇게 리스트에 몇 번째 원소가 될 수 있는지 카운트함으로써 부분 수열을 일일이 구하지 않아도 최장 길이를 구할 수 있다.

 

결과 화면