검색 최적화 : 정렬을 이용해서 부분집합 여부 판단하기

위 문제를 한번 풀어보자.

가장 쉬운 방법은 A에서 인수를 하나씩 꺼내서 B의 모든 인수와 대조하는 것이다.
그리고 두번째 인수를 꺼내서 다시 B의 모든 인수와 대조하고
그렇게 A의 개수 * B의 개수만큼의 LOOP를 반복하게 된다.

이를 대략적인 코드로 나타내면 아래와 같을 것이다.


for i in range(1, count(A)):
    for j in range(1, count(B)):
         if A(i) = B(j) then 1 else 0

그러나 이런식으로 모든 인수를 뒤지는것은 상당히 비효율적이다.

따라서 능력 있는 프로그래머라면 이것을 어떻게 하면 고민을 해야한다.
어떻게 하면 위 문제를 깔끔하게 풀 수 있을까?

답은 바로 '정렬'에 있다.
'정렬'을 이용하면 위와같은 비효율성을 대폭 줄일 수 있다.

A와 B를 정렬시켜 놓고 비교를 하면 아래와 같은 구조로 검색을 하게 될 것이다.

이 알고리즘은
count(A) * count(B)의 불필요한 loop를
+(더하기) 로 바꿔준다는 데에 엄청난 의의가 있다.

B의 인수들을 비교할 때 기존에 찾은 다음부분부터 읽으면 되기 때문에
이미 카운팅한 부분을 다시 탐색할 필요가 없어진다.

작은 트릭 하나로 검색 전체의 효율성이 개선된 것이다.