[코딩테스트 스터디] 5주차 - 이분탐색

이분탐색: 반으로 쪼개면서 탐색하기

 이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 이진 탐색은 위치를 나타내는 변수 3개를 사용하는데 탐색하고자 하는 범위의 시작점, 끝점 그리고 중간점이다. 

- 평균 시간 복잡도: O(logN)

 

* 재귀 함수로 구현한 이진 탐색 소스코드

# 이진 탐색 소스코드 구현 (재귀 함수)
def binary_search(array, target, start, end):
    if start > end:
        return None
    mid = (start + end) // 2
    # 찾은 경우 중간점 인덱스 반환
    if array[mid] == target:
        return mid
    # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
    elif array[mid] > target:
        return binary_search(array, target, start, mid - 1)
    # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
    else:
        return binary_search(array, target, mid + 1, end)

# n(원소의 개수)과 target(찾고자 하는 값)을 입력 받기
n, target = list(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:
            end = mid - 1
        # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
        else:
            start = mid + 1
    return None

# n(원소의 개수)과 target(찾고자 하는 값)을 입력 받기
n, target = list(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)

 

 

#실전2 부품찾기

n = int(input())
n_product = list(map(int, input().split()))
n_product.sort()
m = int(input())
m_product = list(map(int, input().split()))

for item in m_product:
    start = 0
    end = n - 1
    flag = True

    while start <= end:
        mid = (start + end) // 2
        if n_product[mid] == item:
            print('yes', end=' ')
            flag = False
            break
        elif n_product[mid] > item:
            end = mid - 1
        else:
            start = mid + 1
    if flag == True:
        print('no', end=' ')

# 실전3 떡볶이 떡 만들기

n, m = map(int, input().split())
array = list(map(int, input().split()))

# 이진탐색 시작점과 끝점
start = 0
end = max(array)

# 이진 탐색
result = 0
while start <= end:
    total = 0
    mid = (start + end) // 2
    for x in array:
        #잘랐을 때 떡의 양 계산
        if x > mid:
            total += x - mid
        # 떡의 양이 부족한 경우 더 많이 자르기(왼쪽 부분 탐색)
        if total < m:
            end = mid - 1
        # 떡의 양이 충분한 경우 덜 자르기(오른쪽 부분 탐색)
        else:
            result = mid # 최대한 덜 잘랐을 때가 정답
            start = mid + 1

print(result)
Footer

 

#27 정렬된 배열에서 특정 수의 개수 구하기

n, x = map(int, input().split()) # 원소의 개수, 찾는 숫자
array = list(map(int, input().split())) # 수열

# 해당 숫자가 등장한 첫 번째 인덱스
def binary_search_first(array, target, start, end):
  if start > end: # 타겟이 리스트 안에 없을 때
    return None
  mid = (start + end) // 2 # 중간점
  # 해당 값을 가지는(array[mid] == target) 원소 중에 가장 왼쪽에 있는 경우에만 반환
  # 가장 왼쪽 인덱스(mid == 0)이거나, 바로 앞의 값이랑 같지 않을 때(target > array[mid-1])
  if array[mid] == target and (mid == 0 or target > array[mid-1]):
    return mid
  elif array[mid] >= target: # 타겟이 중간점보다 작거나, 같아도 가장 왼쪽은 아닐 때
    return binary_search_first(array, target, start, mid-1)
  elif array[mid] < target: # 타겟이 중간점보다 클 때
    return binary_search_first(array, target, mid+1, end)

# 해당 숫자가 등장한 마지막 인덱스
def binary_search_last(array, target, start, end):
  if start > end:
    return None
  mid = (start + end) // 2
  # 해당 값을 가지는(array[mid] == target) 원소 중에 가장 오른쪽에 있는 경우에만 반환
  # 가장 오른쪽 인덱스(mid == n-1)이거나, 바로 뒤의 값이랑 같지 않을 때(target < array[mid+1])
  if array[mid] == target and (mid == n-1 or target < array[mid+1]):
    return mid
  elif array[mid] > target: # 타겟이 중간점보다 작을 때
    return binary_search_last(array, target, start, mid-1)
  elif array[mid] <= target: # 타겟이 중간점보다 크거나, 같아도 가장 오른쪽은 아닐 때
    return binary_search_last(array, target, mid+1, end)

# 등장한 개수 세는 함수
def count_by_value(array, x):
  n = len(array)
  first = binary_search_first(array, x, 0, n-1)
  if first == None: # 원소가 없다면 -1 출력
    return -1
  last = binary_search_last(array, x, 0, n-1)

  return last - first + 1

print(count_by_value(array, x))
Footer
© 2022 GitHub, Inc.
Footer navigation
Terms

 

#28 고정점 찾기

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> points;

int main(){
    int n;
    
    cin >> n;
    
    for(int i = 0; i < n; i++){
        int a;
        
        cin >> a;
        
        points.push_back(a);
    }
    
    int left = 0, right = n-1;
    
    while(left <= right){
        int mid = (left + right) / 2;
        
        if(points[mid] == mid){
            cout << mid;
            return 0;
        }
        
        if(points[mid] > mid ){
            right = mid - 1;
        }
        else{
            left = mid + 1;
        }
    }
    
    cout << -1;
}

 

#29 공유기 설치

n,c = map(int,input().split())

house = []
for _ in range(n):
    x = int(input())
    house.append(x)

house.sort()

# 좌표값의 최소값
start = 1
# 가장 높은 좌표와 가장 낮은 좌표의 차이
end = house[-1] - house[0]

result = 0

while (start <= end):
    mid = (start+end)//2 # gap
    old = house[0]
    count = 1

    for i in range(1, len(house)):
        if house[i] >= old+mid: # gap 이상
            count+=1
            old = house[i]
    
    if count >=c:
        start = mid + 1
        result = mid
    else:
        end = mid - 1

print(result)