Data Structure

1. Importance of Data Structure

우리는 일상에서 방대한 양의 데이터와 함께 살아간다.

그러나, 아무렇게나 뒹굴고 있는 데이터는 우리의 생활에 빛나는 도움을 주지 못한다.

따라서 데이터들을 찾기 쉬운 형태로 정리하기 위한 바구니가 필요한데, 이것이 바로 자료구조이다.

 

자료구조는 배열, 리스트, 스택, 큐 등 그 종류가 다양하다. 

우리는 상황에 따라 가장 적합한 자료구조를 선택하여 데이터를 저장하고, 쉽게 꺼내쓰면 된다.

 

※  Program = data structure + algorithm

 

 

 

 

2. ADT (Abstract Data Type)

▶ Data type

 : data (-2, 0, 1, 3 ...) & opeartion ( *, +, /, % ...) 집합들의 모임

 

우리는 '무엇'으로 data type이 정의되었는지만 관심있고,
'어떻게' data나 operation들이 실행되는지는 관심 없어도 됨

 

 

 

3. Performance Analysis of Algorithm

① Execution time measure	② Complexity Analysis
실제 컴퓨터에서의 물리적 실행 시간	- Time Complexity Analysis (execution time) - Spatial Complexity Analysis (memory space)

 

② Complexity Analysis

 - 주로 T(n) = number of operations 으로 결정 ( n : number of input )

 - n이 커질수록 알고리즘의 복잡도 ↑

 

알고리즘 효율화

2^n   <<   n^3   <<   n^2    <<   nlogn    <<    n    <<    logn    <<    상수