이진 탐색

시간복잡도

이진 탐색을 진행할 경우 탐색해야할 데이터 수가 절반씩 줄어드므로 수행시간은 \(O(logN)\) 소요된다.
처음 이 말이 이해가 되지 않아 아래와 같이 좀더 풀어서 이해해 보았다.

이진 탐색을 하게되면 데이터 개수가 32개라고 할 때, 찾아야 하는 영역이 32 -> 16 -> 8 -> 4 -> 2 -> 1 형태로 줄어들게 된다. 여기서 수행시간이 \(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:
        binary_search(array, target, start, mid - 1)
    else:
        binary_search(array, target, mid + 1, end)

반복문으로 구현

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 = 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)

문제

부품찾기

p.197

내 풀이(재귀적 이진 탐색)

  n = int(input())
  data = list(map(int, input().split()))
  data.sort()

  target_num = int(input())
  target_list = list(map(int, input().split()))
  target_list.sort()

  def binary_search(array, target, start, end):
  if start > end:
      return 'no'

  mid = (start + end) // 2

  if array[mid] == target:
      return 'yes'

  elif array[mid] > target:
      return binary_search(array, target, start, mid - 1)

  else:
      return binary_search(array, target, mid + 1, end)

  for value in target_list:
  result = binary_search(data, value, 0, n - 1)
  print(result, end=' ')

주의해야 할 부분으로 sort() 함수를 사용하는데 본인은 처음에 data = data.sort() 와 같은 식으로 사용해서 None 타입이 반환되어 당황하였다. 리스트에 대한 sort()를 적용할 때는 위 코드와 같이 따로 객체를 할당받을 필요는 없다는 것을 명심하자.

계수정렬 풀이법: 같은 문제를 계수정렬로 푸는 방법도 있다.

  # 계수 정렬 풀이법
  # 들어오는 데이터가 모두 정수이고, 한번이라도 해당 부분의 값이 채워지면 별다른 처리없이 'yes'를 출력하면 되므로
  # 계수정렬로 풀 수 있다.

  coef_list = [0] * 100001

  n = int(input())
  data_list = list(map(int, input().split()))

  m = int(input())
  target_list = list(map(int, input().split()))
  print(target_list)

  for val in data_list:
  coef_list[val] += 1

  for val in target_list:
  if coef_list[val] != 0:
      print('yes', end=' ')
  else:
      print('no', end=' ')

python에서의 if value in list: 구문을 통해서 매우 쉽게 풀 수도 있다… 이걸 왜 생각 못했을까..

  n = int(input())
  data_list = list(map(int, input().split()))

  m = int(input())
  target_list = list(map(int, input().split()))

  for val in target_list:
  if val in data_list:
      print('yes', end=' ')
  else:
      print('No', end=' ')

떡볶이 떡 만들기

내 풀이

이진 탐색이 어색해서 제한시간안에 풀지는 못했지만, 문제 해설 힌트를 조금 본 뒤 재귀적으로 구현해보았다.

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

dduck_list = list(map(float, input().split()))

def bineary_search(array, target, start, end):
length = 0
    
if start > end:
    return None
        
mid = (start + end) // 2
    
for val in array:
    if val - mid > 0:    # 연산자 우선순위..? 상관없구먼..
    length += (val - mid)
    else:
    pass
    
if length == target:
    return mid

elif length > target:
    result = bineary_search(array, target, mid + 1, end)
    if result != None:
    return result
    else:
    return mid
        
else:
    result = bineary_search(array, target, start, mid - 1)
    if result != None:
    return result
    else:
    return mid
        
result = bineary_search(dduck_list, m, 0, max(dduck_list))

print(f"최종 값 {result}")

max 함수를 이용해서 search 영역을 결정하는 것과, 재귀함수에서 현재값을 저장하고 있는 부분을 구현하는것이 처음에 생각이 나지 않아 주어진 시간 안에 풀지 못하였다. 이 부분은 None을 반환하게 한 뒤 상위 함수에서(현재 실행중인 이진 탐색 함수를 호출했던 부모 함수) 현재 값(mid 값)을 반환하게 하는 식으로 구현해서 풀었다.

정답 코드 (반복문으로 해결)

저자에 따르면 재귀적으로 호출하는게 더 귀찮아서 반복문으로 풀었다고 한다.

# 떡의 개수(N)와 요청한 떡의 길이(M)을 입력받기
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    # 아하 이렇게 구현을 해줘야 종료될 때가 result 최대값이겠구나..
    start = mid + 1 

# 정답 출력
print(result)

추가적으로 아래 포스터에 이진 탐색 문제 풀이 및 고찰을 정리해놨다.

이진 탐색으로 백준 1756번 풀기

PREVIOUS경제