[Algorithm] BaekJoon : 11053. 가장 긴 증가하는 부분 수열 by Python

[문제 바로가기] https://www.acmicpc.net/problem/11053

📌문제 설명

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

---

💡 문제 풀이

LIS(Longest Increasing Subsequence) 알고리즘으로 해결한 문제

간단한 문제지만 LIS가 워낙 유명한 알고리즘인만큼 복습하고자 글을 적었다.

LIS는 완전탐색, DP, 이진탐색으로 구현이 가능하다고 한다.
그중 보편적으로 DP가 최적화하기 가장 좋다고 하여서 DP를 이용하여 문제를 해결했다.

step 1)
변수 선언

• LIS : DP 테이블

step 2)
주어진 숫자의 배열(numbers)에서 인덱스를 하나씩 늘려 LIS를 찾는다.
이 때, 인덱스는 1부터 N까지 진행한다.
※0번째 인덱스의 숫자는 길이가 무조건 1이기 때문!

step 3)
이중반복문을 이용하여 길이를 찾으려는 숫자(step 2에서 인덱스가 가리키는 숫자)의 이전 값들과 비교하여 LIS 배열값을 최신화한다.

※핵심 : 길이를 찾으려는 숫자가 비교할 숫자보다 크면, 그 숫자가 가지고 있는 길이+1과 자신이 길이를 비교해서 큰 값으로 최신화 한다.

코드는 다음과 같다.

import sys

N = int(input())
numbers = list(map(int, sys.stdin.readline().split()))
LIS = [1] * N
for i in range(1, N):
    for j in range(i):
        if numbers[i] > numbers[j]:
            LIS[i] = max(LIS[i], LIS[j]+1)

print(max(LIS))

---