자료구조의 개요

자료구조의 필요성

데이터를 효과적으로 저장하고, 처리하는 방법에 대해서 바르게 이해하기 위해

불필요하게 메모리와 성능을 낭비하지 않기 위해

 

자료구조와 알고리즘

효율적인 자료구조 설계를 하기위해 알고리즘 지식이 필요합니다

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

따라서 자료구조론과 알고리즘 이론은 모두 동일선상에 놓을 수 있습니다

 

기본적인 자료구조들

선형구조

(자료를 구성하는 원소들을 순차적으로 나열시킨 형태)

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

비선형 구조

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

 

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

• 시간 복잡도(Time Complexity) 알고리즘에 사용되는 연산 횟수를 의미합니다
• 공간 복잡도(Space Complexity) 알고리즘에 사용되는 메모리의 양을 의미합니다

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

 

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

이 때 항상 큰 항과 계수만 표시합니다

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

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

 

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

int a[1000] = 4KB

int a[1000000] = 4MB

int a[2000][2000] = 16MB