[이것이 취업을 위한 코딩 테스트다 with 파이썬] (한빛미디어, 나동빈) Chapter7. 이진 탐색

 포스팅 개요

 '혹시나 책에 있을 모든 실수와 오류는 온전히 제 책임이며, 책에 실린 좋은 아이디어와 표현은 모두 리뷰어님들의 조언 덕분입니다. 정말 고맙습니다.'라는 지은이의 글은 나동빈 저자님의 인품을 느낄 수 있는 한 줄이었습니다.

 

 저도 저런 마인드를 가진 사람이 되겠다고 다짐하며 책과의 여정을 떠나보겠습니다.

 

이것이 취업을 위한 코딩 테스트다

---

 포스팅 본문

  이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾아낸다. 시간 복잡도가 O(logN)이다.

 

   이진 탐색은 코딩 테스트에서 단골로 나오는 문제이니 암기를 추천한다. 처리해야 할 데이터의 개수나 값이 1000만 단위 이상으로 넘어가면 이진 탐색과 같은 O(logN)의 속도를 내야 하는 알고리즘이 필요하다.

 

 본 코드는 모두 제 Github에 올려두었습니다. (https://github.com/herjh0405/Coding_Test)

---

7-1. 순차 탐색 소스코드

 순차탐색은 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다.

데이터 정렬 여부와 상관없이 가장 앞에 있는 원소부터 확인해야 하기에 시간 복잡도는 O(N)이다.

def sequential_search(n, target, array) :
     # 각 원소를 하나씩 확인하며
     for i in range(n) :
          # 현재의 원소가 찾고자 하는 원소와 동일한 경우
          if array[i] == target :
               return i+1 # 현재의 위치 반환(인덱스는 0부터 시작하므로 1 더하기)

print('생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요.')
input_data = input().split() # 5 Dongbin
n = int(input_data[0]) # 원소의 개수
target = input_data[1] # 찾고자 하는 문자열

print('앞서 적은 원소 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다.')
array = input().split() # Hanul Jonggu Dongbin Taeil Sangwook

# 순차 탐색 수행 결과 출력
print(sequential_search(n, target, array)) # 2

---

7-2. 재귀 함수로 구현한 이진 탐색 소스코드

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)

 여러모로 유용하니까 꼭 기억해두자.

---

7-3. 반복문으로 구현한 이진 탐색 소스코드

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)

 재귀 함수 방식과 반복문 방식 어느걸로 구현해도 문제가 없다. 본인에게 맞는 코드를 외우면 된다.

---

7-4. 한 줄 입력받아 출력하는 소스코드

# 입력 데이터가 많은 문제는 sys 라이브러리의 readline() 함수를 이용하면 시간 초과를 피할 수 있다
import sys
# 하나의 문자열 데이터 입력받기
input_data = sys.stdin.readline().rstrip() # readline사용시 rstrip사용 필수적, 입력 엔터를 줄 바꿈 기호로 인식하는 데 그것을 방지해줌

# 입력받은 문자열 그대로 출력
print(input_data)

 입력 데이터가 많은 경우 input으로는 시간 초과가 발생할 때가 있다. 실제로 내 경험에 비추어봤을 때도 input의 문제였던 적도 있는 듯하다. 여러 줄의 데이터를 입력받아야 할 때, sys 라이브러리의 readline을 꼭 기억하자.

---

7-5. 부품 찾기

 동빈이네 전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다. 어느 날 손님이 M개 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 동빈이를 때를 놓치지 않고 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다.

 이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자.

Ex)

가게의 부품이 총 5개일 때 부품 번호가 다음과 같다.

N=5, [8, 3, 7, 9, 2]

손님은 총 3개의 부품이 있는지 확인 요청했는데 부품 번호는 다음과 같다.

M=3, [5, 7, 9]

이때 손님이 요청한 부품 번호의 순서대로 부품을 확인해 부품이 있으면 yes를, 없으면 no를 출력한다. 구분은 공백으로 한다.

 

 부품 찾기 문제를 3가지의 풀이 방법으로 해결하겠다. 이러한 풀이법이 있다는 것을 알고 자신에게 맞는 방법을 연습하기를 추천한다.

이진 탐색

import sys
# 이진 탐색 코드 작성
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 가게의 부품 수 입력
n = int(sys.stdin.readline().rstrip())
# 가게의 부품 번호 입력
array = list(map(int, sys.stdin.readline().split()))
array.sort() # 이진 탐색에 sort
# 손님이 요청한 부품 개수
m = int(sys.stdin.readline().rstrip())
vi_list = list(map(int, sys.stdin.readline().split()))

for vi in vi_list :
     result = binary_search(array, vi, 0, n-1)
     if result == None :
          print('no', end=' ')
     else :
          print('yes', end=' ')

계수 정렬

 이진 탐색 말고도 계수 정렬의 개념을 이용하여 문제를 풀 수도 있다.

모든 원소의 번호를 포함할 수 있는 크기의 리스트를 만든 뒤에, 리스트의 인덱스에 직접 접근하여 특정한 번호의 부품이 매장에 존재하는지 확인.

import sys
# 가게의 부품 개수를 입력받기
n = int(input())
array = [0] * 1000000

# 가게에 있는 전체 부품 번호를 입력받아서 기록
for i in input().split() :
     array[int(i)] = 1

# 손님이 확인 요청한 부품의 개수를 입력받기
m = int(input())
# 손님이 확인 요청한 전체 부품 번호를 공백으로 구분하여 입력
vi_list = list(map(int, sys.stdin.readline().split()))

for vi in vi_list :
     if array[vi] == 1 :
          print('yes', end=' ')
     else :
          print('no', end=' ')

 내가 앞으로도 자주 써야할 방식의 코딩이라는 느낌이 든다. 기억해두자.

Set

import sys
n = int(input())
array = set(map(int, sys.stdin.readline().split()))

m = int(input())
vi_list = list(map(int, sys.stdin.readline().split()))

for vi in vi_list : 
     if vi in array :
          print('yes', end = ' ')
     else :
          print('no', end = ' ')

 되게 쉽게 해결됐다. 떠올린다면 가장 간단한 방법이겠지만, 어느 형태의 문제에나 적용되지는 않기에 이런 풀이도 있다는 것을 기억하고 이진 탐색 위주로 공부하는 것이 좋아 보인다.

---

7-8. 떡볶이 떡 만들기

 문제의 내용이 너무 길어서 간단하게만 소개하겠다. N개의 개수의 떡이 각각의 길이를 가지고 있음. H라는 높이를 가진 기계로 잘랐을 때 남은 떡들의 길이를 손님이 가져간다. 원하는 길이를 가져가는 조건에서 가장 큰 H의 높이는? 

import sys
# 떡의 개수(N)과 요청한 떡의 길이(M)을 입력받기
n, m = list(map(int, sys.stdin.readline().split()))
# 각 떡의 개별 높이 정보를 입력받기
array = list(map(int, sys.stdin.readline().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)

 전형적인 이진 탐색 문제이자, 파라메트릭 서치 유형의 문제이다.

파라메트릭 서치는 최적화 문제를 결정 문제로 바꾸어 해결하는 기법이다. '원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제'에 주로 사용.

 

 문제의 풀이는 은근 간단하다. 적절한 높이를 찾을 때까지 절단기의 높이 H를 반복해서 조정한다.

현재 이 높이로 자르면 조건을 만족할 수 있는가?를 확인한 뒤에 조건의 만족 여부(Yes or No)에 따라서 탐색 범위를 좁혀서 해결 가능. 범위를 좁힐 때 이진 탐색의 원리를 사용. 절단기의 높이는 1부터 10억까지의 정수 중 하나이다. 큰 수를 보면 당연하게 이진 탐색을 떠올려야 한다.

---

 Chapter들을 진행할수록 나에게 필요했던 코드들에 대해 배워가는 기분이다. 남은 Chapter들은 난도가 더 높은 편인데 천천히 공부해보도록 하겠다.

 

 Chapter8. 다이나믹 프로그래밍에서 뵙겠습니다. :)