코드잇의 알고리즘의 정석 수업을 수강하고 정리한 글입니다.
1. 하나의 문제를 해결하는 여러 가지 방법
로미오와 줄리엣 책을 찾고자 한다. 어떤 방법이 좋을까?
- 왼쪽부터 오른쪽 까지 하나하나 꺼내보며 "로미오와 줄리엣"인지 확인한다.
- 책이 알파벳 순으로 정리되어있다면?
- 중간 지점의 책을 고른다.
- 찾는 책의 제목과 고른 책 제목의 첫 알파벳을 확인한다.
- 좌, 우의 전체 책을 제외한다.
- 원하는 책을 찾을 때 까지 반복한다.
다양한 방법들을 고민하고 어떤 방법이 좋을지 분석하는것이 알고리즘 공부이다.
2. 선형 탐색과 이진 탐색
우리는 도서관의 책을 찾는 법을 살펴보았다. 이러한 문제를 프로그래밍에서는 "탐색 문제"라고 한다.
탐색 : 저장된 정보들 중에서 원하는 값을 찾는 것
탐색 알고리즘
선형 탐색 알고리즘과 이진 탐색 알고리즘을 이용해 탐색을 수행해보자.
선형 탐색 알고리즘(linear search algorithm): 하나씩 전부 보며 찾는다.
- 2부터 순서대로 데이터를 확인한다.
- 29를 발견하면 더이상 볼 필요없이 탐색을 끝낸다.
이진 탐색 알고리즘(binary search algorithm): 중간값을 확인하고 반씩 제외하며 찾는다.
- 중간값을 확인한다. 확인해보니 19이다.
- 찾고자하는 29는 19보다 크므로, 19 이하의 숫자는 제외할 수 있다.
- 남은 숫자 중에서 또다시 중간 값을 확인한다. 확인해보니 37이다.
- 찾고자하는 29는 37보다 작으므로, 37이상의 숫자는 제외할 수 있다.
- 남은 숫자 중에 중간값을 확인해보니 29이다. 우리가 원하는 값을 찾았다.
우리는 같은 문제를 풀었는데 두가지 해결책을 찾아내었다. 어떤 방법이 효율적일지 고민해보자.
3. 선형 탐색 구현해보기
'선형 탐색(Linear Search)' 알고리즘을 사용해서 어떤 원소가 리스트안에 포함되어있는지 확인하라.
파라미터로 입력되는 element, some_list는 탐색할 값과 검색할 리스트이다.
element를 찾으면 그 위치(인덱스)를 리턴하고 존재하지 않으면 None을 리턴하라.
# 구현 코드
def linear_search(element, some_list):
pass
print(linear_search(2, [2, 3, 5, 7, 11]))
print(linear_search(0, [2, 3, 5, 7, 11]))
print(linear_search(5, [2, 3, 5, 7, 11]))
print(linear_search(3, [2, 3, 5, 7, 11]))
print(linear_search(11, [2, 3, 5, 7, 11]))# 실행 결과
0
None
2
1
4나의 풀이
# 구현 코드
def linear_search(element, some_list):
for i in range(len(some_list)):
if some_list[i] == element:
return i
print(linear_search(2, [2, 3, 5, 7, 11]))
print(linear_search(0, [2, 3, 5, 7, 11]))
print(linear_search(5, [2, 3, 5, 7, 11]))
print(linear_search(3, [2, 3, 5, 7, 11]))
print(linear_search(11, [2, 3, 5, 7, 11]))for문을 이용해서 some_list로부터 element를 탐색하도록 하였고, 함수가 끝났을 때 return을 명시해주지 않으면 None을 반환하므로 return은 따로 명시하지 않았다.
4. 이진 탐색 구현해보기
'이진 탐색(Binary Search)' 알고리즘을 사용해서 어떤 원소가 리스트 안에 포함되었는지 확인하라.
이진 탐색은 정렬된 리스트를 전제로 한다. (그래야만 적용이 가능하다.)
element를 찾으면 그 위치(인덱스)를 리턴하고 존재하지 않으면 None을 리턴하라.
# 구현 코드
def binary_search(element, some_list):
pass
print(binary_search(2, [2, 3, 5, 7, 11]))
print(binary_search(0, [2, 3, 5, 7, 11]))
print(binary_search(5, [2, 3, 5, 7, 11]))
print(binary_search(3, [2, 3, 5, 7, 11]))
print(binary_search(11, [2, 3, 5, 7, 11]))# 실행 결과
0
None
2
1
4나의 풀이
def binary_search(element, some_list):
left = 0
right = len(some_list)-1
while True:
if left>right: # 시작, 끝 인덱스가 역전되면 None을 반환
return None
center = (left + right) // 2 # 중간값에 대한 인덱스 구하기
if some_list[center] == element: # element를 찾았으면 반환
return center
if element > some_list[center]: # 중간값보다 element가 크면 왼쪽은 제외
left = center + 1
else: # 중간값보다 element가 작으면 오른쪽은 제외
right = center - 1
print(binary_search(2, [2, 3, 5, 7, 11]))
print(binary_search(0, [2, 3, 5, 7, 11]))
print(binary_search(5, [2, 3, 5, 7, 11]))
print(binary_search(3, [2, 3, 5, 7, 11]))
print(binary_search(11, [2, 3, 5, 7, 11]))정답
def binary_search(element, some_list):
start_index = 0
end_index = len(some_list) - 1
while start_index <= end_index: # while문의 반복 조건으로 시작 인덱스와 마지막 인덱스가 역전되지 않았을 때만 동작
midpoint = (start_index + end_index) // 2
if some_list[midpoint] == element:
return midpoint
elif some_list[midpoint] > element:
end_index = midpoint - 1
else:
start_index = midpoint + 1
return None
print(binary_search(2, [2, 3, 5, 7, 11]))
print(binary_search(0, [2, 3, 5, 7, 11]))
print(binary_search(5, [2, 3, 5, 7, 11]))
print(binary_search(3, [2, 3, 5, 7, 11]))
print(binary_search(11, [2, 3, 5, 7, 11]))-> while문의 반복 조건으로 시작 인덱스와 마지막 인덱스가 역전되지 않았을 때만 동작하도록 하였다. 이를 통해 반복문 내의 코드가 줄었다.
