Search

BOJ 11053 가장 긴 증가하는 부분 수열

생성일
2024/08/07 02:57
태그
다이나믹 프로그래밍
이번 문제는 LIS(Longest Increasing Subsequence)로 DP의 예제로 잘 알려진 문제입니다. https://www.acmicpc.net/problem/11053

문제 설명

•
크기가 NN인 수열 AA에 대해 가장 긴 증가하는 부분 수열의 길이를 구하는 문제

예제 입력/출력

•
입력1
6 10 20 10 30 20 50
Plain Text
복사
•
출력1
4
Plain Text
복사

제약 조건

•
1≤N<1,0001 ≤ N < 1,000
•
1≤Ai≤1,0001 ≤ A_i ≤ 1,000

문제 풀이

풀이1 브루트 포스 - O(2N)O(2^N)
풀이2 그리디
풀이3 DP - O(N2)O(N^2)

풀이 코드

Bottom-Up 방식
Top-Down 방식

심화 내용

시간 복잡도 개선하기 - O(N⋅logN)O(N \cdot logN)