[알고리즘] 이진 탐색(Binary Search)

순차 탐색(Sequential Search)

• 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 하나씩 차례대로 확인하는 방법
• 정렬 여부와 상관없이 가장 앞에서부터 하나씩 확인
• 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용
• 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 데이터를 찾을 수 있음
• 시간 복잡도 → O(N)

이진 탐색(Binary Search)

• 탐색 범위를 절반씩 좁혀가며 데이터를 탐색
• 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교하여 원하는 데이터 탐색
• 위치를 나타내는 시작점, 끝점, 중간점 3개의 변수 사용
• 배열 내부의 데이터가 정렬되어 있어야만 사용 가능
• 시간 복잡도 → O(logN)

 

트리 자료구조

트리(Tree) 구조

• 노드와 노드의 연결로 표현 ( 노드: 정보의 단위, 어떠한 정보를 가지고 있는 개체)
• 그래프 자료구조의 일종으로 데이터 베이스 시스템이나 파일 시스템과 같은 곳에서 많은 양의 데이터를 관리하기 위한 목적으로 사용

트리 구조의 특징

• 트리는 부모 노드와 자식 노드의 관계로 표현
• 트리의 최상단 노드는 루트 노드
• 트리의 최하단 노드는 단말 노드
• 트리에서 일부를 떼어내도 트리 구조이며 이를 서브 트리라고 함
• 트리는 파일 시스템과 같이 계층적이고 정렬된 데이터를 다루기에 적합

☞ 큰 데이터를 처리하는 소프트웨어는 대부분 데이터를 트리 구조로 저장해 이진 탐색과 같은 탐색 기법을 이용해 빠르게 탐색 가능

 

이진 탐색 트리

• 트리 자료구조 중에서 가장 간단한 형태
• 이진 탐색이 동작할 수 있도록 고안된, 효율적이고 탐색이 가능한 자료구조
• 루트 노드부터 방문하여 찾는 데이터가 루트 노드 값 보다 크다면 오른쪽 자식 노드를 방문하고, 작다면 왼쪽 자식 노드를 방문
• 방문한 자식 노드가 부모 노드가 되어 크기를 비교하여 다음 방문할 노드 선택
• 찾으려는 데이터를 찾을 때까지 반복

이진 탐색 트리 특징

• 부모 노드보다 왼쪽 자식 노드가 작다
• 부모 노드보다 오른쪽 자식 노드가 크다

 

---

이진 탐색 문제

부품  찾기

동빈이네 전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다.
어느 날 손님이 M개 종류의 부품을 대량으로 구매하겠다며 당일날 견적서를 요청했다.
동빈이는 때를 놓치지 않고 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다.
이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자. 

이진 탐색 알고리즘을 사용한 소스 코드

// 이진 탐색
func binary_search(_ arr: [Int], _ target: Int, _ start: Int, _ end: Int) -> Bool{
    var s = start, e = end
    while s <= e{
        var mid = (s+e)/2
        
        if arr[mid] == target{ return true }
        else if arr[mid] > target{ e = mid-1 }
        else { s = mid + 1 }
    }
    return false
}

var n = Int(readLine()!)!
var n_arr = readLine()!.split(separator: " ").map{Int(String($0))!}
n_arr = n_arr.sorted()

var m = Int(readLine()!)!
var m_arr = readLine()!.split(separator: " ").map{Int(String($0))!}

for i in m_arr{
    binary_search(n_arr, i, 0, n-1) ? print("yse", terminator: " ") : print("no", terminator: " ")
}

계수 정렬 개념을 사용한 소스코드

• 모든 원소의 번호를 포함할 수 있는 크기의 배열을 만든 후, 배열 인덱스에 직접 접근하여 특정 번호의 부품이 존재하는지 확인

// 계수 정렬
var n = Int(readLine()!)!
var n_arr: [Int] = Array(repeating: 0, count: 1000001)

for i in readLine()!.split(separator: " ").map{Int(String($0))!}{
    n_arr[i] = 1
}

var m = Int(readLine()!)!
var m_arr = readLine()!.split(separator: " ").map{Int(String($0))!}

for i in m_arr{
    if n_arr[i] == 1 { print("yes", terminator: " ") }
    else { print("no", terminator: " ") }
}

집합 자료형을 이용한 소스 코드

// Set(집합)자료형 사용
var n = Int(readLine()!)!
var n_arr = Set(readLine()!.split(separator: " ").map{Int(String($0))!})

var m = Int(readLine()!)!
var m_arr = readLine()!.split(separator: " ").map{Int(String($0))!}

for i in m_arr{
    if n_arr.contains(i) { print("yes", terminator: " ") }
    else { print("no", terminator: " ") }
}

---

떡볶이 떡 만들기

오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했다. 오늘은 떡볶이 떡을 만드는 날이다.
동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않다. 대신 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춘다.
절단기 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡을 잘리지 않는다.
손님이 왔을 때 요청한 총 길이가 M 일 때, 적어도 M 만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 최대 높이를 구하는 프로그램을 작성하시오.

파라메트릭 서치(Parametric Search) 유형 문제

• 최적화 문제를 결정문제로 바꾸어 해결하는 기법
  • 결정 문제 - "예" 혹은 "아니오"로 답하는 문제
• 원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제에 주로 사용
• ex) 범위 내에서 조건을 만족하는 가장 큰 값을 찾는 문제

var input_data = readLine()!.split(separator: " ").map{Int(String($0))!}
var n = input_data[0], m = input_data[1]
var arr = readLine()!.split(separator: " ").map{Int(String($0))!}

var start = 0, end = arr.max()!

var re = 0
while start <= end{
    var total = 0
    var mid = (start+end)/2
    
    for x in arr{
        if x > mid { total += x - mid }
    }
    if total < m { end = mid - 1}
    else{
        re = mid
        start = mid + 1
    }
}
print(re)