Vol.1: 데이터 구조 개요

이 버전에서는 데이터 구조의 필요성과 데이터 구조의 성능을 측정하는 방법을 배웁니다.

데이터 구조의 필요성

👌 데이터를 효과적으로 저장하고 처리하는 방법을 올바르게 이해해야 합니다.
👌 자료 구조를 제대로 이해하지 않으면 불필요하게 메모리와 성능을 낭비할 여지가 있습니다

예)プログラム内でINT型データが100万個ほど使われると仮定した場合、必要なデータを最も素早く探せる資料構造とは何でしょう？

기본 데이터 구조

📌 선형 구조
- 배열
- 연결 목록
- 스택
- 큐

📌 비선형 구조
- 트리(Tree)
- 그래프(Graph)

데이터 구조와 알고리즘의 상관 관계

👌 효율적인 데이터 구조 설계를 위해서는 알고리즘 지식이 필요합니다.
👌 효율적인 알고리즘을 만들려면 문제의 상황에 따라 적절한 데이터 구조를 사용해야 합니다.
👌 따라서 데이터 구조론과 알고리즘 이론은 모두 동일한 선에 놓을 수 있습니다.

프로그램 성능 측정 방법론

👌 시간 복잡도(Time Complexity)란 알고리즘에 사용되는 연산 횟수를 의미합니다.
👌 공간 복잡도(Space Complexity)란 알고리즘에 사용되는 메모리의 양을 의미합니다.
→ 효율적인 알고리즘을 사용한다고 가정하면 일반적으로 시간과 공간은 반비례 관계입니다.

시간 복잡도를 표현할 때는 최악의 경우를 나타내는 Big-O 표기법을 사용합니다.

복잡도의 경우 수학적으로도 표기가 가능합니다. 프로그램을 작성할 때는 최악의 경우를 산정해 작성해야 하기 때문에, 이와 같이 Big-O 표기법을 사용해 최악의 경우를 베이스로 했을 경우, 얼마나 걸리는가라고 명시할 수 있다 합니다.

예 1) 다음 알고리즘은 O(n)의 시간 복잡도를 가집니다.
🖍O(n) = 변수분 반복의 의미로 이해

int main(void)
{
   int a, b;
   cin >> a >> b;
   int sum =1;
   for (int i = 0; i < b; i++)
   {
           sum *= a;
   }
   cout << sum;
}

예 2) 다음 알고리즘은 O(n²)의 시간 복잡도를 가집니다.

#include<iostream>

using namespace std;

int main(void)
{
   int n;
   cin >> n;
   for (int i = 0; i < n; i++)
   {
           for(int j =0; j<= i; j++){
                    cout << "*";
                }
                cout << '\n';
           }
}

🤔 위 그림과 같이 O의 1에서 n의 수승까지 늘리는 방법으로 다양한 알고리즘의 성능 측정이 가능합니다.

예) n이 1000이라고 가정
↓↓↓↓↓↓↓ Your content

n : 1,000回の演算
nlogn : 約10,000回の演算
n² : 1,000,000回の演算
n³ : 1,000,000,000回の演算

일반적으로 연산 횟수가 10억을 초과하면 1초 이상의 시간이 소요됩니다.
현실 세계의 다양한 문제에서는 시간 제한이 1초라고 생각하면 됩니다.
즉, 어느 모듈이 1초를 넘으면, 사실상 사용자의 입장에서는 많은 시간이 걸린다고 느낄 수 있기 때문입니다.

또한 시간 복잡도를 표기할 때는 항상 큰 항과 계수만 표시합니다.

예)

O(3n²+n) = O(n²)

공간 복잡도를 표기할 때는 일반적으로 MB 단위로 표기합니다.
예)

int a[1000]:4KB
int a[1000000]:4MB
int a[2000][2000]:16MB

→ int형은 4byte의 공간을 차지하므로, int형 변수가 1000개 들어가는 변수를 만들었다면, 4byte X 1000 = 4000byte = 4KB

📚 참고 강의: 컴퓨터 공학 전공 필수 올인원 패키지 Online
👆 위의 강의는 C와 C++ 언어를 전제로 설명합니다.