2022-07-08
🚩이진탐색에 대하여
사실 문제를 푸는데 있어서 이진탐색을 써야겠다는 포인트를 느껴야하는 지점은 꽤나 명확하다.예를 들어 내가 그냥 일반 브루트 포스 방식으로 탐색해야 겠다!하는 범위가 문제에서 명시적으로 어라? 100000000 한 천만 이정도로 넘어가면
이건 거의 90퍼 이상확률로 완전탐색 방식으로 불가능 한 것을 깨닫구
이진탐색을 떠올려야 한다
🚩사용시점
탐색해야 하는 데이터의 개수나 값이 1,000만 단위 이상일 경우 이진 탐색과 같이 시간 복잡도가 O(log N) 수준으로 빠른 속도를 낼 수 있는 알고리즘을 활용하는 것이 좋습니다.
이진탐색의 포인트는 기본 정렬된 상태이다!
따라서 항상 내가 탐색할려는 데이터셋이 정렬이 되어있는지 체크해줄것!!
data.sort()🔑사용방법
이진탐색을 구현하는데 있어서 두 가지 방법은
1) 반복문 구현
2) 재귀적 구현으로 되지만
사실 둘다 같다
mid값과 target값의 비교를 통해 앞으로 더 탐색해야할 범위는 어디일지를
보고 그 쪽으로 줄여나가는 원리!
#반복문 구현 방식
def binary_search(arr,start,target,end):
while start<=end:
mid=(start+end)//2
#중간의 위치에 인덱스를 구한다
if arr[mid]==target:
return mid
#중간인덱스의 값이 타겟 값이랑 같을 때
elif arr[mid]>target:
end=mid-1
#중간인덱스의 값이 타겟 값보다 클 때
else:
start=mid+1
#중간인덱스의 값이 타겟 값보다 작을 때
return None #재귀적 구현
def binary_recursion(arr,target,start,end):
if start>end:
return None
mid=(start+end)//2
if arr[mid]==target:
return mid
elif arr[mid]>target:
binary_recursion(arr,target,start,mid-1)
else:
binary_recursion(arr,target,mid+1,end)
그럼 이진탐색에 있어서 포인트는 무엇인가??
문제에서 구할려는 것을 기준(mid)로 설정을 하고 문제를 풀어나가자!
🙋♂️파이썬 bisect() 모듈
bisect()는 파이썬 자체적으로 이진탐색을 시켜주는 모듈로서 정렬된 리스트에서 내가 특정값을 넣을려고 할때의 그 때의 인덱스 값을 반환해준다.
즉 말이 어렵지 이진탐색에서의 타겟값이랑 같다면 타겟값의 인덱스를 반환!
같지 않더라도 걔보다 크면 그 다음 인덱스값 반환 이런원리이다
사용방법
import bisect
#쓰기 위한 불러오기
bisect.bisect(탐색리스트,타겟값)위키독에 쓰여져있는 문제를 하나 그대로 풀어보면 이해가 된다.
<각 맞는 성적 학생들에게 주기>
출처:https://wikidocs.net/105425
import bisect
result = []
scores = [33, 99, 77, 70, 89, 90, 100] # 애들이 받은 점수
grades = [60, 70, 80, 90] # 기준점수를 등급으로 바꿔주자
for score in scores:
pos = bisect.bisect(grades, score)
# 학생들의 점수를 grades = 기준에 넣는다고 가정했을때 어디 들어가면 될까
grade = 'FDCBA'[pos] # bisect는 인덱스만 리턴한다.
result.append(grade)
print(result)
['F', 'A', 'C', 'C', 'B', 'A', 'A']bisect.bisect_left()와 bisect_right()의 차이점
해당 타겟값을 찾을 때 정렬이 안 깨지는 상태선에서 왼쪽 인덱스를 줄지 오른쪽 인덱스를 줄지에 차이이다.
따라서 해당기능으로 쓸수 있는 응용스타일은
bisect_right()-bisect_left()를
통해 해당 값의 개수가 몇 개나 있는지 파악가능!!
(업데이트)
bisect는 만약에 찾는 값이 리스트에 없더라도 만약 그 값이 끝값보다 크면 그 끝 인덱스보다 하나 큰 값을 줄 것이고 만약에 그 값이 첫값보다 작게 되면 맨 앞에 인덱스인 0을 주게 될것이다
즉,해당 bisect 모듈은 정렬된 iterable한 객체에 대해서 어디에 값을 넣어줄지 인덱스를 찾아주는 함수로서
내가 찾는 값이 아니더도 어떤 인덱스든 값을 비교해서 반환할것이다
따라서
result_pos=bisect_left(a,찾는값)
#이와 같이 실제 해당 반환한 pos에서 값이 찾는 값인지
#확인해주는 과정은 필요하다 만약 존재유무를 파악하기 위해서는
#또한 반환한 인덱스는 끝 인덱스를 넘을수 있기에
#len()보다 작게하자
if result_pos<len(a) and a[result_pos]==찾는값:
print("값이 존재함")
else:
print("값이 없음")🚩문제를 풀고 느낀 점
-
탐색해야 하는 모든 시간의 경우의 수를 담은 리스트를 만들 필요는 없다.
범위를 설정하고 그 안에서 탐색을 진행해도 된다 -
어떤 이진탐색 문제이던지 사람의 수나,삭제해 나가야 할 돌의 수 같이 해당 수를 기준으로 왼쪽,오른쪽의 값이 이동이 필요함
-
start값을 정할 때 start값이 0으로 인해 발생하는 문제가 발생할 수 있으므로 고려해보자
-
문제에서 가장 큰 최댓값을 구하라고 하면 그 mid값일때의 조건을 바로 반환하면 값이 여러개 일 때가 있어서 최댓값이라는 보장을 못해서 좀 더 가봐야 알 수 있다.따라서 조건분기를 이상,그 외로 나눠서 더 진행을 해본다.그리고 그 범위에 해당하는 가장 큰 값을 주기 위해 end값을 주자
-
end 값을 가지고 답을 주는 즉 최대값인 케이스에서는 되도록이면 등호를 붙여서 나누는 경우를
if curr<=M:
start=mid+1
else:
end=mid-1이와 같이 start쪽으로 등호를 붙이게 경우를 짜주자
