분류 전체보기

[백준 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..

[백준 1700번] 멀티탭 스케줄링 (C++)

https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 멀티탭 스케줄링 문제는 그리디 알고리즘으로 해결할 수 있습니다. 콘센트에 꼽혀 있는 기기 중, 앞으로 사용하지 않거나, 가장 나중에 사용할 기기를 선택하여 현재 사용할 기기와 교체해주면됩니다. 증명은 어렵지만, 믿음으로 푼 문제입니다. 알고리즘의 기본 틀은 아래와 같습니다. 멀티탭의 구멍 개수가 기기의 총 사용횟수보다 작은 경우 0을 출력한다. 플러그를 뽑지 않아도 꽂을 수 있는 최대한의 개수를 ..

[백준 2170번] 선 긋기 (C++)

https://www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y(-1,000,000,000 ≤ x n; for(int i = 0; i < n; i++) cin ..