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

Tae_Tae·2024년 7월 3일

알고리즘 자료구조

자료구조 / 알고리즘 (C)

목록 보기

1/29

알고리즘의 비교 방법

어떤 알고리즘이 더 성능이 좋은 알고리즘임을 평가하는 두 가지요소가 있는데

시간 복잡도(time complexity) : 어떤 알고리즘의 실행속도가 더 빠른가
공간 복잡도(space complexity) : 어떤 알고리즘이 메모리를 적게쓰는가

일반적으로 알고리즘을 평가할 때는 실행속도에 초점을 맞춘다.

알고리즘의 수행속도를 평가하는 방법

연산 횟수를 체크
처리할 데이터 수 n에 대한 연산횟수의 함수 T(n)을 구성한다.

중요한 것은 데이터의 수가 많아짐에 따라 연산횟수의 증가 정도에 있다.

(하지만 상황마다 선호되는 알고리즘은 다르다.)

순차 탐색(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;
}

실행결과

타겟 저장 인덱스 : 3
탐색 실패

순차 탐색 알고리즘을 실제로 구현하는 코드만 별도로 체크해보면

for (i = 0; i < len; i++)
{
	if(ar[i] == target)
    	return i;
}

위 코드의 시간 복잡도를 분석해서 데이터 수 $n$ 에 대한 연산횟수의 함수 $T(n)$ 을 구해보자

먼저 연산 횟수의 함수이니 연산자를 체크해야하는데 위 코드에서는 $==$ 이다.

(if안의 조건문이 한번에 true면 한번에 끝나지만 false면 계속 계속 for문이 끝까지 돌기 때문에 $==$ 에 다른 연산자 (<, ++)의 실행 횟수가달려있다.)

순차 탐색 알고리즘의 시간 복잡도 함수

이때 알고리즘의 성능을 판단하는데 있어서 중요한 것은 최악의 경우(worst case)이다.

순차 탐색 알고리즘의 시간 복잡도 (최악의 경우)를 계산하면되는데

순차 탐색이므로 n개의 데이터중 n번째까지 모두 탐색하는 경우이므로
$T(n) = n$ 이다.

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

이진 탐색 알고리즘을 사용하려면 배열에 저장된 데이터는 정렬되어 있어야한다.

한줄로 얘기하면 탐색의 대상을 반복해서 반씩 떨구어 내는 알고리즘이다.

예시로 이러한 array가 있다고 해보자

int ary[10] = { 1,2,3,4,5,6,8,9 };

배열의 시작과 끝은 0과 8이다. (ary[0] / ary[8])

첫 번째 시도
시작과 끝 / 2를 하여 나온 결과(ary[4])가 target 값인지 확인

if true => 탐색 끝
else (false인 경우) => 다시 한번 이진 탐색

일단 첫번째 시도에서 찾은 ary[4]의 값을 target 값과 비교해본다.

if ary[4] > target 탐색 범위는 ary[0] ~ ary[3]
else if ary[4] < target 탐색범위는 ary[5] ~ ary[8]

각각 좁혀진 탐색범위의 시작값 + 끝값 / 2 = x를 진행하고, 나머지는 버린다.

ary[x]를 확인해본다.

만약에 두번째 시도도 실패하면 세번째, 네번째 계속 같은 방법으로 반복한다.

LSearch 부분을 BSearch로 바꿔 구현해본 코드

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 (mid == target)
        {
        	return mid;
        }
        else
        {
        	if (target < ar[mid]) 
            	last = mid - 1;
            else
            	first = mid + 1;
        }
    }
    return -1;
}

첫 번째 시도에 target값을 구하지 못했을 경우 first 또는 last 값을 수정하는데 mid - 1 or + 1을 해주는 이유는 이미 첫 번째 시도에 mid값을 체크했으니 중복 검사를 피하기 위함이다.

first <= mid <= last이렇게 값이 있어야하는데 연산이 mid에 저장된 값을 가감없이 first또는 last에 넣으면 first에 저장된 값이 last보다 커질 수 없으므로 무한루프에 빠지게 된다.

이진 탐색 알고리즘의 시간 복잡도 함수

$T(n) = log_2n$

어떻게 위 함수를 방법은

let 데이터 수 = n
n이 1이 되기까지 2로 나눈 횟수 k
데이터가 1개 남았을 때, 마지막으로 비교연산 1회 진행

T(n) = k + 1이므로 k를 구해야한다.
n X (1/2)^k = 1 으로 나타낼 수 있고 k에 관한 식으로 정리하면
n X 2^-k => n = 2^k => (양변에 log2 (k에 대한 식으로 나타내야하므로))
=> log2n = log22^k => log2n = k 가 나오게 된다.

정확히 하면 $T(n) = log_2n + 1$ 일텐데 +1은 중요하지 않아서 생략해도 된다.

그러면 어떤 건 생략해도 되고 어떤건 생략해도 안되냐라고 의문이 들 수 있는데

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

$T(n) = n^2 + 2n + 1$ 이라는 시간복잡도 함수가 있다고 하자

이 함수를 근사치(approximation) 식으로 구성해도 문제가 되지 않는데

n	n^2	2n	T(n)	n^2의 비율
10	100	20	120	83.33%
100	10,000	200	10,200	98.04%
1,000	1,000,000	2,000	1,002,000	99.80%
100,000	10,000,000,000	200,000	10,000,200,000	99.99%

위 표를 보면 $n^2$ 이 차지하는 비율이 절대적이다.
그래서 위 함수 $T(n)$ 을 빅-오 표기법으로 표현하면

$O(n^2)$ 이고

이를 빅-오 오브 $n^2$ (Big-Oh of $n^2$ ) 라고 읽는다.

단순하게 빅-오를 구하는 방법은

$T(n)$ 이 다항식으로 표현된 경우, 최고 차항이 빅-오가 된다.

대표적인 빅-오 표기

$O(1)$ : 상수형 빅-오
데이터 수에 상관 없이 연산횟수가 고정인 유형의 알고리즘
3회 진행되는 알고리즘일지라도 $O(3)$ 이 아니라 $O(1)$ 이라고 한다.
$O(logn)$ : 로그형 빅-오
'데이터 수의 증가율'에 비해서 '연산횟수의 증가율'이 훨씬 낮은 알고리즘
$O(n)$ : 선형 빅-오
데이터의 수와 연산횟수가 비례하는 알고리즘을 의미
$O(nlogn)$ : 선형로그형 빅-오
데이터의 수가 두 배로 늘 때, 연산횟수는 두 배를 조금 넘게 증가하는 알고리즘
$O(n^2)$ : 데이터 수의 제곱에 해당하는 연산횟수를 요구하는 알고리즘
이중으로 중첩된 반복문 내에서 앍고리즘 관련 연산이 진행되는 경우에 발생한다.
$O(n^3)$ : 데이터 수의 세 제곱에 해당하는 연산횟수를 요구하는 알고리즘
삼중으로 중첩된 반복문 내에서 앍고리즘 관련 연산이 진행되는 경우에 발생한다.
$O(2^n)$ : 지수형 빅-오
사용한다는 것이 비현실적인 알고리즘이다. 연산횟수가 '지수적 증가'로 되기 때문이다.

위에 있는 빅-오 표기법들의 대소관계를 정리하면

$O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)$

순차 탐색 알고리즘과 이진 탐색 알고리즘의 비교

$T(n) = n$
순차 탐색 알고리즘의 $T(n)$
$T(n) = log_2n+1$
이진 탐색 알고리즘의 $T(n)$

빅-오 표기법으로 표기하면

$O(n)$
$O(log_2n)$

이진 탐색 트리가 성능이 더 좋다고 할 수 있다.

코드로 확인해보면

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int Bsearch(int ar[], int len, int target)
{
    int first = 0;
    int last = len-1;
    int mid;
    int opCount = 0;

    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;
            }
            opCount += 1;
        }
    printf("비교연산횟수 : %d \n", opCount);
    return -1;
}

int main(void)
{
    int arr1[500] = {0, };
    int arr2[5000] = {0, };
    int arr3[50000] = {0, };
    int idx;

    idx = Bsearch(arr1, sizeof(arr1)/sizeof(int), 1);
    if (idx == -1)
        printf("탐색 실패 \n\n");
    else
        printf("타겟 저장 인덱스 : %d \n", idx);

    idx = Bsearch(arr2, sizeof(arr2)/sizeof(int), 2);
    if (idx == -1)
        printf("탐색 실패 \n\n");
    else
        printf("타겟 저장 인덱스 : %d \n", idx);

    idx = Bsearch(arr3, sizeof(arr3)/sizeof(int), 3);
    if (idx == -1)
        printf("탐색 실패 \n\n");
    else
        printf("타겟 저장 인덱스 : %d \n", idx);    

    return 0;
}