이진 탐색

1. 백준 1920 수찾기

탐색 데이터수 10만개 X 10만으로 O(N) 연산시 시간초과 발생하여 set 자료형 또는 이진탐색으로 풀이

1. set 자료형 사용

N = int(input())
number_N = set(map(int,input().split()))
M = int(input())
number_M = list(map(int,input().split()))


for m in number_M:
    if m in number_N:
        print(1)
    else :
        print(0)

2. 이진탐색 사용 // 재귀, while문 사용

N = int(input())
number_N = list(map(int, input().split()))
number_N.sort()
M = int(input())
number_M = list(map(int, input().split()))

print(number_N)


def binary_search_while(arr, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        if target == arr[mid]:
            return 1
        elif target < arr[mid]:
            end = mid - 1
        elif target > arr[mid]:
            start = mid + 1
    return 0

def binary_search_recur(arr, target, start, end):
    if start > end:
        return -1
    else :
        mid = (start + end) // 2
        if target == arr[mid]:
            return mid
        elif target < arr[mid]:
            return binary_search_recur(arr, target, start, mid-1)
        elif target > arr[mid]:
            return binary_search_recur(arr, target, mid+1, end)
for i in number_M:
    print(binary_search_while(number_N, i, 0, len(number_N) - 1))
    print(binary_search_recur(number_N, i, 0, len(number_N) - 1))

 

2. 백준 10816 수 찾기 2

딕셔너리 사용하여 해결,

이진탐색시 같은 숫자들을 다시 세는 과정에서 시간 초과발생

 

import sys

N = int(sys.stdin.readline())
numbers_N = list(map(int, sys.stdin.readline().split()))
numbers_N.sort()

M = int(sys.stdin.readline())
numbers_M = list(map(int, sys.stdin.readline().split()))

## dict로 풀이
numbers_N_dict = dict()
for x in numbers_N:
    if x in numbers_N_dict:
        numbers_N_dict[x] += 1
    else:
        numbers_N_dict[x] = 1

for m in numbers_M:
    if m in numbers_N_dict:
        print(str(numbers_N_dict[m]), end=' ')
    else:
        print('0', end=' ')
        
    # binary search로 풀이 -> 시간초과
    # binary_search(numbers_N, m, 0, len(numbers_N) - 1)
    # print(cnt, end=' ')
    
# 이진탐색시 시간초과
def binary_search(arr, target, start, end):
    global cnt
    if start > end:
        return -1
    else:
        mid = (start + end) // 2
        if target == arr[mid]:
            cnt += 1
            temp = mid - 1
            while 0 <= temp and arr[temp] == target:
                cnt += 1
                temp -= 1
            temp = mid + 1
            while temp <= len(numbers_N) - 1 and arr[temp] == target:
                cnt += 1
                temp += 1
            return
        elif target <= arr[mid]:

            return binary_search(arr, target, start, mid - 1)
        else:
            return binary_search(arr, target, mid + 1, end)

3. 백준 1654 랜선 자르기

파라메트릭 서치 : 최적화 문제를 이진탐색 문제로 변환

+1 또는 -1을 더해가면서 탐색하는하지 않고 이진 탐색으로 변환하여 풀이 

import sys
K, N = map(int, sys.stdin.readline().split())
wire = list(map(int, sys.stdin.readlines()))

start = 1
end = max(wire)
max = 0
while True:
    if start > end:
        break
    mid = (start + end) // 2
    line = 0
    for i in range(K):
        line += wire[i] // mid
    if line >= N:
        start = mid + 1
    else:
        end = mid - 1

print(end) #mid 도 동일

 

 

 

https://4legs-study.tistory.com/106

최장 증가 수열 (LIS, Longest Increasing Subsequence)