어떤 값을 찾을 때 정렬의 특징을 이용해 빨리 찾음
- 정렬이 되어있을 경우, 어떤 값을 찾을 때 ::: O(N) ->> O(lgN)
- 처음부터 생각하기 어려움..
- 시간 복잡도를 따져보고 시간이 초과하는 거라면 이진탐색을 떠올리도록 한다.
N개의 수 정렬 ::: O(NlgN)
M개의 수 이진 탐색::: O(M * lgN)
N개의 숫자가 있을 때,A라는 숫자를 찾으려면
만약 전체를 계산하는 거라면 for 0..<n 의 비교를 하게 되는 것이다.
- 전체의 배열을 정렬
- 전체를 반으로 분할하여 해당 위치의 숫자와 찾을 숫자 A와 비교한다.
- 만약 못찾으면 나머지 부분에서 또 절반을 나누어서 숫자 A와 비교한다.
1,2,3,4 라는 4개의 수가 있고 거기서 3을 찾으려고 한다.
가장 먼저 떠올릴 수 있는 for문으로 4개를 모두 탐색하면 O(N) = 4 먼저 절반을 나누어 작은 수가 2가 나오고, 2보다 3이 크기 때문에 다음 남은 우측을 또 반을 쪼개서 작은 수가 3인것을 찾음 O(lgN) = 2
두개의 입력을 받을 예정이다. 찾을 숫자는 4이고 1부터 6까지 총 6개의 숫자의 배열에서 4를 찾는 과정이다.
let input2 = """
4
1 2 3 4 5 6
"""
let input3 = input2.split(separator: "\n")
let target = Int(input3[0])!
let arr = input3[1].split(separator: " ").map{ Int(String($0))!}
let (st, en) = (arr.first!, arr.last!)
binarySearch(st, en, target)
func binarySearch(_ start: Int, _ end: Int, _ target: Int) {
if start == end {
print(start)
return
}
let mid = (start + end) / 2
if arr[mid] < target {
binarySearch(mid+1, end, target)
} else {
binarySearch(start, mid, target)
}
}이 부분에서 binarySearch의 기본 골조는 아래와 같다.
func binarySearch(_ start: Int, _ end: Int, _ target: Int) {
if start == end {
print(start)
return
}
let mid = (start + end) / 2
if arr[mid] < target {
binarySearch(mid+1, end, target)
} else {
binarySearch(start, mid, target)
}
}백준 1920
let input3 = """
10 4790
1
5
10
50
100
500
1000
5000
10000
50000
"""
let totalArr = input3.split(separator: "\n")
//let firstLine = totalArr[0].split(separator: " ").map{ Int($0)!}
let firstLine = readLine()!.split(separator: " ").map{ Int($0)!}
var (coinRow, target) = (firstLine[0], firstLine[1])
//var coins = totalArr[1...].map{Int($0)!}.sorted(by: >)
var coins = [Int]()
for _ in (0..<coinRow) {
let coin = Int(readLine()!)!
coins.append(coin)
}
coins.sort(by: >)
var count = 0
for coin in coins {
count += target / coin
target = target % coin
}
print(count)