10억 개 전화번호에서 이름찾기 이진검색과 퀵 정렬로 검색을 쉽게 만들기

소프트웨어 20, 10억 개 전화번호에서 이름찾기 : 이진검색

 

계산 시간이 데이터의 양에 정비례하거나 선형적으로 비례할 때, 선형 알고리즘(linar algorithm)이라고 함

 

   선형 알고리즘보다 더 나은 방법은 없을까? 이름과 전화번호가 적힌 리스트나 명함 다발이 많이 있다고 가정해보자. 이름이 순서없이 섞여 있는 상태에서 '마이크 스미스'의 전화번호를 찾으려 한다면, 그 이름을 찾을 때까지 리스트를 전부 확인해야 할 것이고 아예 그 이름을 찾지 못할 수도 있다. 하지만 이름이 알파벳순으로 되어 있다면 더 쉽게 찾을 수 있다.

 

  종이 전화번호부에서 이름을 찾는 방법을 생각해보자. 중간 페이지부터 반을 갈라 알파벳순으로 보며 해당 알파벳을 찾으면 절반 관계없는 페이지는 무시하고 점점 범위를 좁히며 찾게된다. 노래방 책 또한 같다.

  이 검색 알고리즘을 이진 검색(binary search)이라고 한다. 이는 분할 정복(divide and con-quer)이라는 일반적인 전략의 한 가지 예로 속도가 매우 빠르다.

 

 

 

  이름 1,024개로 시작한다고 가정 했을 때, 한 번 비교하면 절반인 512개를 검색 대상에서 제외할 수 있다. 한 번 더 하면 256개...128,64,32,16,8,4,2,1 세어보면 10번의 비교가 일어났다. 여기서 2의10제곱이 1,024라는 것은 결코 우연이 아니다.

각 수를 역순으로 따라가보면 1,2,4 ... 1,024까지 따라가보면 매번 2를 곱하고 있음을 알 수 있다.

  

  이진 검색에서 중요한 점은 수행해야 하는 일의 양이 데이터의 양이 증가하는 것에 비해 천천히 증가한다는 것이다.

정렬된 이름 1,000개가 있을 때, 특정 이름을 찾으려면 이름 10개를 확인하는데 2,000개가 있다면 이름 11개만 확인하면 된다. 왜냐하면 첫 번째로 이름을 확인할 때 2,000개 중 1,000개가 검색 대상에서 제외되기 때문이다.

즉, 이름은 1,000개 늘었지만 검사 횟수는 1번 늘어났을 뿐이다.

 

여기서 10억 개 담긴 전화번호부에서 이름을 찾으려한다면 10억은 2의30제곱이기 때문에 30번만 이름을 비교하면 된다는 것을 알 수 있다. 데이터의 양이 1,000배 많아지더라도 10번의 단계만 더 필요하다.

 

또한 70억 명의 참가자가 있더라도 승자를 결정하는 데는 단지 33번의 회전이 필요하다.

그렇다면 한창 유행했던 아키네이터라는 이름 맞추기 게임도 질문이 추가되지만 원리는 같지 않을까??

내가 생각하는 캐릭터를 맞추는 검색 알고리즘 서비스

https://kr.akinator.com/

 

 

 

 

소프트웨어 21, 검색을 쉽게 만드는 정렬 : 선택정렬 VS 퀵 정렬

  애초에 어떻게 하면 이름을 알파벳 순으로 배치할 수 있을까?? 그런 예비 단계 없이는 이진 검색을 이용할 수 없다. 여기서 또 다른 핵심적인 알고리즘 문제인 정렬(sorting)이 등장한다. 정렬은 항목을 순서대로 배열해서 검색이 빨리 실행될 수 있도록 해준다.

  이진 검색으로 효율적으로 찾을 수 있도록 사전에 이름을 알파벳순으로 정렬하고 싶다고 가정해 보자. 먼저 살펴볼 알고리즘은

선택 정렬(selection sort)이다.

 

우리에게 익숙한 16개의 기업 이름을 알파벳순으로 정렬하면서 실제로 확인해보자.

1. 각 기업을 하나씩 비교(열 여섯 번)해서 알파벳순으로 정렬한다면 Apple이 가장 먼저 오게된다.

 

2. 첫 번째 이름을 찾고 하나씩 빼주고 하다보면 결국, 16+15+14+...+3+2+1 총 136번 이름을 확인해야 한다. 훑어볼 때마다 이름이 한 개씩 줄어들기 때문에 다음과 같이 계산된다.

 

N+(N-1)+(N-2)+(N-3)+...+2+1 

 

  이 수열을 제곱으로 풀어본다면 예로 N이 1,000이면 N제곱은 100만이다. 결과적으로 일의 양은 N제곱, 즉 N의 제곱에 거의 비례하게 되는데, 이러한 증가율을 2차(quadratic,제곱)라고 한다. 2차는 일정하게 늘어나는 선형보다 효율이 훨씬 더 낮다. 만약 정렬할 항목의 수가 2배가 되면 4배의 시간이 걸릴 것이고, 10배라면 100배의 시간이 걸릴 것이다. 항목의 수가 1,000배라면 1,000,000배의 시간이 걸린다! 썩 좋지않구만!

 

그래서 이걸 해결해볼 기발한 방법이 바로 퀵 정렬(Quicksort)라는 알고리즘으로 영국인 컴퓨터과 학자인 토니 호어(Tony Hoare)가 1959년경에 고안했다(퀵 정렬 포함한 몇 가지 공로를 인정받아 1980년 튜링상을 받았다.)

 

 

1. 다시 처음 정렬되지 않은 상태에서 시작하면, 먼저 A~M 한 그룹 N~Z까지 다른 그룹으로 모은다. 그럼 각각 반을 나눠 

8개의 이름이 들어간다.

 

2. A-M 그룹을 훑어보면서 A~F, G~M까지를, N-Z 그룹은 N~S, T~Z까지 나눈다.

 

3. A-F그룹을 ABC, DEF / G-M그룹은 GHIJ,KLM / 나머지도 이와 같이 나눠준다. 그럼 두 개 정도의 이름을 담은 여덟개의 그룹이 생긴다. 이후에 한 두번 더 나누면 이름을 한 개씩 담은 16개의 그룹을 갖게되고, 이름들은 알파벳순이 됩니다.

 

  앞선 선택 정렬에서는 16개의 이름을 각각 확인했지만 퀵 정렬은 딱 떨어진다면 그룹을 8개, 4개, 2개 마지막 한 개의 이름이 담길 것이고 단계의 수는 16이 1이 될 때까지 2로 나누는 횟수로 이 값은 밑수 2에 대한 16의 로그로, = 4가 됩니다.

이는 선택 정렬에서 136번 연산하는 것보다 훨씬 적습니다. 지금은 이름이 16개일 때 이야기며,

이름이 더 많아지면 퀵 정렬의 장점은 훨씬 더 커진다. 그림에서 확인해보자

 

 

  퀵 정렬은, 그룹을 나눌 때마다 거의 같은 크기의 덩어리로 나눠야만 효율적이다.

일반적으로 퀵 정렬로 N개 항목을 정렬하려면 약 NlogN번의 연산이 필요하다. 즉, 작업의 양은 N * logN에 비례한다.

선형 보다는 효율이 낮지만 심하지는 않고, N이 조금이라도 크다면 2차, 즉 N제곱(선택 정렬)보다 훨씬 효율적이다.

 

  위의 사진은 수의 개수 별로 정렬 시간을 비교해보았다.결과로 항상 퀵 정렬이 우수하며 경쟁이 되지 않는 수준입니다.

선택 정렬이 100,000개의 항목을 처리하는데 걸리는 시간이 10,000개 보다 100배 클 것으로 예상했지만 실제로는 거의 200배 크다는 점을 알아챌 수 도 있습니다. 미리 고려하지 못한 캐싱, 컴퓨터상황의 영향일 수 있어 계산 과정을 이론적으로 추상화한 것과 프로그램이 실제로 계산을 수행하는 상황 간의 차이를 잘 보여준다.

  이렇게 이진 검색에 대한 방법으로 선택과 퀵 정렬을 알아보고 퀵 정렬이 얼마나 효율적이고 사용해야하는지 알아보았다.

 

추가로 퀵 정렬의 예시로 지인에게 들은 얘기로 주식 종목추천이 이런식으로 진행 된다는 것을 들었는데, 100명을 50,50으로 나눠 종목 하나는 매수, 하나는 매도를 뿌리고 맞춘곳에다가 또 나눠 매수,매도를 뿌리고 이렇게 여러번 맞추다보면 1명은 정말 운이 좋게 뽑힌건데 종목 추천해준 그 회사 자체를 신봉할 수 밖에 없다고 합니다. 그리고 5개 중에 1개만 맞아도 수익률이 높고 돈에 눈이 멀다면 돈 잃는것은 한순간이다.

이렇게 효과적으로 이용할 수 있지만 내가 당할 수도 있다는 것을 잊지말자
더 나아가 내가 어디에 적용할 수 있을지 생각도 해보자