코딩테스트 알고리즘 자료구조 Array 배열 정리

in Study Log on Algorithm, Java, Data Structure

이 장에서 배울 내용

  • Array
  • Array 관련 API

시작하기에 앞서

코딩테스트를 준비하기 위해서 알고리즘을 공부하면, 자료구조를 병행하는 경우가 많은데 간단하게 기본 개념을 공부하고 싶었다. 가장 먼저 Array. Array는 직접 구현해야 하는 문제는 잘 안 나와서 이번에는 개념이나 작동 원리 정도만 정리했다.




Array

같은 Type 의 데이터를 유한한 크기의 배열로 정의한다. 인덱스와 일대일 매칭하여 데이터를 빠르게 접근할 수 있는 자료구조이다. 이를 임의접근(random access)라고 한다. 선언과 동시에 크기를 초기화해주어야하며, 데이터가 들어있지 않은 경우에는 배열 타입에 따라서 0(int) or null(object) or0.0(double) 등으로 초기화된다.

크기 이상으로 값을 할당할 시 Runtime Error 발생!



시간 복잡도

위에서 언급했듯이 배열은 데이터를 인덱스를 통해 바로 접근하므로 O(1) 이다. 삭제하는 경우에도 동일하며, 마지막에 데이터를 삭제할 때에도 마찬가지이다. 하지만, 중간이나 처음에 데이터를 삽입하게 될 경우에는 중간에 들어가기 위해 기존에 있던 데이터를 밀어내는 작업이 필요하므로 O(N) 이다.



Array 관련 메서드

  • string.length() : 문자열의 길이 확인
  • Arrays.toString() : 배열 형태를 문자열로 확인
  • Arrays.sort() : 오름차순/사전순서로 정렬해주는 함수
  • get() : 인덱스를 통해 데이터 확인
  • clone() : 배열 복제
  • equal(int[] a, int[] b) : a와 b가 같은지를 비교하여 true/false 값 반환
  • asList() : 리스트로 변환




.
.
.
.
.

결론

데이터에 자주 접근하거나 읽어야 할 경우에는 배열이 효율적이다. 하지만, 사전에 크기를 할당해주어야 해서 메모리 공간을 충분히 확보 해야하기 때문에 낭비될 수도 있다. 또한 데이터 수정(중간에 삽입/삭제) 할 때 시간 복잡도가 O(N) 이므로 작업 비용이 크다고 볼 수 있다.




[참고자료]