이분 탐색

[프로그래머스 level 3] 입국심사(C++)

이분 탐색을 어떻게 사용해야할 지 떠올리기 정말 힘들었던 문제이다. 그리고 오버플로우도 주의해야 한다. n times return 6 [7, 10] 28 입출력 예 설명 가장 첫 두 사람은 바로 심사를 받으러 갑니다. 7분이 되었을 때, 첫 번째 심사대가 비고 3번째 사람이 심사를 받습니다. 10분이 되었을 때, 두 번째 심사대가 비고 4번째 사람이 심사를 받습니다. 14분이 되었을 때, 첫 번째 심사대가 비고 5번째 사람이 심사를 받습니다. 20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다. 이분 탐색을 하려면 특정 값의 low와 high를 정해야 한다. 이 문제에서 특정..

[백준 14003] 가장 긴 증가하는 부분 수열5 C++

14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 이분 탐색 1. 문제 해결 아이디어 [백준 12015] 가장 긴 증가하는 부분 수열2 C++ 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 이전까지 풀.. hyeo-noo.tistory.com 위 문제에서 추가적인 요소만 넣어준다면 해결 ..

[백준 1208] 부분수열의 합2 C++

1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 이분 탐색 1. 문제 해결 아이디어 N이 40개 이므로 모든 부분수열을 다 구하려면 2^40번의 연산이 필요하다. -> 1초안에 풀 수 없다. 주어진 수열을 절반씩 나누어서 계산해 보자 수열의 길이가 40이라고 가정하자. 20번째 수열부터 40번째 수열(이를 right수열이라고 하자)까지의 모든 부분수열의 합을 구해본다. 이때 시간복잡도는 O(2^20)이므로 시간은 충분하다. right 부분 수열의 합을 sum이라고 하면 ..