[탐색의 종류] 완전탐색/이분탐색/깊이우선탐색/너비우선탐색

1) 완전탐색

: 브루트 포스라고도 불리며 컴퓨터의 빠른계산 성능을 활용하여 가능한 모든 경우의 수를 탐색

풀리지 않는 문제는 없으나 효율성 관점에서 최악.. 

- 완전탐색 구현방법

ㆍ 반복문

ㆍ 재귀함수(완전탐색 외에도 동적계획법, 백트래킹, 탐욕법에서도 사용)

# 반복문으로 구현
def solution(trump):
    for i in range(len(trump):
    	if trump[i] == 8:
        	return i
    return -1
    
# 재귀함수로 구현
def solution(trump, loc):
    if trump[loc] == 8:
    	return loc
    else:
    	return solution(trump, loc+1)

 

2) 이분탐색

이진검색이라고도 표현하며 오름차순으로 정렬된 리스트에서 특정 값의 위치를 찾는 알고리즘

중간의 값을 선택하여 찾고자 하는 값과의 크고 작음을 비교하는 방법

범위를 점차 줄여나가

주로 left, right, mid 값의 조정으로 알고리즘 구성

 

def solution(trump):
    left = 0 #함수 시작 시 left, right선언
    rigth = len(trump) -1 
    while(left <= right):
    	mid = (left + right)//2 # 미드값 계산
        if trump[mid] == 8:
        	return mid
        elif trump[mid] < 8:
        	left = mid + 1
        elif trump[mid] > 8:
        	right[mid] - 1
    return mid

 

3) 깊이우선탐색(Depth First Search)

하나의 경우의 수에 대하여 모든 경우의 수를 조사하고 다음 경우의 수를 조사하면서 해를 찾는 과정

스택에서 활용

ex) 미로찾기

 

4) 너비우선탐색(Breadth First Search)

하나의 경우의 수에 대한 다음 단계의 모든 경우의 수를 조사하면서 해를 찾는 과정

같은 수준의 레벨을 모두 조사하고 다음 레벨로 넘어가

큐에서 활용

ex) 최단경로 찾기