[알고리즘/문제풀이][BOJ 2110번] 공유기 설치

공유기 설치는 최적의 값을 찾는 문제를 참과 거짓을 결정하는 문제로 변환하여 이분법을 통해 해결할 수 있는 문제입니다. 문제의 지문을 그대로 해석하면 가장 인접한 공유기의 거리의 최대값을 구하는 문제로 생각할 수 있습니다. 이러한 최적화 문제를 참과 거짓을 결정하는 결정 문제로 변환하여 이분법을 이용하여 쉽게 해결할 수 있습니다. 위의 최적화 문제를 다음과 같은 결정 문제로 변환할 수 있습니다. "가장 인접한 공유기의 거리가 x이상이 되도록 공유기를 설치할 수 있을까" 이 질문에 대해서는 참 또는 거짓으로만 답을 할 수 있습니다. 만약 이 질문의 답이 참이라고 가정하면 가장 인접한 공유기의 거리가 x 이하인 모든 값으로 설치가 가능하다는 자명한 사실을 알 수 있습니다. 따라서 x이하의 값에 대해서는 더 ..
알고리즘/문제풀이 2021. 9. 22. 20:31
1
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG more
«   2025/01   »
일 월 화 수 목 금 토
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
글 보관함
반응형
250x250