분할 정복 알고리즘이란?

• 분할 정복은 문제를 2개 또는 그 이상의 작은 부분 문제로 나눈 다음 푸는 것(분할)
• DP의 경우는 작은 부분문제가 중복이 되므로 Memorization을 통해 중복을 제거하고, 분할 정복은 문제를 나누었는데, 중복이 되지 않기에 한 번만 풀어주면 가능
• 푼 다음에 다시 합쳐서 정답을 구하는 경우(정복)
• 예시 : 퀵 소트, 머지 소트, 큰 수 곱셈..

대표적인 알고리즘 

1. 이분 탐색 (Binary Search)

정렬되어 있는 리스트에서 어떤 값을 빠르게 찾는 알고리즘

리스트의 크기를 N이라고 했을 때  크기가 N인 리스트를 계속해서 절반으로 나누기 때문에, O(logN)의 시간 복잡도가 걸리게 됩니다.

 

<코드>

while(left<=right) {
    int mid = (left + right) / 2;
    if(a[mid]== x) {
        position = mid;
        break;
    } else if(a[mid]>x) {
        right = mid-1;
    } else {
        left = mid+1;
    }
}

중간값보다 작으면 right = mid -1, 중간값보다 크다면 left = mid + 1 해주면 됩니다.

 

상한과 하한에 대해서

상한 : 큰 수 중 첫 번째 수(upper_bound) 초과 

하한 : 크거나 같은 수 중 첫 번째 수(lower_bound) 이상

https://www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

이 문제는 카드에 적혀있는 숫자가 상근이가 몇 개 가지고 있는지 개수를 출력하는 문제입니다.

<코드>

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n;
	cin>>n;
	vector<int> a(n);
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	sort(a.begin(),a.end());
	int m;
	cin>>m;
	for(int i=0;i<m;i++){
		int num;
		cin>>num;
		cout<<upper_bound(a.begin(),a.end(),num)-lower_bound(a.begin(),a.end(),num)<<' ';
	
	}
	//상한: 큰수 중에 첫번째(초과)  하한 : 같거나 큰 수 중에 첫번째(이상) 
	cout<<'\n';
	
}

테스트케이스 중 하나인 수인 10을 기준으로 upper_bound(10)은 10을 초과하는 인덱스이기 때문에 9가 나오게 되고, 

lower_bound(10)은 10 이상의 수가 처음 나오는 인덱스이기 때문에 6이 됩니다.