Page 102 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

보충수업 3-1 무한 루프의 구현

실습 3-1의 while문은 ‘무한 루프’ 구조를 이루고 있습니다. 이 구조는 무한하게 반복하는 구조를 이
루고 있지만 break문이나 return문을 사용하면 루프에서 빠져나올 수 있습니다. 무한 루프는 아래와
같이 구현됩니다.
for문은 반복을 계속할지를 판단하는 제어식을 생략하면 1이 지정된 것으로 봅니다.

while(1) { for(; ; ) { do {
/*… 중략 …*/ /*… 중략 …*/ /*… 중략 …*/
} } } while(1);

우리는 보통 코드를 위에서 아래로 읽습니다. 그래서 while문과 for문은 첫 번째 행만 읽어도 무한 루
프인지 알 수 있습니다. 반면에 끝까지 읽지 않으면 무한 루프인지 아닌지 알 수 없는 do문에 의한 무
한 루프 구현은 권장하지 않습니다.

보초법

선형 검색은 반복할 때마다 다음의 종료 조건 ①과 ②를 모두 체크합니다. 단순한 판단이라고
생각할 수 있지만 ‘티끌 모아 태산’이라는 말이 있듯이 종료 조건을 검사하는 비용은 결코 무

시할 수 없습니다.

① 검색할 값을 발견하지 못 하고 배열의 끝을 지나간 경우
② 검색할 값과 같은 요소를 발견한 경우

이 비용을 반(50%)으로 줄이는 방법이 보초법(sentinel method)입니다. 앞에서 살펴본 그림
3-2와 그림 3-3의 검색을 보초법에 따라 수행하는 모습을 그림 3-4에 나타냈습니다.

102 C 알고리즘