안녕하세요 오늘은 이진 탐색(이분 탐색) 문제 유형을 분석해보는 시간을 갖도록 하겠습니다.
첫 번째 유형은 정렬이 가능한 집합 안에서 완전 탐색보다 빠르게 탐색을 필요로 하는 문제입니다. 이진 탐색 특성 상 정렬이 되어 있는 집합 내에서만 적용되기 때문에 정렬되지 않은 순서대로 진행해야 하는 집합의 경우 이진 탐색을 적용하기 어렵습니다. 이런 문제들은 입력값의 최대값이 꽤 큰 수로 나오거나 여러 번 곱해야 하는 시간 복잡도를 가지기 때문에 완전 탐색으로 풀기 어렵다는 특징이 있기 때문에 이런 부분을 캐치하면 좋을 것 같습니다.
백준 1920(수 찾기) 문제의 경우 N 집합 안의 수가 M 집합 안에 존재하는지를 확인하는 문제입니다. 완전 탐색 시 NxM으로 시간 초과가 발생하기 때문에 이진 탐색으로 진행합니다. N 집합을 정렬한 후 시작값을 가장 처음 인덱스, 끝값을 가장 마지막 인덱스로 하여 M의 값이 있을 경우 1을, 없을 경우 0을 출력합니다.
백준 1300(K번째 수) 문제의 경우 이차원 배열 A[i][j] = ixj 를 일차원 배열로 넣어 오름차순 정렬했을 때 B[k]값을 구하는 문제입니다. NxN으로 완전 탐색 시 시간 초과가 발생하기 때문에 이진 탐색으로 시작을 1, 끝을 k로 잡고 둘의 중앙값보다 작은 수의 개수를 세면서 범위를 줄여나가면 됩니다. 이 때 중앙값보가 작은 수의 개수는 ixj 형태로 값이 들어가있기 때문에 2차원 배열의 각 행별(1부터 n)로 현재 중앙값을 나눈 값과 N 사이의 최솟값으로 구할 수 있습니다.
두 번째 유형은 상한값 또는 하한값을 기준으로 벗어나는 값들을 조정하는 문제입니다. 이 문제들의 경우 완전 탐색 시 시간 초과가 발생하는 특징을 가지고 있으며 구하고자 하는 값을 중앙값으로 하여 시작값과 끝값을 문제에 맞게 설정하여 조건을 구현하면 됩니다.
백준 2805(나무 자르기) 문제의 경우 적어도 M의 나무를 집에 가져가기 위한 절단기 높이의 최댓값을 구하는 문제입니다. 완전 탐색 시 NxM으로 시간 초과가 발생하기 때문에 이진 탐색으로 절단기 높이를 시작값을 나무의 최솟값, 끝값을 나무의 최댓값으로 설정하여 자른 이후 총합을 계산한 후 M보다 클 경우 정답값을 최댓값으로 갱신하는 방식으로 풀 수 있습니다.
백준 1654(랜선 자르기) 문제의 경우 K개의 랜선을 모두 N개의 같은 길이로 자를 때 최대 랜선의 길이를 구하는 문제입니다. 완전 탐색 시 KxN으로 시간 초과가 발생하기 때문에 이진 탐색으로 랜선 길이를 시작값을 최소 랜선의 길이와 끝값을 최대 랜선의 길이로 설정하여 랜선을 자른 후 자른 랜선의 길이의 최댓값으로 정답을 갱신합니다.
백준 2512(예산) 문제의 경우 예산요청과 국가예산의 총액이 있을 경우 총액 이하에서 가능한 최대의 요청을 진행할 수 있는 총 요청값의 합을 구하는 문제입니다. 완전 탐색 시 NxM으로 시간 초과가 발생하기 때문에 이진 탐색으로 상한액을 시작값을 요청의 최솟값, 끝값을 요청의 최댓값으로 설정하여 총 예산합을 구한 후 최댓값을 갱신합니다.
백준 6236(용돈 관리) 문제의 경우 N일 동안 사용할 금액을 M번만 K원씩 인출한다고 했을 때 인출 금액의 최솟값을 구하는 문제입니다. 인출 금액을 하루 사용 금액 중 최댓값, 끝값을 금액의 총합으로 하여 N일 동안 금액을 사용하면서 금액이 모자랄 경우 K원 인출하는 방식으로 만약 인출 횟수가 M을 초과하지 않을 경우 인출 금액의 최솟값을 갱신합니다.
백준 2343(기타 레슨) 문제의 경우 N개의 강의가 M개의 블루레이에 순서가 바뀌지 않고 모든 블루레이의 크기가 같도록 넣을 때 블루레이의 최소 크기를 구하는 문제입니다. 완전 탐색 시 NxM으로 시간 초과가 발생하기 때문에 이진 탐색으로 블루레이의 크기를 시작값을 단일 강의의 최댓값, 끝값을 강의의 총합으로 하여 순서대로 추가하면서 모든 강의를 블루레이에 추가가 가능할 경우 최솟값을 갱신합니다.
좋은 글 감사합니다!