본문 바로가기
728x90

이분 탐색3

[백준_2470] 중, 이분 탐색, 두 용액 [백준_2470] 중, 이분 탐색, 두 용액 산성 용액과 알칼리성 용액은 각각 양수와 음수의 특성값을 가지고 있다. 두 용액을 섞어 0에 가깝게 만들려고 할 때, 용매 각각의 특성값을 출력하는 문제이다. 이 문제는 처음에도 그렇고 풀고 나서도 그렇고 이분 탐색인지 직관적으로 와닿지 않는다는 게 어려웠다. 처음에 '이전의 start와 end의 합'과 'start index +1', 'end index -1'일 때 각각과 비교해 차이가 더 작은 방향으로 움직여야 한다고 생각했다. 그런데 이렇게 했을 때 문제는 [-95, -4, 3, 100]과 같은 경우 답이 -95, 100으로 출력된다는 점이다. 문제를 푸는 핵심 포인트는 정렬 후 양쪽에서 0의 방향으로 진행하는 부분(이진 탐색) 합이 양수인지 음수인지에 .. 2021. 8. 13.
[백준_2110] 중, 이분 탐색, 공유기 설치 생각 포인트 가장 인접한 두 공유기 사이의 최대 거리를 구해야 하므로 N개의 집의 양 끝에는 공유기가 무조건 설치된다. 그 다음 공유기 설치 위치는 좌표적으로 1번째와 N번째 공유기 중간에 가장 가까운 곳에 위치해야 한다. (순서상 중간이 아니다) 이 부분이 이진 탐색과 연결이 된다. 그럼 중간 좌표와 가장 주변 집의 좌표들 차이의 최솟값을 구해 최소가 되는 지점의 index에 공유기를 설치한다. 그 다음 공유기는 방금 설치한 공유기를 기준으로 1번째와 N번째 공유기 위치와의 거리 중 긴 곳 영역에 설치된다. 이후 반복. 이란 생각으로 풀었는데, 완전 오답 풀이였다.... 일단 이 방식은 딱 중간 가까운 공유기를 설치하기 때문에 공유기 개수가 짝수일 경우에는 오답이다.. 정답 코드를 작성하기 위한 핵심은.. 2021. 8. 13.
[백준_2805] 하, 이분 탐색, 수 찾기 [백준_2805] 하, 이분 탐색, 수 찾기 이분 탐색(Binary Search) 절단기의 높이를 차례대로 높이는 알고리즘으로는 시간 초과가 발생한다. 이 때 사용할 수 있는게 Binary Search(이분 탐색 or 이진 탐색)을 이용해야 한다. 이진 탐색이란 찾고자 하는 target 값을 오름 차순으로 정렬된 list에서, target값과 list의 중간값 비교를 통해 진행된다. 만약 중간값보다 target이 크면 검색 범위를 중간값 이상의 범위에서 다시 찾기 시작한다. 이 때 중간값은 하기와 같은 새로운 중간값을 이용한다. 첫 번 째 코드 import sys input = sys.stdin.readline from typing import Any, Sequence def bin_search(woo.. 2021. 8. 12.
728x90

티스토리툴바