백준 문제 : 가장 긴 증가하는 부분 수열(LIS) [Dynamic Programming /Binary Search, 실버 2단계, python]

문제

수열 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

문제풀이

수열이 주어졌다.

수열에서 몇 개의 수를 순서를 유지한채 뽑았을 때(부분 수열), 뽑은 수들이 증가하도록 하고 싶다.

이때 가장 많이 뽑을 수 있는 수의 개수를 구한다.

ex) 5 2 5 3 4 1 6 -> 이 수열에서 순서를 유지하며 증가하게 부분 수열을 만들었을 때 -> [1,6], [2,3,4,6] ... 등등

 

이때 증가하는 부분 수열은 (1,2,5) 마지막 원소를 제외해도 (1,2) 증가하는 부분 수열이다.

여기서 마지막 원소 (5)를 붙인다면 5보다 앞에있고, 5보다 작은 수로 끝나는 가장 긴 부분 수열에 붙인다.

즉, 지금까지 만들어놓은 증가수열에 수를 추가하려면,

만들어놓은 증가 수열이 추가하려는 수보다 앞에 있어야하고,

마지막 수가 추가하려는 수보다 작아야한다.

 

 

정답 코드 - 2가지 유형

 

[다이나믹 프로그래밍 유형으로 풀기]

 

x = 수열 A의 크기

arr = 수열 A를 이루고 있는 A(i)를 담은 배열

dp = arr[i]를 마지막 원소로 가질 때 가장 긴 증가하는 부분 수열의 길이

x = int(input())

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

dp = [1 for i in range(x)] # 1로 초기화 하는 이유: 첫 시작으로 어떤 수를 넣든 수열길이가 1이됨

# i가 증가하는 순서대로 
for i in range(x):
    for j in range(i):
        if arr[i] > arr[j]:
            dp[i] = max(dp[i], dp[j]+1) # +1인 이유: j까지 온 가장 긴 부분수열에서 하나를 더 추가해서

print(max(dp))

1. dp[i]의 값을 1로 초기화

2. 현재 위치(i)보다 이전에 있는 원소(j)가 작은지 확인한다. (크거나 같으면 가장 긴 증가하는 부분 수열이 될 수 없음)

3. 작다면, 현재 위치의 이전 숫자 중, dp 최댓값을 구하고 그 길이에 1을 더해주면 된다.

 

이분 탐색

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

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

또 다른 문제임. 문제와 입/출력 결과값 똑같지만 이분탐색으로 품. 골드 4단계

import bisect

x = int(input())
arr = list(map(int, input().split()))

dp = [arr[0]]

for i in range(x):
    if arr[i] > dp[-1]:
        dp.append(arr[i])
    else:
        idx = bisect.bisect_left(dp, arr[i])
        dp[idx] = arr[i]

print(len(dp))

 

 

 

https://www.youtube.com/watch?v=sYh62pujaH8 << 강의 들으며 이해 및 참고