[Data Structure] 자료구조와 알고리즘

자료구조의 정의

- 정보의 구조를 이야기 하며, 주로 메모리 안에서 더 좋은 알고리즘 효율을 위해 수행되는 것을 의미합니다.

- 데이터를 모으고 구조화하는 것입니다.

- 데이터 보관 방법과 데이터에 관한 연산의 총체

- A way of concrete representations of data from the point of view of an implementer

- queue, stack, linked list, heap, dictionary, tree etc.

https://teachics.org/data-structure-c-tutorial/categories-of-data-structures/

 

 

데이터 타입이란?

A collection of objects and a set of operations that act on those object.

https://www.geeksforgeeks.org/data-types-in-c/

 

알고리즘의 정의

어떤 문제를 풀기 위한 단계적 절차로 다음을 만족하는 명령어의 유한 집합입니다.

• Input: zero or more inputs
• Output: at least one output
• Definiteness: clear and unambiguous instructions
• Finiteness: terminating after a finite number of steps
• Effectiveness(Machine-executable): basic enough to be carried out

효율적인 알고리즘이란? 자원(시간과 공간)을 덜 사용하는 알고리즘

 

프로그램의 정의

Program = Data Structure + Algorithm

• Data Structure: 어떻게 컴퓨터 메모리에 저장할 것인가
• Algorithm: 저장된 데이터를 어떻게 다룰 것인가

Programming is to represent data(Data Structure) and slove the problem(Algorithms) using the data

 

Abstraction(추상화)란?

세부사항들을 생략하고 핵심만 남기는 작업입니다.

A form of abstraction is to leave out detail of what is being represented.

https://computersciencewiki.org/index.php/Abstraction

 

 

추산 자료형(Abstract Data Type, ADT)

사용자 관점에서 데이터 타입을 정의하는 방법입니다.

구현하고자 하는 구조에 대해 구현 방법은 명시하지 않고 어떤 object들과 operation들이 있는지 설명하는 형태입니다.

즉, 자료구조가 갖춰야 할 일련의 연산

Specification of a set of objects and operations on the objects

https://algs4.cs.princeton.edu/12oop/

 

 

공간 복잡도와 시간 복잡도

• 공간 복잡도(space complexity): an amount of memory needed. (machine-independent) space required by an algorithm
• 시간 복잡도(Time complexity): an amount of time taken for an algorithm to finish. (machine-independent) time required by an algorithm. 시간은 측정하기 어려우므로 시간 대신에 프로그램의 단계(step)으로 계산합니다. Syntactically or semantically meaningful program segment whose execution time is independent of the number of inputs.