Algorithm/Binary Search

[백준 2230번] 수 고르기

https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 수 고르기 문제는 이분탐색을 이용하여 해결할 수 있습니다. 먼저, 수열의 임의의 요소 X를 선택하고 X + m보다 크거나 같은 값 중 가장 작은 값을 Y라고 하면, Y - X의 최솟값을 찾으면 됩니다. 이 값을 찾기 위해 이분탐색이 사용됩니다. lower_bound(first, last, value)는 value보다 크거나 같은 값들 중 제일 작은 값을 찾는데 사용됩니다. 아래..

[백준 3151번] 합이 0 (C++)

https://www.acmicpc.net/problem/3151 3151번: 합이 0 Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다. www.acmicpc.net 합이 0 문제는 이분 탐색으로 해결할 수 있습니다. N이 최대 10,000이기 때문에 10000C3은 = (10000 * 9999 * 9998) / 3!입니다. 따라서, 3중 for문 이용하여 모든 경우의 수에 대해 합이 0이 되는지 확인하는 경우 시간 초과가 발생할 수 있습니다. 두 수 A, B를 선택한 후 (A + B) * -1이 몇개인 지 찾으면 됩니다. ⚠️ 10000C3이므로 주어진 코딩 실력..

[백준 2467번] 용액 (C++)

https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 용액문제는 이분탐색을 이용하여 해결할 수 있습니다. 문제에서 N이 최대 100,000이므로, O(N2)의 알고리즘을 사용하는 경우, 시간초과가 발생할 수 있습니다. 문제에서 용액의 특성값이 주어지고, 두 용액을 혼합했을 때, 0에 가장 가까운 용액을 만들어내는 두 용액을 찾아야 합니다. 첫번째 용액의 특성값이 10,000일 때의 그래프는 아래와 같습니다. (X축은 두번째 용액의 특성값, Y축..

[백준 18869] 멀티버스 2 (C++)

https://www.acmicpc.net/problem/18869 18869번: 멀티버스 Ⅱ M개의 우주가 있고, 각 우주에는 1부터 N까지 번호가 매겨진 행성이 N개 있다. 행성의 크기를 알고 있을때, 균등한 우주의 쌍이 몇 개인지 구해보려고 한다. 구성이 같은데 순서만 다른 우주의 쌍 www.acmicpc.net 멀티버스 2 문제의 해결 방법은 2가지가 있습니다. 정렬을 이용한 방법 먼저, 첫번째 방법은 아래와 같습니다. 문제에서는 아래와 같은 조건을 만족하면, 두 우주가 균등하다고 합니다. Ai Aj → Bi > Bj 따라서 대소 관계가 동일하면 두 우주가 균등하다고 할 수 있습니다. 먼저, 두 우주 A, B를 정렬하고, 정렬 후..

[백준 16401번] 과자 나눠주기 (C++)

https://www.acmicpc.net/problem/16401 16401번: 과자 나눠주기 첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 과자 N개의 길이 L1, L2, ..., LN이 공백으로 구분되어 주어진다. 과자의 길이는 (1 ≤ L1, L2, ..., LN ≤ 1, www.acmicpc.net 과자 나눠주기 문제는 Parametric Search를 이용하여 해결할 수 있습니다. Parametric Search는 최적화 문제를 결정 문제로 변환해 이분탐색을 수행하는 방법을 의미합니다. - [바킹독의 실전 알고리즘] 이분탐색 조카 1명에게 줄 수 있는 막대 과자의 최대 길이를 구하는 문제(최적화 문제)에서..

[백준 2295번] 세 수의 합 (C++)

https://www.acmicpc.net/problem/2295 본 게시글은 바킹독님의 [바킹독의 실전 알고리즘] 0x13강 - 이분탐색을 참고하여 작성되었습니다. 세 수의 합 문제는 이분탐색으로 해결할 수 있습니다. 가능한 방법은 3가지가 있습니다. 4중 for문 이용하여 모든 경우의 수를 확인하는 방법, 시간 복잡도는 O(N4) 가능한 세 수의 합을 구하고, 각 합이 집합 U 안에 존재하는지 확인하는 방법, 시간 복잡도는 O(N3logN) sum[i] + a[j] = a[k]를 만족하는 a[k]의 최댓값을 구하는 방법, 시간 복잡도는 O(N2logN) (단, sum은 두 수의 합을 저장한 배열) N이 최대 1,000이기 때문에 O(N2logN) 알고리즘을 이용하여 해결할 수 있습니다. solutio..

[백준 17219번] 비밀번호 찾기 (C++)

https://www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net 비밀번호 찾기 문제는 이분탐색을 이용하여 해결할 수 있습니다. N이 최대 100,000이 주어지기 때문에, 일반적인 탐색으로는 시간초과가 발생할 수 있습니다. 사이트의 주소와 비밀번호를 입력받고, 사이트의 주소를 기준으로 정렬해준다음, 이분탐색을 수행하면 비밀번호를 찾는 시간을 단축할 수 있습니다. 아래는 전체 코드입니다. #include using namespace..

[백준 1620번] 나는야 포켓몬 마스터 이다솜 (C++)

https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 나는야 포켓몬 마스터 이다솜 문제는 N이 최대 100,000이 될 수 있으므로, for문 이용하여 하나씩 탐색하면 시간초과가 발생할 수 있기 때문에 이분탐색을 이용하여 해결할 수 있습니다. 또한, 문자열과 숫자의 이분탐색을 나누어서 하기 위해 두 개의 벡터를 사용하고, 각각 번호와 이름을 기준으로 정렬한 다음 이분탐색을 수행해주면 됩니다. 아래는 전체 코드입니다. #i..