2021년 12월 4일 토요일

이분탐색 - 징검다리

이분탐색 이란?

이분탐색은 마치 up & down 퀴즈 처럼 최소값과 최대값의 경계를 줄여나가며 최적해를 찾는 방법입니다.


이분탐색 문제의 특징

1. 변수의 범위가 굉장히 크다.

2. 최소값을 찾는 문제인 경우가 많다


이분탐색 문제를 해결하기 위한 스킬

1. 값을 정렬한다.

2. left,right,mid를 설정하여 최대값, 최소값, (최대+최소)//2 으로 초기화 한다

3. 조건에 따라 mid를 이용해서 left,right를 갱신한다.

4. 최소값을 math.inf로 초기화하고 계속 갱신한다.


위의 개념에 유의하여 이분탐색 - 징검다리 문제를 풀어보았습니다.

 문제 = https://programmers.co.kr/learn/courses/30/lessons/43236?language=python3

 구현= https://github.com/YongJaeJung/coding_test/blob/master/%EC%9D%B4%EB%B6%84%ED%83%90%EC%83%89/%EC%A7%95%EA%B2%80%EB%8B%A4%EB%A6%AC/%EC%A7%95%EA%B2%80%EB%8B%A4%EB%A6%AC.ipynb


Share:

0 comments:

댓글 쓰기