탐색 : 찾았다. 내가 찾던 데이터..

📖 탐색(검색)이란?

: 많은 데이터 속에서 원하는 데이터를 찾는 것

• 완전탐색
• 이진탐색
• 깊이우선탐색(DFS)
• 너비우선탐색(BFS)
• 문자열탐색(KMP)
  
  

---

1. 완전탐색

• 브루트 포스(Brute Force)
• 컴퓨터의 빠른 계산 성능을 활용하여 가능한 모든 경우의 수를 탐색하는 방법

🟩 장점

• 모든 데이터를 다 뒤지기 때문에, 완전탐색으로 못 푸는 문제가 없음

🟥 단점

• 최악의 경우, 모든 데이터를 끝까지 다 뒤져봐야하기 때문에 효율성 관점에서 최악

<완전탐색 구현>

1. 반복문을 통해 구현
2. 재귀함수를 이용해 구현
   - 재귀함수의 경우 쉽게 무한루프에 빠질 수 있으므로, 탈출 조건을 꼭 미리 명시해두어야 함
   - 재귀함수는 동적 계획법, 백트랙킹, 탐욕법(greedy algorithm)으로 구현 가능
   
   

---

2. 이진탐색

• '이진검색'이라고도 표현
• 정렬된 리스트에서 탐색 범위를 반으로 점차 줄여나가며 특정 값의 위치를 탐색하는 방법
  
  

🟩 장점

• 완전탐색보다 효율적이고 속도가 빠름

🟥 단점

• 미리 정렬이 되어있는 리스트에서만 사용 가능

<이진탐색 구현>

1. 초기 left, right 인덱스 값 선언
2. left가 right보다 작거나 같다면 아래 반복
   • (left+right)/2 로 mid 값 계산
   • mid 값과 비교하여 찾아야하는 값을 찾으면, 해당 값 return
   • 찾아야하는 값이 mid보다 작으면, right를 -1 이동
   • 찾아야하는 값이 mid보다 크면, left를 +1 이동
3. left와 right가 딱 붙어버리거나 같아지면 탐색 완료

---