반응형
* 선형 검색(순차검색)이란?
배열 검색 중 가장 기본적인 알고리즘으로 요소가 직선 모양으로 늘어선 배열에서 원하는 키값을 찾을 때까지
맨 앞부터 순서대로 요소를 검색하는 것
| 0번째 | 1번째 | 2번째 | 3번째 | 4번째 | 5번째 | 6번째 |
| 6 | 4 | 3 | 2 | 1 | 3 | 8 |
위의 표와 같이 배열이 존재할 경우 1을 찾기 위해 0, 1, 2, 3번째 배열을 모두 검색하는 방법이다.
선형검색을 하게되면 종료의 조건은 아래 두가지로 정의 할 수 있다.
1) 검색값을 찾은 경우
2) 검색값이 존재하지 않는 경우
이때 종료 판단 횟수를 줄이는 역할을 하게 되는 것이 보초법 이다.
* 보초란?
검색하고자 하는 키 값을 맨 끝 요소에 저장하는 값이다.
일반배열에서 7이라는 값을 찾으려고 할때 아래와 같이 배열이 구성 된다.
- 보초 넣은 배열
| 0번째 | 1번째 | 2번째 | 3번째 | 4번째 | 5번째 | 6번째 | 보초 |
| 6 | 4 | 3 | 2 | 1 | 3 | 8 | 7 |
따라서 보초는 반복문에서 종료 판단 중 2)검색값이 존재하지 않는 경우를 체크하지 않아도 되게 함으로써 종료 판단을 2회에서 1회로 줄이는 역할을 한다.
아래는 보초법를 사용한 알고리즘 책의 p106 실습 3-3 예제입니다!
package chap03;
import java.util.Scanner;
public class SeqSearchSen {
static int seqSearchSen(int[] a, int n, int key){
int i=0;
a[n] = key; //보초를 추가
while (true) {
if (a[i] == key) // 검색성공!
break;
i++;
}
return i == n ? -1 : i;
}
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
System.out.print("요솟수 : ");
int num = stdIn.nextInt();
int[] x = new int[num +1]; //요솟수 num+1인 이유는 보초값을 추가하기 위함
for(int i=0;i<num; i++){
System.out.print("x["+i+"] : ");
x[i]= stdIn.nextInt();
}
System.out.print("검색할 값 : ");
int ky = stdIn.nextInt();
int idx = seqSearchSen(x, num, ky); //배열 x에서 값이 ky인 요소를 검색
if(idx == -1){
System.out.println("그 값의 요소가 없습니다.");
}else{
System.out.println(ky+"은(는) x["+idx+"]에 있습니다.");
}
}
}
* 보충수업 3-1 무한루프
do while문은 끝까지 읽어야만 무한 루프인지 알기 때문에 권장하지 않는다!
반응형
'Development > 알고리즘' 카테고리의 다른 글
| [ 백준 알고리즘 ] 10872번 팩토리얼 (JAVA) (0) | 2022.02.10 |
|---|---|
| [ 백준 알고리즘 ] 4153번 직각삼각형 (JAVA/python) (0) | 2020.08.10 |
| [ 백준 알고리즘 ] 3009번 네 번째 점 (JAVA/python) (0) | 2020.08.09 |
| [ 백준 알고리즘 ] 1085번 직사각형에서 탈출 (JAVA/python) (0) | 2020.08.05 |
| [ 백준 알고리즘 ] 9020번 골드바흐의 추측 (JAVA/python) (0) | 2020.07.31 |
