binary search3 [백준 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. 이전 1 다음
