순차탐색 (Sequential Search)

개념

: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 알고리즘

• 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용
• 데이터가 아무리 많아도 시간만 충분하면 항상 원하는 데이터를 찾을 수 있음

동작원리

소스코드

## 순차탐색
def seq_search(n, target, array):
	for i in range(n):
    	if array[i] == target:
        	return i+1 # 인덱스는 0부터 시작하므로 1 더함
            
n, target = input().split()
array = list(input().split())

print(seq_search(n, target, array))

5 Apple
Banana Melon Apple Cherry Orange

3

시간복잡도 : $O(N)$

데이터 정렬 여부와 상관없이 가장 앞에 있는 원소부터 하나씩 확인해야 한다. 따라서 데이터의 개수가 $N$개 일 때 최대 $N$번의 비교 연산이 필요하므로 최악의 경우 시간복잡도는 $O(N)$이다.

이진탐색 (Binary Search)

개념

: 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 알고리즘

• 배열 내부의 데이터가 정렬되어 있어야만 사용 가능
• 중간점을 찾을 때는 인덱스에 대해서 계산하여 찾아야 함
• 중간점이 실수일 때는 소수점 이하를 버림

동작원리

1. 인덱스에 대하여 시작점, 끝점, 중간점을 계산한다.
2. 만약 중간점의 데이터가 타겟값보다 크면 중간점 이후의 데이터는 확인할 필요가 없다. 따라서 끝점을 중간점-1로 옮긴다.
3. 만약 중간점의 데이터가 타겟값보다 작으면 중간점 이전의 데이터는 확인할 필요가 없다. 따라서 시작점을 중간점+1로 옮긴다.
4. 위의 2, 3번 과정을 중간점이 타겟값과 일치할 때 까지 반복한다.

소스코드

1) 재귀함수로 구현

## 이진탐색 - (1) 재귀함수
def bin_search(array, target, start, end):
	mid = (start + end)//2
    
    if start > end:
    	return None
        
    if array[mid] == target:
    	return mid
        
    elif array[mid] > target:
    	return bin_search(array, target, start, mid-1):
        
    else:
    	return bin_search(array, target, mid+1, end):
        
n, target = map(int, input().split())
array = list(map(int, input().split()))

result = bin_search(array, target, 0, n-1)

if result == None:
	print("원소가 존재하지 않습니다.")
else:
	print(result+1)

10 7
1 3 5 7 9 11 13 15 17 19

4

2) 반복문으로 구현

## 이진탐색 - (2) 반복문
def bin_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 = bin_search(array, target, 0, n-1)

if result == None:
	print("원소가 존재하지 않습니다.")
else:
	print(result+1)

시간복잡도 : $O(logN)$

한 번 확인할 때마다 탐색 범위가 절반씩 줄어들기 때문에 $O(logN)$의 시간복잡도를 갖는다.

---

실습

실전문제 1. 부품 찾기

한 전자 매장에는 각각 정수 형태의 고유한 번호를 가지고 있는 N개의 부품이 있다. 어느날 손님이 M개 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 직원은 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다. 이때 손님이 요청한 부품 번호의 순서대로 부품을 확인하여, 가게 안에 부품이 모두 있다면 yes를, 없으면 no를 출력하는 프로그램을 작성하시오.

## 내 풀이
n = int(input()) # 매장에 있는 부품 개수
n_list = list(map(int, input().split())) # 매장에 있는 부품의 번호
m = int(input()) # 손님이 문의한 부품 종류의 개수
m_list = list(map(int, input().split())) # 손님이 문의한 부품의 번호

n_list = sorted(n_list) # 오름차순 정렬
    
def bin_search(array, target, start, end):
    mid = (start + end) // 2 # 중간점 설정
    
    if start > end: # 시작 인덱스가 끝 인덱스보다 큰 경우
        return None # 애초에 성립 불가한 케이스이므로 None 반환
    
    else: # 그 외의 경우
    	# 중간점과 타겟값이 일치하는 경우
        if array[mid] == target: 
            return mid
        
        # 중간점이 타겟값보다 작은 경우 : 끝점을 중간점-1 으로 변경
        elif array[mid] > target: 
            return bin_search(array, target, start, mid-1)
    	# 중간점이 타겟값보다 큰 경우 : 시작점을 중간점+1 으로 변경
        else:
            return bin_search(array, target, mid+1, end)
    

for i in m_list:
    if bin_search(n_list, i, 0, n-1) == None: # 부품이 없는 경우
        print("no", end = ' ')
    else: # 부품을 찾은 경우
        print("yes", end = ' ')

5
8 3 7 9 2
3
5 7 9

no yes yes

실전문제 2. 떡볶이 떡 만들기

떡집에서 파는 떡볶이 떡은 길이가 일정하지 않아, 절단기로 잘라서 한 봉지 안에 들어가는 떡의 총 길이를 맞춰준다. 절단기에 높이 (H)를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다.
예를 들어 높이가 19, 14, 10, 17cm인 떡이 나란히 있고 H를 15cm로 지정하면 절단 후 떡의 높이는 15, 14, 10, 15cm가 될 것이다. 잘린 떡의 길이는 차례대로 4, 0, 0, 2cm가 되어 손님이 가져가는 떡의 길이는 총 6cm이다.
손님이 왔을 때 요청한 총 길이가 M이라면, 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

💡 해결 아이디어

## 내 풀이
n, m = map(int, input().split())
n_list = list(map(int, input().split()))

n_list = sorted(n_list)

def bin_cutting(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2 # 중간점
        s = 0 # 잘린 떡 길이의 총합
        
        for i in n_list:
            if i <= mid: # i번째 떡이 중간점보다 짧은 경우
                s += 0 # s에 0 누적
            else: # i번째 떡이 중간점보다 긴 경우
                s += (i-mid) # s에 잘린 떡의 길이 누적
        
        
        if s == target: # 잘린 떡 길이의 총합이 요청한 길이와 같은 경우
            return mid # 중간점 반환
        
        elif s > target: # 잘린 떡 길이의 총합이 요청한 길이보다 긴 경우
            # 더 길게 잘라야 하므로 시작점을 중간점+1 으로 이동
            return bin_cutting(array, target, mid+1, end)
        
        else: # 잘린 떡 길이의 총합이 요청한 길이보다 짧은 경우
            # 더 짧게 잘라야 하므로 끝점을 중간점-1 으로 이동
            return bin_cutting(array, target, start, mid-1)
    
    
    # 그 외의 경우 None 반환
    return None

# 인덱스에 대해 계산하는 것이 아니라 떡길이 자체에 대해 중간점, 시작점, 끝점 계산
print(bin_cutting(n_list, m, min(n_list), max(n_list)))

4 6
19 15 10 17

15

교재의 해설에 따르면, 이 문제는 이진 탐색 문제이자 '파라메트릭 서치 문제'로 분류된다. 파라메트릭 서치 문제 유형은 이진 탐색을 재귀적으로 구현하지 않고 반복문을 이용해 구현하면 더 간결하게 문제를 풀 수 있다.

모범답안의 소스코드를 살펴보자.

## 모범답안
n, m = map(int, input().split())
n_list = list(map(int, input().split()))

start = 0
end = max(n_list)

result = 0 # 절단기의 높이 (0으로 초기화)

while start <= end:
	mid = (start+end) // 2
    total = 0 # 절단기 높이 H만큼 자른 후 남은 떡 길이의 총합
	
    # 잘랐을 때의 떡 양 계산
	for x in n_list:
    	if x > mid:
        	total += (x - mid)
    
    if total < m : # 요청한 떡의 길이보다 적은 경우
    	end = mid - 1 # 더 짧게 자르기(끝점을 중간점-1 으로 이동)

	else: # 요청한 떡의 길이보다 많은 경우
    	result = mid # 최대한 덜 잘랐을 때가 정답이므로 여기서 result 기록
        start = mid + 1 # 더 길게 자르기(시작점을 중간점+1 으로 이동)
        
print(result) # 정답출력

4 6
19 15 10 17

15

📌 결정 알고리즘

답을 정하고 이 답이 유효한지 확인해 가면서 더 좋은 답을 찾아가는 방식

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

최적화 문제( = 원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제)를 풀기 위해 결정 알고리즘을 사용하여 해결하는 기법으로, 매개변수(입력한 배열, 구하고자 하는 값)를 활용한 탐색 기법

🔗 References

• 이것이 취업을 위한 코딩 테스트다 with 파이썬