[코딩테스트] Array

코딩 테스트를 준비하는 과정에서 학습한 내역들을 기록해 보자.

가장 간단한 배열부터 시작해 보자. 

 

배열이란

데이터들이 연속적으로 이어져서 랜덤 액세스를 지원하는 자료구조.

(랜덤 액세스를 지원하지 않는 자료구조는?! linked list)

(랜덤 액세스란? 각 element들의 인덱스를 통해서 바로 접근하는 것. nums[0], nums[3]..)

 

배열만으로 알고리즘 문제가 만들어지기보다는

BinaryTree, BackTracking과 같은 알고리즘에서 사용되는 자료구조라고 보면 된다.

추후에 차근차근 알아보자..

 

배열 자료구조의 기본이 되는 문제는 정렬(sorting)이다.

-> quick sort, merge sort.. 다양하게 존재

-> 시간 복잡도 O(nlogn)

-> stable, unstable(정렬 전의 순서가 바뀌는가 유지되는가..)

 

추가적인 중요한 문제는 Search이다.

-> 정렬이 되어있지 않다면 모든 element들을 확인해야 해서 O(n)

-> 정렬이 되어있다면 binary search를 통해 O(logn)

 

다중 배열의 문제도 나오는데

대부분은 Graph에 관련된 문제이다. 

추후에 알아보자..