Array

Array 관련 문제는 3가지가 있다. 

1. Insert

2. Delete

3. Search

+

4. In-Place Array Operations

 

 

1. Insert

1-1. Insert를 할때 첫번째 element에 insert하는것.

모든 Elements를 한칸씩 옮기고 첫번째 element에 value를 insert한다.

1-2. 마지막 element에 insert 하는것.

array의 길이를 count하고 마지막 element에 insert한다.

1-3. 중간 element에 insert하는것. 

중간에 지점을 지정하고, 그 뒤의 elements를 옮긴 후, 중간지점에 value를 insert한다.

2. Delete

2-1. Delete를 할때 첫번째 element를 delete 하는것.

첫번째 elements를 overwrite한다. 모든 elements를 앞으로 한칸 씩 옮김으로써 첫번째 index element를 delete한다.

2-2. 마지막 element를 delete 하는것.

queue와 같이 마지막 element를 빼는 방법과 마지막 element이전까지 count하여 delete하는 방법이 있다.

2-3. 중간 element를 delete하는 것.

중간 element를 overwrite한다. 중간지점 이후의 elements를 앞으로 한칸씩 옮김으로써 delete를 진행한다.

3. Search

3-1. Linear Search. 

모든 element를 하나씩 찾음으로써 search를 진행한다. O(N)시간이 소요된다.

3-2. Binary Search.

Binary Search는 sorted array에서 가능하다. 중간지점을 확인하고 값이 작으면 왼쪽에 elements를 확인하고, 값이 크면 오른쪽 elements를 확인해서 search를 수행한다.

 

4. In-Place Array Operations.

추가적인 space를 사용하지 않고 In-Place를 진행한다. two-pointer technique를 사용함으로써, In-place방식으로 문제를 해결 가능하다.

하지만, 만약 original array values가 나중에 사용된다고 하면, In-Place보단 copy 형식으로 문제를 해결한다.