알고리즘 2 | 탐색

탐색(검색)이란?
많은 데이터 속에서 원하는 데이터를 찾는 것으로 웹에서 특정 문자를 가진 웹 문서를 찾거나 신용카드나 버스카드 역시 검색 알고리즘을 사용한다.

탐색의 종류
완전탐색 이분탐색 깊이우선탐색 너비우선탐색 문자열탐색 KMP BM

완전탐색

완전탐색이란?
브루트 포스라고도 불리며 컴퓨터의 빠른 계산 성능을 활용하여 가능한 모든 경우의 수를 탐색하는 효율성 관점에서 최악의 방법
하지만 모든 경우의 수를 탐색하기 때문에 풀리지 않는 문제가 없다는 장점이 있다.

완전탐색 구현방법

1. 반복문
2. 재귀함수 - 동적계획법, 백트래킹, 탐욕법 등 다른 알고리즘에서도 많이 사용됨

반복문

순서대로 확인하는 것.

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)

이분탐색

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

이분탐색구조

범위를 줄여 나가는 것

이분탐색 예시코드

def solution(trump);
	left = 0
    right = 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