이진탐색
-
부품 탐색 문제를 여러 알고리즘으로 풀어보기 with 시간 복잡도알고리즘/이론 2021. 3. 6. 21:42
문제 N개의 부품 배열에서 M개의 문의 부품이 있는지 확인하여 "yes", "no"를 출력한다. 1 ≤ N ≤ 1,000,000 (100만) 1≤ M ≤ 100,000 (10만) → 최댓값 100만 이진 탐색 이용 let n = Int(readLine()!)! var inputs = readLine()!.split(separator: " ").map { return Int($0)!} print(n) print(inputs) let m = Int(readLine()!)! let targets = readLine()!.split(separator: " ").map { return Int($0)! } inputs.sort() for t in targets { binarySearch(inputs, t) } fu..
-
이진 탐색알고리즘/이론 2021. 2. 24. 21:22
본 글은 '이것이 취업을 위한 코딩 테스트다 with 파이썬' 책을 공부하며 기록합니다. 단, iOS를 공부하고 있기 때문에 swift 언어로 코드를 바꿔보고 있습니다. 순차 탐색 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례로 확인하는 방법. 데이터의 정렬 여부와 상관없이 앞에 있는 원소부터 하나씩 확인한다. 시간복잡도는 O(N) func sequentialSearch(n: Int, target: String, array: [String]) -> Int { for i in 0.. Int? { if start > end { return nil } let mid = (start + end) / 2 if array[mid] == target { return mid } else ..