이진 탐색 알고리즘(Binary Search)

 

 

안녕하세요 박스여우입니다.

오늘은 탐색 알고리즘을 알아 보겠습니다.

 

 

Algorithm

 

문제 상황

 

UN이 정상 회담때 각 국가의 대통령들에게 제공할 음료 100개를 준비했다.

하지만 대통령들을 암살할 목적으로 음료에 독극물을 타던 암살자가 붙잡혔다.

다행히 100개의 음료중 한 개의 음료에만 독극물이 타여졌다. 이 음료는 한개에 상상할 수 없을 만큼의 가격이고,

 다시 제작할려면 3개월이나 기다려야 한다. 독극물은 매우 강력해서 독극물이 타여진 음료를 한 방울만 마셔도 즉사하게 된다.

 여기서 독극물이 담긴 음료를 가장 적은 사람의 희생으로 찾을 수 있는 방법은?

 

단, 음료를 한번 시음한 사람은 다시 시음하여 독극물을 확인하지 않는다.

 

 

 

위의 문제 상황은 탐색 알고리즘을 유도할 수 있는 문제입니다.

아래에 답이 있으니 스크롤을 내리지 마시고 한번 곰곰히 생각해 보세요

 

문제 해결 능력은 문제를 많이 해결해 보아야 향상됩니다.

 

 

 

 

 

 

 

Search Algorithm

 

 

위의 문제 상황에서 가장 많이 나온 답은 이진 탐색법 입니다.

 

이진 탐색 알고리즘은 자료들을 둘씩 나눠가며 탐색해 가는 방법입니다.

위의 문제 상황에서 사용해 보게 된다면,

 

처음에는 50개, 50개의 음료를 나눈뒤 한 방울 씩 섞어서 두 명에게 먹입니다.

두번째 역시 위와 같이 독극물이 있는 그룹을 반으로 나눠서 테스트 합니다.

 

이렇게 하게 되면

50 25 12 6 3 2 1 순으로 테스트가 진행되고

최대 6명, 최소 0명을 희생하고 독극물을 찾아낼 수 있습니다.

 

 

 

여기서 잠깐!

 

위의 문제상황에서 음료는 정렬된 자료일까요?

 

이진 탐색 알고리즘을 사용하기 위해서는 자료가 정렬이 되야만 합니다.

따라서 위의 자료는 정렬된 자료입니다.

 

이진 탐색 알고리즘은 자료의 왼쪽 끝과 오른쪽 끝의 중심을 비교하여 자료가 중심보다 크면 오른쪽, 작으면 왼쪽을 비교하는 방식입니다.

출처 : google

 

위의 그림을 통해 설명해 보겠습니다.

우선 그림의 자료 9개의 중앙에 위치한 7의 값과 찾고자 하는 자료인 4를 비교하여 4<7이니 왼쪽의 자료를 비교합니다.

 

두 번 째로 왼쪽의 자료인 1~6까지의 4개 자료의 중앙에 위치한 3의 값과 4를 비교합니다.

4>3이니 오른쪽의 자료들에서 검색합니다.

 

세 번째로 4와 6, 두 개의 자료를 비교한 결과 4<6이니 마지막 하나남은 자료 4의 위치를 찾게 됩니다.

 

 

 

 

이 이진 탐색 알고리즘을 사용해서 자료를 탐색하는 프로그램을 작성하는 것도 알고리즘 작성 능력을

기를 수 있는 좋은 방법이라고 생각합니다.