문제 유형 중, Binary Search의 추천문제들을 풀어보려고 합니다.(Paremetric Search)
추천문제 번호 모음은 여기서 확인할 수 있습니다. 실버와 골드가 섞여있습니다.
https://github.com/tony9402/baekjoon/tree/main/binary_search
GitHub - tony9402/baekjoon: 코딩테스트 대비 문제집(Baekjoon Online Judge)
코딩테스트 대비 문제집(Baekjoon Online Judge). Contribute to tony9402/baekjoon development by creating an account on GitHub.
github.com
문제 풀이를 할 때 마다 계속 추가됩니다.
cmd + F 를 통해 문제번호 찾기를 추천드립니다.
22.04.05 업데이트
22.04.06업데이트
22.04.07 업데이트
22.04.08 업데이트
22.04.10 업데이트
22.04.11 업데이트
22.04.13업데이트
아래 깃허브 주소에서 모든 백준 문제풀이를 확인하실 수 있습니다.
https://github.com/SuminPark-developer/BaekJoonPS
GitHub - SuminPark-developer/BaekJoonPS: 백준 Swift PS
백준 Swift PS. Contribute to SuminPark-developer/BaekJoonPS development by creating an account on GitHub.
github.com
백준 Swift 1789번
문제 유형 : 이분탐색 기본
난이도 : 실버5
// MARK: - 1789번(이분탐색)
let S = Int(readLine()!)!
var low = 1
var high = S
var answer: Int = 0
while low <= high {
let middle = (low + high) / 2
let sum = (middle) * (middle + 1) / 2 // 합 공식: n*(n+1)/2
if sum <= S {
low = middle + 1
answer = middle
}
else {
high = middle - 1
}
}
print(answer)
백준 Swift 2417번
문제 유형 : 이분탐색 기본
- Int형의 범위를 초과하는 숫자여서 애를 먹었다. Double로 변경해서 풀어서 해결함.
난이도 : 실버4
// MARK: - 2417번(이분탐색)
let n = Double(readLine()!)! // Int로 하면 middle제곱부분에서 범위 초과.
//var low = 0
//var high = n
//var answer: Int = 0
//
//while low <= high {
// let middle = (low + high) / 2
//
// if middle * middle >= Int(n) {
// high = middle - 1
// answer = middle
// }
// else {
// low = middle + 1
// }
//}
var low = 0.0, high = n, answer = 0.0 // Double로 하면 이분탐색 가능.
while low <= high {
let middle = Double(Int((low + high) / 2)) // 중간에 Int로 바꾸는 이유는, /2를 했을 때 소수점을 없애기 위해서.
if middle * middle >= n {
high = middle - 1
answer = middle
}
else {
low = middle + 1
}
}
print(Int(answer))
백준 Swift 10815번
문제 유형 : 이분탐색 기본
난이도 : 실버4
// MARK: - 10815번(이분탐색)
let N = Int(readLine()!)!
let sanggeunCards = readLine()!.split(separator: " ").map{Int(String($0))!}.sorted(by: <)
let M = Int(readLine()!)!
let checkCards = readLine()!.split(separator: " ").map{Int(String($0))!}
var answerArray: [String] = Array(repeating: "0", count: M)
for (index, card) in checkCards.enumerated() {
var lowIndex: Int = 0
var highIndex: Int = N - 1
while lowIndex <= highIndex {
let middleIndex = (lowIndex + highIndex) / 2
if sanggeunCards[middleIndex] == card {
answerArray[index] = "1"
}
if sanggeunCards[middleIndex] < card {
lowIndex = middleIndex + 1
}
else {
highIndex = middleIndex - 1
}
}
}
print(answerArray.joined(separator: " "))
백준 Swift 2805번
문제 유형 : 이분탐색 기본 - 단순 합이 아니라, 한번 더 조건을 생각해야 하는 문제였다.
난이도 : 실버3
// MARK: - 2805번(이분탐색)
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, M) = (input[0], input[1])
let trees = readLine()!.split(separator: " ").map{Int(String($0))!}
var lowHeight: Int = 0
var highHeight: Int = trees.max()!
var answer: Int = 0 // 절단기 높이
while lowHeight <= highHeight {
let middleHeight = (lowHeight + highHeight) / 2
// let sum = trees.map{$0 - middleHeight}.reduce(0, +) // 이렇게 하면, 절단기 높이(middleHeight)가 더 높을 때 음수가 같이 더해짐.
var sum: Int = 0
for tree in trees {
sum += tree - middleHeight > 0 ? tree - middleHeight : 0 // (나무 - 중간값) 들의 합 : 만약 음수면 안더함.
}
if sum >= M {
lowHeight = middleHeight + 1
answer = middleHeight
}
else {
highHeight = middleHeight - 1
}
}
print(answer)
백준 Swift 1654번
문제 유형 : 이분탐색 기본
난이도 : 실버3
// MARK: - 1654번(이분탐색)
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (K, N) = (input[0], input[1])
var lan: [Int] = [] // 랜선들 모음.
for _ in 0..<K {
lan.append(Int(readLine()!)!)
}
var low = 1 // 0으로 하면 런타임 에러(자연수라고 했기 때문에)
var high = lan.max()!
var answer: Int = 0
while low <= high {
let middle = (low + high) / 2
var countSum: Int = 0 // 생성되는 랜선개수 합
// for l in lan {
// countSum += (l / middle)
// }
countSum = lan.map{$0 / middle}.reduce(0, +) // for문 축약.
if countSum >= N { // 필요한 랜선이 충분하면, 랜선 길이를 더 늘려본다.(최대 길이를 구해야 하기 때문에)
low = middle + 1
answer = middle
}
else { // 필요한 랜선이 안나오면, 랜선 길이를 줄여본다.
high = middle - 1
}
}
print(answer)
백준 Swift 2512번
문제 유형 : 이분탐색 기본
난이도 : 실버3
// MARK: - 2512번(이분탐색)
let N = Int(readLine()!)!
let moneys = readLine()!.split(separator: " ").map{Int(String($0))!}
let M = Int(readLine()!)!
var low = 1
var high = moneys.max()!
var answer: Int = 0
while low <= high {
let middle = (low + high) / 2
var sum: Int = 0
for money in moneys {
sum += money > middle ? middle : money
}
if sum <= M {
low = middle + 1
answer = middle
}
else {
high = middle - 1
}
}
print(answer)
백준 Swift 19637번
문제 유형 : 이분 탐색 기본 활용 - 처음에 약간 고민을 했다. power가 기준값(values[middleIndex])보다 낮을 때 highIndex를 -1해주는게 중요했다. (lowIndex를 +1해주면 안된다. 더 높은 기준에서 되는지 체크할 게 아니라, 더 낮은 기준에서 되는지 체크해야 되기 때문이다.)
그리고 입력받을 때, 중복되는 값을 제외하려고 하지 않아도 됐다. 처음엔 해야만 문제가 안생긴다고 생각했는데,
시간초과가 나서 다시 고민해보니 어차피 입력이 오름차순으로 들어오고,
예시2처럼 만약 입력이 같더라도 highIndex가 -1이 되면서, 더 최근꺼로 넘어가게 되기 때문에 할 필요가 없었다.
난이도 : 실버3
// MARK: - 19637번(이분탐색)
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, M) = (input[0], input[1])
var titles: [String] = []
var values: [Int] = []
for _ in 0..<N {
let input = readLine()!.split(separator: " ").map{String($0)}
// if !values.contains(Int(input[1])!) { // (예제2처럼) 중복되는 값은 제외. - 이 부분 필요 없었음. 이유 : 어차피 오름차순으로 들어오고, 같더라도 highIndex가 -1이 되면서 더 최근꺼로 출력하게 되기 때문.
titles.append(input[0])
values.append(Int(input[1])!)
// }
}
for _ in 0..<M {
let power = Int(readLine()!)!
var lowIndex: Int = 0
var highIndex: Int = values.count - 1
var answerIndex: Int = 0
while lowIndex <= highIndex {
let middleIndex = (lowIndex + highIndex) / 2
// print(lowIndex, highIndex, middleIndex)
if power <= values[middleIndex] { // 기준이 더 낮을 때도 포함되는지 확인하기 위해,
highIndex = middleIndex - 1 // 높은 인덱스를 -1.
answerIndex = middleIndex
}
else { // 기준이 더 높을 때는 포함되는지 확인하기 위해,
lowIndex = middleIndex + 1 // 낮은 인덱스를 +1.
}
}
print(titles[answerIndex])
}
백준 Swift 11663번
문제 유형 : 이분탐색 활용 - 어려웠다. 하루동안 고민한 거 같다. 뭔가 값은 비슷하게 나오는데, 모든 case에 맞는 답이 계속 안나오더라.
다시 종이에 풀면서 고민을 했다.
계속 고민 하다보니, 한번에 모든 case에 맞는 답이 나오는 게 아니라, case를 나눠서 답을 출력해주면 되겠다 싶었다.
풀이종이를 함께 보면,
case 1 : 인덱스 값끼리 빼준다. ( highIndex - lowIndex)
case 2 : 인덱스 값끼리 빼주고, 1을 더한다. (highIndex - lowIndex + 1)
케이스가 이렇게 두가지로 나뉜다는 걸 알았다.
그 다음,
선분의 작은 값(lowCoord)보다 coords[lowIndexAnswer]가 더 작을 때, 혹은 선분의 큰 값(highCoord)보다 coords[highIndexAnswer]가 더 클 때, 가 case1에 해당하는걸 찾아냈다.
coords가 [4, 7, 11, 19]일 때,
case1의 예시는 선분이 (5~12), (20~30) 등은 왼쪽조건에 해당하고, 선분이 (1~3)은 오른쪽조건에 해당한다. - 하단 코드 참고
규칙성을 찾았으니, 케이스가 나뉘는 부분을 코드로 구현해서 해결했다!
아 그리고 케이스 나눠줬으니까 맞게 푼 거 같았는데 또 틀리더라. 절망했지만... 다시 처음부터 확인하면서 고민해보니, coords의 오름차순정렬을 빠트렸었다. (이런 -_-)
이분정렬을 할 때는 정렬을 절대 빠트리지 말자!
뭔가 힘들었다... 그래도 해결해서 기분은 좋다. 나중에 시간이 지나 잊었을 때 다시 풀어봐야겠다.
난이도 : 실버3
// MARK: - 11663번(이분탐색)
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, M) = (input[0], input[1])
let coords = readLine()!.split(separator: " ").map{Int(String($0))!}.sorted(by: <)
func findHigh(_ coord: Int) -> Int {
var lowIndex: Int = 0
var highIndex: Int = N - 1
var answerIndex: Int = 0
while lowIndex <= highIndex {
let middleIndex = (lowIndex + highIndex) / 2
if coords[middleIndex] <= coord {
lowIndex = middleIndex + 1
answerIndex = middleIndex
}
else {
highIndex = middleIndex - 1
}
}
return answerIndex
}
func findLow(_ coord: Int) -> Int {
var lowIndex: Int = 0
var highIndex: Int = N - 1
var answerIndex: Int = 0
while lowIndex <= highIndex {
let middleIndex = (lowIndex + highIndex) / 2
if coords[middleIndex] <= coord {
lowIndex = middleIndex + 1
answerIndex = middleIndex
}
else {
highIndex = middleIndex - 1
}
}
return answerIndex
}
for _ in 0..<M {
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (lowCoord, highCoord) = (input[0], input[1])
let highIndexAnswer = findHigh(highCoord)
let lowIndexAnswer = findLow(lowCoord)
// print(lowIndexAnswer, highIndexAnswer)
var count: Int = 0
if coords[lowIndexAnswer] < lowCoord || coords[highIndexAnswer] > highCoord { // ex) coords가 [4, 7, 11, 19]일 때, 선분이 (5~12), (20~30) 등은 왼쪽조건에 해당. 선분이 (1~3)은 오른쪽조건에 해당.
count = highIndexAnswer - lowIndexAnswer
}
else {
count = highIndexAnswer - lowIndexAnswer + 1
}
print(count)
}
백준 Swift 2110번
문제 유형 : Parametric Search, 이분탐색 활용 - 이 문제를 보고 이분탐색인지 알아내는게 어려웠다.
다른 풀이들을 보고,
가능한 거리들을 1부터 최대로 둔 다음, 각각의 거리일 때 공유기의 개수를 확인하는 식으로 코드를 짜면 된다는 걸 알게 됐다.
많이 풀다 보면 이 문제가 어떤 유형인지 알 수 있는 날이 오겠...지... ㅠㅠ
난이도 : 골드5
참고 링크 : https://assaeunji.github.io/python/2020-05-07-bj2110/
// MARK: - 2110번(이분탐색)
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, C) = (input[0], input[1])
var houses: [Int] = []
for _ in 0..<N {
houses.append(Int(readLine()!)!)
}
houses.sort(by: <)
var lowDistance = 1 // 가능한 거리 중, 최소 거리
var highDistance = houses[N - 1] - houses[0] // 가능한 거리 중, 최대 거리
var answer = 0
while lowDistance <= highDistance {
let middleDstance = (lowDistance + highDistance) / 2 // gap
var count: Int = 1 // 맨 처음에 공유기 설치.
var base = houses[0]
for i in 1..<N { // 둘째집부터 돌면서 체크.
if (base + middleDstance) <= houses[i] { // 다음 집이 (base+설정한gap)에 포함될 때, 공유기 설치.
count += 1
base = houses[i]
}
}
if count >= C { // 설치된 공유기가 C개 이상이면, gap을 늘려서 더 큰 거리일 때 되는지 체크가 필요. -> gap 늘림.
lowDistance = middleDstance + 1
answer = middleDstance
}
else { // 설치된 공유기가 C개보다 적다는 건, 더 설치 필요. -> gap 축소.
highDistance = middleDstance - 1
}
}
print(answer)
백준 Swift 3079번
문제 유형 : 이분탐색 활용 - 계속 내 힘으로 푸는 게 아니라 참고해서 푼다...
풀다 보니 느낀건 어떤걸 탐색돌려야 하는지와, 탐색의 첫 low와 high를 생각 못해서 못 푸는 것 같다.
문제를 마주했을 때 생각흐름도를 정형화해야겠다.
순서 1. 이분탐색 문제인지 확인한다.
순서 2. 이분탐색 문제라면, 어떤걸 탐색돌려야 하는지 고민한다. (중요!)
순서 3. 어떤걸 탐색돌려야 하는지 찾았다면, 탐색의 범위(low, high)를 찾는다.
이 문제에선 (정답이 되는) 결과 시간을 탐색돌려야 했다.
결과 시간이 x초(middle)일때, 몇 명이 pass했는지 체크하면 되는 문제였다.
각 심사대에서 몇 명이 패스했는지 아는 방법은 (x초 / 심사하는데 걸리는 시간)을 하면 몇 명인지 구할 수 있다.
난이도 : 골드5
// MARK: - 3079번(이분탐색)
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, M) = (input[0], input[1])
var times: [Int] = []
for _ in 0..<N {
times.append(Int(readLine()!)!)
}
times.sort(by: <)
var lowTime = 1 // 최소 결과 시간
var highTime = times[N - 1] * M // 최대 결과 시간
var answerTime: Int = 0
while lowTime <= highTime {
let middleTime = (lowTime + highTime) / 2
var sum: Int = 0
for time in times {
sum += middleTime / time // x초(middleTime)까지의 시간이 지났을 때, 각 심사대에서 pass한 인원의 합.
}
if sum >= M { // M명이상이 이미 통과했으면, 더 적은 시간일 때 어떨지 체크를 위해 high를 감소.
highTime = middleTime - 1
answerTime = middleTime
}
else { // M명이 아직 통과도 못했으면, 더 긴 시간일 때 어떨지 체크를 위해 low를 증가.
lowTime = middleTime + 1
}
}
print(answerTime)
백준 Swift 2470번
문제 유형 : 이분탐색 활용 - 어떤걸 탐색돌려야 하는지 고민했을 때 조합을 쓰고, 그 조합결과에서 나온 값들을 탐색돌려야 한다고 생각해서 틀렸었다.
조합을 쓰면 한단계를 더 거쳐가는 것이기 때문에 불필요하다.
이 문제엔 두가지 핵심이 있었다.
첫번째, 용액 자체들을 바로 탐색을 돌리면 되고, middleIndex가 필요 없다.
두번째, 두 용액이 같을 수는 없기 때문에, while문에서 < 로 해야 하는걸 생각해야 했다.
while (lowIndex <= highIndex) 로 하면 안되는 반례
6
-4 -3 -1 0 2 5 => (0 0)이 나온다. (틀림)
위 반례에서 if문 abs의 < 나 <= 에 따라서, (-4 5) 혹은 (-1 0)이 나와야 한다.
난이도 : 골드5
참고 링크 : https://data-bank.tistory.com/29
// MARK: - 2470번(이분탐색)
let N = Int(readLine()!)!
let liquids = readLine()!.split(separator: " ").map{Int(String($0))!}.sorted(by: <)
var lowIndex: Int = 0
var highIndex: Int = N - 1
var distance: Int = 2000000000 // 0과의 거리. - 최대 1000000000라서 2배.
var answerLowIndex: Int = 0
var answerHighIndex: Int = N - 1
while lowIndex < highIndex {
let temp = liquids[lowIndex] + liquids[highIndex]
if abs(temp) < distance { // 새로운조합이 기존보다 0과의 거리가 더 작으면, (등호가 들어가도 되고 안 들어가도 됨. 등호가 들어가게 되면, 거리가 같은게 있을 때 점점 가운데쪽 인덱스로 가까워짐. 등호가 없으면, 거리가 같은게 있어도 바깥쪽 인덱스에서 가운데쪽으로 가까워지지 않음.)
distance = abs(temp)
answerLowIndex = lowIndex
answerHighIndex = highIndex
if temp == 0 { // 만약 0이면, 더 이상 확인할 필요 없이 바로 stop.
break
}
}
if temp < 0 { // 음(-)이 더 강하면, 양(+)쪽으로.
lowIndex += 1
}
else { // 양(+)이 더 강하면, 음(-)쪽으로.
highIndex -= 1
}
}
print(liquids[answerLowIndex], liquids[answerHighIndex])처음 짠 코드 - 메모리 초과
// MARK: - 2470번(조합, 이분탐색) - 메모리초과
func combi(_ nums: [Int], _ targetNum: Int) -> [[Int]] {
var results: [[Int]] = []
func combination(_ index: Int, _ nowCombi: [Int]) {
if nowCombi.count == targetNum {
results.append(nowCombi)
return
}
for i in index..<nums.count {
combination(i + 1, nowCombi + [nums[i]])
}
}
combination(0, [])
return results
}
let N = Int(readLine()!)!
let liquids = readLine()!.split(separator: " ").map{Int(String($0))!}.sorted(by: <)
let liquidsTwo = combi(liquids, 2)
//print(liquidsTwo)
var sumDict: [Int : Int] = [:]
for (index, nums) in liquidsTwo.enumerated() {
sumDict[index] = nums.reduce(0, +)
// sumArray.append(nums.reduce(0, +))
}
//print(sumDict)
let sumArray: [Int] = sumDict.values.sorted(by: <)
//print(sumArray)
var lowIndex: Int = 0
var highIndex: Int = sumArray.count - 1
var minD = 2000000000 // 0과의 거리
var answerIndex: Int = 0
while lowIndex <= highIndex {
let middleIndex = (lowIndex + highIndex) / 2
if abs(sumArray[middleIndex]) <= minD { // minD보다 더 작은 거리가 있는지 체크하기 위해, highIndex를 줄임.
minD = abs(sumArray[middleIndex])
highIndex = middleIndex - 1
answerIndex = middleIndex
}
else { // minD보다 크면, low를 높여야함.(low보다 index가 더 작은 곳엔, 거리(값)가 더 큰 애들밖에 없음.)
lowIndex = middleIndex + 1
}
}
for data in sumDict {
if data.value == sumArray[answerIndex] {
print(liquidsTwo[data.key][0], liquidsTwo[data.key][1])
break
}
}백준 Swift 20444번
문제 유형 : 이분탐색 활용 - 처음의 생각대로 풀었을 땐, 메모리초과가 났다. 배열에 담았다가 값들을 다시 꺼내오는 식으로 구조를 짜서 문제가 됐다.
값들을 바로 탐색 돌리는 식으로 코드를 수정하니 해결 성공!
(가로방향 + 1) * (세로방향 + 1)이 색종이의 총 개수다.
세로방향은 (n - 가로방향)이므로, let count = (middle + 1) * ((n - middle) + 1) 가 된다. 위 사진 참고!
난이도 : 골드5
// MARK: - 20444번(이분탐색)
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (n, k) = (input[0], input[1])
var low: Int = 0
var high: Int = n/2 // 전체 n번 중, n/2까지만 확인하면 됨.
var answer: String = "NO"
while low <= high {
let middle = (low + high) / 2
let count = (middle + 1) * ((n - middle) + 1) // 종이의 개수 = (가로방향 + 1) * (세로방향 + 1)
if count == k { // 정답일 땐 더 이상 돌아볼 필요 X.
answer = "YES"
break
}
if count > k {
high = middle - 1
}
else {
low = middle + 1
}
}
print(answer)처음 짠 코드 - 메모리 초과 코드
// MARK: - 20444번(이분탐색)
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (n, k) = (input[0], input[1])
//var numArray: [(horizontal: Int, vertical: Int)] = [] // (가로방향으로 자르는 횟수, 세로방향으로 자르는 횟수)
//for i in 0...n/2 {
// numArray.append((i, n - i))
//}
var countArray: [Int] = []
//for nums in numArray {
// countArray.append((nums.horizontal + 1) * (nums.vertical + 1))
//}
for i in 0...n/2 {
countArray.append((i + 1) * ((n - i) + 1))
}
//countArray.sort(by: <)
var lowIndex: Int = 0
var highIndex: Int = countArray.count - 1
var answer: String = "NO"
while lowIndex <= highIndex {
let middleIndex = (lowIndex + highIndex) / 2
if countArray[middleIndex] == k {
answer = "YES"
break
}
if countArray[middleIndex] > k {
highIndex = middleIndex - 1
}
else {
lowIndex = middleIndex + 1
}
}
print(answer)백준 Swift 1477번
문제 유형 : Parametric Search, 이분탐색 활용
처음 문제를 봤을 때 이분탐색일 거라고 생각이 안 들었다.
첫 풀이는 각각의 거리들을 구해 distance배열에 넣고, M번까지 for문을 돌리면서 distance.max() 값의 /2 를 다시 넣어주고, 그 distance배열의 max값을 출력해주면 된다고 생각했다.
하지만 이 풀이방법은 각각의 거리에, 1개씩만 휴게소가 들어간다는 조건일 때에만 가능한 것인거다. 잘못 됐다.
고민 끝에 다른 게시물을 참고해서 풀었다.
주의사항 1. low를 0으로 해서 런타임 에러가 계속 났었다. low와 high값을 잘 확인하자.
주의사항 2. distance가 기준값(middle)에 정확히 나눠떨어질 때 마지막 설치에서 겹치기 때문에, count에 -1을 해줘야 한다.
주의사항 3. 설치 개수가 M보다 적으면, 간격을 더 줄일 때 - M개를 설치했을 때 구간들의 최댓값을 최소로 하려는 거기 때문에, 여기에 등호가 들어간다.
난이도 : 골드4
참고 링크 : https://paris-in-the-rain.tistory.com/44
// MARK: - 1477번(이분탐색)
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, M, L) = (input[0], input[1], input[2])
let storeCoord: [Int] = [0] + readLine()!.split(separator: " ").map{Int(String($0))!}.sorted(by: <) + [L] // 휴게소들 좌표 저장. (시작 0, 끝 L)
var low: Int = 1 // 설치 가능한 최저
var high: Int = L - 1 // 설치 가능한 최대
var answerDistance: Int = 0 // 정답
while low <= high {
let middle = (low + high) / 2 // 기준 거리
var newStoreCount: Int = 0
for i in 1..<storeCoord.count {
let distance = storeCoord[i] - storeCoord[i - 1] // 각각의 거리.
newStoreCount += distance / middle // 각각의 거리에서 나올 수 있는 휴게소의 개수.
if distance % middle == 0 { // 만약 나눠떨어지면, 끝부분에 중복설치가 됨.
newStoreCount -= 1 // 그래서 count값에 -1해줌.
}
}
if newStoreCount <= M { // 개수가 M보다 적으면, 간격을 더 줄여야 함. - M개를 설치했을 때 구간들의 최댓값을 최소로 하려는 거기 때문에, 여기에 등호가 들어감.
high = middle - 1 // (그래야 개수가 늘어나니깐)
answerDistance = middle
}
else { // 개수가 M보다 많으면, 간격을 더 늘려야 함.
low = middle + 1 // (그래야 개수가 줄어드니깐)
}
}
print(answerDistance)
백준 Swift 1939번
문제 유형 : 이분탐색 + DFS/BFS
- 문제를 처음 봤을 때, 어디에서 이분탐색을 돌려야 하는지 알지 못했다. 인접행렬을 만든 뒤, 목표지점까지 도달할 수 있는 여러 길들 중, 각각의 길의 결과weight(최소)를 배열에 넣고, 배열에서 최댓값을 출력하면 된다고 생각했다.
우선 기본 인접행렬을 하면 두 섬 사이에 다리가 여러 개일 때 문제가 생겼다. 또한, 인접행렬을 해결했다고 하더라도, 방문처리를 하는 과정에서 지나간 길은 다시 못지나가는 문제가 생겼다.
결국 초기의 풀이는 틀린 것으로 판단하고, 다른 블로그들에서 풀이를 보고 해결했다.
low와 high를 통해 정해진 mid(기준)중량이 목표지점까지 갈 수 있는지 없는지 체크하는 식으로 해결하면 되는 거였다.
실제 코테에서 이분탐색만 있는 문제는 거의 안 나오고, 이분탐색과 다른 유형이 합쳐진 문제가 주로 출제된다고 하니깐... 더 열심히 해야겠다.
난이도 : 골드4
예시
5 6
1 2 5
5 4 1
4 1 6
5 1 3
4 3 4
3 4 2
2 3
=> 나올 답은 4
참고 링크 : https://woongsios.tistory.com/234 | https://velog.io/@ckstn0778/%EB%B0%B1%EC%A4%80-1939%EB%B2%88-%EC%A4%91%EB%9F%89%EC%A0%9C%ED%95%9C-1-Python
이분탐색 + BFS
// MARK: - 1939번(BFS + 이분체크)
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, M) = (input[0], input[1])
var graph: [[(Int, Int)]] = Array(repeating: [], count: N + 1)
var visited = Array(repeating: false, count: N + 1)
for _ in 0..<M {
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (A, B, C) = (input[0], input[1], input[2])
graph[A].append((B, C))
graph[B].append((A, C))
}
let fromTo = readLine()!.split(separator: " ").map{Int(String($0))!}
let (startX, endX) = (fromTo[0], fromTo[1])
func isEscape(_ island: Int) -> Bool { // 섬번호가 목표지점에 도달하면 탈출.
return island == endX
}
func bfs(_ startIsland: Int, _ standardWeight: Int) -> Bool {
var q: [Int] = [startIsland]
visited[startIsland] = true
while !q.isEmpty {
let islandNumber = q.removeFirst()
if isEscape(islandNumber) { // 탈출 성공 시,
return true // middle(기준)중량으로 운송 가능.
}
for (nextIsland, limitWeight) in graph[islandNumber] {
if limitWeight >= standardWeight && !visited[nextIsland] { // 다음섬과 연결된 다리의 중량제한이 middle(기준)중량 이상일 때에만 다음 섬으로 이동 가능. + 미방문시,
visited[nextIsland] = true
q.append(nextIsland)
}
}
}
return false
}
var low: Int = 1
var high: Int = 1000000001
var answer: Int = 0
while low <= high {
visited = Array(repeating: false, count: N + 1) // 매 middle(기준)중량일 때, 방문배열 초기화해줘야 함.
let middle = (low + high) / 2
if bfs(startX, middle) { // 지금 middle(기준) 중량이 운송 가능하다면, 더 높은 중량에서 가능한지 체크하기 위해 low를 높여본다.
low = middle + 1
answer = middle
}
else { // middle(기준) 중량으로 운송 불가능하다면, 낮춰야 함.
high = middle - 1
}
}
print(answer)이분탐색 + DFS
참고 링크 : https://loosie.tistory.com/313
// MARK: - 1939번(DFS + 이분체크)
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, M) = (input[0], input[1])
var graph: [[(Int, Int)]] = Array(repeating: [], count: N + 1)
var visited = Array(repeating: false, count: N + 1)
for _ in 0..<M {
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (A, B, C) = (input[0], input[1], input[2])
graph[A].append((B, C))
graph[B].append((A, C))
}
let fromTo = readLine()!.split(separator: " ").map{Int(String($0))!}
let (startX, endX) = (fromTo[0], fromTo[1])
func isEscape(_ island: Int) -> Bool { // 섬번호가 목표지점에 도달하면 탈출.
return island == endX
}
//func bfs(_ startIsland: Int, _ standardWeight: Int) -> Bool {
// var q: [Int] = [startIsland]
// visited[startIsland] = true
//
// while !q.isEmpty {
// let islandNumber = q.removeFirst()
//
// if isEscape(islandNumber) { // 탈출 성공 시,
// return true // middle(기준)중량으로 운송 가능.
// }
//
// for (nextIsland, limitWeight) in graph[islandNumber] {
// if limitWeight >= standardWeight && !visited[nextIsland] { // 다음섬과 연결된 다리의 중량제한이 middle(기준)중량 이상일 때에만 다음 섬으로 이동 가능. + 미방문시,
// visited[nextIsland] = true
// q.append(nextIsland)
// }
// }
// }
// return false
//}
func dfs(_ island: Int, _ standardWeight: Int) {
if isEscape(island) {
canTransit = standardWeight // standardWeight = middle 같음.
return
}
for (nextIsland, limitWeight) in graph[island] {
if limitWeight >= standardWeight && !visited[nextIsland] { // 다음섬과 연결된 다리의 중량제한이 middle(기준)중량 이상일 때에만 다음 섬으로 이동 가능. + 미방문시,
visited[nextIsland] = true
dfs(nextIsland, standardWeight)
}
}
}
var low: Int = 1
var high: Int = 1000000001
var canTransit: Int = -1 // // middle(기준)중량으로 운송 가능한지 체크를 위한 변수.
var answer: Int = 0
while low <= high {
visited = Array(repeating: false, count: N + 1) // 매 middle(기준)중량일 때, 방문배열 초기화해줘야 함.
let middle = (low + high) / 2
canTransit = -1 // middle(기준)중량으로 운송 가능한지 여부.
visited[startX] = true
dfs(startX, middle) // canTransit값이 바뀌어 있다면, middle(기준)중량으로 운송 가능.
if canTransit != -1 { // 지금 middle(기준) 중량이 운송 가능하다면, 더 높은 중량에서 가능한지 체크하기 위해 low를 높여본다.
low = middle + 1
answer = middle
}
else { // middle(기준) 중량으로 운송 불가능하다면, 낮춰야 함.
high = middle - 1
}
}
print(answer)백준 Swift 2473번
문제 유형 : 이분탐색 활용 - 2470번 문제를 풀고, 조금만 더 생각해보면 쉽게 풀 수 있는 문제였다. 2개의 용액이 아닌, 3개의 용액을 선택해야 하기 때문에,
index 0..<N-2까지 돌면서 첫번째 용액을 선택 시, 나머지 2개의 용액 선택범위를 low와 high로 선정 후 이분탐색을 돌리면 해결 된다.
난이도 : 골드4
// MARK: - 2473번(이분탐색)
let N = Int(readLine()!)!
let liquids = readLine()!.split(separator: " ").map{Int(String($0))!}.sorted(by: <)
var liquidSumDistance: Int = 3000000001 // 세 용액의 합.
var answerIndex1: Int = 0
var answerIndex2: Int = 0
var answerIndex3: Int = 0
outLoop: for i in 0..<N-2 {
let liq1 = liquids[i] // 첫번째 용액 선택.
var lowIndex: Int = i + 1
var highIndex: Int = N - 1
while lowIndex < highIndex {
let liq2 = liquids[lowIndex]
let liq3 = liquids[highIndex]
let sum = liq1 + liq2 + liq3
if abs(sum) < liquidSumDistance { // 용액의 합(sum)이 0과 더 가깝다면,
liquidSumDistance = abs(sum) // 더 가까운 합으로 0과의 거리 업데이트.
(answerIndex1, answerIndex2, answerIndex3) = (i, lowIndex, highIndex)
}
if sum == 0 { // 더 이상 돌 필요 없이 끝.
break outLoop
}
else if sum > 0 { // 양의 기운이 강한 상태라면, 음쪽으로 가야 함.
highIndex -= 1
}
else { // 음의 기운이 강한 상태라면, 양쪽으로 가야 함.
lowIndex += 1
}
}
}
print(liquids[answerIndex1], liquids[answerIndex2], liquids[answerIndex3])
백준 Swift 13397번
문제 유형 : Parametric Search, 이분탐색
- 어려웠다. 솔직히 감을 못잡았다. 풀이 안 봤으면 계속 못 풀었을 것 같다... 언제쯤 이런 문제도 쉽게 풀 수 있을까..
핵심 1
구간점수들 중 기준이 될 최댓값(middle)을 잡고, numsArray배열을 돌면서 구간점수(max-min)가 middle보다 클 시, 구간이 바뀌는 곳이다.
-> (이해가 처음에 안됐는데, 계속 생각하다 보니 알겠더라.) 기준이 되는 middle보다 구간점수가 커진다는 건, 이미 middle이 나올 수 있는 최댓값이라는 걸 isAble에 들어갈 때부터 정하고 while문을 도는 것이기 때문에 사실 불가능한 상황인 거다. => 그 뜻은, middle보다 구간점수가 커지는 index가 새로운 구간의 시작점이 되는 것이다.
핵심 2
구간이 바뀌는 상황일 때 index를 -1 해줘야 한다.
-> 그렇지 않으면, 구간에 하나의 숫자만 있는 상황이 고려 되지 않는다.
이 테스트케이스들에선 문제되는 케이스가 없어서 다른 글에 있는 코드들이 pass가 된건지 or 논리적으로 고려하지 않아도 돼서 안한건지는 모르겠다.
그래도 나는 위 케이스를 판단해주는 게 맞다고 생각해서 while문으로 작성후 index를 빼줬다. (for문으로 하고 싶었지만, swift에서는 for문 다시 index 되돌아가는 게 없어서...)
참고한 대부분의 블로그에선 하나의 숫자만 있는 상황이 고려되진 않은 것 같다. 참고한 글들 중 유일하게 위 케이스가 고려된 글 - https://loosie.tistory.com/638
핵심 3
count가 0이 아니라 1로 시작해야 한다.
-> 가장 마지막 구간은 카운팅이 안되기 때문이다.
=> count가 만약 0으로 시작.
(쉽게 생각하기 위해) 만약 if문에 해당되는 게 없다면(= 구간이 바뀌는 곳이 없다면) count가 0이 나온다.
배열의 모든 숫자가 하나의 구간인 상황이니까 1이 답인데 말이다!
난이도 : 골드4
참고한 글 : https://loosie.tistory.com/638 | https://kyu9341.github.io/algorithm/2020/03/10/algorithm13397/
// MARK: - 13397번(Parametric Search, 이분탐색)
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, M) = (input[0], input[1])
let numsArray = readLine()!.split(separator: " ").map{Int(String($0))!}
func isAble(_ standardScore: Int) -> Bool {
var index: Int = 0
var count: Int = 1 // 가장 마지막 구간은 카운팅이 안됨. 그래서 1로 시작.
var temp: [Int] = []
while index < N { // index가 0..<N까지. 그 구간에 1개만 있는 상황 체크를 위해, index를 빼줘야 해서 for문이 아닌 while문으로.
temp.append(numsArray[index])
let (max, min) = (temp.max()!, temp.min()!)
if max - min > standardScore { // 기준값보다 클 때 구간이 바뀜.
temp.removeAll()
count += 1
// temp.append(numsArray[index]) // 구간이 바뀌게 된 숫자부터 다시 시작. - 이 코드는 필요 없음. 이유 : 인덱스를 빼주면, 어차피 (코드상)5줄 위에서 다시 그 구간에 1개만 있는 상황으로 됨.
index -= 1 // 인덱스를 다시 하나 빼줘야, 구간에 1개만 있는 상황이 체크됨.
}
index += 1
}
return count <= M // middle(standardScore)로 M개 이하의 구간을 만들었는가.
}
var low = 0
var high = numsArray.max()!
var answer: Int = 0
while low <= high {
let middle = (low + high) / 2
if isAble(middle) { // 구간점수들 중 최댓값(middle)으로 가능하다면, 더 작은 수로는 가능한지 체크하기 위해.
high = middle - 1
answer = middle
}
else { // 최솟값(middle)로 불가능하면, 더 큰 수로는 가능한지 체크하기 위해.
low = middle + 1
}
}
print(answer)
백준 Swift 1300번
문제 유형 : 이분탐색 활용
- 처음엔 실제로 2차원 배열을 생성한 뒤 flatMap을 써서 제출했다. 당연하게.. 메모리 초과. 문제는 짧은데, 생각하기가 어렵다.
이 문제가 이분탐색 문제라는건 알고 있어서 어떻게 접근하면 좋을까 고민을 하다가 모르겠어서 다른 글들을 참고했다.
문제에서 B[k]를 찾는다는 건, k이하의 숫자가 적어도 k개 있다는 뜻이 된다. (=> 즉, 이분탐색의 high는 k가 된다.)
배열을 쓰지 않고(N이 매우 커서 메모리초과가 남) 몇개가 있는지 알아야 k번째 숫자(= 정답)를 구할 수 있을 것이다.
1. low와 high를 통해 middle(기준값)을 정하고, 기준값을 통해 기준값보다 작거나 같은 숫자 개수를 구한다.
1-1. 기준값을 각 행으로 나눠주면, 그 행에서 나올 수 있는 (기준값보다 작은) 숫자의 개수가 나온다.
ex) 구구단의 8단에서, 8의 배수들 중 54보다 작은 숫자의 개수를 구하라고 한다면 어떻게 구할 것인가? 54 / 8 = 6개 일 것이다. 예시와 1-1은 같은 내용이다.
1-2. 각 행에서 나올 수 있는 숫자의 개수는 N개일 것이다. NxN행렬이니깐. 하지만, (middle(기준값) / i(행렬)) 로만 계산한다면 N개보다 큰 값이 나오게 될 수 있다. 따라서, (middle(기준값) / i(행렬)) 과 N 중 작은 숫자를 더해줘야 한다. => count += min(middle/i, N)
ex) N은 3이고 middle은 4일 때, 1행에서 그냥 (middle(기준값) / i(행렬))로만 계산하면 4가 나오게 된다. 3이 나와야 하는데!
기준값이 K보다 크거나 같을 때는, 더 작은 기준값일 때도 K개에 해당하는지 찾기 위해 낮춰보면 된다.
난이도 : 골드2
참고한 글 : https://st-lab.tistory.com/281 | https://woongsios.tistory.com/216
// MARK: - 1300번(이분탐색)
let N = Int(readLine()!)!
let k = Int(readLine()!)!
//var A = Array(repeating: Array(repeating: 0, count: N + 1), count: N + 1)
//
//for j in 1..<N+1 {
// for i in 1..<N+1 {
// A[j][i] = j * i
// }
//}
//
//let B = A.flatMap{$0.filter{$0 > 0}}.sorted(by: <)
//print(B[k])
var low: Int = 1
var high: Int = k
var answer: Int = -1
while low <= high {
let middle = (low + high) / 2
var count: Int = 0
for i in 1...N {
count += min(middle / i, N) // (middle/i)와 N 중, 작은 걸 더해야 한다. 예를 들어, 1행(i=1)에서 나올 수 있는 갯수는 최대 N개인데, 더 큰 값이 나올 수도 있기 때문.
}
if count >= k { // 개수가 K개 이상이면, 더 작은 수일 때도 K개에 해당하는지 찾기 위해 낮춰본다.
high = middle - 1
answer = middle
}
else { // 개수가 K개보다 아직 적다면, 더 큰 수로 만든다.
low = middle + 1
}
}
print(answer)
최근댓글