#7 분할정복 & 이분탐색

분할정복이란?

Divide and Conquer

주어진 문제를 둘 이상의 부분 문제로 나누어 푸는 방법

거의 같은 크기로 부분 문제를 나눔

재귀 호출 사용

 

1) Divide : 부분 문제로 나눌 수 있는 경우 2개 이상의 문제로 나눈다.

2) Conquer : 더 이상 나눌 수 없는 경우 현재 문제를 해결(정복) 한다.

3) Combine : 해결된 부분 문제들을 합쳐서 기본 문제를 해결한다.

 

DP에는 중복이 발생하지만 분할정복에는 중복이 발생하지 않는다.

분할 정복의 전체 높이는 log n이다.

예시문제

백준 1992 (쿼드 트리) c++

 

이분탐색

탐색 범위를 두 부분으로 나눠가면서 원하는 원소를 찾는 방법

탐색 전, 원소가 정렬되어 있어야 함

 

1) 탐색 범위 설정 ex)[s, e]

2) 탐색 지점(mid)설정 후 찾는 값과 비교 ex) mid = (s+e)/2

3) mid가 더 크면 [1, mid-1] 에서 다시 탐색, 더 작으면 [mid+1, e] 에서 다시 탐색

4) s > e 가 될때 까지 2 ~3 반복

탐색을 하는 STL에는 다음과 같은 함수들이 존재합니다.

lower_bound 함수는 찾고자하는 key 이상의 value중 가장 작은값의 인덱스 위치값을 반환합니다.(iterator로 반환)

upper_bound 함수는 찾고자 하는 key 초과의 value중 가장 작은값의 인덱스 위치값을 반환합니다.(iterator로 반환)

binary_search 함수는 찾고자 하는 key가 있으면 true를 반환하고 없으면 false를 반환합니다.

//binary search 
vector<int>v = { 1,2,4,8,9,10 };//항상 정렬되 있어야 한다
vector<int>::iterator it; //반환 받는 iterator 선언
it = lower_bound(v.begin(), v.end(), 3);//3이상의 값중에서 가장 작은값의 인덱스 위치
cout << *it; // 4 (*it 이기 떄문에 위치에 해당하는 값이 나옴)
it = lower_bound(v.begin(), v.end(), 12);
cout << *it; //error(it == v.end())
it = upper_bound(v.begin(), v.end(), 4);//4초과 값중에서 가장 작은값의 인덱스 위치
cout << *it; //8 (*it 이기 때문에 위치에 해당하는 값이 나옴
int x = lower_bound(v.begin(), v.end(), 3) - v.begin(); //첫번째 원소로 부터 떨어진 거리
//v.begin() + 2 - v.begin()
cout << x;//2
x = upper_bound(v.begin(), v.end(), 3) - v.begin();
cout << x;//2
 
cout << binary_search(v.begin(), v.end(), 5); //0(false)

vector<int>v = { 1,2,3,4,4,4,8,9,10 };
cout << upper_bound(v.begin(), v.end(), 4) - lower_bound(v.begin(), v.end(),4); //3

Parametric Search(매개변수 탐색)

최적화 문제(최대, 최소)를 결정문제(참, 거짓)로 바꿔푸는 기법

ex) 적어도 m미터의 나무를 집에 가져가기 위한 절단기의 높이의 최댓값은? (최적화 문제)

-> 절단기의 높이가 k일때 적어도 m미터의 나무를 집에 가져갈 수 있는가? (결정문제)

이분탐색과 유사

차이점 : 이분탐색은 원하는 값이 존재하는가? 존재한다면 어디 있는가?

           파라메트릭 서치 : 조건을 만족하는 값 중 최소/최대가 어디 있는가?

<주의할 점>

최대 or 최소를 구하는 형태여야 한다.

단조성이 있어야 한다.

예시문제

백준 2805 (나무 자르기) c++

예시문제

백준 2343 (기타 레슨) c++