BAEKJOON/이분 탐색 (12) 썸네일형 리스트형 백준 20922번 [겹치는 건 싫어](C++) -yes6686- 티스토리 백준 문제 풀이: 20922 (겹치는 건 싫어)문제 링크: https://www.acmicpc.net/problem/20922문제 설명:길이 N인 정수 수열에서, 같은 정수가 K개를 초과하지 않도록 하면서 만들 수 있는 가장 긴 연속 부분 수열의 길이를 구하는 문제입니다. 즉, 각 정수는 연속된 부분 수열 안에서 최대 K번까지만 등장할 수 있어야 하며, 이 조건을 만족하는 최대 길이를 찾아야 합니다.문제 해결 코드// ✅ 투 포인터 + 빈도 배열을 활용한 풀이#include using namespace std;int arr[200001]; // 수열 저장 배열int cnt[100001]; // 각 값의 등장 횟수 카운트 배열int main() { ios::sync_with_stdio(.. 백준 2230번 [수 고르기](C++) -yes6686- 티스토리 백준 문제 풀이: 2230 (수 고르기)문제 링크: https://www.acmicpc.net/problem/2230문제 설명:정수로 이루어진 N개의 수열에서 두 수를 골라 그 차이가 M 이상이면서 가장 작은 차이를 찾는 문제입니다. N은 최대 100,000이므로 O(n2) 풀이로는 해결이 불가능하며, 효율적인 정렬 기반 이분 탐색 혹은 투 포인터 알고리즘이 요구됩니다.문제 해결 코드// ✅ 투 포인터 풀이#include #include using namespace std;int arr[100001];int main() { int n, m; cin >> n >> m; for (int i = 0; i > arr[i]; } sort(arr, arr + n); int minDi.. 백준 3151번 [합이 0](C++) -yes6686- 티스토리 백준 문제 풀이: 3151 (합이 0)문제 링크: https://www.acmicpc.net/problem/3151문제 설명:정보올림피아드 캠프에서 학생 n명의 실력이 주어진다. 이 중 서로 다른 3명을 뽑았을 때, 실력의 합이 0이 되는 조합의 개수를 구하는 문제이다. 중복 없이 3명을 선택해야 하며, 정렬된 상태를 활용하여 효율적으로 계산할 수 있어야 한다.핵심 알고리즘: 정렬 + 이분 탐색을 활용한 투포인터 기반 조합 탐색. O(n2 log n)문제 해결 코드// 정렬 + 이분 탐색으로 3개의 합이 0인 경우의 수 계산#include #include #include using namespace std;vector v;int main() { ios::sync_with_stdio(false); .. 백준 2343번 [기타 레슨](C++) -yes6686- 티스토리 백준 문제 풀이: 2343 [기타 레슨]문제 링크: https://www.acmicpc.net/problem/2343문제 설명:길이가 n인 강의 목록이 주어졌을 때, m개의 블루레이에 강의를 나누어 저장하려고 합니다. 이때, 블루레이의 크기가 최소가 되도록 해야 합니다. 블루레이의 크기는 각 블루레이에 들어가는 강의 길이 중 최댓값으로 결정됩니다.즉, 최소한의 블루레이 크기를 이분 탐색을 사용하여 구하는 문제입니다.문제 해결 코드#include #include using namespace std;int arr[100001];int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n, m; cin >> n >> m; int s.. 백준 2110번 [공유기 설치](C++) -yes6686- 티스토리 백준 문제 풀이: 2110 [공유기 설치]문제 링크: https://www.acmicpc.net/problem/2110문제 설명:각각의 집이 일직선 상에 주어졌을 때, k개의 공유기를 설치하여 인접한 공유기 사이의 거리 중 최솟값을 최대로 만드는 문제입니다.즉, 가장 가까운 두 공유기 사이의 거리를 최대로 확보하는 것이 목표이며, 이를 위해 이분 탐색을 사용하여 최적의 간격을 찾습니다.문제 해결 코드#include #include using namespace std;int arr[200001];int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n, k; cin >> n >> k; // 집 위치 입력 for (int.. 백준 2473번 [세 용액](C++) -yes6686- 티스토리 백준 문제 풀이: 2473 [세 용액]문제 링크: https://www.acmicpc.net/problem/2473문제 설명:n개의 용액이 주어졌을 때, 세 용액을 혼합하여 그 특성값(합)의 절댓값이 0에 가장 가까운 조합을 찾는 문제입니다. 각 용액은 음수, 0, 양수로 이루어져 있으며, n은 최대 100,000입니다.문제 해결 코드#include #include #include using namespace std;long long int arr[100001];long long int resultArr[3];int main() { int n; cin >> n; for (int i = 0; i > arr[i]; } sort(arr, arr + n); long long in.. 백준 2467번 [용액](C++) -yes6686- 티스토리 백준 문제 풀이: 2467 [용액]문제 링크: https://www.acmicpc.net/problem/2467문제 설명:n개의 용액이 주어졌을 때, 두 용액을 혼합하여 그 특성값(합)의 절댓값이 0에 가장 가까운 두 용액을 찾는 문제입니다. 용액은 음수, 0, 양수로 구성되며, 두 용액을 혼합했을 때의 특성값은 두 용액의 합으로 정의됩니다.용액의 수 n은 최대 100,000개입니다.두 용액의 특성값이 0에 가까운 조합을 출력합니다.문제 해결 코드#include #include #include using namespace std;int arr[100001];bool compare(int a, int b) { return abs(a) > n; for (int i = 0; i > arr[i]; .. 백준 1166번 [선물](C++) -yes6686- 티스토리 백준 문제 풀이: 1166 (선물)문제 링크: https://www.acmicpc.net/problem/1166문제 설명:n개의 정육면체 선물을 상자(l × w × h)에 담으려고 합니다. 선물은 모두 같은 크기로 만들어야 하며, 가능한 가장 큰 선물의 한 변의 길이를 구하는 문제입니다. 길이는 소수점 아래 10자리까지 정확해야 합니다.문제 해결 코드#include #include using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(NULL); // 입력 받기 double n, l, w, h; cin >> n >> l >> w >> h; // 이분 탐색 초기화 double s = 0; // 가능.. 이전 1 2 다음
