강의 보고 공부한 것을 정리하는 목적으로 작성된 글이므로 틀린 점이 있을 수 있음에 양해 부탁드립니다. (피드백 환영입니다)

퀴즈

일단 먼저 퀴즈!

[1][8][15][23][32][44][56][63][81][91]
vector에 이러한 숫자들이 있다고 하였을 때

여기안에 82라는 숫자가 있을까? 라는 질문을 하였을 때 어떻게 코드를 짤 것인가?
일반적으로 일일이 스캔을 한다면 조금 느릴 것이다(O(N)).
하지만 만약에 데이터가 정렬이 되어 있다는 힌트가 있다면 다른 접근을 할 수 있다.

1, 8, 15, 23, 32, 44, 57, 63, 81, 91 이러한 값이 있을 때

일단 중간을 찍어서(32정도) 판별을 해본다면 32가 82보다 작기때문에 검색할 범위가 절반으로 줄어들 것이다.
즉, 1, 8, 15, 23, 32는 날라가 버리고 또 중간을 골라서(63) 판별을 하면 63이 82보다 작기때문에 44, 56, 63이 날라가 버린다.

이런식으로 계속 판별을 해줘서 반씩 날려버려서 최종적으로 82라는 숫자가 있는지 없는지 알 수 있을 것이다.
이러한 것을 이진 탐색(binary search)라고 한다.

이진 탐색

이진 탐색의 시간복잡도는 O(logN)이라는 것도 알 수 있다.
왜냐면 저번에 말했던 것처럼 뭔가 반을 나누는 것에는 log를 붙이라고 하였기 때문에 이진탐색은 계속 범위를 반으로 줄이기때문에 O(logN)이라는 것을 알 수 있다.

데이터가 N개가 있을 때 몇 번을 서치를 해야지만 최악의 경우 N을 찾을 수 있냐고 하면

수학 공식상
2^? = N
? = logN
이기 때문이다.

그래서 사실상 정렬이 되어 있다는 보장만 있다면 굉장히 좋은 방식이라고 할 수 있다. 이것이 이진 탐색(binary search)이다!

그리고 이 이진 탐색에 경우에는 코딩시험에 자주나온다.

그럼 한 번 구현 해보자

구현

일단 토대는 이런식으로 짤 수 있을 것이다.

vector<int> numbers;

void BinarySearch(int N)
{

}

int main()
{
	numbers = {1, 8, 15, 23, 32, 44, 57, 63, 81, 91};
    BinarySearch(81);
}

이런식에 코드가 있을 때 짜볼것이다.
여기서는 재귀함수의 사용여부에 따라 코드를 짜는 것이 달라질 것이다.

재귀함수를 사용하지 않는다면 while문을 사용해서 한 번에 만들 수 있고
재귀함수를 사용하면 start와 end를 매개변수로 추가적으로 받아서 만들 수 있다.

우리는 일단 재귀함수를 사용하지 않고 구현해볼 것이다.

먼저 left와 right를 만들어서 시작 인덱스와 끝 인덱스를 관리해 줄 것이다.
그리고 mid라는 중간 인덱스와 비교를 하여서 만약 찾는 N값이 mid보다 크다면 left를 mid의 자리로 옮겨주면 된다 반대로 N값이 mid보다 작다면 right를 mid의 자리로 옮겨주면 된다.
그리고 언젠가는 한 값만 남게 될 것인데 만약 그 값으로 판단하면 된다.

vector<int> numbers;

void BinarySearch(int N)
{
    int left = 0;
    int right = numbers.size() - 1;

    while (left <= right)
    {
        cout << "탐색 범위 : " << left << "~" << right << endl;

        int mid = (left + right) / 2;

        if (N < numbers[mid])
        {
            cout << N << " < " << numbers[mid] << endl;
            right = mid - 1;
        }
        else if (N > numbers[mid])
        {
            cout << N << " > " << numbers[mid] << endl;
            left = mid + 1;
        }
        else
        {
            cout << "찾았음!" << endl;
            break;
        }
    }
}

int main()
{
    numbers = { 1, 8, 15, 23, 32, 44, 57, 63, 81, 91 };
    BinarySearch(81);
}

이런식으로 구현해줄 수 있다.

그러면 이런식으로 값이 출력된다.

그래서 이런식으로 접근을 하는 것이 이진 탐색이다.

이진 탐색 한계

지금 우리는 vector로 작업을 하였지만 list로 할 수 있을까?

안된다!

지금 우리는 특정 인덱스에 접근할 수 있는 임의접근을 사용해서 코드를 만들었기때문에 list로 사용할 수가 없다.
list는 중간에 원하는 인덱스에 바로 접근을 할 수 없다. (임의 접근 불가)

그래서 우리는 list로 이진 탐색을 할 수가 없다.

이진 탐색의 시간복잡도가 O(logN)으로 생각보다 빠르기 때문에 나중에
mmorpg에서 몬스터를 서치할 때 vector로 이진탐색을 사용하면 되지 않을까? 라고 생각할 수 있다. (그냥 쭉 서치하는 것보다는 빠르기 때문에)

그러면 "mmo를 만들때 왜 map까지 사용을 하냐? 그냥 vector로 충분하지 않느냐?" 라고 할 수 있다.
하지만 한계가 있다..그러면 어떠한 한계가 있을까를 알고 다음것을 배워야 한다.

그 한계는 정렬에 있다.
"엥? 그럼 그냥 값을 넣을 때 중간에 찾아서 넣어주면 되는거 아닌가요?"라고 할 수 있는데..여기서 중요한 점은 vector는 중간 삽입/삭제가 안된다. (할 수는 있지만 느림..)

그래서 고정된 데이터라면 분명 좋지만 대부분의 상황에서는 몬스터가 들어가고 나오고이럴꺼기 때문이다.

이진탐색이 좋긴 좋지만 중간삽입삭제가 느리다는 배열의 특징때문에 데이터가 고정적인 상황에서만 사용을 할 수 있고 데이터가 계속 변화하는 상황에서는 한계가 명확하다.

그래서 대안으로 중간삽입/삭제가 빠르지만 up, down을 할 수 있는 걸 찾는 것인데
그것이 트리구조를 개선시켜서 발전시키면서 공부하는 것이 목표이다.

마무리

이진탐색은 결국 고정된 데이터에 한정되어서 사용할 때 빠르고
중간 삽입/삭제가 있다면 느려진다..

그래서 다음에는 개선된 버전인 Binary Search Tree를 공부해볼 것이다!