티스토리 뷰
이분 탐색 (Binary Search)
정렬된 리스트를 logN 시간 복잡도로 순차 탐색보다 빠르게 탐색하는 알고리즘
매개 변수 탐색 (Parametric Search)
정의 : 최적화 문제를 결정 문제로 바꾸는 것 (이건 도대체 무슨 소리인가)
그냥 쉽게, 이분 탐색을 응용하는 문제들을 다 매개 변수 탐색이라고 생각하면 된다
매개 변수 탐색의 핵심 아이디어는 "최적으로 구할 해"를 이분 탐색으로 찾는 것이다
매개 변수 탐색 문제는 최적해를 구할 변수와 이와 연관된 변수(편의상 매개 변수라고 하겠다)가 주어진다
그래서 이름에 매개 변수가 들어가는 건가
- 입국심사에 걸리는 최소 시간(최적해)과 사람 수(매개 변수)
- 공유기 설치에서 최대 거리차의 최솟값(최적해)과 공유기 수(매개 변수)
매개 변수 탐색 문제를 접근할 때는 다음과 같은 기본 틀을 기준으로 로직을 구상해야 한다
start, end = 0, 1 # 이분 탐색을 진행할 최적 해의 시작값과 끝값
answer = 0
while start <= end:
mid = (start + end) // 2
# 메인 로직 : 최적해와 매개 변수의 연관관계를 적절히 활용한다
# 분기 조건 : 매개 변수로 검사한다
if 블라블라:
start = mid + 1
answer = mid
else:
end = mid - 1
print(answer)
<문제 접근 순서>
1. start와 end를 구하고자 하는 최적해를 기준으로 설정한다
(ex. 거리의 최댓값 => 거리를 이분 탐색해야 함, 시간의 최솟값 => 시간을 이분 탐색해야 함)
2. 매개 변수와 최적해를 적절히 연관 지어서 메인 로직을 구상한다
3. 분기 조건을 검사한다
메인 로직과 분기 조건이 뭔지 이해가 잘 안 되면 아래 예시 문제들을 보면서 파악해보자
예시 문제
[기초] 백준 실버 3 나무 자르기
https://www.acmicpc.net/problem/2805
2805번: 나무 자르기
첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보
www.acmicpc.net
최적해 : 잘라야 하는 나무 "높이"의 최댓값
start, end = (기준 : 높이) 가장 작은 나무, 가장 큰 나무
메인 로직 : mid를 기준으로 각 나무를 잘라서 total(잘라진 나무의 길이)에 더한다
분기 조건 : total과 가져가야 할 나무의 총 높이를 비교하면서 분기를 나눈다
- 잘라진 총 길이 >= 가져가야 할 길이 → 자르는 높이를 줄여야 함 → mid를 늘린다 → start = mid + 1
- 잘라진 총 길이 < 가져가야 할 길이 → 자르는 높이를 늘려야 함 → mid를 줄인다 → end = mid - 1
[기초] 백준 실버 3 랜선 자르기
https://www.acmicpc.net/problem/1654
1654번: 랜선 자르기
첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그
www.acmicpc.net
나무 자르기와 동일
[응용] 백준 골드 5 공유기 설치
https://www.acmicpc.net/problem/2110
2110번: 공유기 설치
첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가
www.acmicpc.net
최적해 : 각 공유기끼리 떨어진 "거리"
start, end = (기준 : 거리) 공유기끼리 한 칸만 떨어져 있는 경우, 맨 처음과 맨 끝에 공유기가 떨어진 경우
메인 로직 : 공유기를 배치할 수 있는 집의 좌표를 반복문을 돌면서 전에 놓은 공유기 위치와 현재 집의 위치의 차가 mid와 비교해서 공유기를 설치 (count 변수로 현재 설치한 공유기 수 체크)
분기 조건 : count를 설치할 공유기 수와 비교해서 분기
※ count >= 공유기 수 → 공유기가 원하는 것 보다 더 설치됨(간격을 늘려서 덜 설치해야 함)
→ mid를 늘린다 → mid = start + 1
※ count < 공유기 수 → 공유기가 원하는 것 보다 덜 설치됨(간격을 줄여서 더 설치해야 함)
→ mid를 줄인다 → mid = end - 1
[응용] 프로그래머스 레벨 3 입국심사
https://programmers.co.kr/learn/courses/30/lessons/43238
코딩테스트 연습 - 입국심사
n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한
programmers.co.kr
최적해 : 입국 심사에 걸리는 최종 "시간"
start, end = (시간) 0, max(times) * n
메인 로직 : 현재 mid(시간) 값을 times의 각 요소의 몫을 구해서 count (사람 수)에 더한다
(mid 시간안에 처리할 수 있는 총 사람 수를 구한다)
분기 조건 : count와 n을 비교해서 분기
※ 처리할 수 있는 사람 수 >= 목표 사람 수 → 시간(mid)을 너무 여유롭게 설정함(시간을 줄여서 사람 수를 늘려 본다)
→ mid를 줄인다 → mid = end - 1
※ 처리할 수 있는 사람 수 < 목표 사람 수 → 시간(mid)을 너무 타이트하게 설정함(시간을 늘려서 사람 수를 줄여 본다)
→ mid를 늘린다 → mid = start + 1
[응용] 백준 골드 4 휴게소 세우기
https://www.acmicpc.net/problem/1477
1477번: 휴게소 세우기
첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. 둘째 줄에 현재 휴게소의 위치가 공백을 사이에 두고 주어진다.
www.acmicpc.net
도전 중 너무 어려움
<정리>
- 최적해(mid)를 계산할 start와 end를 설정한다
- 최적해를 구해야하는 변수와 이와 연관된 매개 변수로 메인 로직을 구상한다
- 조건 분기는 매개 변수를 기준으로 검사하여 최적해 값을 판단할 범위를 이분 탐색으로 줄여 나간다
- 최종적으로 매개 변수와 이를 검사하는 변수가 값이 동일해지는 시점이 최적해(mid)가 되는 시점이다