Binary Search
-
백준 1450 냅색문제Algorithm/BOJ 2021. 4. 6. 14:48
출처: www.acmicpc.net/problem/1450 분류: 이분탐색 접근방식 n이 30으로 크기 때문에 그대로 부분합을 구하면 2^30 시간제한을 통과하기 어렵습니다. 따라서 반반 나눈 뒤 이분탐색으로 접근하는 방법으로 접근합니다. 부분합은 재귀적으로 구해줬습니다. func partition(_ idx: Int, _ to: Int, _ array: inout [Int], _ sum: Int) { guard sum Int { var low = 0 var high = sumB.count while low < high { let mid = (low + high)/2 if target < sumB[mid] { high = mid } else { low = mid+1 } } return low } 참고로 ..
-
백준 2632 피자판매Algorithm/BOJ 2021. 4. 2. 13:14
출처: www.acmicpc.net/problem/2632 분류: 이분탐색 접근방식 이분탐색을 통해 해결해볼 수 있었습니다. 전체적인 풀이 과정은 다음과 같습니다. 1. 각 피자에서 가능한 피자 조각을 모두 구한다. (n == 1000 이므로 n^2 이면 충분합니다.) 2. 한쪽 피자에서 선택했을 경우 또는 하지 않을 경우 다른 쪽 피자의 값이 무엇이 되어야 할지 기대할 수 있기 때문에 이를 이분탐색으로 파악합니다. 가능한 피자 조각을 구할 때 주의해야 할 점은 피자 조각이 원형이라는 점입니다. 주어진 예제처럼 2 2 1 7 2 에서 피자 조각 경우를 구할 때, 원형으로 생각을 해줘야 합니다. 2 2 1 7 2 - 여기서 1부터 시작한다면 가능한 조합은 [1], [1, 7], [1, 7, 2], [1, ..
-
백준 3020 개똥벌레Algorithm/BOJ 2021. 3. 31. 11:36
출처: www.acmicpc.net/problem/3020 분류: 이분탐색 접근방식 이 문제는 가로 20 세로 50만이므로 모두 탐색한다거나 h만큼 일일이 배열에 담아준다거나 하는 방식으로는 시간초과를 면하기 어렵습니다. 저희가 원하는 건 특정 높이에서 만나는 장애물의 개수 입니다. 순서는 상관이 없죠! 따라서 이분탐색을 떠올려볼 수 있습니다. 대신 종유석과 석순이 서로 반대방향으로 나있기 때문에 이분탐색 upper/lower 바운드를 잘 섞어서 사용해줘야 하겠습니다. 이분탐색 upper/lower bounds가 익숙하지 않으시다면 여기를 읽어주세요 :] 조금 더 구체적으로 알아볼게요. 석순과 종류석의 높이를 따로 배열에 담고 정렬해줍니다. 저는 석순이 난 방향부터 높이를 1로 생각해서 계산해보려고 합니..
-
Binary Search 이진탐색(2) Lower/Upper boundAlgorithm/Theory 2020. 6. 12. 15:07
이진탐색이 정확히 원하는 값을 찾는 거라면, lower/upper bound는 원하는 값보다 처음으로 크거나 작은 값이 나오는 위치를 찾는 방법으로 중복된 요소나 타겟의 상한 하한을 찾는 경우 등 다양한 방식으로 활용될 수 있습니다. 이진 탐색에서 약간의 변형이 들어간 것으로 이진탐색을 이해하셨다면 어렵지 않게 이해할 수 있습니다. 이진탐색이 궁금하다면? --> 여기로 코드를 보기 전에 lower와 upper의 차이를 간략하게 정리해보고 가겠습니다. lower bound는 타겟보다 같거나 큰 값이 나오는 처음 위치를 찾습니다. upper bound는 타겟보다 처음으로 큰 값이 나오는 위치를 찾습니다. [1, 2, 2, 3, 3, 3, 4, 6] LowerBound(3) --> 3 UpperBound(3)..
-
Binary Search 이진탐색Algorithm/Theory 2020. 6. 12. 12:21
이진탐색 - 배열에서 원하는 원소를 찾는 탐색 방법이다. - 이미 정렬이 되어있는 상태에서만 사용할 수 있다. - 반씩 끊어가며 찾는 방법으로 O(logN) 의 시간복잡도를 갖는다. 이진 탐색은 이미 정렬이 되어있는 배열에서 원하는 원소를 효율적으로 찾을 수 있는 알고리즘입니다. 원리는 간단합니다. 이미 정렬이 되어있는 상태이기 때문에 반을 뚝 짤라서 찾는 원소가 왼쪽인지 오른쪽인지 확인해 아닌 부분은 버립니다. 조금 더 살펴보면, 시작 부분을 low, 끝 부분을 high라고 해볼게요. array = [1, 5, 7, 15, 22, 65, 80, 100] 배열이 이런식으로 있고 65를 찾고 싶다면, 시작할 때 low = 0, hight = 6 (array.count-1) 이고 mid = 3 = (0 + ..