[알고리즘] 순차 탐색

순차 탐색(Sequential Search)

리스트의 처음부터 끝까지 차례대로 탐색하면서 원하는 데이터를 찾는 가장 기본적인 알고리즘입니다.
(탐색: 여러 데이터 중에서 원하는 데이터를 찾아내는 것)

 

순차 탐색 알고리즘 동작 방식

1. 첫 번째 원소부터 탐색 시작
2. 현재 원소가 찾고자 하는 값과 같은지 비교
3. 같으면 해당 인덱스를 반환
4. 끝까지 탐색해도 없으면 -1 반환

순차 탐색의 시간 복잡도

• 최선의 경우: `O(1)` (첫 번째 요소가 찾는 값일 때)
• 최악의 경우: `O(n)` (리스트 끝까지 탐색)
• 평균적인 경우: `O(n)`

 

프로그래밍 연습

임의 리스트가 다음과 같이 `randDataList`로 있을 때
원하는 데이터의 위치를 리턴하는 순차 탐색 알고리즘 작성해 보기
(원하는 데이터가 없을 경우 `-1` 리턴)

import java.util.*;

public class SequentialSearchExample {

    // 순차 탐색 메서드
    public static int sequentialSearch(List<Integer> dataList, int searchData) {
        for (int i = 0; i < dataList.size(); i++) {
            if (dataList.get(i) == searchData) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        // 무작위 데이터 생성
        Random rand = new Random();
        List<Integer> randDataList = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            randDataList.add(rand.nextInt(100) + 1);  // 1 ~ 100
        }

        System.out.println("데이터: " + randDataList);

        // 검색할 데이터 지정 (예: 3번째 인덱스 값)
        int target = randDataList.get(3);
        int result = sequentialSearch(randDataList, target);

        System.out.println(target + "의 인덱스 위치: " + result);
    }
}

 

순차 탐색 정리

항목	내용
알고리즘 이름	순차 탐색 (Sequential Search)
동작 방식	앞에서부터 하나씩 차례로 검사
조건	정렬 필요 없음
시간 복잡도	O(n)
장점	단순하고 구현이 쉬움
단점	데이터가 많을수록 느려짐

 

정렬이 되어 있지 않거나, 리스트가 작을 때는 유용하지만
데이터가 많다면 이진 탐색 등 더 효율적인 알고리즘이 필요합니다.