일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- 위상정렬
- concurreny
- BFS
- 백트래킹
- Java
- Meet in the middle
- 구현
- 누적 합
- MST
- springdoc
- DP
- 투 포인터
- disjoint set
- kapt
- kruskal
- MySQL
- 분리 집합
- union-find
- spring boot
- 이분 탐색
- tarjan
- miller-rabin
- Linux
- 페르마 소정리
- 알고리즘
- 그래프
- SCC
- 위상 정렬
- DFS
- BindingAdapter
- Today
- Total
목록이분 탐색 (3)
기맹기 개발 블로그
BOJ 2473 세 용액 난이도 : 골드 3 https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 전략 생각할 수 있는 가장 간단한 방법은 세 용액의 모든 조합을 찾는 것이다. 3중 for문으로 세 용액의 조합을 만든다면 O(N^3)이다. N의 범위는 [3, 5000] 이므로 N^3은 5^3 * 10억이다. 따라서 다른 방법을 찾아야 한다. 만약 두 개의 용액 조합을 찾는다면 나머지 하나의 용액은 모두 찾을 필요 없이 이진 탐색..
BOJ 2143 두 배열의 합 난이도 : 골드 3 https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 전략 처음에는 prefix sum을 구해놓고 포인터를 움직여가는 방식은 어떨까 생각해봤는데 배열이 두개라서 상당히 복잡할 것 같았다. 따라서 부배열 합들을 모두 저장해놓고 탐색하는 것이 좋겠다고 생각했다. 길이가 N인 배열에서 모든 부배열의 합을 구하는 것은 O(N^2..
BOJ 14003 가장 긴 증가하는 부분 수열 5 난이도 : 플래 5 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 전략 수열의 크기 N이 최대 1,000,000이므로 O(N^2) 알고리즘으로는 해결할 수 없다. 이를 O(NlogN)만에 해결할 수 있는 LIS 알고리즘은 이분 탐색과 메모이제이션을 함께 사용한다. 1. dp[len]은 길이가 len인 증가하는 부분 수열 중에서 가장 작은 마지막 원소가 저장된다. ..