본문 바로가기
PS/Algorithm

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

by 이지이즤 2022. 2. 2.
728x90

**본 포스팅은 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;
}

 

 

 

 

관련 문제

 

 

728x90

'PS > Algorithm' 카테고리의 다른 글

[알고리즘 개념정리] 9. 트리  (0) 2022.02.09
[알고리즘 개념정리] 8. 그래프/그래프 탐색  (5) 2022.02.05
[알고리즘 개념정리] 6. 완전탐색/백트래킹  (0) 2022.01.29
[알고리즘 개념정리] 5. 선형 자료구조(스택,큐,덱)  (0) 2022.01.27
[알고리즘 개념정리] 4. 그리디  (0) 2022.01.22

관련글

댓글

티스토리툴바