[알고리즘] 탐색 알고리즘 기본적인 이해와 구현 - 1. 선형 탐색

1. 선형 탐색 (Linear Search)
2. 이진 탐색 (Binary Search)
3. 점프 탐색 (Jump Search)
4. 보간 탐색 (Interpolation Search)
5. 지수 탐색 (Exponential Search)
6. 깊이 우선 탐색 (Depth-First Search, DFS)
7. 너비 우선 탐색 (Breadth-First Search, BFS)

 

 

선형 탐색

선형 탐색은 탐색 알고리즘 중 가장 간단한 형태로, 배열이나 리스트 등의 자료구조에서 원하는 값을 찾을 때 처음부터 끝까지 순차적으로 비교하면서 찾는 방식입니다. 다른 복잡한 알고리즘에 비해 구현이 쉽고 직관적이어서 소규모 데이터셋에서 자주 사용됩니다.

 

1. 특징

• 순차적 탐색: 시작 위치에서 끝까지 모든 요소를 순서대로 탐색하므로, 값이 배열의 앞에 있든 끝에 있든 일관된 방법으로 탐색합니다.
• 정렬 필요 없음: 선형 탐색은 데이터가 정렬되어 있지 않아도 사용할 수 있어 초기 데이터 전처리가 필요하지 않습니다.
• 구현의 단순성: 코드가 간단하고 직관적이며, 대부분의 언어에서 몇 줄의 코드로 쉽게 구현할 수 있습니다.

 

2. 복잡도

• 시간 복잡도: 최악의 경우 O(n)으로, 탐색 대상의 길이에 비례하여 시간이 증가합니다. 예를 들어 배열의 마지막 요소가 탐색 대상일 경우, 모든 요소를 비교해야 하므로 n번의 비교가 필요합니다.
• 공간 복잡도: O(1)로, 추가적인 메모리 공간이 거의 필요하지 않습니다. 보조 메모리를 사용하지 않기 때문에 메모리 효율성이 좋습니다.

 

3. 예제

public class LinearSearchExample {
    public static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i; // 찾은 경우 인덱스 반환
            }
        }
        return -1; // 찾지 못한 경우 -1 반환
    }

    public static void main(String[] args) {
        int[] arr = {2, 4, 6, 8, 10};
        int target = 8;
        int result = linearSearch(arr, target);

        if (result == -1) {
            System.out.println("원소를 찾을 수 없습니다.");
        } else {
            System.out.println("원소는 인덱스 " + result + "에 위치해 있습니다.");
        }
    }
}

• 이 코드에서는 배열 arr에서 원하는 값 target을 찾기 위해 처음부터 끝까지 각 요소와 비교합니다. 찾으면 해당 인덱스를 반환하고, 없으면 -1을 반환합니다.

 

4. 주 사용처

• 소규모 데이터셋: 선형 탐색은 데이터의 크기가 작거나 정렬되어 있지 않은 경우 효과적입니다.
• 단순 검색 기능: 복잡한 알고리즘을 적용할 필요가 없을 때 유용합니다.
• 리스트 검색: 연관 배열이나 간단한 리스트에서 특정 값이나 객체를 찾는 데 자주 사용됩니다.

 

감사합니다.