array

배열이란 무엇인가?

같은 종류의 데이터를 메모리에 연속으로 나란히 저장하는 자료구조다. 아파트 호수처럼 번호(인덱스)가 매겨져 있어서, 번호만 알면 원하는 데이터에 바로 접근할 수 있다.

Array is a collection of items of the same variable type that are stored at contiguous memory locations. When an array is created, it occupies a contiguous block of memory. Each element can be accessed using its index.

부분 배열(Subarray)이란 무엇인가?

배열에서 연속된 원소들을 순서 그대로 잘라낸 조각이다. 줄 서 있는 사람들 중 가운데 몇 명을 그대로 뽑아낸 것과 같다.

A subarray is a contiguous part of an array, formed by selecting one or more consecutive elements while maintaining their original order.

배열의 장점은 무엇인가?

첫째, 인덱스만 알면 어떤 위치든 즉시(O(1)) 접근할 수 있다. 둘째, 데이터가 메모리에 나란히 놓여 있어 캐시 효율이 높아 처리 속도가 빠르다.

Random Access: i-th item can be accessed in O(1) Time as we have the base address and every item or reference is of same size.

Cache Friendliness: Since items/references are stored at contiguous locations, we get the advantage of locality of reference.

임의 접근(Random Access)이란 무엇이고, 왜 O(1)인가?

배열의 시작 주소와 각 원소의 크기가 동일하므로, "시작 주소 + (인덱스 x 원소 크기)"라는 간단한 계산만으로 원하는 위치를 바로 찾을 수 있다. 순서대로 하나씩 찾아갈 필요가 없어 항상 일정한 시간(O(1))이 걸린다.

i-th item can be accessed in O(1) Time as we have the base address and every item or reference is of same size.

배열이 캐시 친화적인 이유는?

배열의 원소가 메모리에 연속으로 저장되어 있어서, 하나를 읽을 때 주변 데이터도 함께 캐시에 올라온다. 덕분에 다음 원소를 읽을 때 느린 메모리까지 가지 않고 빠른 캐시에서 바로 가져올 수 있다.

Since items/references are stored at contiguous memory locations, we get the advantage of locality of reference.

배열의 단점은 무엇인가?

중간에 데이터를 넣거나 빼려면 뒤의 원소를 전부 밀거나 당겨야 해서 느리다(O(n)). 검색도 정렬되어 있지 않으면 처음부터 끝까지 하나씩 확인해야 하므로 O(n)이 걸린다.

It is not useful in places where we have operations like insert in the middle, delete from middle and search in a unsorted data.

Insertion/Deletion: 삽입, 삭제가 O(n)임.

Searching: sorted array + binary search인 경우에 한해 O(log n)이지, 그 외 나머지 전부 O(n)임.

배열에서 삽입/삭제가 O(n)인 이유는?

배열은 데이터가 빈틈 없이 나란히 저장되어 있으므로, 중간에 새 원소를 넣으려면 그 뒤의 모든 원소를 한 칸씩 뒤로 밀어야 한다. 삭제도 마찬가지로 빈자리를 채우기 위해 원소들을 앞으로 당겨야 해서, 최악의 경우 전체 원소 수(n)만큼의 이동이 필요하다.

Arrays are stored in contiguous memory locations, meaning elements are arranged in a sequential block.

Insertion:

Identify the Position: Determine where the new element should be inserted.

Shift Elements: Move the existing elements one position forward to create space for the new element.

Insert the New Element: Place the new value in the correct position.

Update the Size: If the array is dynamic, its size is increased.

삽입 위치가 성능에 어떤 영향을 미치는가?

맨 앞에 삽입하면 모든 원소를 한 칸씩 밀어야 하므로 가장 느리고, 중간이면 그 뒤의 원소만 밀면 된다. 맨 끝에 삽입하면 밀어야 할 원소가 없으므로 가장 빠르다.

Beginning (Index 0): Every element must shift one position right. This is the least efficient case for large arrays as it affects all elements.

Specific Index: Elements after the index shift right.

End: The simplest case since no shifting is required.