week10. 이분 탐색
필수 문제 풀이
1. 백준 17266번 어두운 굴다리
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
int streetLamp(int n, int m, vector<int> x) {
int x_size = x.size();
int max_distance = max((x[1] - x[0]), (x[x_size - 1] - x[x_size - 2]));
for (int i = 1; i < x_size - 2; i++) {
int tmp_distance = ceil(double((x[i + 1] - x[i])) / 2); ////가로등 사이의 간격이 홀수일 경우 때문에 반올림 필요
max_distance = max(max_distance, tmp_distance); //가로등 간격의 최댓값 갱신
}
return max_distance; //가로등 간격의 최댓값이 가로등 높이의 최솟값
}
int main() {
int n, m; // 굴다리의 길이, 가로등의 개수
vector<int> x; //설치할 수 있는 가로등의 위치
int x_tmp;
//입력
cin >> n;
cin >> m;
x.push_back(0);
for (int i = 1; i <= m; i++) {
cin >> x_tmp;
x.push_back(x_tmp);
}
x.push_back(n);
//연산 & 출력
cout << streetLamp(n, m, x);
return 0;
}2. 백준 10815번 숫자 카드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int binarySearch(int n, int key_num, vector<int>& card_num) {
int left = 0;
int right = n - 1;
int mid;
while (left <= right) {
mid = (left + right) / 2;
if (card_num[mid] == key_num) { // 카드 정수에 해당 값이 존재하면 1 반환
return 1;
}
else if (card_num[mid] > key_num) { //왼쪽(더 작은 쪽) 탐색
right = mid - 1;
}
else { //오른쪽(더 큰 쪽) 탐색
left = mid + 1;
}
}
return 0; //존재하지 않으면 0 반환
}
int main() {
cin.tie(0); cout.tie(0);
ios_base::sync_with_stdio(NULL);
int n, m;
int key_num;
//입력
cin >> n;
vector<int> card_num(n);
for (int i = 0; i < n; i++) {
cin >> card_num[i];
}
sort(card_num.begin(), card_num.end()); //정렬
cin >> m;
while(m--) {
cin >> key_num;
//연산 & 출력
cout << binarySearch(n, key_num, card_num) << " ";
}
return 0;
}3. 백준 16401번 과자 나눠주기
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//최대 과자 길이가 'length'가 되도록 과자를 배분했을 때, 과자를 받은 조카의 수
int cntNephew(int length, vector<int>& snack) {
int cnt = 0; //cnt값 0으로 초기화
for (int i = 0; i < snack.size(); i++) {
if (snack[i] >= length) {
int tmp = snack[i] / length; //과자를 여러 조각으로 쪼갤 수 있으므로
cnt += tmp;
}
}
return cnt;
}
int binarySearch(int n, int m, vector<int>& snack) {
int left = 1;
int right = snack.back(); //1 ~ 주어진 제일 긴 과자 길이까지의 범위를 탐색
int mid;
while (left <= right) {
mid = (left + right) / 2;
int distributed = cntNephew(mid, snack);
if (distributed >= m) { //모든 조카(m명)에게 과자를 나눠줄 수 있으면 -> 과자의 길이를 늘려서 탐색
left = mid + 1;
}
else { //모든 조카(m명)에게 과자를 나눠줄 수 없으면 -> 과자의 길이를 줄여서 탐색
right = mid - 1;
}
}
//과자의 총 길이 합
int sum = 0;
for (int i = 0; i < snack.size(); i++) {
sum += snack[i];
}
if (sum < m) { //모든 조카에게 같은 길이의 과자를 나눠줄 수 없는 경우 0 반환
return 0;
}
else {
return left - 1; //탐색이 끝난 후 upper bound 값에서 1을 뺌
}
}
int main() {
ios_base::sync_with_stdio(NULL);
cin.tie(0); cout.tie(0);
int m, n;
//입력
cin >> m >> n;
vector<int> snack(n);
for (int i = 0; i < n; i++) {
cin >> snack[i];
}
sort(snack.begin(), snack.end()); //정렬
//연산 & 출력
cout << binarySearch(n, m, snack);
return 0;
}도전 문제 풀이
1. 백준 2343번 기타 레슨
2. 백준 3079번 입국심사
11주차 개념 예습
투 포인터
두 개의 포인터로 배열을 빠르게 탐색하는 알고리즘
특징
- 주로 반복문(while문)으로 구현
- 시간 복잡도: O(n^2)의 문제를 O(n)으로 가능
탐색 방법
- 2개의 포인터가 서로 다른 위치에서 시작해서 서로에게 다가가는 방향으로 탐색
*정렬된 배열에서 성립- 2개의 포인터가 같은 위치에서 시작하여 같은 방향으로 이동하며 탐색
*슬라이딩 윈도우는 2개의 포인터 사이의 거리를 고정하고, 2번 방식으로 탐색한 것
-> 부분 배열의 합이나 평균을 계산하는 등의 문제에 사용될 수 있음- 포인터가 가까워지는 방법과 멀어지는 방법이 있음
- 가까워지는 방법 -> 중복이 없고 정렬된 배열에 사용. 두 개의 포인터가 가리키는 값만 고려
- 멀어지는 방법 -> 두 개의 포인터가 가리키는 값 사이의 모든 값을 고려
효율성 테스트 문제로 주로 출제됨
문제 예시
- 특정한 합을 가지는 부분 연속 수열을 찾는 문제
== 포인터가 멀어지는 방법
(1) 시작점과 끝점이 첫번째 원소의 인덱스를 가리키도록 함
(2.1) 현재 부분의 합이 target과 같다면 카운트
(2.2) 현재 부분의 합이 target보다 작다면 end를 1 증가
(2.3) 현재 부분의 합이 target보다 크다면 start를 1 증가
(3) 모든 경우를 확인할 때까지 (2) 과정 반복
- 주어진 정수 배열에서 두 개의 숫자를 선택하여 합이 특정한 값(target)을 갖는지 확인하는 문제(두 포인터의 합과 차)
== 가까워지는 방법
(1) left, right 두 개의 포인터를 배열의 양 끝에서 시작
(2) left < right 동안 반복
(3) left와 right의 합을 sum에 저장
(4.1) 만약 sum이 target과 같다면, count 값을 증가하며 left 인덱스는 오른쪽으로 이동, right 인덱스는 왼쪽으로 이동
(4.2) sum이 target보다 작다면, left를 한 칸 오른쪽으로 이동
(4.3) sum이 target보다 크다면, right를 한 칸 왼쪽으로 이동
(5) 해당 조건에 만족하는 count 반환
참고
https://adjh54.tistory.com/384
https://velog.io/@heyggun/Algorithm-Two-Pointers-Algorithm-%ED%88%AC-%ED%8F%AC%EC%9D%B8%ED%84%B0-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
