[C++ STL] C의 선형 검색

[C++ STL] C의 선형 검색

선형적인 구간에 대해 작동하는 알고리즘의

중요한 아이디어에 대해 이야기해보자.

선형적인 구간이란, 하나의 첫 번째 요소와 하나의 마지막

요소가 존재하며, 마지막 요소를 제외한 모든 요소들에는 '그 다음 요소'가 있고,

첫 번째 요소에서 시작해서 다음 요소들을 계속 따라가다 보면 마지막 요소에

도달하게 되는 1차원적인 요소들의 모음을 말한다. 이러한 선형적인 구간들에

대해 작동하는 알고리즘들이 STL의 핵심부를 이루고 있다.

C의 선형 검색

C의 라이브러리 함수 strchr을 보도록 하자.

char* strchr(char* s, int c);

char* strchr( char* s, int c){

while ( *s != '\0' && *s != c)

++s;

return *s == c ? s : (char*) 0;

}

선형 검색의 일반적인 아이디어는

1. 순차열의 시작에서부터 요소 하나씩 거쳐가면서 주어진 값다 비교한다

2. 현재 요소가 주어진 값과 같으면, 알고리즘은 순차열 안에서의 현재 요소를 리턴

3. 같지 않다면 다음 요소로 넘어간다.

4. 다음 요소가 없다면 실패했음을 알리는 뭔가를 리턴

이러한 선형 검색을 구현할 때에는 몇 가지 이슈가 있다.

1. 검색하고자 하는 순차열을 어떻게 지정할 것인가?

2. 순차열 안의 한 위치를 어떻게 표현할 것인가?

3. 다음 요소로 넘어가려면 어떻게 할 것인가?

4. 순차열의 끝에 도달했음을 어떻게 알아낼 것인가?

5. 실패했음을 알리는 값으로 무엇을 사용할 것인가?

1. ctrchr 함수를 호출할 때 검색할 문자열의 첫 번째 요소를

가리키는 포인터를 넘겨준다.

2. 문자열 안의 한 위치 또한 포인터로 나타낸다.

3. 포인터 연산을 통해 접근한다.

4. 검색할 순차열은 하나의 C문자열, 즉 널로 끝나는 문자열이다.

때문에 현재 포인터가 \0을 가르킨다면 끝에 도달한 것

5. 선형 검색을 하는 동안 해당 문자를 찾지 못했다면

포인터는 문자열의 끝에 가 있을 것이므로 널 포인터를 리턴.

하지만 strchr은 일반적이지 않다. 이 함수는 char들의 배열 안에서

하나의 char를 검색하는 데에만 사용할 수 있다.

그리고, strchr의 첫 번째 인수는 널 종료 문자 배열을 가리키는

하나의 포인터이어야 하는데, 이는 보기보다 일반적이지 않다.

C에서는 널 종료 문자열이 대부분이긴하지만 부분문자열을

표현하려한다면 문제각 생기는 것도 사실이다.

부분 문자열을 지원하기 위해 strchr의 인터페이스를 수정해보자.

검색할 배열의 끝을 가리키는 포인터를 또 다른 인수로 지정해 보자.

char* find1 (char* first, char* last, int c){

while (first != last && *first != c)

++first;

return first;

}

이 find1 구현은 배열의 끝을 루프 반복의 종료 조건으로 해서

포인터로 배열을 훑는, 흔히 볼 수 있는 C관용구를 이용한다.

이 루프는 first가 last와 같으면 즉시 끝나며, 따라서 last는

역참조 되지 않는다. 즉, last 바로 전까지 모든 요소를 검색한다.

위의 함수에서는 3가지 포인터들이 사용된다.

1. 역참조할 수 있는 보통의 포인터

2. NULL 같은 유효하지 않은 포인터

3. 역참조할 수 없지만 포인터 산술에 사용할 수 있는 끝을 넘어선 포인터

char A[N];

C의 모든 배열에는 끝을 넘어선 포인터가 하나 존재한다. (A+N)

아무것도 가리키지 않기 때문에 역참조해서는 안되며,

딱 하나만 있으므로 포인터를 증가시키려 해서도 안된다.

오직 포인터 산술 연산에만 사용된다. (시작 이전 포인터 같은 것은 없다. A-1과 같은 ... )