이분탐색(binary search)에 대한 탐구 feat. 시간 복잡도, 정렬 etc

 

 

 

 

이 포스팅에는 제가 이분탐색 문제를 풀면서 깨달은 바를 적어보겠습니다.

(고수분들은 보지 않으셔도 좋습니다. 하수가 적은 것이기 때문에...)

 

 

보통 이분탐색은 탐색해야 하는 범위가 너무 큰 경우, 시간을 줄이기 위해서 사용하게 됩니다.

주로 작은 수부터 큰 수로 정렬을 한 뒤에 특정 숫자보다 크면 범위를 작은 숫자가 있는 범위로 옮기고, 작으면 큰 숫자가 있는 범위로 옮겨서 탐색을 하게 됩니다.

 

그렇기 때문에 어느 새인가부터 습관적으로 배열을 정렬해서 사용하기 시작했습니다.

물론 정렬을 사용해서 푸는 것이 틀린 것은 아닙니다.

하지만 어떤 경우에는 정렬을 하지 않는 것이 시간복잡도가 줄어드는 경우가 있습니다.

 

https://www.acmicpc.net/problem/16401

 

백준의 과자 나눠주기(16401) 문제입니다.

배열의 크기의 범위가 1 ≤ N ≤ 1,000,000, 그 안의 숫자들 역시 1 ≤ L1, L2,..., LN ≤ 1,000,000,000로 감당이 안 되는 수준입니다.

 

 

 

하지만 동일한 로직임에도 불구하고 정렬은 한 경우 시간이 1188ms, 정렬을 하지 않고 그냥 n번을 전부 탐색한 경우 692ms가 나왔습니다.

왜 이럴까요? 저는 GPT에게 질문할 수 밖에 없었습니다. (스스로는 모르기 때문에)

GPT는 이렇게 답했습니다.

 

• Arrays.sort()는 O(n log n)으로, 배열의 크기가 커질수록 상당한 시간이 소요됩니다.
• 단순한 for 반복문은 O(n)으로, 배열을 순회하면서 계산하는 것이므로 비교적 빠릅니다.

정렬을 하는 경우 시간복잡도가 nlogn, 단순반복은 n이니 때문에 정렬을 하는 것이 더 시간복잡도가 높아지기 때문이었습니다.

 

그렇다면 정렬을 해야 하는 경우, 아닌 경우는 어떻게 나눌 수 있을까요?

 

 

• 배열이 정렬된 상태에서 특정 값을 찾아야 할 때는 정렬이 필수적입니다. (예: 값을 찾는 문제)
• 하지만 최대값, 최적화된 값을 구할 때는 배열이 정렬될 필요가 없고, 정렬을 생략하는 것이 시간 효율성을 높일 수 있습니다.

그렇다고 합니다.