[c] 자료구조와 알고리즘의 이해

자료구조

데이터의 표현 및 저장방법

알고리즘

표현 및 저장된 데이터를 대상으로 하는 문제 해결 방법

 

알고리즘을 평가하는 두가지 요소

• 시간 복잡도(time complexity) : 속도
• 공간 복잡도(space complexity) : 메모리 사용량

보통은 수행 속도를 우선을 본다.

수행 속도가 빠르다는 것을 판단하기 위해 연산 횟수를 보는데, 연산을 적게 수행할 수록 좋은 알고리즘이다.

특히 값을 비교하는 == 연산, 즉 비교연산 수행횟수가 적은 것이 좋다. (타 연산은 == 연산에 의존적)

 

알고리즘의 성능을 판단하는데 있어 중요한 것은 최악의 경우이다. (평균적인 경우를 계산하기 쉽지 않기 때문)

 

순차 탐색(Linear Search) 알고리즘

맨 앞부터 순서대로 탐색을 진행하는 알고리즘

#include <stdio.h>

int LSearch(int ar[], int len, int target){
	int i;
    for(i=0; i<len; i++){
    	if(ar[i] == target)
    		return i;
    }
    return -1;
}

int main(void){
	int arr[] = {3,5,2,4,9};
    int idx;
    
    idx = LSearch(arr, sizeof(arr)/sizeof(int),4);
    if(idx == -1)
    	printf("탐색실패\n");
    else
    	printf("타겟 저장 인덱스 : %d\n", idx);
        
    idx = LSearch(arr, sizeof(arr)/sizeof(int),7);
    if(idx == -1)
    	printf("탐색 실패\n");
    else
    	printf("타겟 저장 인덱스: &d\n", idx);
        
    return 0;
 }

 

이진 탐색(Binary Search) 알고리즘

배열에 저장된 데이터가 정렬되어 있을 때만 사용 가능하다,

다음은 실행예제이다.

 

다음과 같은 배열이 있다. 숫자 3이 저장되어 있는지 확인하기 위한 이진탐색 알고리즘을 적용해보겠다.

1	2	3	7	9	12	21	23	24
idx0	idx1	idx2	idx3	idx4	idx5	idx6	idx7	idx8

 

1. 배열 인덱스의 시작과 끝은 각각 0,8이다.
2. 0과 8을 합하여 그 결과를 2로 나눈다
3. 2로 나눠서 얻은 결과 4를 인덱스 값으로 하여 arr[4]의 저장된 값이 3인지 확인한다

 

1	2	3	7	9	12	21	23	24
arr[0]	arr[1]	arr[2]	arr[3]	arr[4]	arr[5]	arr[6]	arr[7]	arr[8]

 

1. arr[4]의 저장된 값 9와 탐색 대상인 3을 비교한다
2. 대소의 비교결과는 arr[4]>3이므로 탐색 범위를 인덱스 기준 0~3으로 제한한다
3. 0과 3을 더한 결과를 2로 나눈다. 나머지는 버린다.
4. 2로 나눠서 얻은 결과가 1이니 arr[1]에 저장된 값이 3인지 확인한다.

 

1	2	3	7	9	12	21	23	24
arr[0]	arr[1]	arr[2]	arr[3]	arr[4]	arr[5]	arr[6]	arr[7]	arr[8]

 

1. arr[1]의 저장된 값 2와 탐색 대상인 3을 비교한다
2. 대소의 비교결과는 arr[1]<3이므로 탐색 범위를 인덱스 기준 2~3으로 제한한다
3. 2과 3을 더한 결과를 2로 나눈다. 나머지는 버린다.
4. 2로 나눠서 얻은 결과가 2이니 arr[2]에 저장된 값이 3인지 확인한다.

 

1	2	3	7	9	12	21	23	24
arr[0]	arr[1]	arr[2]	arr[3]	arr[4]	arr[5]	arr[6]	arr[7]	arr[8]

 

이렇듯 이진 탐색 알고리즘은 탐색의 대사을 반복해서 반씩 떨구어 내는 알고리즘이다.

시작위치의 인덱스값이 마지막 인덱스값보다 큰경우 탐색이 종료되며, 이렇게 종류된 경우 탐색에 실패했음을 뜻한다.

 

#include <stdio.h>

int Bsearch(int ar[], int len, int target){
	int first =0;
    int last = len-1;
    int mid;
    
    while(first<=last){
    	mid = (first+last)/2;
        
        if (target == ar[mid]){
        	return mid;
        }
        else{
        	if(target <ar[mid])
            	last = mid-1;
            else
            	first = mid+1;
                //mid 값을 제외시키기 위함
        }
    }
    return -1;
}

int main(void){
	int arr[] = {1,3,5,7,9};
    int idx;
    
    idx = BSearch(arr, sizeof(arr)/sizeof(int),7);
    if(idx == -1)
    	printf("탐색실패\n");
    else
    	printf("타겟 저장 인덱스 : %d\n", idx);
        
    idx = BSearch(arr, sizeof(arr)/sizeof(int),4);
    if(idx == -1)
    	printf("탐색 실패\n");
    else
    	printf("타겟 저장 인덱스: &d\n", idx);
        
    return 0;
 }

 

빅-오 표기법(Big-Oh Notation)

시간복잡도 함수 T(n)을 구했을때, 가장 영향력 있는 부분만 사용하는 것을 말한다.

다항식일 경우 최고차항의 차수가 빅-오가 된다.

 

대표적인 빅-오

• O(I)

상수형 빅-오. 데이터 수에 상관없이 연산횟수가 고정인 유형의 알고리즘.

• O(log n)

로그형 빅-오. '데이터 수의 증가율'에 비해 '연산횟수의 증가율'이 훨씬 낮은 알고리즘. 가장 바람직한 유형.

로그의 밑의 차이는 미미하기 때문에 대부분 무시.

• O(n)

선형 빅-오. 데이터수와 연산횟수가 비례하는 알고리즘.

• O(n log n)

선형로그형 빅-오. 데이터의 수가 두배 늘때, 연산횟수는 두 배 조금 넘게 증가하는 알고리즘.

• O(n^2)

데이터 수의 제곱에 해당하는 연산횟수를 요구하는 알고리즘.중텁된 반복문이 사용될 때 발생하며 데이터 양이 많을 때 사용하기 부적절.

• O(n^3)

데이터 수의 세제곱에 해당하는 연산횟수를 요구하는 알고리즘. 삼중으로 중첩된 반복문이 사용될때 발생하며 위와 동일.

• O(2^n)

지수형 빅-오. 사용하는 것 자체가 비현실적인 알고리즘. 매우 무서운 연산횟수의 증가로 추천하지 않음.

 

성능의 대소비교

O(I) < O(log n) < O(n) < O(n log n) < O(n^2) < O(n^3) < O(2^n)