포스팅 제목 : [python] 문제 풀이 - 12[2110 : 공유기 설치]
안녕하세요 :)
나의 코드가 작품이 되다. 입시전문 코딩 학원! 아이브 코딩 학원입니다.
지난 포스팅에서는 ”2512번 : 예산” 문제를 함께 알아보았습니다. 오늘은 백준 온라인 저지의 ”2110번 : 공유기 설치” 문제를 함께 공부해보겠습니다.
이진 탐색 - “Binary Search”의 특징에 대해 알아보겠습니다.
이진 탐색에서 이진의 의미는 범위를 2로 나누어 반씩 줄여 나가는 것과 연관됩니다. 탐색할 데이터의 전체 범위에 대해 1회 실행할 때 마다 참조하는 범위가 반씩 줄어듭니다. 따라서 시간 복잡도는 $O(Log_2N)$이 됩니다.
실행 횟수를 $x$라고 하면
$$ Log_2N = x \\ N = 2^x \\
다음을 만족하는 $x$가 실행 횟수가 됩니다.
예를 들어 16개의 데이터 중 찾는 데이터가 처음에 있다고 하면 알고리즘을 1회 수행시 참조할 인덱스는 1~8로 줄어듭니다. 2회 수행시 1~4로 줄어듭니다. 3회 수행시 1~2로 줄어듭니다. 이때 답을 찾을 수도 있고 4회 수행하여 찾을수도 있으며 5회 수행될 수도 있습니다. 구현한 알고리즘별로 약간의 차이가 있을 수 있지만 유의미한 차이가 아니며 Big-O 표기법 상으로는 차이가 없습니다.
이진 탐색 알고리즘에서 검색할 인덱스를 절반씩 줄이는 방법은 다음과 같습니다. 정 중앙의 인덱스의 값이 찾는 값 보다 큰지, 작은지, 혹은 원하는 조건과 부합하는지 부합하지 않는 지에 따라 전 단계에서 중앙보다 작은 인덱스를 참조할 지 큰 인덱스를 참조할 지 결정합니다. 이런식으로 범위를 좁혀가며 탐색합니다.
보통 정렬이 되어있는 자료구조에서 활용할 수 있으며 속도 면에서 굉장히 효과적입니다. 다만 이진 탐색을 할 수 있는 엄밀한 조건은 “오름차순으로 정렬이 되어있어야 한다”는 아닙니다. 이에 대해 추가적으로 공부해보면 좋겠습니다.