추측 게임
ko.khanacademy.org
설명
알고리즘 개념에 대해 미숙한점이 많아 칸아카데미에서 한 번 알고리즘을 숙지하는 시간을 가져본다. 이번 글에선 추측게임을 통한 알고리즘의 기본개념에 대해 알아보자.
위와 같이 16개의 수가 있다. 컴퓨터는 무작위로 정답을 고르고 우리는 그 수를 맞춰야한다. 우리가 틀릴때마다 컴퓨터는 정답이 더 높은 수인지, 낮은 수 인지 알려준다.
만약 정답을 찾기위해 1부터 16까지 차례대로 체크를 한다면 이는 어떤 알고리즘이라고 부를까? 선형검색 알고리즘이다. 영어로는 linear search다.
하지만 여러분 중 선형검색 알고리즘으로 정답을 맞춰야지라고 생각했던 사람은 드물것이다. 아마도 가장 유사한 방법이 위의 방법과 같다. 가운데쯤 찔러보고 높은지 낮은지 살펴보고 또 가운데 찔러보고 높은지 낮은지 보고... 계속 반복...
이 방법을 이진 탐색이라고 부른다. 영어로는 binary search다. 이 방법대로 하게되면 위 문제를 최대 네 번이면 수를 무조건 맞출 수 있다. 모르고 풀었을땐 이 사실을 몰랐는데, 알고나니 참 재미있다.
이번엔 위 숫자에서 정답을 맞춰보자. 최대 9번의 기회로 정답을 맞출 수 있다.
이진탐색(binary search)를 사용하면 최대 9번이면 정답을 추려낼 수 있다.
이상입니다.