[C++] Binary Search, Parametric Search, Two pointer 알고리즘을 활용한 문제 풀이 방법

Binary Search

정렬된 배열에서 원하는 항목을 빠르게 찾는 알고리즘

일반적으로 O(log n)의 시간 복잡도를 가짐

---

방법

1. Array가 정렬이 되어있는 지 확인 (미정렬 시 이분 탐색 사용 불가)
2. 탐색하려는 배열의 중앙 값을 찾음
3. 중앙 값이 찾으려는 값과 같은지 확인
4. 만약 중앙 값이 찾으려는 값과 같다면, 탐색을 종료하고 인덱스 값을 반환
5. 만약 중앙 값이 찾으려는 값보다 크다면, 배열의 왼쪽 반쪽을 새로운 배열로 간주하여 이진 탐색을 수행
   • 이 때, 왼쪽 배열의 마지막 인덱스는 중앙 인덱스 - 1
6. 만약 중앙 값이 찾으려는 값보다 작다면, 배열의 오른쪽 반쪽을 새로운 배열로 간주하여 이진 탐색을 수행
   • 이 때, 오른쪽 배열의 첫 인덱스는 중앙 인덱스 + 1
7. 찾으려는 값이 배열 내에 없다면, 탐색을 종료하고 -1과 같은 특별한 값이나 에러 메시지를 반환

---

구현

#include <iostream>
#include <algorithm>
using namespace std;

int arr[] = { 3, 99, 21, 33, 4, 1, 5, 55, 7, 10 };

void bs(int target) {

		// arr가 정렬이 안 되어 있으면 꼭 정렬시켜야 함
		sort(arr, arr + 10);  // 오름차순 정렬
		
    int left = 0;  // 시작 index
    int right = 9;   // 끝 index
    int flag = 0;   // 찾았다 안 찾았다 표시
    
    while (left <= right) {
        int mid = (left + right) / 2; // mid를 예측
        
        if (arr[mid] == target) {
            flag = 1;                  // 답을 찾았으면 flag가 1로 표시됨
            break;
        }

        else if (target < arr[mid]) {  // target이 array의 mid 값보다 작다면
            right = mid - 1;           // target은 왼쪽에 있으므로, 오른쪽을 mid-1으로 이동
        }

        else if (target > arr[mid]) {  // target이 array의 mid 값보다 크다면
            left = mid + 1;            // target은 오른쪽에 있으므로, 왼쪽을 mid+1로 이동
        }
    }

    cout << flag; // 1: target을 찾았다, 0: target이 없다
}

int main() {
    int target;
    cin >> target;
		
		bs(target);
}

---

언제 써야 효율적인 지

• 배열에서 여러 번 찾아야 할 때
  • N 개의 배열에서 특정 값을 Q번 찾아야 함
    • 일반 : O(N) * Q
    • 이분 탐색 : O(NlogN) (최초 1회) + O(logN)*Q
  • Q = N 이라 하면
    • 일반 : O(N^2)
    • 이분 탐색 : O(NlogN)

 

 

---

 

Parametric Search

최적화 문제(Optimization problem)를 푸는 데 사용되는 알고리즘

이진 검색(Binary Search)을 응용하여 최적값을 찾는 방식을 의미

 

*최적화 문제

• 여러 조건들 중에서 **목적 함수(Objective function)**를 최대 또는 최소화하는 값을 찾는 문제
• 문제에 따라 함수가 다양한 형태를 가질 수 있지만, 일반적으로 **단조적(monotonic)**이어야 최적값에 근접할 수 있음

 

---

예시) Binary Search vs Parametric Search

1. 이진 검색(Binary Search) 예시 : 정렬된 배열에서 특정 값 찾기
   • 목적 함수: 주어진 배열에서 특정 값을 찾는 함수
   • 조건: 배열은 정렬되어 있어야 함
   • 이진 검색을 사용하여 배열을 반으로 나누어 검색 범위를 점차 줄여가며 특정 값을 찾음

 

1. Parametric Search 예시 : 정렬되지 않은 배열에서 중간값 찾기
   • 목적 함수: 주어진 배열에서 함수의 입력값보다 작은 값의 개수를 반환하는 함수
   • 조건: 배열은 정렬되어 있지 않음
   • Parametric Search를 사용하여 중간값을 찾음
   • Parametric Search를 적용하기 위해서는 이 함수가 단조 함수여야 함

 

---

Parametric Search 문제풀이 방법

N개의 대리석이 있다.

N개의 대리석은 길이가 일정하지 않을 수 있다.
대리석은 길이에 비례하게 값을 받는다. (폭은 무시)

따라서 N개의 대리석을 최대한 길면서, 일정한 K개의 크기로 만들어서 고객에게 팔려고 한다.

예를 들어 N = 3, K = 4 이며, 30, 40, 50의 길이의 대리석을 갖고 있다면,
K개의 가장 긴 일정한 대리석의 길이는 25이며, 30에서 잘려나간 5와 40에서 잘려나간 15의 길이의 대리석은 버려진다. (대리석은 금이 가있으면 상품 가치가 떨어지기 때문에, 부분들을 붙여서 사용할 수는 없다.)

다른 예로, N = 2, K = 2인 상태에서, 100, 22 길이의 대리석이 있다면, K개의 가장 긴 일정한 크기의 대리석은 50이다. 이 상황에서는 22의 길이의 대리석은 사용되지 않는다.

N개의 대리석을 K개 이상으로 일정하게 만들었을 때, 하나의 대리석이 가질 수 있는 최대 길이를 출력하시오.

입력
첫 번째 줄에는 대리석의 개수 N과 고객이 원하는 대리석의 분할 개수 K가 공백으로 구분되어 주어진다.
(1 <= N <= 10,000, 1 <= K <= 1,000,000, N <= K)
두 번째 줄부터 N개의 줄에 걸쳐 각 대리석의 길이가 입력된다.
대리석의 길이는 정수 범위 내로 입력된다.

출력
첫 번째 줄에 N개의 대리석을 K개로 일정하게 나눌 수 있는 최대 길이를 출력한다.

 

 

---

설계

1. 문제 조건을 토대로 low(left), high(right) 정하기
   • 마지막 mid 값을 answer로 반환할 것이니, low와 high는 answer의 단위와 같다.
   • answer는 “최대 길이” → low와 high는 길이와 관련된 값
   • low는 1(최소 길이), high는 주어진 대리석 길이중 가장 긴 것으로 정의 가능

 

1. 목적 함수 정의하기
   • 이 문제에서 목적 함수는 mid 값을 가지고 계산을 거쳐 true/false를 반환해야 한다.
   • 목적 함수는 항상 증가하거나, 항상 감소하여야 한다(단조 함수).
   • 위의 조건을 생각하며 목적함수 정의
     • 대리석의 길이(mid)를 넣었을 때, 해당 길이의 대리석을 몇 개(K와 비교하기 위함)를 만들 수 있는 지 계산
     • K값과 비교하여 true(만들기 가능) / false(만들기 불가능)을 반환

 

 

---

구현

#include <iostream>
#include <algorithm>
using namespace std;

int N, K; // N : 주어지는 대리석 개수, K : 고객이 요청하는 대리석의 분할 개수

int arr[10000]; // 갖고 있는 대리석의 길이를 저장

bool condition(int cut_len) {
    long long sum_ = 0; // cut_len으로 각각을 잘랐을 시 얻을 수 있는 대리석 개수

    for (int i = 0; i < N; i++) {
        sum_ += arr[i] / cut_len; // 원하는 크기로 대리석 잘라보기
    }

    if (sum_ >= K) // K개 이상을 만들 수 있다 
        return true;

    return false; // K개 이상을 만들 수 없다
}

void psearch(int high) {

    int left = 1; 
    int right = high; 
    int ans = 0;

    while (left <= right) {
				// 가능성 -> 정답이라고 가정한 값 
        int mid = (left + right) / 2;

				// 이 가능성이 정답이 될수 있는 지
        if (condition(mid) == true) {
						// 정답이 될 가능성이 있는 값을 찾았을 때
            // 상한선을 높여 볼까? -> left 값 변경
						ans = mid;

            left = mid + 1;
        }

        else {
						// 이 mid 값은 정답이 될 수 없다
            // 상한선의 가장 큰 값의 범위를 낮춘다 ->  right 값 변경
            right = mid - 1;
        }
    }

    cout << ans; // K개 잘랐을 때, 얻을 수 있는 최대 길이
}

int main() {

    cin >> N >> K;

    int max_ = 0; // 내가 가진 대리석의 길이 중 가장 긴 것

    for (int i = 0; i < N; i++) {
        cin >> arr[i];

        if (max_ < arr[i])
            max_ = arr[i];
    }

    psearch(max_);

}

 

 

 

---

Two pointer

배열이나 리스트와 같은 순차 자료 구조에서 두 개의 포인터를 이용하여 문제를 해결하는 방법

보통 O(n)의 시간 복잡도를 가짐

#include <iostream>
using namespace std;

int main() {
    int arr[] = { 1,2,3,1,2,3,5,6,7,8 };

    int target = 6; // 찾고자 하는 배열의 합

    int left = 0; // slow pointer
    int right = 0; // fast pointer

    int sum = 0; // pointer들이 가리키는 배열의 합
    int cnt = 0; // target과 같은 합이 나오면 check

    while (left <= 10 && right <= 10) {

        if (sum == target) {
            // target 값과 같다 -> 왼쪽을 줄여서 이동 (right를 움직이면 배열 idx 초과 오류 가능성)
            cnt++;
            sum -= arr[left++];
        }
        else if (sum < target) {
            // sum이 목표보다 작다 -> 오른쪽으로 늘려서 이동
            sum += arr[right++];
        }
        else if (sum > target) {
            // sum이 목표보다 크다 -> 왼쪽을 줄여서 이동
            sum -= arr[left++];
        }
    }

    cout << cnt; // 5
}

 

 

---

Sliding Window

특정 구간의 합이 내가 원하는 답인 지 알아보기 위함

#include <iostream>
using namespace std;

int main() {
    int arr[] = { 1,2,3,1,2,3,5,6,7,8 };
    int size_ = 10; // arr 크기
    int N = 3;

    // 1. 초기 포인터 setting
    int left = 0;
    int right = N-1;

    // 2. 초기 공통 구간 setting

    int sum = 0;
    for (int i = left; i < right; i++) {
        sum += arr[i];
    }

    // 3. sliding window
    int ans = 21e8;

    while (right < size_) {
        
        // a. 구간 완성
        sum += arr[right];
    
        // b. 수행
        if (sum < ans)
            ans = sum;

        // c. 다음 공통 구간 만들기
        sum -= arr[left];

        // d. left와 right 포인터 이동
        left++;
        right++;
    }

}

 

 

---

#2 문제 풀이 적용

// 위와 비교해 어떤 구현방법이 직관적이고 편한 지는 본인이 선택해서 구현
// 구간 합이 가장 큰 부분 찾기 문제

#include <iostream>
using namespace std;

int main() {
  int arr[] = { 1,2,3,1,2,3,5,6,7,8 };
  int size_ = 10;
  
	int N = 3;

	int left = 0;
	int right = N - 1;

	int sum_ = 0;

	for (int i = left; i <= right; i++) {
		sum_ += arr[i]; // 1. 구간 전체를 더해서 시작
	}

	int max_ = -21e8;
	int max_l = left, max_r = right;

	while (right < size_) {

		if (max_ < sum_) {
			max_l = left;
			max_r = right;
			max_ = sum_;
		}
		cout << left << " " << right << " " << sum_ << endl;

		right++;
		sum_ += arr[right]; // right를 옮기고 값을 더함

		sum_ -= arr[left];  // 값을 빼준 후 left를 옮김
		left++;

	}

}