교대최소제곱법
[백준 파이썬 12015번 가장 긴 증가하는 부분 수열 2] DP, Bisect 본문
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
풀이방법
- DP를 활용한다
- 시간복잡도 O(N^2) : N < 10^4
- 타겟 수열의 원소까지 알 수 있다 -> dp를 구하고 dp의 크기 역순으로 index 접근
- bisect 라이브러리의 bisect_left 함수를 활용
- 시간복잡도 O(N logN) : N < 10^6
타겟 수열의 원소는 알 수 없다
가장 긴 증가하는 부분 수열(LIS) 완전 정복 - 백준 파이썬
최근 들어, 알고리즘에 재미를 붙였다. 백준 문제를 풀면 문제 난이도마다 티어가 올라가는 재밌는 사이트(solved.ac)가 생겨서 뭔가 동기 부여되는 것 같다. 언어는 python을 사용하고 있다. (취준
seohyun0120.tistory.com
+ 23.10.06
Bisect를 활용해도 타겟 수열의 원소를 알 수 있다
-> bisect_left로 나오는 index는 "해당 숫자보다 작은 숫자의 개수!" 라는 점을 이용한다
idx가 2라는 것은 그 수보다 작은 수가 2개는 앞에 있다라는 것이기 때문에 이를 저장하면 dp와 똑같은 값이 나온다
따라서 무조건 bisect를 활용해서 푸는게 좋다!!
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://my-coding-notes.tistory.com/270
[🏅5 / 백준 14003 / 파이썬] 가장 긴 증가하는 부분 수열 5
14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 문제
my-coding-notes.tistory.com
'코딩테스트' 카테고리의 다른 글
| [백준 파이썬 2638번 치즈] 구현 최적화 (0) | 2023.10.09 |
|---|---|
| [백준 파이썬 14502번 연구소] 구현 최적화 (1) | 2023.10.09 |
| [백준 파이썬 1005번 ACM Craft] 위상정렬 (0) | 2023.09.26 |
| [백준 파이썬 1647번 도시 분할 계획] 튜플과 리스트의 시간 차이 (0) | 2023.09.25 |
| [백준 파이썬 1197번 최소 스패닝 트리] 크루스칼 알고리즘, 프림 알고리즘 (0) | 2023.09.24 |
