Binary Search / 이진 트리 / 파라메트릭 서치

[WonYong-Jang]

이진 탐색 트리 : 이진 트리 기반의 탐색을 위한 자료 구조

조건

• 모든 노도의 키는 유일
• 왼쪽 서브 트리의 키들은 루트의 키보다 작다. / 오른쪽도 동일
• 왼쪽과 오른쪽 서브트리도 이진 탐색 트리

이진 탐색 트리의 시간 복잡도

- 탐색, 삽입, 삭제 연산의 시간 복잡도는 트리의 높이를 h 라고 했을 때 O(h)

따라서 n개의 노드를 가지는 이진 탐색 트리의 경우, 균형 잡힌 이진 트리의 높이는 logN 이므로 이진 탐색 트리 연산의 평균적인 경우는 O(logN)

[WonYong-Jang]

Parametric Search(파라메트릭 서치)

• 이진 탐색의 응용 버전
• 최소값이나 최대값 등의 최적해 문제를 구할 때 유용하게 쓸 수 있다.

관련 문제

• 2110 공유기 설치

• 1300 k 번째 수

*우선 배열에 ij의 숫자들이 저장 되어 있으므로 K보다 작은 숫자의 개수를 찾고 싶다면 K/i를 해야 구할 수 있다는 것이 포인트**

문제의 예시를 보면 N이 3이고 K가 7일때를 예로 들고 있습니다. 이경우

3*3 배열이므로 아래와 같이 수가 있고 예를 들어 7보다 작은 숫자의 개수를 찾고 싶다면 7/1 + 7/2 + 7/3 을 하는데 이때 7/1 같은경우 7이라는 숫자가 나옵니다. 따라서 몫이 N보다 큰경우는 그 개수가 N개인것과 동일하므로 min(K/i, N) 이라는 식을 사용해야 하는 것을 알 수 있습니다.

1 2 3 2 4 6 3 6 9

자 그렇다면 이제 여기에 이분탐색을 적용시켜 시작 위치를 1로 끝 위치를 K로 하여서 진행을 해주면 됩니다. 위의 예시로 진행과정을 보면 start = 1 end = 7 이므로 mid 지점은 4가 됩니다. 따라서 총 개수는 3+2+1로 6개 입니다. K가 7이므로 start를 mid+1인 5로 바꿔줍니다. 2번째 과정에서 mid는 6이므로 6을 대상으로 계산을하면 3+3+2 = 8개가 나옵니다. 이제 8은 K보다 크므로 result에 mid값을 넣어주고 end에 mid-1을 넣어줍니다. 3번째 과정은 start = 5 end = 5 이므로 mid가 5가나옵니다. 이때 총 개수는 3+2+1 = 6개입니다. start와 end가 동일하므로 마지막 과정이고 5보다 작은수는 6개이고 6보다 작은수는 8개이므로 7번째 수는 6이라는 것이 나오게 됩니다.

long s=1, e= K, mid =0, ans = 0;
while( s <= e) // parametric search
{
    mid = (s + e )/ 2;
    long cnt =0;

    for(int i=1; i<= N; i++)
    {
        cnt += min(N, mid / i);    //mid보다 작은 j의 수(i * j <= mid) !!!!!!!!!!!!!!!!
    }
    if(cnt < K) s = mid + 1;
    else {
        e = mid-1;
        ans = mid;
    }
}

[WonYong-Jang]

k-th number 알고리즘 / 정렬

관련 문제

• 7469 k 번째 수

a = (1, 5, 2, 6, 3, 7, 4) query(2, 5, 3) ==> 2 ~ 5 번째 수를 정렬하고 3번째수 리턴 ==> a[2, 3, 5, 6] 에서 결과 5리턴

index : 1 2 3 4 5 6 7 num: 1 5 2 6 3 7 4

num 기준으로 오름 차순 정렬

index : 1 3 5 7 2 5 6 num : 1 2 3 4 5 6 7

이때 for 문을 돌면서 쿼리 2~ 5번 인덱스를 만나게 되면 카운트를 세어준다 카운트 k == 3 을 만나게 되면 종료 후 출력 오름 차순 정렬해 주었으므로 해당 인덱스 안에만 들어오면 조건 만족함

for(int i=1; i<= N; i++)
{
    num = Integer.parseInt(st.nextToken());
    data[i].num = num;
    data[i].idx = i;
}
Arrays.sort(data, 1, N+1, new mySort());

public static void search(int s, int e, int tCnt)
{
    int count = 0;
    for(int i=1; i<= N; i++)
    {
        if(data[i].idx >= s && data[i].idx <= e) count++;

        if(count == tCnt) {
            System.out.println(data[i].num);
            return;
        }
    }
}

[WonYong-Jang]

관련문제

leetcode 153 Find Minimum in Rotated Sorted Array

leetcode 74. Search a 2D Matrix

=> 2차원 배열 이분탐색 ! => 1차원 배열로 생각하여 탐색 dx = mid / col dy = mid % col

[WonYong-Jang]

class Solution {
    public int searchInsert(int[] nums, int target) {

        int start = 0;
        int end = nums.length - 1;

        while (start <= end) {

            // int mid  = (start + end) / 2; // may exceed the int range

          int mid = start + (end - start) / 2; // better way to find mid 

            if(target > nums[mid] ) {
                start = mid + 1;
            } else if(target < nums[mid]) {
                end = mid - 1;
            } else{
                return mid;
            }

        }

        return start;

    }
}