이분탐색과 업앤다운 게임

* backjoon 문제번호

이분탐색/삼분탐색 - 1654, 2805, 2110, 10815, 10816, 11662

완전탐색 - 1476, 1107, 1451, 9095, 10819, 10971, 1697, 1963, 9019, 1525, 2251, 2186, 3108, 5014, 1759, 2580, 1987, 6603, 1182, 2003, 1806, 1644, 1261, 1208, 7453, 2632, 2143

 

기본 문법을 얼추 떼고, 알고리즘 세계로의 입문이다. 탐색이며 시간복잡도며, 낯선 단어들을 도장깨기 하고 있다.

 

탐색

컴퓨터는 인간이 할 수 없는 속도로 어떤 solution을 제공한다. 예를 들어, 목적지까지 가는 1000가지의 경로 중 어떤 것이 가장 효율적인가? 같은 문제들을 컴퓨터는 1초도 안되는 시간에 해낸다. 탐색은 쉽게 말해, 조건에 맞는 답을 찾아내는 것이다. 고등학교 때 재밌게 풀던 방정식을 떠올려보면, 여러 조건에 맞는 하나의 x값을 찾아내는 점이 탐색과 닮아있다.

 

이분 탐색

탐색은 단순하게 하나씩 다 계산해보는 방법, 반씩 쪼개서 범위를 좁혀가는 방법 등이 있고, 또 탐색해나가는 순서에 따라(깊이, 넓이) 종류가 나뉜다. 그 중에서도 이분탐색은 반씩 쪼개서 범위를 좁히는 방법이다. 소주뚜껑 술게임을 연상해보면 이분탐색은 훨씬 이해하기 쉬워진다. 소주 뚜껑에는 보통 100이하의 숫자가 적혀있다. 이 숫자를 특정 횟수 안에 맞추는 게임으로 업앤다운의 일종이다.

만약 12라는 숫자가 적혀있다고 할 때, 맞추는 사람은 범위를 효과적으로 좁히기 위해 50을 외친다. 이 때 출제자는 50보다 작은 숫자가 적혀있으므로 다운이라는 힌트를 준다!

다음으로 외치게 될 숫자는 당연히 25 혹은 26! 다운.

12! 정답.

 

단 세 번만에 1~100의 범위에서 12를 찾아냈다. 만약 당신이 1부터 순차적으로 100까지 불렀다면 최악의 경우 100번째에 숫자를 맞추게 될 수 있다. 이처럼 이분탐색은 범위가 큰 숫자에서 반씩 쪼개 효과적으로 범위를 좁혀가는 원리를 적용하는 알고리즘이다.

 

적용

예시 문제는 백준 2110번을 활용한다.

 

 

2022. 03. 13 작성중