이분탐색
-
백준 13397 구간 나누기 2Algorithm/BOJ 2021. 5. 21. 08:10
출처: https://www.acmicpc.net/problem/13397 분류: 이분탐색 접근방식 이분탐색으로 m개 이하의 구간으로 나눠서 만들 수 있는지 확인하면서 최소값을 갱신해나가는 방법으로 해결할 수 있었습니다. 배열의 값이 1...10000 값이기 때문에 음수는 나올 수 없으니 right를 배열의 합, left를 0으로 두고 이분탐색을 돌렸습니다. var left = 0, right = numbers.reduce(0, +) var minSegmentMax = right while left Bool { var low = numbers[0], high = numbers[0] var count = 1 for num in numbers { if num < low { low = num } if num ..
-
백준 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, ..
-
백준 1981 배열에서 이동Algorithm/BOJ 2021. 4. 1. 21:05
출처: www.acmicpc.net/problem/1981 분류: 이분탐색 접근방식 이 문제는 n이 최대 100으로 100 x 100 배열이기 때문에 단순 무식하게 BFS 접근하면 시간초과를 맞게 됩니다. 어떻게 하면 방문을 범위를 제한할 수 있을까요? 이 문제에서도 이분탐색의 아이디어를 적용해볼 수 있습니다. 우선 차이가 가장 작아지는 경우는 언제일까요? 경로의 최대최소가 같은 경우면 차이가 최소가 될 수 있겠죠? 때문에 최소는 언제나 가능성이 있으니 0으로 둡니다. 그럼 차이가 최대가 될 때는 언제일까요? 배열에 나오는 최대값과 최소값이 모두 들어있을 때, 즉 최대 - 최소가 차이의 최대가 되겠네요. 저희는 최소를 구해야 하기 때문에 만약 0 ~ 8 까지 가능성이 있을 때, 차이를 4로해서 가는 경우..
-
백준 3020 개똥벌레Algorithm/BOJ 2021. 3. 31. 11:36
출처: www.acmicpc.net/problem/3020 분류: 이분탐색 접근방식 이 문제는 가로 20 세로 50만이므로 모두 탐색한다거나 h만큼 일일이 배열에 담아준다거나 하는 방식으로는 시간초과를 면하기 어렵습니다. 저희가 원하는 건 특정 높이에서 만나는 장애물의 개수 입니다. 순서는 상관이 없죠! 따라서 이분탐색을 떠올려볼 수 있습니다. 대신 종유석과 석순이 서로 반대방향으로 나있기 때문에 이분탐색 upper/lower 바운드를 잘 섞어서 사용해줘야 하겠습니다. 이분탐색 upper/lower bounds가 익숙하지 않으시다면 여기를 읽어주세요 :] 조금 더 구체적으로 알아볼게요. 석순과 종류석의 높이를 따로 배열에 담고 정렬해줍니다. 저는 석순이 난 방향부터 높이를 1로 생각해서 계산해보려고 합니..
-
백준 1939 중량제한Algorithm/BOJ 2021. 3. 4. 17:06
출처: www.acmicpc.net/problem/1939 분류: 이분 탐색 접근방식 하 이번 문제도 너무 어려웠습니다... 설명이 애매해서 이해도 어려웠고 메모리제한............ ㅂㄷㅂㄷ 먼저 문제의 마지막에 " 한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 구하는 프로그램을 작성하시오. " 라고 되어있어서 마지막에 주어진 두 섬으로 한 번에 가는 경우를 체크하는건가? 그럼 중간에 경로들은 왜 주어진거지? 문제가 좀 이상한데? 라고 생각했었습니다. 결국 여기서 말하는 한 번의 이동이란 처음 섬에서 특정 중량으로 출발시킨 짐이 목표 섬까지 도착하는 경로를 의미합니다. 중량을 기준으로 이분 탐색을 해서 각 중량으로 이동이 가능한지 체크해서 해결했습니다. var mostWeight = 0..