[기술 면접] 1. Array 는 어떤 자료구조인가요?

Array는 데이터를 순차적으로 저장하고 효율적인 접근을 제공하는 자료구조로, 알고리즘의 기본이며 프로그래밍에서 빈번하게 사용되기 때문에 면접에서 자주 다루어집니다.

Q : Array는 어떤 자료구조인가요?

Array는 연관된 data를 메모리상에 연속적이며 순차적으로, 미리 할당된 크기만큼 저장하는 자료구조입니다.

Q : Array의 특징은 어떤 것들이 있나요?

대표적으로 고정된 저장 공간과 순차적 데이터 저장이 있습니다.

• Array의 장점은 lookup과 append가 빠르다는 것입니다. 따라서 조회를 자주 해야되는 작업에서 사용됩니다.

• 단점으로는, fixed-size 특성상 선언 시에 크기를 미리 지정해야 된다는 것입니다. 이는 메모리 낭비나 Overhead가 발생할 수 있습니다.

Q : Array의 시간 복잡도에 대해 말씀해보세요.

Access (접근) – O(1): 배열의 특정 인덱스에 접근하는 시간은 상수 시간이 소요됩니다. 배열의 각 원소가 연속된 메모리 공간에 저장되기 때문에, 원하는 인덱스에 바로 접근할 수 있습니다.

Append (끝에 추가) – O(1): 배열의 마지막에 원소를 추가합니다. 배열에 남은 공간이 있다면 바로 추가할 수 있지만, 배열이 꽉 찬 경우에는 더 큰 배열을 생성하고 기존 배열의 모든 원소를 복사해야 한다는 것도 알아두셔야 합니다. 이 경우는 O(n)의 시간이 걸립니다.

마지막 원소 Deletion (삭제) – O(1): 배열의 마지막 원소를 삭제합니다. 배열을 반복하며 별도 index를 찾을 필요가 없기 때문에 O(1)로 가능합니다.

Insertion (삽입) – O(n): 배열 중간에 삽입하는 경우, 그 이후의 모든 원소를 오른쪽으로 이동해야 하므로 O(n)의 시간이 소요됩니다. 배열의 크기를 n이라고 생각하시면 쉽게 이해할 수 있습니다.

Deletion (삭제) – O(n): 배열 중간에 있는 원소를 삭제하려면, 삭제 이후 모든 원소를 왼쪽으로 이동해야 하므로 O(n)의 시간이 소요됩니다.

Search (탐색) – O(n): 배열에서 특정 원소를 찾으려면 배열을 순차적으로 탐색해야 하므로, 최악의 경우 O(n)의 시간이 걸립니다.

Q : 미리 예상한 것보다 더 많은 수의 data를 저장하느라 Array의 size를 넘어서게 됐습니다. 이 때, 어떻게 해결할 수 있을까요?

기존 size보다 더 큰 Array를 선언하여, 데이터를 옮기고 기존 Array를 삭제합니다. 이와 같이 동적으로 배열의 크기를 조절하는 자료구조를 Dynamic array라고 합니다.

size를 예측하기 쉽지 않다면, Array 대신 Linked List를 사용함으로써, 데이터가 추가될 때마다 메모리 공간을 할당받는 방식을 사용합니다.

Q : Array와 ArrayList의 차이점이 무엇인가요?

Array는 크기가 고정적이며, ArrayList는 가변적이라고 할 수 있습니다. Array는 초기화 시, 메모리에 할당 되는 이유로, ArrayList보다 속도가 빠르고, ArrayList는 데이터를 추가하거나 삭제할 때 메모리를 재할당 하기 때문에 Array보다 느립니다.

마치며

자료구조 Array에 대한 면접 질문 내용을 정리했습니다. Array의 구조, 특징, 시간 복잡도 등을 다루었는데 면접 준비의 기초가 되실 거라 생각합니다. 모두 자신 있게 준비하시고 좋은 결과를 기원합니다.

다음 시간엔, Dynamic Array는 어떤 자료구조인지에 대한 면접 질문들을 알아보겠습니다.