[Python/파이썬] 백준 알고리즘 11053번 - 가장 긴 증가하는 부분 수열 (DP)

 

 

 

<풀이>

사실 이 문제를 볼 때 부분 수열을 만들 때 기존 수열의 순서를 그대로 따라야하는지가 헷갈렸다.

 

하지만 그렇다면 그냥 set으로 중복을 제거하고 수를 구하면 될 것이다...

그래서 아마 이것은 아니겠지 하고 풀었다.

 

처음에는 완전 탐색으로 풀 생각을 했다..

"""
1. 아이디어
- 가장 작은 수 하나를 구한다
    - 이후 뒤 수열을 for문으로 돌며 큰 수를 찾는다.

2. 시간 복잡도
- 두개의 포인터 : O(N)
- 전체 조회 : O(N^2) = 1,000,000        -> 가능

3. 변수
- N : int
- A : int[]
"""
import sys

input = sys.stdin.readline

N = int(input())

A = list(map(int, input().split()))

max_length = 0

for i in range(N):
    min_value = A[i]
    new_rs_length = 1
    for j in range(i + 1, N):
        if A[j] > min_value:
            min_value = A[j]
            new_rs_length += 1

    max_length = max(max_length, new_rs_length)

print(max_length)

인덱스 0부터 for문을 돌며 하나를 기준으로 잡고 해당 숫자가 전체 수열의 시작점이라고 가정했을 때 증가하는 수열의 길이를 구해서 가장 큰 길이인 max_length를 구하는 방식으로 작성하였다.

 

하지만 놓친 부분이 있었다.

위와 같이 코드를 짜면 {10, 30, 20, 30, 40} 과 같은 수열이 있을 때 가장 긴 수열의 길이를 3으로 구한다는 것이었다.

한 시작점을 최소값을 가정하고 뒤에 값을 비교할 때 문제가 있었는데, 10을 최소로 가정하고 30을 받는 과정에서 min_value가 30이 되어버려 {10, 30, 40} 을 가장 긴 증가 수열로 인식하기 때문이었다.

 

이를 해결하기 위해서 우선 문제를 잘게 쪼갤 필요가 있었다.

 

바로 DP를 이용한 풀이었다.

메모이제이션과 반복문을 사용해서 구현하는 Bottom-Up 방식의 DP를 이용해 풀어보겠다.

 

DP의 핵심은 큰 문제를 작은 문제로 쪼개서 재귀적 구조를 활용할 수 있는 점화식을 만드는 것이다.

이를 통해 얻은 작은 문제를 해결하는 방법으로 전체의 큰 문제를 해결해야한다.

 

우선 위 문제를 쪼개보면 받은 전체 수열의 길이를 쪼개는 방식을 생각해볼 수 있다.

수열의 길이가 1일 때부터 N일 때까지 올려가며 각각의 수열에서 최대 길이를 갖는 수열의 길이를 구하는 것이다.

이를 재활용하여 큰 전체 문제에 활용해야하기 때문에 각각의 결과값은 메모이제이션한다.

 

코드로 구현하면 아래와 같다.

"""
1. 아이디어
- DP
- 수열의 길이를 1부터 N까지 증가시켜가며 각각의 최대 길이 수열 값을 저장한다.

2. 시간 복잡도
- O(N^2) : 1,000,000       -> 가능

3. 변수
- N : int
- A : int[]
- longest_length : int[]
"""
import sys

input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))

longest_length = [1] * N

for i in range(N):
    for j in range(i):
        if A[i] > A[j]:
            longest_length[i] = max(longest_length[i], longest_length[j] + 1)

print(max(longest_length))

첫번째 for문이 의미하는 바는 "해당 인덱스까지 수열이 있다고 가정 한다"이다.

그렇게 하나씩 숫자를 추가해가며 가장 긴 수열의 길이를 찾아나가는 것이다.

 

두번째 for문을 통해 정해진 수열 범위에서 새로 추가된 숫자보다 작은 수를 발견했을 때 저장해둔 최대 길이를 가져와 활용한다.(메모이제이션)

 

최종적으로 longest_length 배열의 최대값을 출력한다.

 

 

 

<핵심 정리>

1. 문제를 정확히 파악하는 것이 무엇보다 중요하다.

2. 문제가 복잡하다면 쪼개서 푸는 방법을 생각해보자.