알고리즘] 이분탐색에 대해서 알아보자 (스테픈 2km 완료)

yonggyu01 (73)in SCT.암호화폐.Crypto • 21 days ago

어제 백준 문제를 풀어보던중에

이런 문제를 접하게 되었다.

상근이가 가지고있는 N개의 카드와 비교대상인 M의 카드를 비교해서 상근이가 가지고 있는 카드인 경우 1

아닌경우 0으로 표시하는 문제인데

아무생각없이 반복문을 중첩해서 문제를 처리했다.

하나식 대입해서 있는경우 1을 넣어주고 없는경우 기존에 0이 들어있으니 패스하는 방식인데

이렇게 해서

정답처럼 나오게 만들었는데

정답을 제출하면 시간초과가 뜬다.

문제를 다시 읽어보면

시간복잡도에서 N의 값에 최대 500,000 이 들어갈 수 있다는 말인데

내가 작성한 코드의 시간복잡도를 먼저 계산하자면

N * (N *O(1)) +O(1) 이럴것이다.

여기서 정수값을 빼고 최고차항끼리 곱해주면

N^2 라는 값이 나온다.

이 문제는 2초라는 시간이 주어진다.

시간복잡도에서 10^8 이 약 1초다.

그렇다면 해당 문제에서 최대값으로 숫자가 들어온다면

내 계산대로라면 약 41분의 시간이 걸릴수도 있다는 소리이다.

한마디로 내가 작성한 알고리즘이 잘못되었다는 소리이다.

이번 문제를 계기로 문제를 풀기전에 주어지는 N의 최대값이 어느정도인지 에 따라서

어떤 알고리즘을 사용해야할지를 유추가 가능하다

이번 문제를 보니 이분탐색 알고리즘을 사용해서 풀면 시간초과가 걸리지 않는다고 한다.

이야기가 길어졌는데

이분탐색에 대해서 알아보자

*이진 탐색(이분 탐색) 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.
(출처 : https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%EA%B2%80%EC%83%89_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98)

ezgif.com-gif-maker61.gif

이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다.
변수 3개(start, end, mid)를 사용하여 탐색한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색의 과정이다.

간단하게 1~ 10까지 있는 배열로 예를 들자면

내가 찾고자하는 값이 7인경우

1~10중에 딱 절반을 자른다. mid 값과 내가 찾는값을 비교해서 내가 찾는값보다 mid가 작은경우

mid +1 값에서 다시 10에서 절반을 자른뒤

mid 값과 내가 찾는값을 비교하는 방식으로 진행된다.

내가 처음 작성했던 중첩 반복문으로 문제를 해결하게된다면

주어지는 값이 커질수록 최악의 경우 500,000 까지의 숫자를 하나씩 탐색해서 찾아야하는 경우가 발생하는데

이렇게 이분탐색을 활용하면 값이 증가한다고 검색을 하게되는 양이 똑같이 증가하는게 아니기 때문에

이분탐색이 엄청난 효율이라는걸 알 수 있다.

이를 코드로 구현하면 이렇게 된다.

이분탐색의 핵심은 반복 루프가 돌때마다 찾는 범위를 반씩 잘라내서 탐색하는것인데

시간복잡도를 보면 단순 중첩 반복문을 사용하는것과 비교하면 엄청난 효율을 자랑한다.

내가 위에서 작성했던 코드는 시간복잡도가 n^2 인 반면에 이분탐색의 시간복잡도는

단계마다 탐색 범위를 반으로(÷2) 나누는 것과 동일하므로 위 시간 복잡도를 가지게 된다.
예를 들어 처음 데이터의 개수가 32개라면, 이론적으로 1단계를 거치면 약 16개의 데이터가 남고, 2단계에서 약 8개, 3단계에서 약 4개의 데이터만 남게 된다. 즉, 이진 탐색(이분 탐색)은 탐색 범위를 절반씩 줄이고, O(logN)의 시간 복잡도를 보장한다.

다시 돌고 돌아서 원래의 문제로 돌아와보자

이분탐색을 하기위해서는 일단 정렬이 되어야한다.

지난 포스팅에서 정렬을 직접 구현해보았다.