코딩테스트 Arrays 이론 | 코드없는 프로그래밍

출처 - 코드없는 프로그래밍

인터뷰 배열 기초 - YouTube

 

Array - 가장 간단한 자료 구조

 

array란

데이터들이 연속적으로 이어져있고

랜덤 엑세스를 지원하는 자료 구조를 말한다. 

 

* 랜덤 엑세스 - 인덱스를 통해 바로 접근할 수 있게 해준다. 

 

배열 문제는 인덱스를 사용할 수 있다는 점을 중요하게 사용하게 됨. 

ex - array를 활용한 BackTracking (?)

 

기본적인 문제의 경우,

sorting과 관련이 된다. 

 

sorting의 종류에는 heap sort / quick sort / merge sort가 있다.

배열이 stable하면 merge sort

배열이 unstable하면 quick sort, heap sort를 사용한다. 

 

이때 stable한 것은, 정렬이 된 후에도 ABCDE 등 본래 순서를 유지하는 경우

unstable한 것은 그렇지 않은 경우를 의미한다. 

 

만약 배열이 정렬이 되어 있으면 binary search를 사용할 수 있고 O(logn)

그렇지 않으면 배열의 모든 요소를 돌어야 한다. O(n)

 

search가 중요함. 배열의 모든 요소를 돌아야 한다. O(n)

 

다음은 2차원 array, 다차원 배열

이들은 대부분 graph 문제다.