[C 자/알] 자료구조와 알고리즘의 개념

자료구조(Data Structure)
자료(Data)를 저장하는 구조를 의미한다
각 자료구조마다 장단점이 다르기 때문에

상황에 적절한 자료구조를 잘 선택하는 것이 중요하다

자료구조의 종류

선형 자료구조와 비선형 자료구조로 구분된다
선형 자료구조: 배열 / 가변배열 / 스택 / 큐 / 해시테이블
비선형 자료구조: 링크드 리스트 / 트리 / 그래프 / 힙

 

---

알고리즘(Algorithm)
특정 문제를 해결하는 증명된 방법이다
모든 문제를 해결할 수 있는 알고리즘은 존재하지 않는다
증명된 방법이기 때문에 굳이 해당 알고리즘 템플릿 코드를 이해하고, 암기하는 것이 중요하다

 

복잡도(Complexity)

알고리즘을 비교할 때, 시간과 공간을 비교하고
시간 혹은 공간을 많이 사용할수록 복잡하다고 말한다
복잡도에는 시간 복잡도와 공간 복잡도가 있다
복잡도를 표기하는 방법에는 대표적으로 빅오 표기법을 사용한다

빅오 표기법(Big-O Notation)
대문자 O를 이용한 표기법으로 O의 의미는 “대략 ~정도, Order of ~”이다
입력 개수 N에 따른 작업 완료에 필요한 연산 횟수를 계산하는 것으로

영향력이 가장 큰 최고차항만 남기고 계수들은 무시하고 계산한다

최고 효율 ←———————————————→ 최저 효율
O(1) / O(logN) / O(N) / O(NlogN) / O(N^2) / O(2^N) / O(N!)