[알고리즘] 보초법(sentinel method)이란?

 

 

선형검색을 할 때,

결과는 두 가지다.

 

1. 원하는 값을 찾았는가?

2. 원하는 값을 못 찾았는가?

 

그래서 if문도 두 가지다.

 

//검색 시작
for(int i =0; i<array.length;i++) {

            // 1. 검색 결과를 찾았는가?
			if(array[i]== search) {
				System.out.println(search + "를 찾았습니다.");
				break;
			}

			// 2. 검색결과를 못 찾고 끝에 도달했는가?
			if(i==array.length-1) {
				System.out.println(search + "를 못 찾았습니다.");
			}
		}

 

if문을 두 개를 썼다.

반복을 10번 했다면

판단을 최대 20번 한 것이다.

 

만약 if를 한 번으로 줄일 수 있다면

판단 횟수는 절반으로 줄어들 것이다.

 

이것이 바로 보초법이다.

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		Scanner scan = new Scanner(System.in);
		System.out.println("원하는 데이터 수를 입력해주세요. : ");
		int input = scan.nextInt();
		int i;
		
		//방 하나를 더 만든다. input + 1
		int[] array = new int[input+1];
		
		System.out.println("1~10사이 검색할 수를 입력해주세요 : ");
		int search = scan.nextInt();
		
		// 1~20사이의 랜덤 숫자를 배열에 저장
		for(i =0; i<array.length;i++) {
			array[i] = (int)(Math.random()*20);
		}
		
		//보초값 넣어주기;
		array[input] = search;
		
		//검색 시작
		for(i =0; i<array.length;i++) {
            // 1. 검색 결과를 찾았는가? (if문 1개만 반복)
			if(array[i]== search) {
				break;
			}
		}
		
		//검색결과 출력
		if(i==input) {
			System.out.println(search + "를 못 찾았습니다.");
		}
		else {
			System.out.println(search+"를 찾았습니다.");
		}
	}
}

 

배열을 생성할 때 끝에 방 하나를 더 생성한다. 그리고 그곳에 원하는 검색 결과를 넣어준다. 이것을 보초값이라고 한다.

 

그렇다면 반복문의 if문은 1개로 줄어든다.

 

 

원하는 검색 결과를 찾았는가?

 

 

보초값을 넣어주었기에 당연히 원하는 검색결과를 찾게 된다. 그러니 결과는 둘 중 하나다.

 

1.인덱스(i)가 배열의 끝이냐?

2. 인덱스(i)가 배열의 끝이 아니냐?

 

 

배열의 끝이라면 보초값을 의미하므로 검색되지 않는 것이다. 그러므로 검색이 실패했음을 의미한다. 배열의 끝이 아니라면, 보초값 외에 다른 값도 존재한다는 의미이므로 검색이 성공했음을 의미한다.

 

---

 

정리

 

보초법을 사용하지 않으면, 반복을 100번 했을 시, if문이 2개이니 최대 200번의 판단을 하게 된다. 반대로 보초법을 사용하면 if문이 1개이니, 절반인 100번의 판단만 한다. 그리고 마지막 인덱스 판단까지 합하여 최대 총 101번의 판단만 하면 된다. 이렇듯 보초법은 선형검색 시, 검색효율을 1.5배 끌어 올릴 수있다.