IT/알고리즘
[python/자료구조] 탐색( 완전탐색 / 이분탐색 )
유달잇
2021. 2. 5. 21:59
728x90
탐색이란?
많은 데이터 속에서 원하는 데이터를 찾는 것
탐색의 종류
- 완전탐색
- 이분탐색
- 깊이우선 탐색
- 너비우선 탐색
- 문자열 탐색
- KMP
- BM
1. 완전탐색
- 브루트 포스라고도 불리며 컴퓨터의 빠른 계산 성능을 활용하여 가능한 모든 경우의 수를 탐색,
효율성 관점에서 최악의 방법
1-1. 반복문
def solution(trump):
for i in range(len(trump)):
if trump[i] == 8 :
return i
return -1
1-2. 재귀함수(동적계획법, 백트래킹, 탐욕법)
- 무한루프에 빠질 수 있음에 주의!
def solution(trump, loc):
if trump[loc] == 8 :
return loc
else :
return solution(trump, loc+1)
2. 이분탐색
- 이진검색이라고도 하며 오름차순으로 정렬된 리스트에서 특정 값의 위치를 찾는 알고리즘,
중간의 값을 선택하여 찾고자 하는 값과의 크고 작음을 비교하는 방법으로 left, mid, right를 사용하여 조정한다.
def solution(trump):
left = 0
right = len(trump)-1
# left가 right보다 작거나 같다면
while(left<=right):
mid = (left+right) // 2 # mid 값 계산
if trump[mid] == 8:
return mid # 정답일 경우 정답 반환
elif trump[mid] < 8:
left = mid + 1 # 정답보다 작을 경우 left를 mid+1로 이동
elif trump[mid] > 8:
right = mid -1 # 정답보다 클 경우 right를 mid-1로 이동
return mid
728x90