이 문제는 단순히 모든 수를 확인하는 방법으로는 풀 수 없습니다.
m, n이 최대 10만이므로 28, 29번 줄의 반복문은 최대 100억번 반복됩니다.
1920번 - 수 찾기
이 문제는 단순히 모든 수를 확인하는 방법으로는 풀 수 없습니다.
m, n이 최대 10만이므로 28, 29번 줄의 반복문은 최대 100억번 반복됩니다.
이분 탐색(binary search) 알고리즘을 사용합니다.
예를 들어 아래와 같이 정렬되어 있는 배열을 가정해봅시다.
1 2 5 7 10 13 17 20 21 24 28 30
이 배열에서 24가 존재하는지 이분 탐색으로 확인하겠습니다.
우선 가운데 원소를 먼저 확인합니다.
가운데 원소 13은 24보다 작기 때문에 왼쪽은 탐색 대상이 아닙니다. (배열은 정렬되어 있기 때문입니다.)
13보다 큰 값에 대해 다시 한번 탐색합니다.
가운데 원소 21은 24보다 작기 때문에 21보다 큰 값에 대해 탐색합니다.
이 과정을 반복하면 수가 존재하는지 찾을 수 있습니다.
1 2 5 7 10 13 17 20 21 24 28 30
^ left(0) ^ mid(5) ^ right(11)
^ left ^ mid ^ right
(반복)
이분 탐색 알고리즘은 한번 탐색할때마다 후보를 반으로 줄이기 때문에 시간 복잡도는 O(logn) 입니다.
댓글을 작성하려면 로그인해야 합니다.
kongrpt 2년 전