[백준] 12015 가장 긴 증가하는 부분 수열 2 (파이썬)

골드 Ⅱ 

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

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

 

📄 문제

• 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
• 수열 A의 크기는 N (1 ≤ N ≤ 1,000,000)이다.
• 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50}이고, 길이는 4이다.

 

---

💡 아이디어

• 최장 증가 부분 수열(LIS, Longest Increasing Subsequence) 알고리즘을 활용해야 한다.
• 이 문제에서 포인트는 '최장'이라는 것과 '증가'라는 것이다.
• 순서대로 탐색하며 이전 값보다 작은 값이 등장했을 때,
  • 앞서 만들어진 가장 긴 수열의 길이를 저장하고 있어야 한다.
  • 앞서 만들어진 수열의 값도 저장하고 있으며,
  • 새로운 값이 기존 수열의 몇 번째 순서에 오게 되는지도 알아야 한다.

 

1. 수열을 저장할 빈 배열(increase)을 만들어준다.
2. 빈 배열(increase)에 첫 번째 숫자를 넣고 수열을 앞에서부터 차례대로 탐색한다.
3. 새로운 배열(increase)에 담긴 마지막 숫자와 탐색하는 수열의 값을 비교한다.
4. 마지막 숫자보다 탐색 값이 크면 increase 배열에 추가한다.
5. 마지막 숫자보다 탐색 값이 작으면 increase 배열에서 탐색 값이 올 순서를 찾는다.
   • 이분 탐색을 활용한다.
   • 하지만, 정확한 값을 찾아 것이 아니기 때문에 일반적인 이분 탐색과는 다르다.
   • 이 문제(LIS)에서 이분 탐색의 용도는 타깃 값이 해당하는 순서를 찾는 것이다.
   • 즉, 범위에 숫자가 2개 남으면 양쪽을 모두 비교해봐야 한다.
   • 따라서, while의 탐색 범위는 (s <e)이고 e = mid 가 되어야 한다.
6.  increase 배열에서 탐색 값이 올 순서를 찾으면 해당 순서의 값과 바꿔준다.
   • 이렇게 하는 이유는 이전에 찾은 최장 길이를 유지하기 위해서이다.
   • 이전의 최장 길이를 유지하기 위해 안에 값만 바꿔 주는 것이다.
7. 다음에 오는 값도 마지막 숫자보다 작으면 5, 6번을 반복하며 해당 순서를 찾아 바꿔준다.
8. 마지막 탐색이 끝난 뒤 increase 배열의 길이를 구해주면 된다.

 

---

예시

수열 A = {10, 20, 15, 30, 25, 50, 20, 40, 60}가 있다.

for 문으로 수열 A를 탐색하면서 increase 배열의 변화 과정을 살펴볼 것이다.

수열을 첫 번째 수(10)를 increase 배열에 담고 이후 숫자(20)부터 탐색을 시작한다.

 

탐색 값	현재 increase 배열	비교 (마지막값, 탐색 값)	추가/변경	수정된 increase 배열
20	[10]	10 < 20	추가	[10, 20]
15	[10, 20]	20 > 15	변경	[10, 15]
30	[10, 15]	15 < 30	추가	[10, 15, 30]
25	[10, 15, 30]	30 > 25	변경	[10, 15, 25]
50	[10, 15, 25]	25 < 50	추가	[10, 15, 25, 50]
20	[10, 15, 25, 50]	50 > 20	변경	[10, 15, 20, 50]
40	[10, 15, 20, 50]	50 > 40	변경	[10, 15, 20, 40]
60	[10, 15, 20, 40]	40 < 60	추가	[10, 15, 20, 40, 60]

 

---

 

최장 증가 부분 수열(LIS, Longest Increasing Subsequence) 알고리즘

간단히 말해, 가장 긴 증가하는 부분 수열을 찾는 알고리즘이다.

 

2가지 풀이 유형이 존재한다.

 

1. Dynamic Programming
   • 시간복잡도는 O(n^2)이다.
   • 인풋 값이 1,000,000개 정도만 되어도 O(n^2)의 알고리즘은 실행시간이 10초 이상 소요된다.
2. Binary Search(Logarthmic Search Algorithm)
   • 시간복잡도를 개선하기 위하여 LIS를 구성할 때 이분탐색을 활용한다.
   • 이분탐색은 일반적으로 시간복잡도가 O(log n)이다.
   • 이분탐색을 활용한 LIS의 길이 구하기의 시간복잡도는 O(nlog n)으로 개선시킬 수 있다.

 

https://bu119.tistory.com/50

[알고리즘] 최장 증가 부분 수열(LIS) 알고리즘

 

📝 문제 풀이 (Code)

import sys
input = sys.stdin.readline

def binary_search(target):
    s = 0
    e = len(increase) - 1

    # target 값과 같거나 큰 가장 작은 값을 찾아야 하기 때문에 일반 이분 탐색과는 조건이 살짝 다르다.
    while s < e:
        mid = (s + e) // 2

        if increase[mid] == target:
            return mid

        elif increase[mid] > target:
            e = mid
        else:
            s = mid + 1

    return e


n = int(input())
arr = list(map(int,input().split()))
increase = [arr[0]]

for i in range(1, n):
    if increase[-1] < arr[i]:
        increase.append(arr[i])
    elif increase[-1] > arr[i]:
        idx = binary_search(arr[i])
        increase[idx] = arr[i]

print(len(increase))

 

구조만 다른 코드

• 이분 탐색을 함수로 안 만들었다.
• increase 배열의 초기값을 수열의 첫 번째 값이 아닌 0으로 두었다.

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int,input().split()))
increase = [0]

for num in arr:
    if increase[-1] < num:
        increase.append(num)

    elif increase[-1] > num:
        s = 0
        e = len(increase) - 1

        # num값과 같거나 큰 가장 작은 값을 찾아야 하기 때문에 일반 이분 탐색과는 조건이 살짝 다르다.
        while s < e:
            mid = (s + e) // 2

            if increase[mid] < num:
                s = mid + 1
            else:
                e = mid

        increase[e] = num

print(len(increase)-1)