이분탐색6 [Swift][이분 탐색][중간에서 만나기] 백준 1208번 (부분수열의 합 2) 요구능력 해시와 이분탐색 문제풀이 일반적인 부분수열의 합으로 풀기에는 시간복잡도가 2^40까지 나와서 시간초과가 나오게된다. 2^40이 나오는 이유는 이 문제는 더하기, 더하지않기라는 경우의 수밖에 없기때문이다. 그렇다면 어떻게 풀어야할까? 나는 여기서 중간에서 만나기라는 개념을 처음 접했는데, 대충 이런개념인것같다. 반을 쪼개서 해시로 dictionary에 값들을 저장해주고, 나머지 반에서 값들을 구하면서 (목표값 - 구한값)을 해시에 저장된 값에서 가져오면 중간에서 만나는(?) 개념이 성립되는것 같다. 그리고 문제에서는 크기가 양수인 부분수열이라고 했는데, 아래와 같이 재귀로 sum을 계속 들어가면 하나도 더하지않는 경우(공집합)가 생기므로 s가 0인경우에는 공집합이 생기는 경우를 제거해야한다. 후기.. 2022. 5. 10. [Swift][프로그래머스][이분탐색] 입국심사 요구능력 이분탐색 문제풀이 시간을 이용하여 이분탐색을 진행한다. 맨처음은 0분으로 설정했고, 가장 오래걸리는 시간은 times배열에서 심사하는데 가장오래걸리는사람 * n을 해주면된다. left와 right를 비교해가며 이분탐색을 진행한다. 후기 이분탐색은 처음써보는데 쓸만한 알고리즘인거같다. 코드 import Foundation func solution(_ n:Int, _ times:[Int]) -> Int{ let time = times.sorted() var left = 0 var right = n * time.last! while left = n{ right = mid - 1 }else if people < n{ left = mid + 1 } } return left } 2022. 5. 3. 이전 1 2 다음