자료구조의 개요

자료구조의 필요성

- 데이터를 효과적으로 저장하고, 처리하는 방법에 대해서 바르게 이해할 필요가 있음

- 자료구조를 제대로 이해하지 못하면 불필요하게 메모리와 성능을 낭비할 여지가 있음

 

기본적인 자료구조들

- 선형 구조

배열, 연결 리스트, 스택, 큐

 

-비선형 구조

트리, 그래프

 

자료구조와 알고리즘

- 효율적인 자료구조 설계를 위해 알고리즘 지식이 필요함

- 효율적인 알고리즘을 작성하기 위해서는 문제 상황에 맞는 적절한 자료구조가 사용되어야 함

- 자료구조론과 알고리즘 이론은 동일선상에 놓을 수 있음

 

프로그램의 성능 측정 방법론

1.

- 시간 복잡도(Time Complexity)란 알고리즘에 사용되는 연산 횟수를 의미

- 공간 복잡도(Space Complexity)란 알고리즘에 사용되는 메모리의 양을 의미

- 효율적인 알고리즘을 사용한다고 가정했을 때 일반적으로 시간과 공간은 반비례 관계

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

 

* 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;
}

 

* O(n2)의 시간 복잡도

#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';
    }
}

 

 

* [예시] n이 1000일 때

 

n : 1,000번 연산

nlogn : 약 10,000번의 연산

n2 : 1,000,000번의 연산

n3 : 1,000,000,000번의 연산

 

보통 연산 횟수가 10억을 넘어가면 1초 이상의 시간이 소요됨

 

2.

- 시간 복잡도를 표기할 때는 항상 큰 항과 계수만 표시

 

O(3n2 + n) = O(n2)

 

- 현실적인 다양한 문제에서는 시간제한이 1초 정도라고 생각하면 됨

- 공간 복잡도를 표기할 때는 일반적으로 MB 단위로 표기

 

int a [1000] : 4kb

int a [1000000] : 4mb

int a [2000][2000] : 16mb

 

 

- 자료구조의 종류로는 스택, 큐, 트리 등이 있음

- 프로그램을 작성할 때는 자료구조를 적절히 활용하여 성능 최적화를 노려야 함