[백준/BOJ] 백준 코딩 알고리즘 11053번 가장 긴 증가하는 부분 수열 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

예제 입력 1

6
10 20 10 30 20 50

예제 출력 1

4

 

첫 번째 풀이 (오답)

import sys
input = sys.stdin.readline

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

cnts = [[0] * N for _ in range(N)]
for i in range(N):
  cnts[i][i] = 1
  max_val = A[i]
  for j in range(i + 1, N):
    if A[j] > max_val:
      max_val = A[j]
      cnts[i][j] = cnts[i][j-1] + 1
    else:
      cnts[i][j] = cnts[i][j-1]

maximum = 0
for i in range(N):
  maximum = max(maximum, cnts[i][-1])
print(maximum)

커진 값이  다시 작아졌을 때, LIS이 더 길어질 수 있음을 고려하지 않았기 때문에 풀이 방법이 틀렸다고 나왔다

 

위 설명에 해당하는 반례

입력값:

6
1 2 5 3 4 6

정답: 5

위  코드의 출력값: 4

 

두 번째 풀이 (O(N^2) 풀이)

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
cnts = [0] * N

cnts[0] = 1 
for i in range(1, N):
  maximum = 0
  for j in range(i):
    if A[j] < A[i]:
      maximum = max(maximum, cnts[j])
  cnts[i] = maximum + 1

print(max(cnts))

LIS 길이를 저장하는 배열 cnts를 생성한다

배열의 길이가 1인 경우를 고려하여 맨 처음 초기값 cnts[0] = 1 을 저장한다

 

이후 배열을 순차적으로 순회하며 탐색을 진행한다

2번째 숫자부터 마지막 숫자까지 반복문을 돌고 → O(N)

각 숫자에 따라서, 이전 자리의 숫자 중 자기보다 작은 값을 가진 숫자에 대한 LIS 최대값을 가져와 1을 더한다 → O(N)

 

모든 탐색을 종료하면, cnts 배열의 최대값을 찾아 출력한다.

최종적으로 시간복잡도는 O(N*N + N)이고, 이는 O(N^2)로 표현이 가능하다

 

 

세 번째 풀이 (O(NlogN 풀이)

lower bound를 사용하는 경우로

탐색 시 이분 탐색을 사용하기 때문에 N을 logN으로 줄일 수 있고

최종적으로 NlogN의 시간에 풀이가 가능하다.

 

 

참고: https://seungkwan.tistory.com/8

가장 긴 증가하는 부분 수열 (Longest Increasing Subsequence)

참고: https://duckracoon.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Lower-Bound%EC%99%80-Upper-Bound

[알고리즘] Lower Bound와 Upper Bound