[코딩 테스트] Python을 통해 알아보는 이진탐색과 비트연산자

 

 

 

 

백준 문제 다른 분 풀이를 참고하는 중에 이진 탐색을 이용해서 푸는 법을 알게 됐다.

(백준 문제 참고 링크: https://www.acmicpc.net/problem/2292)

---

이진 탐색 관련 코드

def fn(t):
	...
    
    
def solve(n):
	result = 0
    l, r = 0, 100000

    while l <= r:
        mid = (l + r) >> 1
        
        if fn(mid) >= n:
        	result = mid
            r = mid - 1
        else:
        	l = mid + 1
            
	return result + 1

 

이진 탐색 알고리즘이 중요한 부분이라 fn 함수에 대해서는 자세한 내용은 생략한다.

 

mid = (l + r) >> 1

중간에 보면 위와 같은 코드가 있는데 이것이 비트연산자(>>)를 이용한 방식이다.

아래 코드와 같은 역할이다(나누기 2와 같다는 뜻).

mid = (l + r) // 2

 

 

이진 탐색에 비트 연산자를 쓰는 이유

1. (과거)

/ 나 // 보다 비트 연산자를 쓰면 경과시간이 더 빠르다는 이유 때문. 

요새 Python에서는 성능 차이가 거의 없다시피 해서 //를 써도 좋다.

C/C++에는 차이가 있다고 한다.

 

2. (근래)

이진 탐색 관용구라 한다. 많이 쓰다보니 계속 쓰는?

 

 

결론

그냥 알아두자.