완전탐색 이분탐색

탐색이란?

• 많은 데이터 속에서 원하는 데이터를 찾는 것
• 웹에서 특정 문자를 가진 웹 문서를 찾거나 신용카드나 버스카드 역시 검색 알고리즘을 사용

탐색 종류

• 완전탐색
  • 완전탐색이란
    • 브루트 포스 라고 불리며 컴퓨터의 빠른 계산 성능을 활용하며 가능한 모든 경우의 수를 탐색함.
    • 효율성은 매우 나쁨. O(경우의 수) 시간복잡도
  • 반복문
    • EX) 카드 10개중 특정 값을 찾기 위해서 카드의 1부터 하나씩 찾기

    • for i in range(10):
      	if card[i] == 8:
          	print(i)
          	exit()
              
       print("not found")

  • 재귀함수

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

    • 동적 계획법
    • 백트래킹
    • 탐욕법
• 이분탐색
  • ex) https://www.acmicpc.net/problem/10816
  • 오름차순으로 정렬된 리스트에서 특정 값의 위치를 찾는 알고리즘.
  • 중간의 값을 선택하여 찾고자 하는 값과의 크고 작음을 비교하는 것
  •  
• 깊이우선탐색
• 너비우선탐색
• 문자열탐색
• KMP
• BM