알고리즘 정리 - 자료구조란?

자료구조란?

- 다수의 자료를 담기 위한 구조

- 데이터의 수가 많아질 수록 적절한 자료구조가 필요하다

 

=> 데이터를 효과적으로 저장하고, 처리하는 방법에 대해 알면 불필요한 메모리와 계산을 낭비할 여지가 없다!

---

자료구조의 종류

1. 선형 구조

- 배열(array)

- 연결 리스트(linked list)

- 스택(stack)

- 큐(queue)

 

2. 비선형 구조

- 트리(tree)

- 그래프(graph)

---

선형 자료 구조란?

- 하나의 데이터 뒤에 다른 데이터가 하나 존재하는 자료구조를 뜻함.

- 데이터가 일렬로 연속적으로 연결되어 있다.

ex) 스택, 큐, 배열 , 연결리스트

 

비선형 자료 구조란?

- 하나의 데이터 뒤에 다른 데이터가 여러 개 올 수 있는 자료구조를 뜻함.

- 데이터가 일직선상으로 연결되어 있지 않아도 된다.

ex) 그래프, 트리

---

프로그램 성능 측정 방법

- 시간 복잡도(time complexity): 알고리즘에 사용되는 연산 횟수를 측정

- 공간 복잡도(space complexity): 알고리즘에 사용되는 메모리의 양을 측정

 

- 빅오(Big-O)표기법 : 복잡도를 표기할 때 쓰는 표기법. 가장 빠르게 증가하는 항만을 고려하는 표기법