[알고리즘] 25. 선형 탐색(Linear Search)
지난 글에서는 유니온 파인드(Union-Find)에 대해 정리했습니다. 이번 글부터는 탐색 알고리즘 영역으로 들어갑니다. 그 첫 번째 주제는 가장 기본적인 탐색 방법인 선형 탐색(Linear Search)입니다.
선형 탐색은 배열이나 리스트의 값을 처음부터 끝까지 하나씩 확인하면서 원하는 값을 찾는 방법입니다. 복잡한 자료구조나 정렬이 필요하지 않아 알고리즘 입문 단계에서 가장 먼저 익히기 좋은 탐색 방식입니다.
선형 탐색은 데이터를 앞에서부터 하나씩 확인하며 원하는 값을 찾는 가장 기본적인 탐색 방법입니다.
1. 선형 탐색이란?
선형 탐색은 데이터를 순서대로 하나씩 확인하는 탐색 방법입니다. 배열의 첫 번째 값부터 시작해서 마지막 값까지 차례대로 비교합니다.
배열: [3, 7, 2, 9, 5]
찾을 값: 9
3 확인 → 아님
7 확인 → 아님
2 확인 → 아님
9 확인 → 찾음위 예시에서는 9를 찾기 위해 앞에서부터 값을 하나씩 확인했습니다. 이처럼 순서대로 쭉 확인하는 방식이 선형 탐색입니다.
선형 탐색은 가장 단순하지만, 어떤 데이터에도 사용할 수 있는 기본 탐색 방법입니다.
2. 선형 탐색이 필요한 상황
선형 탐색은 아래와 같은 상황에서 사용할 수 있습니다.
- 데이터가 정렬되어 있지 않을 때
- 배열이나 리스트에서 특정 값을 찾아야 할 때
- 특정 조건을 만족하는 값을 찾아야 할 때
- 데이터 개수가 많지 않을 때
- 처음 등장하는 위치를 찾아야 할 때
- 전체 값을 확인해야 하는 문제일 때
특히 데이터가 정렬되어 있지 않다면 이분 탐색 같은 방법을 바로 사용할 수 없습니다. 이럴 때는 처음부터 끝까지 확인하는 선형 탐색이 가장 자연스러운 방법입니다.
3. 선형 탐색의 기본 흐름
선형 탐색의 기본 흐름은 단순합니다.
- 배열의 첫 번째 값부터 확인한다.
- 현재 값이 찾는 값과 같은지 비교한다.
- 같으면 탐색을 종료한다.
- 다르면 다음 값으로 이동한다.
- 끝까지 찾지 못하면 값이 없다고 판단한다.
이 흐름은 대부분의 탐색 문제에서 기본 틀이 됩니다.
처음부터 확인 → 조건 비교 → 찾으면 종료 → 못 찾으면 끝까지 진행선형 탐색의 핵심은 반복문으로 모든 값을 순서대로 확인하는 것입니다.
4. 배열에서 특정 값 찾기
가장 기본적인 예제로 배열에서 target 값을 찾는 코드를 보겠습니다.
int[] numbers = {3, 7, 2, 9, 5};
int target = 9;
boolean found = false;
for (int i = 0; i < numbers.length; i++) {
if (numbers[i] == target) {
found = true;
break;
}
}
System.out.println(found);출력 결과는 다음과 같습니다.
true배열 안에 9가 있으므로 found 값이 true가 됩니다. 찾는 값을 발견하면 더 이상 확인할 필요가 없으므로 break로 반복문을 종료합니다.
5. 값이 없는 경우 처리하기
탐색 문제에서는 찾는 값이 없을 수도 있습니다. 따라서 값이 없는 경우도 반드시 처리해야 합니다.
int[] numbers = {3, 7, 2, 9, 5};
int target = 4;
boolean found = false;
for (int i = 0; i < numbers.length; i++) {
if (numbers[i] == target) {
found = true;
break;
}
}
if (found) {
System.out.println("찾았습니다.");
} else {
System.out.println("찾지 못했습니다.");
}출력 결과는 다음과 같습니다.
찾지 못했습니다.target 값 4는 배열에 없기 때문에 found는 false로 남습니다. 탐색 문제에서는 찾은 경우와 찾지 못한 경우를 모두 고려해야 합니다.
탐색 문제에서는 정답이 없는 경우를 반드시 처리해야 합니다.
6. 찾은 위치 반환하기
값이 있는지 여부만 필요한 경우도 있지만, 값이 있는 위치를 찾아야 하는 경우도 많습니다. 이때는 인덱스를 저장하거나 반환하면 됩니다.
int[] numbers = {3, 7, 2, 9, 5};
int target = 9;
int index = -1;
for (int i = 0; i < numbers.length; i++) {
if (numbers[i] == target) {
index = i;
break;
}
}
System.out.println(index);출력 결과는 다음과 같습니다.
3배열에서 9는 인덱스 3에 있습니다. 만약 값을 찾지 못했다면 index는 그대로 -1입니다.
탐색 실패를 표현할 때는 보통 -1을 사용합니다.
7. 처음 등장하는 값 찾기
배열에 같은 값이 여러 번 등장할 수 있습니다. 이때 선형 탐색은 앞에서부터 확인하기 때문에 가장 먼저 등장하는 위치를 찾기 좋습니다.
int[] numbers = {5, 3, 7, 3, 9};
int target = 3;
int index = -1;
for (int i = 0; i < numbers.length; i++) {
if (numbers[i] == target) {
index = i;
break;
}
}
System.out.println(index);출력 결과는 다음과 같습니다.
13은 인덱스 1과 3에 등장하지만, 앞에서부터 탐색하므로 인덱스 1을 먼저 찾습니다.
8. 마지막으로 등장하는 값 찾기
마지막으로 등장하는 위치를 찾고 싶다면 두 가지 방법이 있습니다. 하나는 끝까지 탐색하면서 index를 계속 갱신하는 방식입니다.
int[] numbers = {5, 3, 7, 3, 9};
int target = 3;
int index = -1;
for (int i = 0; i < numbers.length; i++) {
if (numbers[i] == target) {
index = i;
}
}
System.out.println(index);출력 결과는 다음과 같습니다.
3값을 찾을 때마다 index를 갱신했기 때문에 마지막으로 발견한 위치가 저장됩니다.
또 다른 방법은 배열의 뒤에서부터 탐색하는 것입니다.
int[] numbers = {5, 3, 7, 3, 9};
int target = 3;
int index = -1;
for (int i = numbers.length - 1; i >= 0; i--) {
if (numbers[i] == target) {
index = i;
break;
}
}
System.out.println(index);뒤에서부터 탐색하면 마지막 등장 위치를 더 빨리 찾을 수 있습니다.
9. 조건을 만족하는 값 찾기
선형 탐색은 특정 값뿐 아니라 조건을 만족하는 값을 찾을 때도 사용할 수 있습니다. 예를 들어 배열에서 첫 번째 짝수를 찾아보겠습니다.
int[] numbers = {3, 7, 5, 8, 9};
int result = -1;
for (int i = 0; i < numbers.length; i++) {
if (numbers[i] % 2 == 0) {
result = numbers[i];
break;
}
}
System.out.println(result);출력 결과는 다음과 같습니다.
8배열을 앞에서부터 확인하다가 처음으로 짝수 8을 발견하고 탐색을 종료했습니다.
이처럼 선형 탐색은 “특정 값 찾기”뿐 아니라 “조건을 만족하는 첫 번째 값 찾기”에도 사용할 수 있습니다.
10. 조건을 만족하는 값의 개수 세기
어떤 값을 찾는 것이 아니라 조건을 만족하는 값이 몇 개인지 세야 하는 경우도 있습니다. 이때도 배열을 처음부터 끝까지 확인하면 됩니다.
int[] numbers = {1, 2, 3, 4, 5, 6};
int count = 0;
for (int i = 0; i < numbers.length; i++) {
if (numbers[i] % 2 == 0) {
count++;
}
}
System.out.println(count);출력 결과는 다음과 같습니다.
3짝수는 2, 4, 6으로 총 3개입니다. 이처럼 조건을 확인하면서 count를 증가시키는 방식은 기초 구현 문제에서 매우 자주 사용됩니다.
11. 문자열에서 문자 찾기
선형 탐색은 배열뿐 아니라 문자열에서도 사용할 수 있습니다. 문자열을 앞에서부터 한 글자씩 확인하면 됩니다.
String word = "algorithm";
char target = 'r';
int index = -1;
for (int i = 0; i < word.length(); i++) {
if (word.charAt(i) == target) {
index = i;
break;
}
}
System.out.println(index);출력 결과는 다음과 같습니다.
4문자 r은 문자열 algorithm에서 인덱스 4에 있습니다. 문자열도 인덱스가 0부터 시작한다는 점을 기억해야 합니다.
문자열 탐색도 결국 문자 배열을 하나씩 확인하는 것과 비슷합니다.
12. 선형 탐색의 시간복잡도
선형 탐색은 최악의 경우 모든 값을 확인해야 합니다. 배열의 길이를 N이라고 하면 시간복잡도는 O(N)입니다.
| 상황 | 설명 | 시간복잡도 |
|---|---|---|
| 가장 앞에서 찾음 | 첫 번째 값만 확인 | O(1) |
| 중간에서 찾음 | 일부 값을 확인 | O(N) |
| 마지막에서 찾음 | 거의 모든 값을 확인 | O(N) |
| 값이 없음 | 끝까지 확인 | O(N) |
운이 좋으면 첫 번째 값에서 바로 찾을 수도 있지만, 알고리즘에서는 보통 최악의 경우를 기준으로 생각합니다. 따라서 선형 탐색의 시간복잡도는 O(N)으로 봅니다.
선형 탐색은 입력 개수에 비례해서 탐색 시간이 증가합니다.
13. 선형 탐색의 장점
선형 탐색은 단순하지만 장점이 분명합니다.
- 구현이 매우 쉽다.
- 데이터가 정렬되어 있지 않아도 사용할 수 있다.
- 배열, 리스트, 문자열 등 다양한 곳에 사용할 수 있다.
- 특정 값뿐 아니라 조건을 만족하는 값도 찾을 수 있다.
- 데이터가 작을 때는 충분히 빠르게 동작한다.
처음 알고리즘 문제를 풀 때는 선형 탐색으로 먼저 접근해보는 것이 좋습니다. 문제 구조를 이해한 뒤, 입력 크기가 크다면 더 효율적인 방법을 고민하면 됩니다.
14. 선형 탐색의 단점
선형 탐색의 단점은 데이터가 많아질수록 느려질 수 있다는 점입니다. 모든 값을 하나씩 확인해야 하기 때문입니다.
| N | 최악의 경우 확인 횟수 |
|---|---|
| 10 | 10번 |
| 1,000 | 1,000번 |
| 100,000 | 100,000번 |
| 1,000,000 | 1,000,000번 |
한 번만 탐색한다면 괜찮을 수 있지만, 여러 번 반복해서 탐색해야 한다면 비효율이 커질 수 있습니다.
예를 들어 N개의 데이터에서 M개의 값을 매번 선형 탐색으로 찾으면 최악의 경우 O(N × M)이 될 수 있습니다. 이런 경우에는 HashSet, HashMap, 이분 탐색 등을 고려해야 합니다.
선형 탐색은 단순하지만 반복 횟수가 많아지면 비효율적일 수 있습니다.
15. 선형 탐색과 HashSet 비교
값의 존재 여부를 여러 번 확인해야 한다면 HashSet을 사용하는 것이 더 효율적일 수 있습니다.
| 구분 | 선형 탐색 | HashSet |
|---|---|---|
| 준비 작업 | 없음 | set에 값 저장 필요 |
| 한 번 찾기 | O(N) | 평균 O(1) |
| 정렬 필요 여부 | 필요 없음 | 필요 없음 |
| 적합한 상황 | 한두 번만 찾을 때 | 존재 확인을 여러 번 할 때 |
한 번만 찾는 문제라면 선형 탐색도 충분합니다. 하지만 존재 여부를 여러 번 확인해야 한다면 HashSet을 고려하는 것이 좋습니다.
16. 선형 탐색에서 자주 하는 실수
선형 탐색 문제를 풀 때는 아래 실수를 조심해야 합니다.
- 값을 찾은 뒤 break를 하지 않아 불필요하게 계속 탐색하는 경우
- 찾지 못한 경우를 처리하지 않는 경우
- 인덱스 초기값을 잘못 설정하는 경우
- 배열 범위를 i <= arr.length로 작성하는 경우
- 처음 등장 위치와 마지막 등장 위치를 헷갈리는 경우
- 조건을 만족하는 값이 없을 때 기본값 처리를 하지 않는 경우
- 탐색을 여러 번 반복해야 하는 문제에서 매번 선형 탐색을 사용하는 경우
특히 배열 반복문에서는 대부분 아래 조건을 사용해야 안전합니다.
for (int i = 0; i < arr.length; i++) {
// 탐색
}배열의 마지막 인덱스는 arr.length가 아니라 arr.length - 1입니다.
선형 탐색은 단순한 만큼 인덱스 범위와 실패 처리를 꼼꼼히 확인해야 합니다.
17. 정리
이번 글에서는 선형 탐색에 대해 정리했습니다.
- 선형 탐색은 데이터를 처음부터 끝까지 하나씩 확인하는 탐색 방법이다.
- 데이터가 정렬되어 있지 않아도 사용할 수 있다.
- 특정 값이나 특정 조건을 만족하는 값을 찾을 때 사용할 수 있다.
- 값의 존재 여부는 boolean 변수로 처리할 수 있다.
- 찾은 위치가 필요하면 인덱스를 저장하면 된다.
- 찾지 못한 경우를 표현할 때는 보통 -1을 사용한다.
- 선형 탐색의 시간복잡도는 O(N)이다.
- 존재 확인을 여러 번 해야 한다면 HashSet이나 HashMap을 고려할 수 있다.
선형 탐색은 가장 기본적인 탐색 알고리즘입니다. 복잡한 알고리즘을 배우기 전, 데이터를 하나씩 확인하면서 조건을 판단하는 흐름을 정확히 익히는 것이 중요합니다.
선형 탐색의 핵심은 처음부터 끝까지 순서대로 확인하며 원하는 값을 찾는 것입니다.
다음 글 예고
다음 글에서는 이분 탐색 기초에 대해 알아보겠습니다.
정렬된 데이터에서 탐색 범위를 절반씩 줄여가며 값을 찾는 방법과 left, right, mid 개념을 예제로 정리해보겠습니다.
'Problem Solving > Algorithm' 카테고리의 다른 글
| [알고리즘] 27. 이분 탐색 응용 (0) | 2026.07.10 |
|---|---|
| [알고리즘] 26. 이분 탐색 기초 (0) | 2026.07.09 |
| [알고리즘] 24. 유니온 파인드(Union-Find) (0) | 2026.07.07 |
| [알고리즘] 23. 그래프 기초 (0) | 2026.07.06 |
| [알고리즘] 22. 트리 기초 (0) | 2026.07.05 |