[열혈자료구조] 1강. 자료구조와 알고리즘의 이해

* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다.

자료구조 vs 알고리즘

자료구조: 데이터의 표현 및 저장 방법
알고리즘: 표현 및 저장된 데이터를 대상으로 하는 문제의 해결방법
 
즉 데이터 자체를 다루는 것이 자료구조, 데이터를 가지고 문제를 해결하는 것이 알고리즘이다.
 
ex)
자료구조의 예시: 배열의 선언

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

 
알고리즘의 예시: 반복분의 구성

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

 

---

알고리즘의 성능 분석

시간 복잡도: "속도". 알고리즘을 시행하는 데 시간을 얼마나 쓰는가?
공간 복잡도: "메모리". 알고리즘을 시행하는 데 얼마나 많은 메모리를 잡아먹는가?
 
인공지능 연구할 때도 CPU를 GPU로 바꾸어 트레이닝하면 시간 복잡도를 개선할 수 있지만, 공간 복잡도를 개선하기 위해서는 RAM(메모리)을 건드려야 한다.
 
시간 복잡도는 데이터의 수 n에 대한 연산횟수 함수 T(n)을 잡아 계산한다. 이를 이용해 n=N 이하에서는 알고리즘 A, n=N 초과에서는 알고리즘 B를 사용하는 등 최적의 방법을 사용할 수 있다. 이전 포스팅에서 다루었던 선형 탐색(linear search)를 C언어로 구현해 보자.
https://cascade.tistory.com/62

탐색 알고리즘 (백준 1920번)

 
C언어 개발환경을 로컬에 세팅하기 귀찮아서 일단은 온라인 C 컴파일러(https://www.programiz.com/c-programming/online-compiler/)를 쓰기로 했다. 윤성우의 열혈 자료구조 교재가 전부 C로 되어 있어서, 하다가 불편하면 세팅하는 걸로...
 

#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("search failed\n");
    else
        printf("target index: %d\n", idx);
    idx = LSearch(arr, sizeof(arr)/sizeof(int), 7);
    if(idx == -1)
        printf("search failed\n");
    else
        printf("target index: %d\n", idx);
    return 0;
}

 
출력은 이런 식으로 나온다.
 

 
이 알고리즘은 <, ++, == 의 연산자를 사용했는데, 시간 복잡도를 계산하고자 한다면 어떤 연산의 횟수를 세야 하는가? 답은 "==" 이다. 탐색 알고리즘의 다른 연산은 모두 ==에 의존적이기 때문에, ==만 세면 된다. 만약 우리가 찾는 target이 arr의 가장 앞에 있다면(best case) 1번만에 끝나겠지만, 가장 뒤에 있다면(worst case) n번만에 끝날 것이다. 일반적으로 알고리즘을 평가할 때 best case는 다루지 않는다. 또한 average case는 계산하기 까다롭다. 따라서, 알고리즘 평가를 할 때는 일반적으로 worst case로 평가한다. 이 알고리즘에서 worst case를 사용한 연산횟수 함수 T(n) = n이 된다.
 
또한, 이진 탐색 알고리즘에서의 T(n)은 얼마가 될까?(이건 굳이 구현하지 않겠다) worsk case는 데이터를 계속 반으로 쪼개고, 더 이상 쪼갤 수 없을 때까지 쪼갰을 때 서칭이 끝나는 경우이다. 즉 데이터 수를 쪼개고 쪼개고 쪼개서 하나만 나맜을 때 2로 나눈 횟수를 k라고 했을 때, 마지막 비교연산까지 고려하면 T(n) = k+1이 된다. 이때 k를 계산해 보면,

가 되므로 T(n) = log_2_n 이 된다. 여기서 k+1에서의 1은 중요하지 않은 게, 데이터 수가 증가했을 때 연산횟수의 변화 정도에 영향을 못 미치므로 무시해도 된다.
 

Big-O notation

모든 알고리즘에서 데이터 수 n에 대한 T(n)을 계산하는 것은 쉽지 않기 때문에, Big-O notation을 이용하여 최고차항만 남기고 나머지 항들을 다 날려버릴 수 있다. 즉, T(n) = n^2 + 2n + 1인 경우 O(n) = n^2이다.
 
대표적인 Big-O에는 O(1), O(log n), O(n), O(nlog n), O(n^2), O(n^3), O(2^n) 등이 있다. 뒤로 갈수록 시간적으로 무거운 알고리즘인데, O(2^n) 같은 것들은 사용하기 비현실적이므로 다른 알고리즘으로 바꿔야 한다.