[백준] 12015 가장 긴 증가하는 부분 수열 2

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

초기에 2중 반복문을 이용하여 풀이하였으나, 시간 초과 문제가 발생하였습니다.

시간 단축을 위해 고민하던중 '최장 증가 부분 수열 (LIS)' 를 새롭게 학습하여 해결하였습니다.

2) 알고리즘

• 최장 증가 부분 수열 (LIS)

3) 풀이 코드

사용 언어 - Python

import sys
import bisect
sys.stdin = open('input.txt')

N = int(sys.stdin.readline())                               # 수열의 길이
A = list(map(int, sys.stdin.readline().split()))            # 수열
lis = [0]                                                   # 최장 증가 부분 수열(LIS)

for num in A:                                               # 수열 하나씩 확인
    if num > lis[-1]:                                       # LIS의 가장 우측 리스트의 값 보다 현재 값이 더 크면
        lis.append(num)                                     # LIS에 값 추가
    else:
        lis[bisect.bisect_left(lis, num, lo=1)] = num       # 현재 숫자가 LIS 변수에 들어갈 위치 찾기

print(len(lis)-1)

 

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

최초에 반복문을 이용하여 풀이하였으나, 시간초과 문제가 발생하였습니다.

시간 단축을 위한 알고리즘을 생각하는데 어려움을 겪었습니다.

2) 새롭게 학습한 내용

최장 증가 부분 수열 (LIS) 알고리즘에 대해 새롭게 학습하였습니다.

(1) 참고 사이트

• 블로그

---

🔗 문제 링크

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

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

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다