자료구조 필요한 이유, 자료구조 성능 측정 방법 2가지(시간복잡도, 공간복잡도)

 

1. 자료구조가 왜 필요할까?

 

프로그래머라면 누구나 데이터를 효과적으로 저장하고, 처리하는 방법에 대해서 바르게 이해할 필요가 있다. 그런데 자료구조를 제대로 이해하지 못하면 불필요하게 메모리와 성능을 낭비할 여지가 있다. 예를 들어 프로그램 내에서 INT형 데이터가 100만 개 가량 사용된다고 가정했을 때, 원하는 데이터를 가장 빠르게 찾도록 하는 자료구조는 무엇 일지에 대한 고민을 하면서 프로그램을 짜야한다. 이를 위한 다양한 방법을 제시하는 것이 자료구조이며 가장 효율적인 방법이 무엇인지 알 수 있으려면 자료구조를 알아야 한다. 

 

기본적인 자료구조들은 다음과 같다.

(1) 선형 구조 - 배열, 연결 리스트, 스택, 큐 등

(2) 비선형 구조 - 트리, 그래프 등

 

자료구조와 알고리즘의 상관관계

효율적인 자료구조 설계를 위해 알고리즘 지식이 필요하다. 효율적인 알고리즘을 작성하기 위해서는 문제 상황에 맞는 적절한 자료구조가 사용되어야 한다. 따라서 자료구조론과 알고리즘 이론은 동일선상에 놓을 수 있다. 

 

2. 프로그램의 성능 측정 방법들

 

흔히 프로그램이 빠르게 잘 돌아가고 원하는 대로 즉각적인 처리가 가능할 때 우리는 성능이 좋다고 한다. 이 '성능'을 측정하는 방법은 2가지가 있다. 

 

(1) 시간 복잡도(Time Complexity): 알고리즘에 사용되는 연산 횟수

(2) 공간 복잡도(Space Complexity): 알고리즘에 사용되는 메모리의 양

 

시간 복잡도와 공간 복잡도 모두 고려해서 프로그램을 짜는 것이 컴퓨터 분야에서 매우 중요하다. 효율적인 알고리즘을 사용한다고 가정했을 때, 일반적으로 시간과 공간은 반비례 관계다. 

 

시간 복잡도를 표현할 때는 최악의 경우를 산정해야 하기 때문에, 최악의 경우를 나타내는 Big-O 표기법을 사용한다. 다음 알고리즘은 O(n) 시간 복잡도를 가진다. 입력받은 b의 값만큼 i가 돌기 때문이다. 

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)의 시간 복잡도를 가진다. 2는 제곱이다. 이중 for문은 i가 한 번씩 돌 때마다 j가 한 바퀴를 돌기 때문에 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)이다. 단순히 더한 값을 바로 출력하고 있기 때문이다. 

#include <iostream>

using namespace std;

int main(void) 
{ 
    int a, b;
    cin >> a >> b;
    cout << a + b;
}

 

이렇게 알고리즘 성능은 O(1), O(n), O(nlogn), O(n2), O(n3) 이렇게 측정이 된다. n이 1,000이라고 가정해 보면 n3(n의 세제곱)은 1,000,000,000번(10억 번)의 연산을 하게 되는 것이다. 보통 연산 횟수가 10억을 넘어가면 1초 이상의 시간이 소요된다. 현실적인 다양한 문제에서는 시간제한이 1초 정도라고 생각하면 된다. 따라서 웬만하면 성능이 O(n3)이 되지 않도록 코드를 작성하는 것이 좋다. 

 

시간 복잡도를 표기할 때는 항상 큰 항과 계수만 표시한다. n이 무한정 커진다고 했을 때 3n2이나 n2나 큰 차이가 없기 때문이다.  

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

 

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

int 형 변수는 일반적으로 4 Bytes 만큼 차지하기 때문에 int형 변수가 1,000개 들어가는 배열을 만들었다면 4KB인 것이다. 

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