자료구조와 알고리즘의 이해 - 자료구조


01-1 자료구조에 대한 기본적인 이해

자료구조(Data Structure)
 - 데이터를 표현하고 저장하는 방법이다.
 - 데이터의 저장을 담당하는 것이 자료구조이다.

선형 자료구조
 - 자료를 표현 및 저장하는 방식이 선형(linear)이다.
 - 데이터를 선의 형태로 나란히 혹은 일렬로 저장하는 방식이다.

- 리스트, 스택, 큐

비선형 자료구조
 - 데이터를 나란히 저장하지 않는 구조이다.

- 트리, 그래프

자료구조에 따라서 알고리즘이 달라진다. 즉, 알고리즘은 자료구조에 의존적이다.

01-2 알고리즘의 성능분석 방법

시간복잡도(Time Complexity)
 - 어떠한 상황에서 더 빠르고 또 느린지 평가하는 '속도'에 해당하는 알고리즘의 수행시간 분석결과이다.

공간 복잡도(Space Complexity)
 - 어떠한 상황에서 메모리를 적게 쓰고 또 많이 쓰는지 '메모리 사용량'에 대한 분석결과이다.

알고리즘의 수행속도를 평가할 때는 처리해야 할 데이터의 수 n에 대한 연산횟수 T(n)을 구성한다.

알고리즘은 상황에 맞게 답을 내려야한다.

시간 복잡도 분석의 핵심요소는 연산 횟수가 가장 많은 상황을 가정한 '최악의 경우'로 알고리즘의 성능을 판단한다.