Algorithm | 선형 탐색(순차 검색, Linear search)
선형 탐색 알고리즘(순차검색, Linear search algorithm)
찾고자 하는 값을 리스트의 맨 앞에서부터 끝까지 차례대로 찾아 나가는 알고리즘이다.
- 장점: 검색 방법 중 가장 단순하여 구현이 쉽고, 정렬되지 않은 리스트에서도 사용할 수 있다.
- 단점: 검색할 리스트의 길이가 길면 비효율적이다.
package com.devkuma.algorithum.programming.search.linear;
public class LinearSearch {
void search(int[] nums, int target) {
int index = -1;
for(int i = 0; i < nums.length; i++) {
if (nums[i] == target) {
index = i + 1;
break;
}
}
if (index > 0) {
System.out.println(target + "은 " + index + "번째 있습니다.");
} else {
System.out.println(target + "은 없습니다.");
}
}
public static void main(String[] args) {
LinearSearch search = new LinearSearch();
search.search(new int[]{1, 5, 3, 2, 8, 9}, 8);
search.search(new int[]{1, 5, 3, 2, 8, 9}, 4);
}
}
실행 결과:
8은 5번째 있습니다.
4은 없습니다.
선형 탐색 알고리즘으로 최소값 구하기
아래 코드는 모든 요소에 대해서 minValue보다 작은 값이 발견될 때마다 minValue를 갱신해 가면 최소값을 구한다.
(최대값도 동일한 알고리즘이다)
package com.devkuma.algorithum.programming.search.linear;
public class MinLinearSearch {
void searchMinimum(int[] nums) {
int minValue = Integer.MAX_VALUE; // 최대값
for(int i = 0; i < nums.length; i++) {
if (nums[i] < minValue) {
minValue = nums[i];
}
}
System.out.println("최소값은 " + minValue + "입니다.");
}
public static void main(String[] args) {
MinLinearSearch search = new MinLinearSearch();
search.searchMinimum(new int[]{1, 5, 3, 2, 8, 9});
search.searchMinimum(new int[]{2, 7, 8, 6, 5, 4});
}
}
실행 결과:
최소값은 1입니다.
최소값은 2입니다.
선형 탐색 알고리즘으로 최소값 구하기
이제 선형 탐색 알고리즘을 이용해서 문제를 풀어보자.
문제
N개의 정수 a(0), a(1), ..., a(N-1)과 b(0), b(1), ..., b(N-1)가 있다고 했을 때,
이 2개의 수열로부터 하나씩 수 a(i), b(j) [i = 0, 1, ..., N-1, j = 0, 1, ..., N-1]를 구해서 그 합이 정수 R 이상의 범위에서의 최소값을 구하라.
해결 방법
package com.devkuma.algorithum.programming.linearsearch;
public class LinearSearchQuiz1 {
void minSum(int[] aNums, int[] bNums, int r) {
int minSum = Integer.MAX_VALUE; // 최대값
for(int i = 0; i < aNums.length; i++) {
for(int j = 0; j < bNums.length; j++) {
int sum = aNums[i] + bNums[j];
if (sum >= r && minSum > sum) {
minSum = sum;
}
}
}
System.out.println("최소값은 " + minSum + "입니다.");
}
public static void main(String[] args) {
LinearSearchQuiz1 search = new LinearSearchQuiz1();
int[] aNums = new int[]{9, 5, 3, 7, 8, 9};
int[] bNums = new int[]{3, 9, 5, 8, 3, 5};
int r = 7;
search.minSum(aNums, bNums, 7);
}
}
실행 결과:
최소값은 8입니다.
위 예제의 복잡도는 O(N^2)이 된다.
최종 수정 : 2022-04-02