kongrpt   2년 전

이렇게 작성을 했는데 계속 시간초과가 뜹니다.
StringBuilder를 사용 안 하고 작성하고 싶은데 방법이 있을까요 ?

euphoric_n   2년 전

이 문제는 단순히 모든 수를 확인하는 방법으로는 풀 수 없습니다.

m, n이 최대 10만이므로 28, 29번 줄의 반복문은 최대 100억번 반복됩니다.

kongrpt   2년 전

내장 함수를 사용하는 건가요 ?

euphoric_n   2년 전

이분 탐색(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) 입니다.

댓글을 작성하려면 로그인해야 합니다.