[자료구조 및 알고리즘] CH1. Intro to Data Structures

Data structure란?

• 데이터를 효율적으로 사용하기 위해 데이터를 organizing하는 특정한 방법
• 용도에 따라 그에 적합한 data structure가 존재
  • Database -> B-trees
  • Compile -> hash table

효과적인 Data structure를 고르는 방법

• 문제로부터 resource constraints(time, space)을 분석
• 필요한 basic operation을 결정
  • 사용자의 요청이 어떠한 형태인지도 예시가 될 수 있다. 예컨대, exact-match query인지 아니면 range query인지
• 위 두 가지를 고려해 가장 잘 맞는 것을 선택한다.

Data type이란?

• 다음의 네 가지를 결정하는 분류이다.
  • 해당 type의 데이터가 가질 수 있는 value
  • 해당 type에 수행될 수 있는 operation
  • 해당 type의 데이터가 저장되는 방식

선형자료구조 vs 비선형자료구조

• 선형구조 : 데이터 저장 방식이 선형(linear)으로 나란히 혹은 일렬로 저장
• 비선형구조 : 데이터를 나란히 저장하지 않는 방식, 선형보다 고난도

선형자료구조와 비선형자료구조(출처:boycoding 티스토리)

ADT(추상자료형)란?

• 비슷한 동작을 지닌 특정 data object들을 다루는 데 필요한 수학적 모델로 수행되는 operation에 의해 간접적으로 정의 됨
• EX) stack, queue, tree, graph...
• 예를 들어 부연설명 하자면) stack에 필요한 기능은 간단히 push,pop,peek 정도가 있다. 이 때, data object가 paper인지 wooden인지에 무관하게 두 곳에 사용되는 'stack'이라는 것에 동일성을 논할 수 있다. data object의 type이 무엇인지, 그 양이 어느 정도인지와는 무관하다.

ADT(추상자료형)의 필요성(이점)은?

• 구현자와 사용자를 분리해 사용자는 특정 기능의 내부적인 구현이 어떻게 되어있는지 몰라도 해당 기능을 사용할 수 있게 해준다.
• 비슷한 기능을 필요로 하는 데이터에 대해 적용 가능(재사용성) - EX) stack of paper, stack of wooden

객체지향언어(OO)에서 클래스란?

• ADT + 그것의 implementation