[자료구조] 완전탐색/이분탐색

완전탐색

0) 정의

-> 가능한 모든 경우의 수를 다 구해서 값을 찾는 과정으로, 브루트 포스(Brute Force)라고도 불린다. 

 

1) 동작

2) 구현

· 반복문

def solution(trump):
    for i in range(len(trump)): 
        if trump[i] == 7:
            return i 
    return -1   # 7이 없을 경우

· 재귀함수  - 동적 계획법, 백트래킹, 탐욕법 등에 사용됨 

def solution(trump, loc):
    if trump[loc] == 8:
        return loc 
    else:
        return solution(trump, loc + 1)

 

이분탐색

0) 정의

-> 이진검색이라고도 표현하며, 오름차순으로 정렬된 리스트에서 특정 값의 위치를 찾는 알고리즘이다. 중간의 값을 선택하여 찾고자 하는 값과의 크고 작음을 비교한다.

 

1) 동작

· index_0의 위치를 left, index_n의 위치를 right, left와 right의 중간 값을 갖는 위치를 mid로 지정 

· mid 값과 구하고자 하는 값을 비교

· 기존 mid보다 1이 더 큰 값으로 left를 다시 설정 

· 업데이트된 left와 right값을 이용하여 mid를 다시 지정 

· 원하는 값을 찾을 때까지 위 과정 반복 

 

2) 구현

def solution(trump):
    left = 0
    right = len(trump) - 1
    
    while(left <= right):
        mid = (left + right) // 2 
        
        if trump[mid] == 7:
            return mid 
        elif trump[mid] < 7:
            left = mid + 1 
        elif trump[mid] > 7:
            right = mid -1 
    return mid