이진탐색(Binary Search), 순차탐색(Sequential Search) + Parametric Search

*이진탐색(Binary Search)

분할정복과 이진탐색

• 분할정복 알고리즘(Divide and Conquer)
  • 문제를 하나 또는 둘 이상으로 나눈다. (Divide)
  • 나눠진 문제가 충분히 작고, 해결이 가능하다면 해결하고, 그렇지 않다면 다시 나눈다.(conquer)
• 이진탐색
  • 리스트를 두 개의 서브리스트로 나눈다. (Divide)
  • (1) 검색할 숫자(search) > 중간 값 => 뒷 부분의 서브리스트에서 검색할 숫자를 찾는다.
  • (2) 검색할 숫자(search) < 중간 값 => 앞 부분의 서브리스트에서 검색할 숫자를 찾는다.

#코드1 : 재귀호출 사용

import random
 
def binary_search(data, search):
  if len(data) == 1 and search == data[0]:
    return True
  if len(data) == 1 and search != data[0]:
    return False
  if len(data) == 0:
    return False
  
  medium = len(data)//2 # 나누기 연산 후 소수점 이하의 수를 버리고 정수부분만 구함
  if search == data[medium]:
    return True
  else:
    if search > data[medium]:
      return binary_search(data[medium+1:], search)
    else:
      return binary_search(data[:medium], search)
 
  
 
data_list = random.sample(range(100), 10)
data_list.sort()
print(data_list)
getRes = binary_search(data_list, 66)
if getRes == True:
  print('YES')
else: 
  print('NO')

#코드2 : 재귀호출 사용안함

def binary_search2(data, search):
    testCnt = 0
    while True:
        if len(data) == 1 and search == data[0]:
            return True
        if len(data) == 1 and search != data[0]:
            return False
        if len(data) == 0:
            return False
        
        medium = len(data)//2 # 나누기 연산 후 소수점 이하의 수를 버리고 정수부분만 구함
        if search == data[medium]:
            return True
        else:
            if search > data[medium]:
                data = data[medium+1:]
            else:
                data = data[:medium]
 
  
 
data_list = [81, 82, 44, 16, 43, 1, 84, 51, 54, 66]
 
getRes = binary_search2(data_list, 66)
if getRes == True:
  print('YES')
else: 
  print('NO')

 

#시간복잡도 : O(logn)

*순차탐색(Sequential Search)

• 데이터가 담겨있는 리스트를 앞에서부터 하나씩 비교해서 원하는 데이터를 찾는 방법.

#코드

import random
 
def sequential_search(data, search):
  for i in range(len(data_list)):
    if data_list[i] == search:
      return True
  return False
 
 
data_list = random.sample(range(100), 10)
getRes = sequential_search(data_list, 66)
print(data_list)
if getRes == True:
  print('YES')
else:
  print('NO')

#시간복잡도 : O(n)

*파라메트릭 서치(Parametric Search)

• https://velog.io/@lake/%EC%9D%B4%EB%B6%84%ED%83%90%EC%83%89-%ED%8C%8C%EB%9D%BC%EB%A9%94%ED%8A%B8%EB%A6%AD-%EC%84%9C%EC%B9%98Parametric-Search

[이분탐색] 파라메트릭 서치(Parametric Search)

#코드

n, s = map(int, input().split())
getInfo = list(map(int, input().split()))
 
# 구간 : 1 2 3 4 5 6 7 8 9 10 11 12...
#        x x x o o o o o o o o o o 
#        s(초기값 : 1)......................e(초기값 : n)
 
start = 1 # start는 무조건 X를 가리킴
end = n   # end는 무조건 O를 가리킴
 
 
def check(interval):
  # 구간의 길이 interval만큼 정했을 때, 
  # 그 합이 S이상인 경우가 있는가?
  # 있으면 True, 아니면 False
  # 2 1 8 1 3 7 2 6 3
  # - - -
  #   - - -
  # 2 1 8 에서 다음으로 넘어가려면 
  # 0번째 2를 빼주고, 3번째 1을 더해준다
  sum = 0
  # 1. 앞 세개의 합
  for i in range(interval):
    sum += getInfo[i]
  if sum >= s: 
    return True
  # 2. 다음으로 이동
  for i in range(n-interval):
    sum = sum - getInfo[i] + getInfo[i+interval]
    if sum >= s: return True
  return False
  
  
if check(1): print(1) #구간 1이 될 경우... 1출력
if check(n) == False: print('-1') #구간 마지막이 안될 경우 -1출력
 
while start + 1 < end: # start와 end가 붙으면 끝
  mid = (start + end) // 2
  if check(mid): end = mid
  else: start = mid
  
print(end)
    

**입력 

9 14
2 1 8 1 3 7 2 6 3

** 출력

3

 

#코드

import sys
 
def check(interval):
  global getInfo
  # 구간의 길이 interval만큼 정했을 때, 그 합이 S이상인 경우가 있는가?
  # 있으면 True, 없으면 False
  # 9 14
  # 2 1 8 1 3 7  2 6 3
  
  # 1. 앞의 세 개(구간의 길이 만큼 즉 interval)의 숫자를 더해준다.
  sum = 0
  for i in range(interval): 
    sum += getInfo[i]
  if sum >= s: return True # 앞의 구간의 합이 이미 s를 넘어버린 경우
  
  # 2. 1 8 1 부터 시작해서 구간을 돌아야한다. 6번 돌 수 있다.
  #    9 - 3 = 6 -> n - interval 
  for i in range(n-interval):
    # ..2 1 8 1 ..구간에서 1 8 1 의 합은
    # 맨 앞구간의 합(sum)에서 앞의 2를 빼고 뒤의 1을 더해준 것과 같다.
    sum = sum - getInfo[i] + getInfo[i+interval] 
    if sum >= s: return True
  
  return False
  
 
if __name__ == "__main__":
  n, s    = map(int, input().split())
  getInfo = list(map(int, input().split()))
  
  # 구간
  # 1 2 3 4 5 6 7 8 9 10 11 12, ..
  # s                       e
  start = 1 # start는 무조건 X를 가리킴
  end   = n # end는 무조건 O를 가리킴
  flag  = True 
  
  if check(1): # 구간 1이 가능하다면 1이 답.
    print(1)
    flag = False
  
  if not check(n): # 구간 n을 해봤을 경우에 안된다면 가능한 방법이 없다.
    print(-1)
    flag = False
  
  
  if flag:
    # 1 2 3 4 5 ... 10 11 12 ...
    # x x x x x ... x  O  O ...
    #               s  e    => start+1 == end 끝났다는 의미
    while start+1 < end:
      mid = (start+end)//2 
      if check(mid): # mid의 값이 O라는 뜻 즉 end가 움직여야된다.
        end = mid
      else:
        start = mid
    print(end)
 
    # 2 1 8 1 3 7 2 6 3
    # s               e
    # 9 - 1 = 8