- O(n^2)의 시간복잡도
- O(nlogn)의 시간복잡도 - 길이만 구하기
- O(nlogn)의 시간복잡도 - 길이와 수열 모두 구하기
1. O(n^2)의 시간복잡도
https://www.acmicpc.net/problem/11053
11053번: 가장 긴 증가하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이
www.acmicpc.net
2. O(nlogn)의 시간복잡도 - 길이만 구하기
https://www.acmicpc.net/problem/12015
12015번: 가장 긴 증가하는 부분 수열 2
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)
www.acmicpc.net
3. O(nlogn)의 시간복잡도 - 길이와 수열 모두 구하기
https://www.acmicpc.net/problem/14003
14003번: 가장 긴 증가하는 부분 수열 5
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)
www.acmicpc.net
https://www.acmicpc.net/problem/3745
3745번: 오름세
입력은 여러개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 주가를 관찰한 날의 수 N (N ≤ 100000)이 주어진다. 둘째 줄에는 관찰한 주가가 첫 날부터 순서대로 주어진다.
www.acmicpc.net
https://www.acmicpc.net/problem/1365
1365번: 꼬인 전깃줄
첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가
www.acmicpc.net
<Reference>
'자료구조 + 알고리즘' 카테고리의 다른 글
| 위상정렬 (Topological Sorting) (0) | 2021.09.14 |
|---|---|
| LCS (Longest Common Subsequence, 최장 공통 부분수열) (0) | 2021.09.14 |
| LCA (Lowest Common Ancestor, 최소공통조상) (0) | 2021.09.14 |
| 문자열 매칭 알고리즘 (0) | 2021.09.14 |
| 최소비용 최대유량 알고리즘 (0) | 2021.09.14 |