[알고리즘 개념정리] 7. 이분탐색/분할정복

**본 포스팅은 22Winter 신촌캠프 초급반 강사 raararaara님의 강의를 참고하여 작성하였습니다.**

 

 

이분탐색(Binary Search)

: 정렬된 리스트 arr에서 특정한 값 key를 찾는 알고리즘

• 탐색 구간의 중앙값 mid와의 대소 비교를 통해 다음 탐색 구간을 설정함
• 탐색 연산이 반복적으로 요구될 때 사용함
• key값의 유무를 반환함

https://www.acmicpc.net/blog/view/109

bool binary_search(int *arr, int len, int key){
    int l = 0;
    int r = len-1;
    int mid;

    while(l <= r) {
        mid = (l + r) / 2;    //중앙 값

        if (arr[mid] == key) {    //key값을 찾았음
            return true;
        } 
        else if (arr[mid] > key) {   //key값이 mid 값보다 작으면 왼쪽으로
            r = mid - 1;
        } 
        else {  //key값이 mid 값보다 크면 오른쪽으로
            l = mid + 1;
        }
    }
    return false;
}

시간 복잡도

• 탐색 구간을 새로 설정할 때마다 길이가 절반씩 감소
• 최악의 경우 탐색 구간의 길이가 1(=2^0) 일 때 탐색 중지
• 리스트의 크기를 n=2^m이라 할 때, m(=log_2_n)번의 반복 끝에 존재 여부 확인 가능

따라서 탐색의 시간 복잡도는 O(logN) 이다.

정렬하는데 O(NlogN)이고 탐색하는데 O(logN)이면 총 O(NlogN)인데
그럼 그냥 선형 탐색 O(N)이 더 낫지 않나..?라고 생각할 수 있다.

하지만 N, 탐색 횟수 K가 크다면 얘기가 달라진다.

정렬하지 않고 선형 탐색 K번을 하면 O(KN),
정렬 한번 하고 이분 탐색 K번을 하면 O(KlogN) 이므로
후자가 더 유리하다.

즉, 정렬이 많이 일어나지 않고 탐색이 많이 일어날 때는 이분 탐색을 사용하는 것이 좋다.

 

**
lower_bound

: key 이상의 값이 처음 나오는 위치를 반환함
  즉, 인덱스가 아니라 주소 값(iterator)을 반환한다!

ex) arr = [2, 3, 5, 7, 11, 11], key = 8
    lower_bound(arr, arr+6, key) - arr = 4
      lower_bound(arr, arr+6, key) : 주소값
      arr : 배열의 idx 0의 주소값     
      4 : 배열에서 key값이 있는 곳의 idx  

 

upper_bound

: key 초과의 값이 처음 나오는 위치를 반환함
  즉, 인덱스가 아니라 주소값(iterator)를 반환한다!

ex) arr = [2, 3, 5, 8, 8, 11], key = 8
     upper_bound(arr, arr+6, key) - arr = 5

lower/upper_bond 구현 코드는 아래 링크 참고
https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=bestmaker0290&logNo=220820005454

 

 

---

 

 

좌표압축

: 간격 또는 중복 정보를 제거하여 많은 점 집합을 더 작은 범위에 mapping 하는 기법

• 실제 간격의 정보가 덜 중요할 때
• 중복 값이 많고 상대적인 순서만 알아도 될 때
• (좌표상에서) 범위는 크지만 실제 점 개수(좌표 정보의 개수)는 적을 때

ex)

real	1	5	3	7	2
pressed	0	3	2	4	1

 

int n, a[n];
vector<int> list;

cin>>n;
for(int i=0; i<n; i++){
    cin>>a[i];
    list.push_back(a[i]); // real값들을 입력받아서 벡터에 담아준다.
}

sort(list.begin(), list.end()); // 오름차순 정렬
list.erase(unique(list.begin(), list.end()), list.end());
// unique는 중복되는 원소들을 뒤로 빼는 함수이며, 중복이 시작되는 위치를 리턴한다.
// erase는 중복이 시작되는 위치부터 끝까지 중복원소를 제거해준다.

for(int i=0; i<n; i++){
    a[i] = lower_bound(list.begin(), list.end(), a[i]) - list.begin();
    // real a[i]값을 compressed a[i]값으로 갱신시켜준다.
    // list에서 a[i]가 (처음)등장하는 곳의 idx가 a[i]를 좌표압축한 결과이다.
}

 

 

 

---

 

 

매개변수 탐색

: 최적화 문제를 결정 문제로 바꾸어 푸는 기법

•  결정 문제
    : 어떤 문제 상황이 주어지고 그 문제의 답변이 True/False의 형태로 나오는 문제
     ex) 너 실버1 문제 풀 수 있니?
  
  
•  최적화 문제 
    : 최솟값/최댓값을 요구하는 문제
     ex) 지금까지 푼 문제 중 가장 어려운 문제는?
  -> 결정 문제로 바꾸어 풀 수 있다!
     ex) 모든 문제에 대해 "이 문제가 가장 어렵니?"라고 물어보기

일반적으로 
결정 문제의 난이도 <= 최적화 문제의 난이도이다.

따라서 최적화 문제를 결정 문제로 바꾸어 푸는 기법을 매개변수 탐색이라고 한다.

 

그래서 최적화 문제를 결정문제로 푸는 방법은??
: 특정 파라미터를 기준으로 조건을 만족하는 부분과 만족하지 않는 경계점을 찾는다.

ex) 너가 푼 문제 중에 가장 어려운 문제는?
     실버5  실버4  실버3  실버2 | 실버 1                   
                 : true (풀었음)       | :false (안 풀었음) 
                               이 경계점을 찾자!

 

 

---

---

 

 

분할정복(Divide & Conquer)

: 문제를 (비슷한 크기의) 둘 이상의 부분 문제로 나눈 뒤 (Divide)
 각 문제에 대한 답을 계산하고 (Conquer)
 원래 문제에 대한 답으로 병합 (Merge)

일반적으로, 중복되는 부분 문제없이 완벽하게 나눠진다.

* DP와의 차이점?
 : DP는 중복되는 부분 문제가 있어서 이를 메모이제이션으로 해결한다.

 

시간 복잡도

구간 길이 N에 대한 처리 비용을 T(N)이라 하고 문제를 k분할했을 때
T(N) = kT(N/K) + C(N)
        : k개 구간 분할 + 병합 비용

구간을 절반씩 쪼갠다고 하면
N개의 원소를 정렬하는데 드는 비용 T(N) = 2T(N/2) + N이 된다.
N = 2^m을 대입하고 수식의 규칙을 찾아 적절히 정리하면 T(N) = NlogN 이다.

 

분할 정복의 대표적인 예시로는 병합 정렬(Merge sort)이 있다.
정렬방법 및 코드는 아래 링크 참고
https://dpdpwl.tistory.com/53

 

 

---

 

 

 

분할정복을 이용한 거듭제곱

: a^n = a * a * ... * a 를 O(logN)으로 푸는 방법

* 내장 함수 pow() 쓰면 되는 거 아닌가?
  : pow()는 리턴 타입이 실수형이라서 실수 오차가 발생한다.
    ex) 2022.01.16 - [PS/Baekjoon] - [백준/C++] 5525번: IOIOI(S2)
   따라서 정수형 거듭제곱은 실제로 구현이 필요한 경우가 있을 수 있다.

 

a의 b승 (b=19)를 구해보자.

• basecase는 b==0일 때이다. (a^0 = 1)
• b가 홀수인 경우는 -1해서 짝수로 만들고 a를 곱한다. (a^19 = a^18 * a^1)
• b가 짝수인 경우는 그 절반에 해당하는 값을 두 번 곱한다. (a^18 = a^9 * a^9)
  중복되는 부분은 여러 번 계산하지 않기 위해 두 번 곱한다. (a^9는 한 번만 분할 정복) 

int pow(int a, int b){
    if(b==0) return 1;
    if(b%2==1) return pow(a,b-1)*a;
    
    int half = pow(a, b/2);
    return half * half;
}

 

 

 

 

---

관련 문제

• 이분탐색
  10816. 숫자카드 2 (정답코드)
  
  
• 좌표압축
  18870. 좌표 압축 (정답코드) (좌표압축 개념 참고용)
  2022.02.03 - [PS/Baekjoon] - [백준/C++] 2370번: 시장 선거 포스터(G4)
  2022.03.12 - [PS/Baekjoon] - [백준/C++] 11997번: Load Balancing (Silver)(G4) 이차원
  
  
• 매개변수 탐색
  2022.02.03 - [PS/Baekjoon] - [백준/C++] 16564번: 히오스 프로게이머(S1)
  
  
• 분할정복
  17829. 222-풀링 (정답코드)
  1802. 종이접기 (정답코드)
  
  
• 분할정복을 이용한 거듭제곱
  1629. 곱셈 (정답코드)
  14440. 정수수열 (정답코드) (행렬 거듭제곱) 
  
  
• 분할정복을 이용한 거듭제곱 + DP
  : solved.ac에 아래의 태그로 문제 검색을 하면 많이 나온다.
    tag: exponentiation_by_squaring tag: dp