[이코테/Python] 5장 - 탐색

0. 순차탐색

이때까지 했던 가장 많이 사용했던 탐색은 순차탐색이다.

 

별 어려운 알고리즘이 아니라 리스트의 요소 하나하나에 접근해 찾는 값이 맞는지 체크하는 알고리즘이다.

 

#순차탐색

li = [1,3,2,5,4,6,7,9,8,0]

#7을 찾으려면

for i in li:
	if i == 7:
    	print("찾았다!")
    else:
    	print("못찾았다!")

 

이처럼 간단하게 구현 할 수 있고, 장점은 정렬이 안되어 있어도 찾을 수 있다는 점이다.

 

이전글에서 배웠던 정렬 없이 사용할 수 있어서 좋다면 좋은 알고리즘이다.

 

하지만 리스트가 길면 길수록 시간이 더 더 걸린다는 단점이 있다.

 

이어서 이진탐색을 설명하겠다.

 

1. 이진탐색

이진탐색은 다음과 같다.

 

확실히 순차탐색보다 적은 수의 탐색을 하면 된다.

 

이진탐색을 수행하려면 리스트가 항상 정렬되어있어야 한다.

 

이진탐색은 범위가 2000만 이상 될때 사용하면 유용하다. (수가 많을수록 유용하다. 단, 정렬에서 좀 더 효과적인 알고리즘을 써 시간을 단축시키는게 목표일것 같다.)

 

다음은 이진탐색을 재귀적, 반복적 두 가지 방법으로 구현한 코드이다.

li = [0,2,4,6,8,10,12,14,16,18,20]

#재귀적
def binary(array,target,start,end):
    mid = (start + end) // 2 #몫만 취한다  
    if start > end:
        return None #못찾았다면 None반환
    
    if array[mid] == target:
        return mid #찾았다면 인덱스 반환
    elif array[mid] < target:
        return binary(array,target, mid + 1, end) #찾는값보다 중간값이 작다면 mid아래쪽을 버림
    else:
    	return binary(array,target, start, mid - 1) #크다면, mid위쪽을 버림.
        
binary(li,7,0,len(li) - 1)    
    
    
 
#반복적
start = 0
end = len(li) - 1 #인덱스니깐 1 빼줌

target = 7

while start <= end:
    mid = (start + end) // 2
    
    if li[mid] == target:
        break #찾았다면 바로 반복문 탈출. mid의 변경 없음.
    elif li[mid] < target:
        start = mid + 1 
    else:
        end = mid - 1
        
print(li[mid])

 

둘 중 아무거나 써도 되지만 뭔가 재귀적으로 구현하는게 더 끌린다.

 

마지막으로 이코테의 예제와 동일한 백준 저지 문제를 가지고 왔다.

---

2. 문제 

https://freeedeveloper.tistory.com/entry/%EB%B0%B1%EC%A4%80Python-S2-2805-%EB%82%98%EB%AC%B4-%EC%9E%90%EB%A5%B4%EA%B8%B0

[백준/Python] (S2) 2805 - 나무 자르기