백준 11053 파이썬 - 가장 긴 증가하는 부분 수열 - 동적 계획법, LIS

백준 11053 파이썬

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

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

이번 문제는 수열의 가장 긴 증가하는 부분 수열의 길이를 구하는 문제이다. LIS(Longest Increasing Subsequence)라고 한다.

A라는 수열 {10, 20, 10, 30, 20, 50}이 있다면 {10, 20, 10, 30, 20, 50}이 가장 긴 부분 수열이다.

 

이번 문제는 집합에서 현재 위치까지 가장 긴 부분 수열의 길이를 기억하는 방법을 어떻게 저장할지가 관건이다. 집합전체 중 가장 긴 수열이기 때문에... 집합의 위치중 가장 긴 값을 출력하거나... 가장 긴 값을 유지하면서 최종적으로 값을 출력하는 방법 두가지가 있다.

 

 

Python 풀이 1

해당 풀이는 집합의 위치별로 가장 긴 증가하는 부분 수열을 저장하고 최종적으로 최대값을 출력하는 방식이다.

import sys
read = sys.stdin.readline

N = int(read())
A = [0] + list(map(int, read().split()))
cache = [0] * (N+1)
cache[1] = 1

for i in range(2, N+1):
    temp = []
    for j in range(1, i):
        if A[j] < A[i]:
            temp.append(cache[j])
    cache[i] = max(temp) + 1 if temp else 1
print(max(cache))

• 캐시의 가장 최초값은 길이가 1이기 때문에 1로 저장한다.
• 2부터 집합의 마지막까지... 현재 보다 이전 위치의 숫자가 적은 경우... 해당 위치에서의 가장 긴 수열의 길이 값을 리스트에 임시로 추가한다.
  • 메모이제이션 캐시값은 현재 위치보다 적은 숫자를 갖고 있는 전 위치의 가장 긴 증가하는 부분 수열의 길이에 +1한 값이다.

 

 

Python 풀이 2

풀이1의 경우 매번 for문을 2개 사용하는데.... 해당 위치까지 확인해줘야한다. 그래서 집합의 크기가 커질수록 시간도 오래 걸린다. 이번 풀이에서도 for문을 2개 사용하지만... 이전 위치가 아닌... 가장 긴 부분 수열의 크기를 기준으로하는 리스트를 생성해서 사용한다.

import sys
read = sys.stdin.readline

N = int(read())
seq = list(map(int, read().split()))

counts = [seq[0]]
for i in range(1, N):
    if counts[-1] < seq[i]:
        counts.append(seq[i])
    else:
        idx = 0
        for j in range(len(counts)):
            if counts[j] < seq[i]:
                idx += 1
            else:
                counts[idx] = seq[i]
                break
print(len(counts))

• 초기 값으로 첫번 째 수를 counts 리스트에 넣어준다.
• 주어진 수열의 숫자를 확인하는데 두가지 조건으로 분기한다.
  • counts 수열의 마지막 숫자보다 크면 리스트에 추가한다.
  • 마지막 수열보다 작으면 counts를 순회하면서 교체할 숫자를 찾는다.
    • 오름차순을 유지하고 위치를 찾으면 더 큰 숫자와 자리를 교체한다.
      
      • 더 긴 수열을 수열이 만들어 질 수 있기 때문에 큰 숫자와 교체한다.
• 최종적으로 리스트의 길이를 반환한다.

 

리스트의 숫자들을 계속 교체해주는 이유는 더 긴 길이의 수열이 있는지 확인하기 위함이다.

A = {7, 8, 9, 1, 2, 3, 4} 답은 1,2,3,4 길이 4 이다.

가장 크고 작은 숫자를 기준으로 무언가 구분했다면... 앞에 7, 8, 9 까지 추가하다가 뒤에 추가하지 못하는 경우가 발생할 수 있다. 이렇게 숫자를 위치에 맞게 교체해간다면 중간 이후에 있는 더 긴 길이의 부분 수열을 잡아낼 수 있다.