250x250
Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
Tags
- FetchType
- 유니크제약조건
- 백트래킹
- SQL프로그래밍
- 연관관계
- fetch
- execute
- 일대다
- 이진탐색
- 데코레이터
- exclusive lock
- 다대다
- 비관적락
- JPQL
- 힙
- 낙관적락
- 동적sql
- querydsl
- BOJ
- 연결리스트
- eager
- 스토어드 프로시저
- 즉시로딩
- dfs
- 다대일
- 지연로딩
- CHECK OPTION
- shared lock
- PS
- 스프링 폼
Archives
- Today
- Total
흰 스타렉스에서 내가 내리지
Parametric Search의 전형적인 문제 - BOJ2805 본문
728x90
https://www.acmicpc.net/problem/2805
# Parametric Search
- 최적화 문제를 결정 문제로 바꾸어 해결하는 기법이다.
- '원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제'에 파라메트릭 서치를 사용한다.
- 예를 들어 범위 내에서 조건을 만족하는 가장 큰 값을 찾으라는 최적화 문제라면, 이진 탐색으로 결정 문제를 해결하면서 범위를 좁혀갈 수 있다.
- 코딩 테스트에서는 보통 파라메트릭 서치 유형은 이진 탐색을 이용하여 해결한다.
# 풀이
- '현재 이 높이로 자르면 조건을 만족할 수 있는가?'를 확인한 뒤에, 조건의 만족 여부(yes or no)에 따라 탐색 범위를 좁혀서 해결한다.
- 범위를 좁힐 때는 이진 탐색의 원리를 이용하여 절반씩 탐색 범위를 좁혀 나간다.
- 중간점의 값은 시간이 지날수록 '최적화된 값'을 찾기 때문에, 과정을 반복하면서 결과값을 중간점 값으로 갱신해준다.
n, m = map(int, input().split())
data = list(map(int, input().split()))
start, end = 0, max(data)
res = 0
while start <= end:
total = 0
mid = (start + end) // 2
for x in data:
if x > mid:
total += x-mid
if total < m:
end = mid-1
else:
res = mid
start = mid + 1
print(res)
1. start은 min(data)로 하면 안되는 걸까?
→ 안된다. min(data)-1도 안되더라...
2. while start < end: 는 안되는 걸까?
→ 안된다.
* 이진탐색에서 start는 안전하게 항상 0으로 가정하자.
* 반복문으로 구현하는 이진탐색의 while문에서는, start==end 인 상황도 가정한다. 리스트가 하나면 start==end 니까!
* 절단기의 높이는 1부터 10억 까지의 정수 중 하나인데, 이처럼 큰 수를 보면 당연하다는 듯이 가장 먼저 이진 탐색을 떠올려야 한다.
'Problem Solving' 카테고리의 다른 글
최단 경로 찾기 (1) | 2023.12.28 |
---|---|
다이나믹 프로그래밍과 메모이제이션 (0) | 2023.12.27 |
파이썬 언어에서, 입력 데이터를 빠르게 입력 받기 (0) | 2023.12.26 |
탐색 (1) | 2023.12.26 |
정렬 기법 (0) | 2023.12.25 |