이분탐색5 20551 : Sort 마스터 배지훈의 후계자 (C++) 20551번: Sort 마스터 배지훈의 후계자 지훈이는 Sort 마스터다. 오랫동안 Sort 마스터 자리를 지켜온 지훈이는 이제 마스터 자리를 후계자에게 물려주려고 한다. 수많은 제자들 중에 후계자를 고르기 위해서 지훈이는 제자들에게 문제 www.acmicpc.net lower_bound 함수를 참조해서 만든 함수로 푼 문제이다. #include #include using namespace std; int grayLower_bound(int* arr, int N, int temp) { int left = 0; int right = N; int cnt = 0; // 탐색하려는 수가 없을 때 -1을 리턴하기 위해 카운트 변수 선언 int mid; while(left < right) { mid = (left .. 2021. 2. 18. 10815 : 숫자 카드 (C++) 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 바로 전 문제(숫자 카드 2)와는 다르게 중복 값이 없는 문제여서 그냥 바로 이분탐색으로 쉽게 풀리는 문제이다. #include #include using namespace std; int main() { int N, M; scanf("%d", &N); int arr[N]; for(int i = 0; i < N; i++) { scanf("%d", &arr[i]); } sort(arr, arr + N); // 이분탐색을 수행하기위해 정.. 2021. 2. 17. 1920 : 수 찾기 (C++) 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 입력이 최대 N이 10만개, M이 10만개 들어올 수 있으므로 하나하나 전부 탐색하면 100억의 연산을 수행해 2초인 시간제한을 넘어가 버린다. 그래서 이분탐색을 실행하여 계산을 해줘야하므로 이분탐색으로 문제를 해결하였다. #include #include using namespace std; int main() { int N, M; scanf("%d", &N); int arr[N]; for(int i = 0; i .. 2021. 2. 11. 2805 : 나무 자르기 (C++) 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 이분탐색... 어려워 #include using namespace std; int N, M; int main() { cin >> N >> M; int tree[N]; int maxTree = 0; for(int i = 0; i > tree[i]; maxTree = maxTree < tree[i] ? tree[i] : maxTree; } int left = 1; // 시작값 int right =.. 2021. 2. 10. 1654 : 랜선 자르기 (C++) 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 풀기싫어... #include using namespace std; int K, N; unsigned int ans; int search(unsigned int left, unsigned int right, unsigned int LAN[]) { int cnt = 0; if(left > right) { return -1; } unsigned int mid = (left + right) / 2; for(int i = 0; i < K; .. 2021. 2. 10. 이전 1 다음
