자료구조(DataStructure)란?
- 다수의 자료(data)를 담기 위한 구조이다.
- 데이터의 수가 많을수록 효율적인 자료구조가 필요하다.
자료구조의 개요
- 성능 비교를 통해 자료구조/알고리즘의 성능 측정 방법에 대해 이해하고 불필요한 메모리와 계산을 낭비하지 않기 위해 사용한다.
자료구조의 종류
자료구조는 크게 두 종류로 나눌 수 있다.
1. 선형 구조(Linear data structure)
하나의 데이터 뒤에 다른 데이터가 하나 존재하는 자료구조이다.
- 배열 (array)
- 연결 리스트 (linked list)
- 스택 (stack)
- 큐 (queue)
2. 비선형 구조(non-linear data structure)
하나의 데이터 뒤에 다른 데이터가 여러 개 올 수 있는 자료구조이다.
- 트리 (tree)
- 그래프 (graph)
자료구조와 알고리즘의 연관성
- 효율적인 자료구조 설계를 위해 알고리즘이 필요하다.
- 효율적인 알고리즘을 작성하기 위해서 문제 상황에 맞는 적절한 자료구조가 사용되어야 한다.
따라서 프로그램을 작성할 때 자료구조와 알고리즘을 모두 고려해야 한다.
어떻게 고려할 것인가 ?
알고리즘의 성능 비교를 통해 고려하면 된다.
- 시간 복잡도 (time complexity) : 연산 횟수 측정
- 공간 복잡도(space complextiy) : 메모리의 양 측정
주로 공간을 많이 사용하더라도 시간을 단축하는 방법이 흔히 사용된다.
또한 Big-O 표기법으로 시간 복잡도를 측정하는데 Big-O 표기법은 가장 큰 항만을 표시한다.
O(3n^2 + n)라면 Big-O로 O(n^2)로 표기한다.
Hello World !