자료구조에 대한 기본적인 이해, 성능 분석

 

1-1 자료구조에 대한 기본적인 이해

첫번째 학습 목표

1. 구조체 정의 및 구조체 대상의 typedef 선언 가능

2. malloc과 free 사용을 통한 메모리 동적 할당 이해

3. 포인터 변수의 선언과 포인터 연산에 대한 거부감 없도록 함

4. 헤더파일에 대한 이해

5. #ifndef ~ #endif 이해

6. 둘 이상의 소스파일과 헤더파일에 나누어 담기

7. 재귀 함수 이해

자료구조란?

프로그램을 이루는 데이터의 표현, 저장과 데이터의 처리 중에서 '데이터의 표현, 저장'을 담당하는 것.

넓은 의미에서 보면 정수를 저장하기 위한 int형 변수와 구조체도 데이터를 표현 및 저장하는 하나의 방법으로 자료구조에 포함됨.

배열도 자료구조의 일종.

자료구조의 분류

선형구조(리스트, 스택, 큐)와 비선형구조(트리, 그래프)

파일구조(순차파일, 색인파일, 직접파일)과 단순구조(정수, 실수, 문자, 문자열)

보통 자료구조의 공부는 나란히, 일렬로 저장되는 선형구조와 그렇지 않은 비선형구조가 해당.

비선형구조의 트리, 그래프에서 파생되는 종류는 상당히 많고 비선형 자료구조에서 공부를 포기하는 경우가 많음.

알고리즘과의 차이는?

자료구조가 '데이터의 표현 및 저장방법'을 뜻한다면 알고리즘은 '문제의 해결 방법'

자료구조의 예시

1

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

cs

알고리즘의 예시

for(idx=0; idx<10; idx++)
    sum += arr[idx];

자료구조에 따라 알고리즘은 달리지고 알고리즘은 자료구조에 의존적.

서로 다른 과목이지만 매우 많은 연관성을 지님.

1-2 알고리즘의 성능분석 방법

시간 복잡도와 공간 복잡도

시간 복잡도 - 어떤 알고리즘이 어떠한 상황에서 더 빠르고 또 느린가?

공간 복잡도 - 어떤 알고리즘이 어떠한 상황에서 메모리를 작게 쓰고 또 많이 쓰나?

속도에 관한 것과 메모리의 사용량에 관한 것

일반적으로는 메모리의 사용량보다 실행속도에 초점.

알고리즘의 수행속도 평가에는 '연산의 횟수', '처리해야 할 데이터의 수 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() {
    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) 알고리즘

순차 탐색 알고리즘보다 좋은 성능.

먼저 이진 탐색을 적용하기 위해서는 배열이 정렬되어 있어야 한다.

#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;
        }
    }
    return -1;
}

int main() {
    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;
}

빅오 표기법

이름 그대로 큰 O라는 뜻에서 유래됨.

시간 복잡도 함수 T(n)에서 가장 큰 부분을 따지는 방식.

T(n)=n²+2n+1

위의 식이라면 근사치 식을 구성해도 문제가 되지 않음을 기인하여

T(n)=n²+2n

T(n)=n²

순으로 축소할 수 있다.

n²이 차지하는 비율이 매우 크기 때문.

단순하게 빅-오 구하기

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

ex)

T(n)=n²+2n+9 → O(n²)

T(n)=n⁴+n³+n²+1 → O(n⁴)

T(n)=5n³+3n²+2n+1 → O(n³)

대표적인 빅-오

O(1)

상수형 빅-오

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

연산의 횟수가 데이터 수에 상관없이 3회 진행되는 알고리즘일지라도 O(3)이 아닌 O(1)이라 표기.

O(log n)

로그형 빅-오

데이터 수의 증가율에 비해서 연산횟수의 증가율이 훨씬 낮은 알고리즘

매우 바람직한 유형

O(n)

선형 빅-오

데이터의 수와 연산횟수가 비례하는 알고리즘

O(n log n)

선형로그형 빅-오

데이터의 수가 두 배로 늘 때, 연산횟수가 두 배를 조금 넘게 증가하는 아고리즘

O(n²)

데이터 수의 제곱에 해당하는 연산횟수를 요구하는 알고리즘

이중 중첩된 반복문 내에서 알고리즘에 관련된 연산이 진행되는 경우

O(n³)

데이터 수의 세 제곱에 해당하는 연산횟수를 요구하는 알고리즘

삼중으로 중첩된 반복문 내에서 알고리즘에 관련된 연산이 진행되는 경우

O(2ⁿ)

지수형 빅-오

'지수적 증가'라는 연산횟수의 증가.

사용하기에 무리가 있고 사용하는 것 자체가 비현실적인 알고리즘.

이진 탐색 알고리즘의 비교연산 횟수 확인

#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() {
    int arr1[500] = {0,}; // 모든 요소 0으로 초기화
    int arr2[5000] = {0,};
    int arr3[50000] = {0,};
    int idx;

    // 배열 arr1을 대상으로, 저장되지 않은 정수 1을 찾으라고 명령
    idx = BSearch(arr1, sizeof(arr1)/sizeof(int), 1);
    if(idx == -1)
        printf("탐색 실패\n");
    else
        printf("타겟 저장 인덱스: %d\n", idx);

    // 배열 arr2를 대상으로, 저장되지 않은 정수 2를 찾으라고 명령
    idx = BSearch(arr2, sizeof(arr2)/sizeof(int), 2);
    if(idx == -1)
        printf("탐색 실패\n");
    else
        printf("타겟 저장 인덱스: %d\n", idx);

    // 배열 arr3을 대상으로, 저장되지 않은 정수 3을 찾으라고 명령
    idx = BSearch(arr3, sizeof(arr3)/sizeof(int), 3);
    if(idx == -1)
        printf("탐색 실패\n");
    else
        printf("타겟 저장 인덱스: %d\n", idx);
  
    return 0;
}

#	순차 탐색 연산횟수	이진 탐색 연산횟수
500	500	9
5,000	5,000	13
50,000	50,000	16