이진 탐색

본 글은 '이것이 취업을 위한 코딩 테스트다 with 파이썬' 책을 공부하며 기록합니다.
단, iOS를 공부하고 있기 때문에 swift 언어로 코드를 바꿔보고 있습니다.

순차 탐색

리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례로 확인하는 방법.
데이터의 정렬 여부와 상관없이 앞에 있는 원소부터 하나씩 확인한다.
시간복잡도는 $O(N)$

func sequentialSearch(n: Int, target: String, array: [String]) -> Int {
    for i in 0..<n {
        if array[i] == target {
            return i + 1
        }
    }
    return -1
}

print("생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요.")
let inputs = readLine()!.split(separator: " ")
let n = Int(inputs[0])!
let target = String(inputs[1])

print("앞 서 적은 원소 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다.")
let array = readLine()!.split(separator: " ").map { return String($0) }

print(sequentialSearch(n: n, target: target, array: array))

이진탐색

배열 내부의 데이터가 정렬되어 있어야만 사용 가능한 알고리즘.
탐색 범위를 절반씩 좁혀가며 데이터를 탐색하여 빠르다.
시작점, 끝점, 중간점 3개의 변수를 이용한다.

찾으려는 데이터와 중간점 위치의 데이터를 반복적으로 비교하여 찾는다.
한 번 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어들기 때문에 시간복잡도는 $O(logN)$

따라서 데이터의 개수가 1000만개 이상이면 한 번 고려해보자.

• 재귀함수 이용

func binarySearch(array: [Int], target: Int, start: Int, end: Int) -> Int? {
    if start > end {
        return nil
    }
    let mid = (start + end) / 2
    if array[mid] == target {
        return mid
    } else if array[mid] > target {
        return binarySearch(array: array, target: target, start: start, end: mid - 1)
    } else {
        return binarySearch(array: array, target: target, start: mid + 1, end: end)
    }
}

let inputs = readLine()!.split(separator: " ").map { return Int($0)! }
let n = inputs[0], target = inputs[1]
let array = readLine()!.split(separator: " ").map { return Int($0)! }

if let result = binarySearch(array: array, target: target, start: 0, end: n - 1) {
    print(result + 1)
} else {
    print("원소가 존재하지 않습니다")
}

• 반복문 이용

func binarySearch(array: [Int], target: Int, start: Int, end: Int) -> Int? {
    var start = start, end = end
    while start <= end {
        let mid = (start + end) / 2
        if array[mid] == target {
            return mid
        } else if array[mid] > target {
            end = mid - 1
        } else {
            start = mid + 1
        }
    }
    return nil
}

let inputs = readLine()!.split(separator: " ").map { return Int($0)! }
let n = inputs[0], target = inputs[1]
let array = readLine()!.split(separator: " ").map { return Int($0)! }

if let result = binarySearch(array: array, target: target, start: 0, end: n - 1) {
    print(result + 1)
} else {
    print("원소가 존재하지 않습니다")
}

이진 탐색 문제는 입력 데이터가 매우 많거나(1000만 개 이상) 탐색 범위의 크기가 1000억 이상인 경우가 많다.

→ swift로 입출력 받을 시에 시간 초과 가능성 있음 ㅠ

python일 경우 sys 라이브러리를 import하여 빠른 입력을 받을 수 있다.
input_data = sys.stdin.readline().rstrip()

트리 자료구조

트리 자료구조는 그래프 자료구조의 일종으로 데이터베이스 시스템이나 파일 시스템 등에서 사용, 많은 양의 데이터를 관리하기 위한 목적으로 사용된다.

트리는 노드와 노드의 연결로 표현하며, 노드는 정보의 단위로 어떠한 정보를 가지고 있는 개체이다.

• 특징
  • 부모와 자식 노드의 관계를 가진다
  • 최상단 노드를 루트 노드라고 한다
  • 최하단 노드를 리프 노드(단말 노드)라고 한다
  • 트리에서 일부를 떼어내도 트리 구조여야 하고, 이를 서브 트리 라고 한다
  • 파일 시스템과 같이 계층적이고 (부모-자식), 정렬된 데이터에 적합하다
  • 빠른 탐색이 가능

이진 탐색 트리(Binary Search Tree)

이진 탐색 트리는 가장 간단한 형태의 트리 구조로 이진 탐색이 용이하게 고안되었다.

• 특징

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

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

    즉, 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드

• 탐색 과정

  1. 루트 노드 부터 방문 하여 찾으려는 데이터와 비교한다.

     → 루트 노드보다 데이터가 작으면, 오른쪽 자식 노드는 무시하고 왼쪽 자식 노드로 간다.
     → 루트 노드보다 데이터가 크면, 왼쪽 자식 노트는 무시하고 오른쪽 자식 노드로 간다.

  2. 찾으려는 데이터와 동일한 원소 값이 나올 때까지 반복한다.

참고

https://book.naver.com/bookdb/book_detail.nhn?bid=16439154
https://m.blog.naver.com/PostView.nhn?blogId=cylife3556&logNo=221483971423&proxyReferer=https:%2F%2Fwww.google.co.kr%2F
https://ratsgo.github.io/data%20structure&algorithm/2017/10/22/bst