😆 동빈나 님의 이코테 2021 강의 몰아보기를 보면서 공부한 내용을 정리하고 있습니다. 책은 이것이 취업을 위한 코딩 테스트다 with 파이썬을 참고하여 학습했습니다.😊
탐색
순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법
이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
→ 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다!!
이진탐색의 시간 복잡도는 logN을 만족해
이진탐색 알고리즘 소스코드
#이진 탐색 소스코드 구현 (재귀 함수)
def binary_search(array, target, start, end):
if start > end:
return None #데이터 존재하지 않기에 None 반환
mid = (start + end) //2 #중간점 인덱스
if array[mid] == target:
return mid #원하는 값 찾았기에 인덱스 반환
elif array[mid] > target: #중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽확인!!!
return binary_search(array, target, start, mid -1)
elif array[mid] < target: #중간점의 값보다 찾고자 하는 값이 더 크면 오른쪽 확인
return binary_search(array, target, mid+1, end)
#N(원소의 개수)와 target(찾고자 하는 값) 입력받기
N, target = map(int, input().split())
#전체 원소 입력
array = list(map(int, input().split()))
#이진 탐색 수행 결과 출력
result = binary_search(array, target, 0, N-1)
if result == None: #없어
print("원소가 존재하지 않습니다")
else:
print(result + 1) #위치 반환!
#이진탐색 소스코드 구현(반복문)
def binary_search(array, target, start, end):
while start <= end: #같을때까지만 돌아가야지
mid = (start + end)//2 #중간값 인덱스
if array[mid] == target: #찾은 경우
return mid #인덱스 반환
elif array[mid] < target: #찾고자 하는 값이 중간값보다 큰 경우 오른쪽!
start = mid+1 #중간값 인덱스 다음부터 찾아야하니까!
elif array[mid] > target: #찾고자 하는 값이 중간값보다 작은경우 왼쪽!
end = mid-1
return None #반복문을 탈출하는 경우라면 못찾은거니깐 None반환!
#N(원소의 개수)와 target(찾고자 하는 값)을 입력 받기
N, target = map(int, input().split())
#전체 원소 입력 받기
array = list(map(int, input().split()))
result = binary_search(array, target, 0, N-1)
if result == None:
print("원소가 존재하지 않습니다.")
else:
print(result + 1) #위치 반환!코딩테스트를 위해 알아두면 좋은 라이브러리
- bisect_left(list, target)
- bisect_right(list, target)
🎈 target의 가장 왼쪽 인덱스 , 가장 오른쪽 인덱스 반환
right_index - left_index 값이 바로 해당 값의 범위에 포함되어 있는 데이터의 개수를 구할 수 있어!!
🎃 파라메트릭 서치
이 부분부터 중요해
🎈 이진탐색을 활용해야 하는 문제가 출제되는 경우! 파라메트릭 서치 유형으로 출제되는 경우가 많아!
- 즉 답의 유효한 범위가 정해지는 경우 이진탐색을 활용해볼 수 있다.
관련 문제
매 높이마다 조건의 만족 여부를 설정했어야 했구나...
탐색 범위가 클 때는 이진 탐색부터 떠올리자 - 답의 범위가 그래도 정해져 있는 경우.
- 즉 답의 범위가 특정한 범위로 유효한 경우에 이진 탐색을 생각해보자 !!
🎈 잘린 떡의 길이를 통해 계속 M과 비교하면서 절단기 높을 때의 값을 얻어낼 수 있겠다 ! (이런 생각을 할 수 있게끔 문제를 계속 풀어나가자)
가장 긴 떡의 길이를 끝점으로 설정하는거야
완전히 같은 경우 그냥 끝내면 되겠다.
더이상 탐색 범위가 줄어들지 않을 때까지 시작점과 끝점의 위치를 바꿔가면서 높이값을 매번 바꿔보면서 찾아보는거였어.
🧨 여기서 알고 넘어가야할 것은 중간값은 반복문을 돌리면 돌릴수록 최적화된 값이다 ! 과정을 반복하면서 얻을 수 있는 떡의 길이 합이 필요한 떡의 길이보다 크거나 같을 떄마다 기록. (M보다 크더라도 답의 범위에 들어가잖아!!)
떡볶이 떡 만들기 소스 코드
#떡볶이 떡 만들기 답안 코드!
# from re import A
# import sys
# sys.stdin = open("input.text", "rt")
N, M = map(int, input().split()) #떡의 개수, 요청한 떡의 길이
array = list(map(int, input().split())) #떡의 개별 높이
#이진탐색을 위한 시작점과 끝점 설정
start = 0
end = max(array) #가장 긴 떡의 길이를 끝점으로 설정해야지!
#이진 탐색 수행(반복적)
while start <= end:
total = 0 #매번 이제 잘린 길이의 합과 M의 크기를 비교할꺼야!
mid = (start + end) //2 #중간값 인덱스
for x in array: #잘랐을 때의 떡의 양 계산
if x > mid: #절단기높이(mid) 보다 길어야 떡을 잘라서 저장할 수 있잖아
total += x - mid
#떡의 양이 부족한 경우 (더 많이 잘라야해) 왼쪽 부분 탐색
if total < M:
end = mid - 1 #더 많이 잘라야하니깐 끝점을 왼쪽으로 땡겨야지!
#떡의 양이 많은 경우 (적게 잘라야해) 오른쪽 부분 탐색
elif total >= M:
result = mid #최대한 덜 잘랐을 때가 정답이라 일단 여기서 값 저장해야해!!!!!!!!!!!!!!!
start = mid + 1 #더 적게 잘라야 하니까 시작점을 오른쪽으로 옮겨야지!
print(result) #정답 출력
#새로운 문제를 통해 다시 이진탐색을 알아보자
문제 해결 아이디어를 생각할 수 있어야해! → 생각의 흐름을 천천히 따라가
특정 값이 등장하는 첫 번째 위치와 마지막 위치를 찾아 위치 차이를 계산해 문제를 해결할 수 있다..???
즉!!! 이 문제는 처음 전체 탐색 범위에 대해서 이진 탐색을 2번 수행하여 하나의 이진 탐색은 첫 위치를 찾도록 만들고 다른 하나의 이진 탐색은 마지막 위치를 찾도록 만들어서 문제를 해결해야해!!!
이러한 코드는 이진 탐색을 직접 구현해서 작성할 수도 있고 표준 라이브러리를 이용해서도 구현할 수도 있어!!
이 소스코드는 표준 라이브러리를 사용해서 작성한 코드
#정렬된 배열에서 특정 수의 개수 구하기! 시간 복잡도 logN이여야함 --> 이진탐색 활용
from bisect import bisect_left, bisect_right
N, x = map(int, input().split())
array = list(map(int, input().split()))
#수열의 원소 중에서 값이 x인 원소의 개수를 출력 단 값이 x인 원소가 하나도 없다면 -1 출력
#시간복잡도 logN으로 알고리즘 설계해라 ---> 이진탐색으로 해야겠다
#중복 허용되는 리스트...
#값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수
def count_by_range(array, left_value, right_value):
right_index = bisect_right(array, right_value)
left_index = bisect_left(array, left_value)
return right_index - left_index #개수 반환!!
N, x = map(int, input().split())
array = list(map(int, input().split()))
#값이 [x, x] 범위에 있는 데이터의 개수 계산
count = count_by_range(array, x, x)
if count == 0: #존재 x
print(-1)
else: #값이 존재한다면
print(count)
