들어가는 글

알고리즘은 어떤 일을 하기 위한 명령의 집합.

이 책에서 선택한 알고리즘은 다른 코드보다 속도를 더 빠르게 하거나 흥미로운 문제를 풀기 위한 것이다.

• 1장에서 이진 탐색을 사용하여 어떻게 코드의 속도를 빠르게 할지 설명함
• 네비게이션은 6,7,8장에서 배울 그래프 알고리즘을 사용하여 목적지까지의 최단 경로를 계산한다
• 9장에서 배울 동적 프로그래밍을 사용하면 체커 게임을 하는 인공지능 알고리즘을 구현할 수 있다

성능에 대하여

여러가지 다른 알고리즘 간의 장단점을 배우게 되어 단순히 다른 자료구조를 사용하는 것만으로도 성능이 크게 달라질 수 있다.

이진 탐색

전화번호 부에서 K로 시작하는 사람의 이름을 찾는다고 가정해보자. 처음부터 한 장씩 넘겨가며 찾을 수도 있고 K니까 중간쯤에 있을 것으로 예상해서 책 중간부터 펼쳐 볼 수도 있을 것이다.

페이스북에 로그인한다고 치자. 아이디를 치고 로그인을 할 때 데이터베이스에서 아이디와 매치되는 비밀번호를 찾아야한다. K로 시작하는 아이디를 찾는다고 생각해보자. A부터 모든 데이터를 뒤지려면 시간이 오래 걸릴 것이다.

이러한 문제를 탐색(search)문제라고 한다. 위의 경우들은 이진 탐색(binary search)라고 하는 알고리즘을 사용하는 것이 좋다.

1과 100사이의 숫자를 하나 생각한다고 하자. 가능한 적은 횟수의 추측으로 숫자를 알아내야 한다.

1부터 차례대로 추측한다면 답이 100일 경우 100번의 추측을 해야한다. 이것을 단순 탐색(simple search)라고 한다.

좋은 방법은 범위의 중간 값을 부르는 것이다. 0과 100사이에 숫자인 50을 불러서 작다고 하면 그 다음엔 25를 부르는 식이다. 이것이 이진 탐색이다.

한 번에 아주 많은 숫자를 제거할 수 있기 때문에 어떤 숫자가 답이 되든지 최대 7번만에 정답을 맞출 수 있다.

n개의 원소를 가진 리스트의 경우 단순 탐색의 경우 n번이 될 수 있는 탐색 수를 log₂n로 크게 줄일 수 있다.

NOTE: 이진 탐색은 리스트의 원소들이 전화번호부처럼 정렬되어 있어야만 사용가능함.

이진 탐색 프로그램 만들기

binary_search 함수는 정렬된 배열 하나와 아이템 하나를 받는다. 아이템이 배열 안에 있으면 아이템 위치를 반환한다.

검색해야할 인덱스를 기억하기 위해서 처음과 끝의 인덱스를 초기화한다.

low = 0
high = len(list) - 1

가운데 원소 값 확인하기

mid = (low + high) // 2
guess = list[mid]

추측한 값이 작으면 low 값을 변경

if guess < item:
	low = mid + 1

크면 high값을 변경

if guess > item:
	high = mid - 1

전체 코드는 다음과 같다

def binary_search(list, item):
	low = 0
	high = len(list) - 1
	
	while low <= high:
		mid = (low + high) // 2
		guess = list[mid]
		
		if guess == item:
			return mid
		elif guess > item:
			high = mid - 1
		else:
			low = mid + 1
			
	return None

my_list = [1,3,5,7,9]

print(binary_search(my_list, 3)
print(binary_search(my_list, -1) 

실행 시간(running time)

빅오 표기법

빅오 표기법 (Big O notation)은 알고리즘이 얼마나 빠른지 표시하는 방법.

빅오 표기법을 사용하면 수행해야 할 일이 많아질 때 알고리즘에 걸리는 시간이 어떤 식으로 증가하는지를 알 수 있다.

예를 들어 이진 탐색은 크기가 n인 리스트를 확인하기 위해 log(n)번의 연산이 필요함.

O(log n)으로 표현한다

다음은 앞으로 자주 보게 될 다섯 개의 빅오 실행시간의 예이다.

• O(log n), 로그 시간 : 예) 이진 탐색
• O(n), 선형 시간 : 예) 단순 탐색
• O(n * log n) : 예) 퀵 정렬
• O(n²) : 예) 선택정렬
• O(n!): 예) 외판원 문제