전체 글 (704) 썸네일형 리스트형 이분탐색. [2473] [1. 문제 설명] https://www.acmicpc.net/problem/2473 [2. 풀이 접근] 먼저 두 용액의 조합을 모두 찾는다. 이제 각 조합에 대해서 한 용액만 첨가하여 0에 가장 가까워지는 조합을 찾아내도록 한다. 주석 참조 삼분 탐색 (?) [3. 코드] 이분탐색. [2467] [1. 문제 설명] https://www.acmicpc.net/problem/2467 [2. 풀이 접근] 용액을 하나 정한다. 전체에 대해서, 이 용액과 더해서 그 합이 0에 가장 가까워 지는 용액을 이분 탐색으로 찾는다. 용액들이 이미 정렬 된 상태이므로, 이분 탐색 시 두 용액의 합이 0보다 작다면 # 양수 용액을 더해서 0으로 만들 수 있다. # 따라서 다음 탐색 구간을 (mid ~ hi] 구간을 잡아야 한다. 0보다 크다면 # 음수 용액을 더해서 0으로 만들 수 있다. # 따라서 다음 탐색 구간을 [lo ~ mid) 구간을 잡아야 한다. [3. 코드] 이분탐색. [1253] [1. 문제 설명] https://www.acmicpc.net/problem/1253 [2. 풀이 접근] 풀이 시 주의 할점 std::lower_bound 에 대응되는 sort.Search() 는 하한 값 중 가장 먼저 오는 index 를 반환한다. 중복된 값에 대해서도 확인이 필요한 경우, upper_bound 에 해당하는 index 까지 구할 필요가 있다. 즉, [lo, hi) 까지 순차적으로 확인 해 볼 필요가 있다. 시간 복잡도는 O(N^2 logN) 인데, N 의 최대가 2,000 이므로, 현실적인 시간 내에 해결 가능하다. [3. 코드] 이전 1 ··· 30 31 32 33 34 35 36 ··· 235 다음