학습 목표: 이분 탐색 응용 (Parametric Search) · 그리디 알고리즘 설계 원칙 · 정렬 기반 그리디 패턴 · 최적해 증명 연습
1️⃣ 이분 탐색 (Binary Search)
개념
정렬된 배열에서 찾는 값의 범위를 절반씩 줄여나가는 탐색. O(n) 선형 탐색 → O(log n) 으로 획기적으로 줄여준다.
📖 비유: 1~100 숫자 맞추기 게임에서 "50보다 크냐?"부터 물어보는 것!
매번 절반을 날려버리니까 최대 7번(log₂100 ≈ 7)이면 찾을 수 있음.
기본 구현 -값 찾기
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid # 찾음!
elif arr[mid] < target:
left = mid + 1 # 오른쪽 절반으로
else:
right = mid - 1 # 왼쪽 절반으로
return -1 # 없음
arr = [1, 3, 5, 7, 9, 11, 13]
print(binary_search(arr, 7)) # 3 (인덱스)
print(binary_search(arr, 4)) # -1 (없음)
Lower Bound / Upper Bound
import bisect
arr = [1, 2, 2, 2, 3, 4, 5]
# lower_bound: target 이상인 첫 번째 위치
print(bisect.bisect_left(arr, 2)) # 1
# upper_bound: target 초과인 첫 번째 위치
print(bisect.bisect_right(arr, 2)) # 4
# 2의 개수
print(bisect.bisect_right(arr, 2) - bisect.bisect_left(arr, 2)) # 3
💡 실전 꿀팁: 정렬된 배열에서 특정 값의 개수, 범위 안의 원소 개수 구할 때
bisect라이브러리 쓰면 O(log n)에 해결!
2️⃣ 파라메트릭 서치 (Parametric Search)
개념
"답이 될 수 있는 값의 범위"에 이분 탐색을 적용하는 기법. "최솟값을 최대화", "최댓값을 최소화" 유형에서 자주 나온다.
핵심 발상:
"어떤 값 X가 정답이 될 수 있냐?"를 O(n)으로 검증할 수 있다면
→ X의 범위에 이분 탐색 적용 → 전체 O(n log n)
파라메트릭 서치 템플릿
def parametric_search():
left, right = 최솟값, 최댓값
while left <= right:
mid = (left + right) // 2
if is_possible(mid): # mid가 정답이 될 수 있냐?
answer = mid
left = mid + 1 # 더 큰 값도 가능한지 탐색 (최대화)
# right = mid - 1 # 더 작은 값도 가능한지 탐색 (최소화)
else:
right = mid - 1 # 불가능하면 범위 줄이기
# left = mid + 1
return answer
예시 -나무 자르기 (높이 H 결정)
N개의 나무를 절단기 높이 H로 잘랐을 때 M미터 이상 가져갈 수 있는 최대 H는?
def can_get(trees, H, M):
# 높이 H로 잘랐을 때 얻는 나무 총량
total = sum(max(0, tree - H) for tree in trees)
return total >= M
def solution(trees, M):
left, right = 0, max(trees)
answer = 0
while left <= right:
mid = (left + right) // 2
if can_get(trees, mid, M):
answer = mid # 가능하면 정답 후보
left = mid + 1 # 더 높게 잘라도 되는지 확인 (H 최대화)
else:
right = mid - 1 # 불가능하면 H를 낮춰야 함
return answer
trees = [20, 15, 10, 17]
print(solution(trees, 7)) # 15
흐름:
H=10: 10+5+0+7 = 22 ≥ 7 → 가능, answer=10, left=11 H=15: 5+0+0+2 = 7 ≥ 7 → 가능, answer=15, left=16 H=17: 3+0+0+0 = 3 < 7 → 불가능, right=16 H=16: 4+0+0+1 = 5 < 7 → 불가능, right=15 → 최종 answer = 15
예시 -공유기 설치 (거리 최대화)
N개의 집에 C개의 공유기를 설치할 때, 공유기 사이 최소 거리를 최대화하라
def can_install(houses, C, min_dist):
count = 1
last = houses[0]
for i in range(1, len(houses)):
if houses[i] - last >= min_dist:
count += 1
last = houses[i]
return count >= C
def solution(houses, C):
houses.sort()
left, right = 1, houses[-1] - houses[0]
answer = 0
while left <= right:
mid = (left + right) // 2
if can_install(houses, C, mid):
answer = mid # 가능하면 정답 후보
left = mid + 1 # 거리를 더 늘려볼 수 있는지 확인
else:
right = mid - 1 # 불가능하면 거리 줄이기
return answer
houses = [1, 2, 4, 8, 9]
print(solution(houses, 3)) # 3
3️⃣ 그리디 (Greedy) 알고리즘
개념
매 순간 현재 기준으로 가장 좋아 보이는 선택을 하는 방법. 전체적으로 봤을 때도 최적이 되는지 증명이 필요함.
🍕 비유: 피자 8조각 중 가장 큰 걸 계속 먹는 것!
매 순간 최선의 선택이 전체 최선으로 이어질 때만 그리디가 통한다.
그리디 알고리즘 설계 원칙
1. 탐욕적 선택 가능성 (Greedy Choice Property)
→ 매 순간의 최선 선택이 전체 최적해로 이어지는가?
2. 최적 부분 구조 (Optimal Substructure)
→ 부분 문제의 최적해가 전체 문제의 최적해에 포함되는가?
두 조건이 모두 성립해야 그리디로 풀 수 있음!
그리디가 틀리는 경우 -중요!
# 동전 거스름돈 문제
# 그리디가 통하는 경우: 동전이 배수 관계일 때
coins = [500, 100, 50, 10] # 서로 배수 관계
def greedy_coins(target, coins):
result = 0
for coin in sorted(coins, reverse=True):
result += target // coin
target %= coin
return result
print(greedy_coins(1260, coins)) # 6개 (정답)
# 그리디가 틀리는 경우: 배수 관계가 아닐 때
coins2 = [1, 4, 6]
# target = 8일 때 그리디: 6+1+1 = 3개
# 실제 최적: 4+4 = 2개
# → 이런 경우엔 DP를 써야 함!
4️⃣ 정렬 기반 그리디 패턴
패턴 1 -회의실 배정 (종료 시간 기준 정렬)
회의가 겹치지 않게 최대한 많이 배정하기
def meeting_rooms(meetings):
# 종료 시간 기준 오름차순 정렬 (같으면 시작 시간 기준)
meetings.sort(key=lambda x: (x[1], x[0]))
count = 0
end_time = 0
for start, end in meetings:
if start >= end_time: # 이전 회의가 끝났으면
count += 1
end_time = end # 현재 회의 선택
return count
meetings = [(1,4), (3,5), (0,6), (5,7), (3,8), (5,9), (6,10), (8,11), (8,12), (2,13), (12,14)]
print(meeting_rooms(meetings)) # 4
왜 종료 시간 기준으로 정렬?
일찍 끝나는 회의를 먼저 배정해야 다음 회의를 위한 시간이 더 많이 남아!
패턴 2 -동전 (큰 동전부터 선택)
def min_coins(n, coins):
coins.sort(reverse=True)
count = 0
for coin in coins:
count += n // coin
n %= coin
return count
print(min_coins(1260, [500, 100, 50, 10])) # 6
# 500×2 + 100×2 + 50×1 + 10×1 = 1260
패턴 3 -숫자 카드게임 (행에서 최솟값, 열에서 최댓값)
def card_game(matrix):
result = 0
for row in matrix:
min_val = min(row) # 각 행의 최솟값
result = max(result, min_val) # 그 중 최댓값
return result
matrix = [
[3, 1, 2],
[4, 1, 4],
[2, 2, 2]
]
print(card_game(matrix)) # 2
패턴 4 -정렬 기반 최적화
# 곱하기 or 더하기 (무조건 곱하기가 좋지 않음)
def multiply_or_add(s):
result = int(s[0])
for i in range(1, len(s)):
num = int(s[i])
# 0 또는 1이면 더하기, 그 외엔 곱하기
if num <= 1 or result <= 1:
result += num
else:
result *= num
return result
print(multiply_or_add("02984")) # 576
5️⃣ 최적해 증명 연습
그리디 문제를 풀 때 "왜 이 선택이 최적인가?" 를 설명할 수 있어야 함.
증명 방법 -교환 논증 (Exchange Argument)
"그리디 선택 대신 다른 선택을 했을 때 결과가 나빠진다는 것을 보이면 된다"
예시 -회의실 배정
주장: 종료 시간이 가장 빠른 회의를 선택하는 것이 최적이다.
증명:
- 최적해 O에서 그리디 선택 G 대신 다른 회의 A를 선택했다고 가정
- A의 종료 시간 ≥ G의 종료 시간 (G가 가장 빨리 끝나므로)
- G를 선택해도 A 이후에 선택 가능한 회의는 모두 선택 가능
- 따라서 G로 교환해도 결과가 나빠지지 않음 → G 선택이 최적 ✅
그리디 vs DP -언제 뭘 써?
그리디를 써야 할 때 매 순간의 최선 선택이 전체 최적으로 이어질 때 (교환 논증으로 증명 가능) 정렬 후 순서대로 선택하는 패턴일 때 "~를 최대화/최소화해라" 유형에서 탐욕적 선택이 명확할 때
DP를 써야 할 때 이전 선택이 이후 선택에 영향을 줄 때 그리디로 풀었는데 반례가 존재할 때 "모든 경우를 고려해야 최적해가 나올 때"
동전 거스름돈 (배수 관계) → 그리디
동전 거스름돈 (배수 아님) → DP
회의실 배정 → 그리디
배낭 문제 (0/1 Knapsack) → DP
6️⃣ 이분탐색 3문제 + 그리디 3문제 풀이
✅ 이분탐색 1 -수 찾기
import sys
input = sys.stdin.readline
def solve():
n = int(input())
a = list(map(int, input().split()))
m = int(input())
b = list(map(int, input().split()))
a.sort()
for x in b:
lo, hi = 0, n - 1
found = False
while lo <= hi:
mid = (lo + hi) // 2
if a[mid] == x:
found = True
break
elif a[mid] < x:
lo = mid + 1
else:
hi = mid - 1
print(1 if found else 0)
✅ 이분탐색 2 -나무 자르기 (파라메트릭 서치)
def solve():
n, m = map(int, input().split())
trees = list(map(int, input().split()))
left, right = 0, max(trees)
answer = 0
while left <= right:
mid = (left + right) // 2
total = sum(max(0, t - mid) for t in trees)
if total >= m:
answer = mid
left = mid + 1
else:
right = mid - 1
return answer
✅ 이분탐색 3 -랜선 자르기 (파라메트릭 서치)
def solve():
k, n = map(int, input().split())
cables = [int(input()) for _ in range(k)]
left, right = 1, max(cables)
answer = 0
while left <= right:
mid = (left + right) // 2
count = sum(cable // mid for cable in cables)
if count >= n:
answer = mid
left = mid + 1 # 더 길게 자를 수 있는지 확인
else:
right = mid - 1
return answer
✅ 그리디 1 -동전 0 (큰 단위부터 선택)
def solve():
n, k = map(int, input().split())
coins = [int(input()) for _ in range(n)]
coins.sort(reverse=True)
count = 0
for coin in coins:
count += k // coin
k %= coin
return count
✅ 그리디 2 -회의실 배정 (종료 시간 정렬)
def solve():
n = int(input())
meetings = [tuple(map(int, input().split())) for _ in range(n)]
meetings.sort(key=lambda x: (x[1], x[0])) # 종료시간 기준 정렬
count = 0
end = 0
for start, finish in meetings:
if start >= end:
count += 1
end = finish
return count
✅ 그리디 3 -ATM (대기 시간 최소화)
def solve():
n = int(input())
times = list(map(int, input().split()))
times.sort() # 처리 시간 짧은 순 정렬
total = 0
wait = 0
for t in times:
wait += t
total += wait
return total
# 예: [3, 1, 4, 3, 2] → 정렬: [1, 2, 3, 3, 4]
# 대기: 1, 3, 6, 9, 13 → 합: 32
왜 짧은 순서?
먼저 온 사람이 오래 걸릴수록 뒤 사람 전체의 대기가 늘어난다..
짧은 것부터 처리하면 전체 대기 시간의 합이 최소가 됨!
핵심 요약
이분 탐색
→ 정렬된 배열에서 O(log n) 탐색
→ left <= right, mid = (left+right)//2 가 기본 틀
파라메트릭 서치
→ "X가 정답이 될 수 있나?" 검증 함수 만들기
→ 답의 범위에 이분 탐색 적용
→ "최솟값 최대화", "최댓값 최소화" 유형
그리디 설계 원칙
→ 탐욕적 선택 가능성 + 최적 부분 구조 둘 다 성립해야 함
→ 반례가 존재하면 그리디 불가 → DP 고려
정렬 기반 그리디 패턴
→ 회의실: 종료 시간 기준 정렬
→ 동전: 큰 단위부터 선택
→ ATM: 처리 시간 짧은 순 정렬
그리디 vs DP
→ 매 선택이 독립적 → 그리디
→ 이전 선택이 영향을 줌 → DP
🔥 이분탐색 & 그리디 -언제 뭘 쓸지 실전 정리
"몇 번째 값이냐?" 정렬 후 이분 탐색 → O(log n)
"최소/최대값을 구하되, X 이상/이하 가능한지 검증 가능하다" 파라메트릭 서치 → 범위에 이분 탐색
"매 순간 가장 큰/작은 것을 선택하면 된다" 그리디 (교환 논증으로 최적해 증명 가능)
"그리디로 풀었는데 반례가 있다" → DP로 전환 필요