[알고리즘] 10. 탐색

1. 탐색의 활용

1) 탐색 개요

• 기억 공간에 저장된 데이터나 입력 데이터에서 특정 조건을 만족하는 데이터를 찾는 과정.

• 필요한 데이터를 신속하게 찾으면 자원을 효율적으로 활용 가능.

• 탐색이 빠르면 후속 작업을 빠르게 실행할 수 있어 매우 중요함.

• 탐색 대상이 정렬된 경우와 정렬되지 않은 경우로 구분됨.

• 컴퓨터에 저장된 자료 중 원하는 항목을 찾는 작업.

- 탐색 성공: 원하는 항목을 찾은 경우.

- 탐색 실패: 원하는 항목을 찾지 못한 경우.

- 탐색 키: 자료를 구별할 수 있는 고유한 키 값.

- 삽입/삭제 작업에서 탐색: 원소를 삽입하거나 삭제할 위치를 찾기 위해 탐색 수행.

 

2) 탐색 방법

수행 위치에 따른 분류

• 내부 탐색: 모든 데이터를 주기억장치에서 검색.

• 외부 탐색: 데이터가 많아 일부만 주기억장치에 올려 검색.

• 주기억장치 접근 속도가 빠르므로 내부 탐색이 외부 탐색보다 빠름.

 

탐색 방식에 따른 분류

• 비교 탐색: 키 값을 비교하며 탐색 (순차 탐색, 이진 탐색).

• 계산 탐색: 수학적 계산을 이용한 탐색 (해싱).

 

 

 

2. 순차 탐색 (Sequential Search)

1) 순차 탐색 개요

• 데이터를 처음부터 하나씩 비교하며 찾는 방법.

• 선형 탐색이라고도 하며, 구현이 간단하지만 비효율적.

• 탐색 대상이 크면 속도가 느려짐.

 

2) 정렬되지 않은 데이터의 순차 탐색

• 첫 번째 원소부터 마지막 원소까지 순서대로 탐색.

• 찾으면 해당 원소의 위치를 반환, 없으면 탐색 실패.

 

3) 정렬된 데이터의 순차 탐색

• 원소가 찾는 값보다 크면 더 이상 탐색하지 않고 실패 처리.

 

4) 순차 탐색의 특징

• 데이터의 순서를 몰라도 탐색 가능.

• 탐색 시간이 데이터 개수에 비례하여 증가 (시간 복잡도 O(n)).

• 자주 탐색되는 데이터를 앞부분에 배치하면 성능 향상 가능.

 

5) 개선된 순차 탐색 방법

• 탐색된 데이터를 맨 앞으로 이동 → 자주 사용되는 데이터의 탐색 속도 향상.

• 탐색된 데이터를 바로 직전 위치로 이동 → 교체 비용 절감.

• 그러나 대량 데이터를 처리하는 데는 적절하지 않음.

 

 

 

3. 이진 탐색 (Binary Search)

1) 이진 탐색 개요

• 탐색 대상을 절반씩 줄여가는 방법.

• 중간 값을 기준으로 크기를 비교하여 탐색 범위를 축소.

• 정렬된 데이터에서만 사용 가능.

• 탐색 속도가 빠르며, 순차 탐색보다 효율적임.

 

2) 탐색 과정

• 중간 값을 찾고, 찾고자 하는 값과 비교.

• 값이 중간 값보다 크면 오른쪽 탐색, 작으면 왼쪽 탐색.

• 반복적으로 수행하여 원하는 값을 찾음.

 

3) 효율성

• 탐색 횟수는 logn에 비례 (시간 복잡도 O(log n)).

• 성능이 우수하지만 삽입/삭제 시 정렬 상태를 유지해야 함.

• 삽입/삭제가 많은 경우 추가적인 정렬 작업이 필요하여 비효율적일 수 있음.

---

이 내용은 휴넷사회복지평생교육원의 알고리즘 강의를 듣고 정리한 것입니다.