본문 바로가기

이분 탐색6

[백준 C++] 1208번: 부분수열의 합 2 1. 문제https://www.acmicpc.net/problem/1208 2. 알고리즘 분류이분 탐색중간에서 만나기 3. 소스 코드#include #include #define MAX_N 40using namespace std;int N, S;int arr[MAX_N];map sum2cnt;long long cnt;// 오른쪽 부분수열의 모든 경우의 수 계산void rightSeq(int mid, int sum) { // 수열의 끝까지 도달했을 경우, if (mid == N) { sum2cnt[sum]++; // 부분수열의 합을 저장 return; } rightSeq(mid + 1, sum + arr[mid]); // 해당 index의 수열의 값을 더했을 경우, rightSeq(mid + 1, su.. 2024. 5. 1.
[알고리즘] 이진 탐색(이분 탐색, Binary Search) 1. 개요1. O(logN) 시간 복잡도로 해당 배열에서 특정 값을 찾는 알고리즘 2. 알고리즘 코드vector ans;// 이진 탐색 알고리즘int binary_search(int n){ int low = 0; int high = ans.size() - 1; int ret = MAX_N; while (low = n) { ret = min(ret, mid); high = mid - 1; } else low = mid + 1; } return ret;} 3. 문제https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가.. 2024. 4. 14.
[백준 C++] 12015번: 가장 긴 증가하는 부분 수열 2 1. 문제 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 2. 알고리즘 분류 이분 탐색 가장 긴 증가하는부분 수열 3. 소스 코드 #include #include #include #define MAX_N 1000001 using namespace std; int nums[MAX_N]; vector ans; // 이진 탐색 알고리즘 int binary_search(int n) { int low = 0; int high = ans.size() -.. 2024. 4. 14.
[백준 C++] 2473번: 세 용액 1. 문제 https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 2. 알고리즘 분류 정렬 이분 탐색 두 포인터 3. 소스 코드 Key Point) 1. 투 포인터 알고리즘을 활용하기 위해 정렬한다. 2. 3개의 값을 비교할 때는 하나를 정해 놓고 2개의 값을 '투 포인터' 알고리즘을 통해 계산한다. #include #include #include using namespace std; long long solutions[5000].. 2023. 10. 3.
[백준 C++] 2143번: 두 배열의 합 1. 문제 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 2. 알고리즘 분류 자료 구조 이분 탐색 누적 합 3. 소스 코드 Key Point) 1. 두 A, B의 배열의 누적 합들을 모두 구한다. 2. B를 오름차순으로 정렬한 후, 이진 탐색을 하면 빠르게 해답을 찾을 수 있다. #include #include #include using namespace std;.. 2023. 10. 3.
[백준 C++] 2467번: 용액 1. 문제 https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 2. 알고리즘 분류 이분 탐색 두 포인터 3. 소스 코드 #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); // 전체 용액의 수 입력 int N; cin >> N; vector numbers(N); // 용액의 특성값 입력 for (i.. 2023. 6. 10.

티스토리툴바