(자료구조 강의) Chapter 01 - 자료구조를 공부하는 이유

자료구조 꼭 배워야 할까?

❝ 자료구조 몰라도 프로그램 만드는 데 문제 없던데요? ❞

네 맞아요, 자료구조를 몰라도 프로그램을 만드는 데 문제가 없어요.

어 그럼 안배워도 되냐구요? 나 혼자 쓰는 프로그램이나 처리할 데이터양이 적은 프로그램만 만들거라면 안배워도 됩니다.

하지만 우리는 개발자가 되고 싶은 거고, 기업에 들어가거나 창업을 해서 많은 사람들이 사용하고 싶어하는 프로그램을 만들고 싶잖아요.

기껏 만든 프로그램이 사용자가 한 번에 몰려서 서버가 터져버리거나 간단한 데이터 처리를 하는데 10초 이상이 걸리면 아무도 그 프로그램을 쓰고 싶지 않을거에요.

자료구조와 알고리즘을 적절히 활용하여 프로그램을 만들면 성능을 더 좋게 만들 수 있어요.

 

 

얼마나 차이가 나는데?

속도차이가 얼마나 나는지 직접 보면 더 좋겠죠.
간단한 예제를 가져와서 비교해보도록 하겠습니다.

선형 탐색 알고리즘과 이진 탐색 알고리즘을 비교해볼건데 이게 뭔지는 다음 챕터에서 자세히 알아볼게요.

간단히 설명하면 선형 탐색 알고리즘은 처음부터 끝까지 내가 찾고 싶은 데이터가 있는지 차례대로 모두 찾아보는 방식,
이진 탐색 알고리즘은 정렬된 데이터를 반으로 계속 나누면서 찾아보는 방식이라고 이해하시면 됩니다.

0~99로 이루어진 1,000,000개의 배열에서 내가 원하는 데이터를 랜덤으로 10개 찾는 프로그램입니다.

 

1. 선형 탐색 알고리즘 연산 속도

선형 탐색 알고리즘의 평균 탐색 시간은 약 500마이크로초입니다.
프로그램을 10번 정도 실행해봤는데 비슷하게 나옵니다.

 

2. 이진 탐색 알고리즘 연산 속도

이진 탐색 알고리즘의 평균 탐색 시간은 약 5마이크로초입니다.
선형 탐색 알고리즘과 약 100배가 차이나는 것을 볼 수 있습니다.

이진 탐색 알고리즘은 정렬된 데이터에서만 사용할 수 있는데 딱 한 번만 정렬 해놓으면 탐색을 100번, 1000번 해도 5마이크로초만에 데이터를 찾을 수 있으니 더 효율적이라고 볼 수 있습니다.

 

 

이미 만들어진 라이브러리 가져다 쓰면 되는데?

맞아요! C++ STL이나 파이썬, 자바에서 기본으로 제공하는 컬렉션 등

이미 구현된 좋은 라이브러리가 많아서 프로그래밍 할 때 우리가 직접 자료구조나 알고리즘을 구현할 일이 많지 않을 수도 있어요.

라이브러리란, 쉽게 가져다 쓸 수 있도록 이미 만들어진 함수나 클래스의 집합을 의미해요.

그래도 그 라이브러리들이 어떤 식으로 돌아가는지 내부 작동 원리를 알고 쓰는 것과 모르고 쓰는 것은 분명 차이가 있어요.

고급 개발자가 되기 위해 같이 자료구조를 학습해보면 좋겠습니다.
위 테스트에 쓰인 코드를 첨부하고 마치겠습니다.

 

1,000,000개의 숫자 생성하는 코드

#include <iostream>
#include <fstream>
#include <random>

int main(void)
{
    std::ofstream ofs("./number.txt", std::ios::out | std::ios::app);
    std::random_device rd;

    std::mt19937 gen(rd());
    std::uniform_int_distribution<int> dis(0, 99);

    for(int i=0; i<1000000; i++)
        ofs << dis(gen) << std::endl;

    ofs.close();
    return 0;
}

 

선형 탐색 알고리즘 코드

#include <iostream>
#include <chrono>
#include <fstream>
#include <vector>
#include <random>
#include <algorithm>

using namespace std;
using namespace chrono;

bool linear_search(vector<int> numbers, int target)
{
    for(auto i=0; i<numbers.size(); i++)
    {
        if(numbers[i] == target)
            return true;
    }

    return false;
}

int main(void)
{
    vector<int> numbers;
    ifstream ifs("./number.txt", ios_base::in);

    while(!ifs.eof())
    {
        int num;
        ifs >> num;

        numbers.push_back(num);
    }

    std::random_device rd;

    std::mt19937 gen(rd());
    std::uniform_int_distribution<int> dis(0, 99);

    system_clock::time_point start_time;
    system_clock::time_point end_time;

    double linear_total = 0.0;

    for(int i=0; i<10; i++)
    {
        start_time = system_clock::now();
        if(linear_search(numbers, dis(gen)))
            cout << "Found!" << endl;
        else
            cout << "Not Found!" << endl;

        end_time = system_clock::now();

        linear_total += duration_cast<microseconds>(end_time - start_time).count();
    }

    cout << "탐색 연산 평균: " << linear_total / 10 << " microseconds" << endl;

    ifs.close();
    return 0;
}

 

이진 탐색 알고리즘 코드

#include <iostream>
#include <chrono>
#include <fstream>
#include <vector>
#include <random>
#include <algorithm>

using namespace std;
using namespace chrono;

int main(void)
{
    vector<int> numbers;
    ifstream ifs("./number.txt", ios_base::in);

    while(!ifs.eof())
    {
        int num;
        ifs >> num;

        numbers.push_back(num);
    }

    std::random_device rd;

    std::mt19937 gen(rd());
    std::uniform_int_distribution<int> dis(0, 99);

    system_clock::time_point start_time;
    system_clock::time_point end_time;

    start_time = system_clock::now();
    sort(numbers.begin(), numbers.end());
    end_time = system_clock::now();

    cout << "정렬 연산: " << duration_cast<microseconds>(end_time - start_time).count() << " microseconds" << endl;

    double bin_total = 0.0;

    for(int i=0; i<10; i++)
    {
        start_time = system_clock::now();
        if(binary_search(numbers.begin(), numbers.end(), dis(gen)))
            cout << "Found!" << endl;
        else
            cout << "Not Found!" << endl;

        end_time = system_clock::now();

        bin_total += duration_cast<microseconds>(end_time - start_time).count();
    }

    cout << "탐색 연산 평균: " << bin_total / 10 << " microseconds" << endl;

    ifs.close();
    return 0;
}