탐색 알고리즘 - 1. 선형 탐색 / 2. 이진 탐색 알고리즘
이글은 코드잇
의 알고리즘 강의와 오픈소스
들을 참고하여 정리한 글입니다^^
알고리즘 공부 방법
하나의 문제를 해결하는 방법에는 여러가지가 있다. 그 방법들을 찾아서 가장 좋은 방법을 찾는 것이 알고리즘 공부 방법이다.
예를 들어, 책장에서 원하는 책을 찾는 방법 2가지 방법을 확인해보자.
왼쪽부터 하나씩 확인
하다가 찾기책이 알파벳순으로 정렬되어 있다는 것을 활용하여,
(1) 전체 중중간을 선택
한 뒤, 원하는 책이 앞인지 / 뒤인지 확인하기(2) 남은 책들 중에 중간지점을 선택한 뒤, 확인하기
(3) 이렇게 반씩 줄이는 것을 반복하다보면 원하는 책을 찾을 수 있다.
탐색문제
위에서 살펴보면 문제는 탐색문제
이다.
탐색이란? 저장된 정보들 중에 원하는 값을 찾는 것이다. ex> 파이썬 숫자 리스트 중 특정값 찾기
탐색문제 해결방법 2가지
선형 탐색 알고리즘(Linear search algorithm)
: 순서대로 하나하나씩 찾기이진 탐색 알고리즘(Binary search algorithm)
: 반씩 제외시키면서 찾기
선형 탐색 알고리즘
: 순서대로 하나하나씩 찾기왼쪽부터 하나하나씩 원하는 값을 찾아본다.
원하는 값 발견시, 더이상 안보고 끝낸다.
이진 탐색 알고리즘
: 반씩 제외하면서 찾기중간지점(중간값)을 먼저 선택한 뒤, 왼쪽 or 오른쪽만 남긴다.
남은값들 중에 중간값을 선택(여기서는 그냥 왼쪽것을 선택)하고, 왼쪽or오른쪽 남기기
반복해서 찾아가기
2가지 탐색문제 해결방법 중 어느 것이 더 효율적일까??
탐색 알고리즘 2개 비교
16개의 원소를 가지고 있는 리스트가 있다고 가정하고, 얼마나 걸리는지 한번 생각해보자.
선형탐색
의 경우, 언제 가장 빨리 마치고/ 언제 가장 늦게 마칠 까?
정답이 리스트 첫 원소인 경우 ->
1번
걸림정답이 마지막 원소이거나 없는 경우 ->
16번
걸림
이진탐색
의 경우, 가장 빨리 되는 경우는
- 정답이 가운데( 0 + 15 // 2) 있는 경우 ->
1번
- 정답이 없는 경우 = ex> 0을 찾는 경우 ->
4번
이진 탐색의 경우 최악의 경우시 4번만 봐도 되지만, 선형 탐색은 16번 다 봐야한다.
최악의 경우를 일반화 해보면, n
개의 원소 리스트는
- 선형탐색 ->
n
번 - 이진탐색 ->
2^m = n
의m
번 걸린다. - 리스트의 길이가 길어지더라도, 이진 탐색은 걸리는 시간이 아주 천천히 늘어난다.
언제 선형탐색을 쓸까???
이진 탐색의 전제조건은 정렬된 리스트-이진탐색
이다.
만약, 리스트가 정렬되지 않은 상태라면 정렬x리스트-선형탐색
을 쓸 수 밖에 없다.
# 선형 탐색 알고리즘 for 정렬안된 리스트 | |
def linear_search( element, some_list ): | |
# list 탐색을 idx를 가지고 할 수 있는 range(len()=1부터 개수) = 0부터 인덱스 | |
for i in range(len(some_list)): | |
if some_list[i] == element: | |
return i | |
return None | |
# 이진 탐색 알고리즘 for 정렬 리스트 | |
def binary_search(element, some_list): | |
# 1. 매번 중간인덱스로 가야한다 -> 처음과 끝 인덱스를 변수로 관리하여, a+b/2를 이용하자 | |
# 2. 초기값 | |
start_index = 0 | |
end_index = len(some_list) - 1 # 3. 어떤 리스트의 마지막인덱스는 len()=개수 - 1 | |
# 7. 최악의 경우의 수만큼 : for _ in ... 2^m = len(list) 의 m만큼.. -> log2( len(list)) | |
# 8. 그냥 반씩 줄이다가, 남은 원소가 1개가 되었을 때까지를 조건으로 | |
# 조건동안 유지할 반복문 : while | |
# - 만약, list에 [2]만 남았는데, 찾고자하는 element가 1이다. | |
# - start, end, mid_index = 0 => some_list[0] = 2 > element => | |
# - element가 왼쪽에 있다고 판단하여, end_index = mid -1 = 0 -1을 대입하게된다. | |
# - 리스트가 1개일 때는, 원하는 것이 없을 때 엇갈리게 된다. | |
# - 나는 리스트 1개, 원하는 것이 항상 그것이라고만 생각하는 경향이 있음. | |
while start_index <= end_index: | |
# 4. 반복분에서 변하는 값 | |
mid_index = (start_index + end_index) // 2 # 5. 홀짝관계없이 그냥 정수몫(나중에 -1, +1 알아서됨) | |
# 6. | |
if element == some_list[mid_index]: | |
return mid_index | |
elif element < some_list[mid_index]: | |
end_index = mid_index - 1 | |
#다시 반복 | |
else: | |
start_index = mid_index + 1 | |
#다시반복 | |
# 9. | |
return None |
'알고리즘 > Python - 알고리즘' 카테고리의 다른 글
선형/이진 탐색알고리즘 평가하기 및 주의사항 (0) | 2019.05.17 |
---|---|
알고리즘 평가기준 - 시간복잡도와 점근표기법-O(n) (0) | 2019.05.13 |
정렬 알고리즘 - 1. 선택 정렬(index) / 2. 삽입 정렬(value) (2) | 2019.05.06 |