1. 자료구조의 개요 - 자료구조의 필요성 / 기본적인 자료구조들 / 자료구조와 알고리즘 / 프로그램의 성능 측정 방법론

자료구조의 필요성

데이터를 효과적으로 저장하고, 처리하는 방법에 대해서 바르게 이해할 필요가 있다. 자료구조를 제대로 이해하지 못하면 불필요하게 메모리와 성능을 낭비할 여지가 있기 때문이다. 자료구조를 배우고 나면, 특정 상황에서 원하는 데이터를 가장 빠르게 찾도록 해주는 자료구조를 택해 프로그램을 설계할 수 있다.

 

기본적인 자료구조들

선형구조

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

비선형구조

• 트리(Tree)
• 그래프(Graph)

 

자료구조와 알고리즘

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

 

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

시간 복잡도(Time Complexity)

알고리즘에 사용되는 연산 횟수를 의미한다.

공간 복잡도(Space Complexity)

알고리즘에 사용되는 메모리의 양을 의미한다.

 

효율적인 알고리즘을 사용한다고 가정했을 때, 일반적으로 시간과 공간은 반비례 관계이다. 이 시간 복잡도와 공간 복잡도를 얼마나 효과적으로 써서 프로그램을 만들 수 있는지가, 컴퓨터 공학 분야에서는 정말 중요한 주제이다.

시간 복잡도(Time Complexity)

시간 복잡도를 표현할 때는 최악의 경우를 나타내는 Big-O표현법을 사용한다. 일반적으로 for문이 한번 포함되면 O(n)의 시간 복잡도를 가지는데, 어떠한 변수만큼 반복을 한다는 의미이다.

2중 for문이 포함 된 경우, 해당 알고리즘은 O(n^2)의 시간 복잡도를 가진다. (n의 제곱 만큼 반복한다는 의미)

 

보통 연산 횟수가 10억을 넘어가면 1초 이상의 시간이 소요되므로, 연산횟수가 10억 이상 넘어가지 않도록 하는 것이 좋다.

시간 복잡도를 표기할 때는 항상 큰항과 계수만 표시하므로,

O(3(n^2)+n) = O(n^2)

위와 같이 된다. (n을 무한대로 가정하기 때문이다.)

현실의 다양한 문제에서는 시간제한이 1초 정도라고 생각하면 된다.

공간 복잡도(Space Complexity)

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

int a[1000] : 4KB

int a[1000000]: 4MB

int a[2000][2000] : 16MB

 

요약

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