자료구조와 알고리즘에 대한 기본적인 이해

자료구조와 알고리즘에 대한 기본적인 이해 

자료구조, 알고리즘이란 무엇인가?

 

우선 자료구조를 정말 간단하게 말하자면 데이터를 표현하고 저장하는 방법이다.

그리고 크게 이 방법을 두 가지로 나눈다.

1. 선형 구조 : 데이터를 선의 형태로 나란히 혹은 일렬로 저장하는 방식(리스트, 스택, 큐)

2.비선형 구조 : 데이터를 나란히 저장하지 않는 구조 (트리, 그래프)

 

자료구조가 '데이터의 표현 및 저장 방법'을 뜻한다면,

알고리즘은 표현 및 저장된 데이터를 대상으로 하는 '문제의 해결 방법'을 뜻한다. 

 

숫자 데이터를 가지고 있는 배열을 예로 들자면, 

• 자료구조적 측면 :  int arr[10] = {1,2,3,4,5,6,7,8,9,10};

• 알고리즘적 측면 :

 

for(idx = 0; idx = 10; idx++){

sum += arr[idx];

}

 

알고리즘의 성능 분석 방법

우리는 잘 동작하는 것은 물론이거니와 좋은 성능까지 보장받기를 원한다. 때문에 자료구조와 알고리즘을 분석하고 평가할 수 있어야 한다.

- 시간 복잡도(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;

}

 

 

for(i=0; i<len; i++)

{

if(ar[i]==target)

return i;    // 찾은 대상의 인덱스 값 반환

}

 

그러면 "어떠한 연산을 적게 수행하는 탐색 알고리즘이 좋은 탐색 알고리즘일까?"

==> 값의 동등을 비교하는 ==연산을 적게 수행하는 탐색 알고리즘이 좋은 탐색 알고리즘이다.

 

비교 연산의 수행횟수에 따라 < 연산과 ++ 연산의 수행 횟수가 줄어들기도 늘어나기도 한다.

따라서 우리는 ==연산의 횟수를 대상으로 시간 복잡도를 분석하면 된다. 

 

 

- 순차 탐색 알고리즘의 시간 복잡도 계산하기 1: 최악의 경우(worst case)

찾고자 하는 값이 배열의 맨 마지막에 저장되어 있거나 찾고자 하는 값이 아예 저장되어 있지 않으면 비교 연산의 수행 횟수는 n이 된다.

알고리즘을 평가하는데 '최선의 경우'는 관심대상이 아니다. 알고리즘의 성능을 판단하는 데 있어서 중요한 것은 '최악의 경우'이다. 

데이터의 수가 n개일 때, 최악의 경우에 해당하는 연산 횟수는 (비교연산횟수는 ) n이다.

T(n) = n 최악의 경우를 대상으로 정의한 함수 T(n)

 

- 순차 탐색 알고리즘의 시간 복잡도 계산하기 2 : 평균적인 경우(average case)

평균적인 경우의 연산횟수 계산을 위해서 다음과 같이 두 가지 가정을 하겠다.

• 가정 1. 탐색 대상이 배열에 존재하지 않을 확률을 50%라고 가정한다.
• 가정 2. 배열의 첫 요소부터 마지막 요소까지, 탐색 대상이 존재할 확률은 동일하다. 

그럼 배열에 탐색 대상이 존재하는 경우와 존재하지 않는 경우를 나눠서 연산 횟수를 계산해보자.

• 탐색 대상이 존재하지 않는 경우의 연산횟수 = n
• 탐색 대상이 존재하는 경우의 연산횟수 = n/2

탐색 대상이 배열에 존재하지 않는 경우와 존재하는 경우의 확률이 각각 50%이니 

n* 1/2 + n/2 * 1/2 = 3n/4 (1/2씩 곱해서 더한 이유는 탐색 대상이 존재하지 않을 확률과 존재할 확률이 각각 50%이기 때문이다.)

==> 최악의 경우에 비해서 상대적으로 시간 복잡도를 구하는 것이 쉽지 않다. 또한 프로그램의 성격에 따라서 배열에 탐색 대상이 존재할 확률은 50%보다 높을 수도 있고 낮을 수도 있다. 그렇기에 이 계산은 '최악의 경우'의 시간 복잡도 보다 신뢰도가 낮다.