자료구조 & 알고리즘이란

특정 자료구조와 알고리즘이 언제, 왜 쓰이는지, 따라서 상황에 따른 최선의 자료구조와 알고리즘 조합이 무엇인지 아는 것이 핵심!!

⇒ 각 자료구조의 operation에 따른 시간복잡도를 파악할 줄 알아야!

⇒ 이 때, operation 하는 방식이 알고리즘!

 

 

자료구조 종류

1. 배열 array
2. 해시테이블 hash tables
3. 큐 queu & 스택 stack : 추상적 자료구조(ADT)

 

4가지 operation

1. 검색 searching
2. 읽기 reading
3. 삽입/추가 inserting/adding
4. 삭제 deleting

 

알고리즘

1. Search algorithm : linear, binary
2. Sorting algorithm : bubble(O(N^2)), selection(O(N^2)), insertion(O(N^2)) → 여기서 알 수 있듯이, 빅오 시간복잡도만 가지고는 실제로 어떤게 더 퍼포먼스가 좋은지 판단하기 어려움. 또한 자료의 크기가 작은지 큰지에 따라서도 달라짐.

 

시간복잡도

물리적 시간보단 단계의 개념! 알고리즘의 퍼포먼스를 비교/파악하기 위함.

1. big-O 표기법
2. big-오메가 표기법

 

 

Array

• Volatile vs non-volatile memory

       비휘발성 메모리 non-volatile memory: 하드드라이브

       휘발성 메모리 volotile memory: RAM(Random Access Memory)

• 배열 길이 할당 : js, python은 메모리 공간(배열 길이) 일일이 할당해줄 필요없이 프로그램이 알아서 핸들링. 때문에 구체적으로 직접 프로그래밍해야 하는 C와 비교했을 때 편함. 다만, 속도가 느릴 수도 있다는 단점이 있음.
• Reading : 익덱싱을 통해 바로 접근 가능 (rendom access) → 시간복잡도 O(1)
• Searching (linear searching 선형검색) : 시간복잡도 O(N)
• Inserting : 시간복잡도 O(N) (C 언어와 같은 경우, 미리 할당한 메모리 공간이 꽉찼을 때 하나를 더 추가하려면 메모리 공간을 아예 새로 할당해야함. 즉, 자료를 새로 구축해야함.)
• Deleting : 시간복잡도 O(N)