[백준] 수 찾기, 이진 탐색(Binary Search) 알고리즘

이분 탐색(Binary Search)

  이진 탐색(Binary Search) 은 '정렬된 데이터'를 절반씩 나누어 탐색하는 방법입니다. 그래서 속도적인 측면에서 매우 빠른 시간내에 원하는 데이터를 찾을 수 있는 방법이죠. 기초가 되는 탐색 방법으로서 코딩 테스트에서도 제법 출제되는 유형입니다.

 

배열 A에서 데이터 5를 찾는다고 가정해봅시다.

이때 이진 탐색(Binary Search)으로 찾는다면, 단 2번의 순회로 배열 A 에 데이터 5가 있는지 없는지 확인할 수 있습니다.

 

핵심

  이진 탐색(Binary Search)은 반드시 정렬된 데이터일 때 사용할 수 있는 탐색법입니다. 따라서 배열 순회 전에 오름차순으로 데이터를 정렬해야 합니다. 물론 내림차순으로 해도 상관없지만 반대로 생각해야겠지요?

  두 번째로 이진 탐색(Binary Search)은 시작 인덱스 또는 끝 인덱스를 조절하여 탐색 범위를 절반씩 줄여나가는 탐색법입니다. 따라서 중간을 잡아주는 일이 중요한데, 이는 코를 보면 금방 이해할 수 있습니다.

 

 

기본 개념

  시작 인덱스(Start)와 끝 인덱스(End)의 중간 인덱스(Mid) 값을 기준으로 탐색합니다. 만약 찾는 값이 중간 값인 3보다 크다면 3 위에서만 찾으면 됩니다. 3보다 크다면 3보다 작은 숫자는 볼 필요가 없으니까요.

 

  1회 순회를 마친 뒤 보아하니, 찾고자 하는 데이터 5는 3보다 크군요. 따라서 시작 인덱스를(Start) 중간 인덱스(Mid)로 바꿔줍니다. 이때, 중간 인덱스(Mid)의 값이었던 3 은 이미 확인했기 때문에 Mid + 1 한 값을 시작 인덱스로 바꿉니다.

  이제 2회째 순회를 하게되면 중간 인덱스(Mid)의 값인 5와 찾고자 하는 값이 같습니다. 찾았습니다. 이제 순회를 마치고 결과를 출력하면 됩니다.

 

 

코드

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val num = readLine()!!.toInt()		//데이터 갯수
    var ns = StringTokenizer(readLine()!!)	//공백으로 나누어진 데이터들
    var nArr = arrayListOf<Int>()
    for (n in 0 until num) {
        nArr.add(ns.nextToken().toInt())	//배열에 담기
    }

    nArr.sort()

    val mum = readLine()!!.toInt()		//찾을 데이터 갯수
    var ms = StringTokenizer(readLine()!!)	//공백으로 나누어진 찾고자 하는 데이터들
    val str = BufferedWriter(OutputStreamWriter(System.out))

    for (i in 0 until mum) {
        var start = 0
        var mid = 0
        var end = nArr.size-1
        var m = ms.nextToken().toInt()		//찾고자 하는 데이터를 1개씩 뽑아 조회

        while(true) {
            mid = (start+end)/2			//매회 중간 인덱스를 재설정
            if (start > end) {
                str.append("0\n")
                break
            }
            if (m == nArr.get(mid)) {
                str.append("1\n")
                break
            }
            else if (m > nArr.get(mid)) {
                start = mid+1			//찾고자 하는 값이 기준 값보다 클때.
            }
            else if (m < nArr.get(mid)) {
                end = mid-1			//찾고자 하는 값이 기준 값보다 작을때.
            }
        }
    }

    str.flush()
    str.close()
    close()
}

 

  코드를 보면 알 수 있듯이 중간 인덱스(Mid)의 값과 비교 후 크면 시작 인덱스(Start) 에 중간 인덱스(Mid) +1 을, 작으면 끝 인덱스(End) 에 중간 인덱스(Mid) -1 을 합니다. 그리고 중간 인덱스(Mid) 는 Start + end / 2 가 되겠고요.

  이때 별별코딩에서는 while(true) 로 썼기에 빠져나오는 조건이 필요합니다. 하나는 값을 찾았을 때고, 다른 하나는 찾지 못했을 때인데 시작 인덱스(Start) 가 끝 인덱스(End) 를 넘었을 때입니다. Start 가 End 를 넘는다면 값이 없다는 뜻이 될테니까요.

 

  이 코드는 백준의 '수 찾기' 라는 문제의 풀이입니다. 이분 탐색(Binary Search)의 기본을 안다면 풀 수 있는 문제인데, 시간초과에 걸려서 조금 해멨는데요, 입력과 출력을 BufferedReader/Writer 로 쓰고 이분 탐색법(Binary Search) 를 사용해야지만 풀 수 있는 문제입니다.

www.acmicpc.net/problem/1920

1920번: 수 찾기

 

감사합니다.