순차탐색
원하는 값이 존재하는 지 확인을 하기 위해 배열의 앞에서부터 뒤까지 탐색하는 과정이다. 값이 존재한다면 그 위치를, 없다면 -1을 반환한다.
int SequentialSearch(int *arr, int n, int x) {
for (int i = 0; i < n; i++) {
if (arr[i] == x) {
return i;
}
}
return -1;
}
배열의 정렬 시 순차탐색의 효율성
배열이 정렬되어 있는 경우에 순차탐색을 더욱 빠르게 할 수 있다. 목표 값을 찾는 경우에 배열의 순회를 중단할 수 있기 때문이다.
활용: 값의 개수 세기
값의 개수를 셀 때 배열을 정렬한 후에 순차탐색을 하는 것이 효율적이다.
int SequentialSearch(int *arr, int n, int x) {
for (int i = 0; i < n; i++) {
if (arr[i] == x) {
return i;
}
}
return -1;
}
int SortedCountHelper(int *arr, int n, int x, int start) // start 사용
{
int count = 0;
for (int i = start; i < n; i++) {
if (arr[i] != x) {
break;
}
count += 1;
}
return count;
}
int SortedCount(int *arr, int n, int x) {
InsertionSort(arr, n); // 배열 정렬
int i = SequentialSearch(arr, n, x); // x의 첫번째 위치 반환
if (i >= 0)
return SortedCountHelper(arr, n, x, i + 1) + 1; // 다음 위치부터 갯수 세기
else
return 0;
}
활용: 문자열 압축문제
문자열이 주어졌을 때 문자 하나당 개수만큼 붙여서 변환하는 문제다. 문자열 전체를 순회하면서 문자 하나하나의 개수를 세야한다. 성능을 위해 문자열을 정렬한 후에 문자열을 순회하면서 문자가 변할 때마다 지정을 하고 개수를 세는게 좋다.
void compress_string(char *arr, int n) { // arr은 문자열, n은 문자열의 크기
InsertionSort(arr, n); // 문자열 정렬
cout << arr << endl;
char c = arr[0]; // 첫번째 글자부터 시작
int count = 1; // 1부터 셈
cout << c;
for (int i = 1; i < n; i++) {
if (arr[i] == c) {
count += 1;
} else {
cout << count;// 결과 출력
c = arr[i]; // 문자 갱신
count = 1; // 다시 1부터 시작
cout << c; // 문자 출력
}
}
cout << count << endl; // 마지막 count 출력
}