14.탐색 - 순차 탐색과 이진 탐색 / 문자열 순차 탐색 구현 / strcmp 함수 / 순차 탐색 / 이진 탐색 / 이진 탐색 구현

순차 탐색

순차 탐색(Sequential Search)은 특정한 원소를 찾기 위해 원소를 순차적으로 하나씩 탐색하는 방법이다.

찾을 문자열

깜보

인덱스	0	1	2	3	4
원소	코코	왕자	다롱	깜보	뽀랑

(인덱스 0부터 해당 원소를 찾을 때까지 하나하나 탐색한다.)

 

순차탐색은 데이터 정렬 유무에 상관 없이 가장 앞에 있는 원소부터 하나씩 확인해야 한다는 점에서 O(N)의 시간 복잡도를 가진다.

문자열 순차 탐색 구현

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define LENGTH 1000

char **array; //2차원 배열(2중 포인터)
int founded; //해당 값을 발견 했는지에 대한 정보

int main(void){
    int n; //전체 데이터 갯수
    char *word; //찾을 문자열
    word = malloc(sizeof(char)*LENGTH);
    scanf("%d %s", &n, word);
    array = (char**) malloc(sizeof(char*) * n ); //문자열들이 담겨 있는 배열
    for (int i = 0; i < n; i++){
        array[i] = malloc(sizeof(char*) * LENGTH); //문자열이 들어갈 공간 할당
        scanf("%s", array[i]); //하나씩 떼어서 저장
    }
    for (int i = 0; i < n; i++){
        if(!strcmp(array[i], word)){ //특정 원소를 찾은 경우
            printf("%d번째 원소입니다.\n", i+1);
            founded = 1;
        }
    }
    if (!founded) printf("원소를 찾을 수 없습니다/ \n");
    system("pause");
    return 0;
}

 

strcmp 함수

매개변수로 들어온 두개의 문자열을 비교해서, 문자열이 완전히 같으면 0을 반환하고, 그 외의 경우 음수나 양수를 반환하는 함수이다.

strcmp(str1, str2)
-> str1 < str2 인 경우 음수 반환
-> str1 > str2 인 경우 양수 반환
-> str1 == str2인 경우 0을 반환

strcmp함수는 두 문자를 아스키 코드로 비교하기 때문에,

1. 대소문자 구분
2. 대소비교

가 가능하다. 

 

이진 탐색

이진 탐색(Binary Search)은 배열 내부 데이터가 이미 정렬 되어 있는 상황에서 사용 가능한 알고리즘이다. 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징이 있다. O(logN)의 시간 복잡도를 가진다.

 

ex) 오름차순으로 정렬된 배열에서 찾을 원소 이진 탐색

 

이진 탐색은 위와 같이, 한번 확인할 때마다 봐야하는 원소의 갯수가 절반씩 줄어든다는 점에서 탐색 시간이 O(logN)의 시간복잡도를 가진다.

 

이진 탐색 구현 (정의 및 사용하기)

이진 탐색 정의

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define MAX_SIZE 100000

int a[MAX_SIZE];
int founded = 0;

int search(int start, int end, int target){
    if(start > end) return -9999;
    int mid = (start + end) / 2;
    if(a[mid] == target) return mid;
    else if (a[mid] > target) return search(start, mid - 1, target); //왼쪽 구간에 대해서 재귀적으로 탐색
    else return search(mid + 1, end, target); //오른쪽 구간에 대해서 재귀적으로 탐색
}

이진 탐색 사용하기

int main(void){
    int n, target; //원소 갯수 n, 찾을 원소 target
    scanf("%d %d", &n, &target);
    for(int i = 0; i < n; i++) scanf("%d",&a[i]);
    int result = search(0, n-1, target);
    if (result != -9999) printf("%d번째 원소입니다.\n", result + 1);
    else printf("원소를 찾을 수 없습니다.\n");
    system("pause");
    return 0;

 

요약

1. 순차탐색은 O(N)의 시간 복잡도를 가진다.
2. 이진탐색은 정렬이 된 상태에서만 사용가능하며, O(logN)의 시간복잡도를 가진다.(순차탐색 보다 좀 더 빠르다)