2024-04-03-07. Arrays, for Search, Insert, Delete
Search, Insert, Delete는 자료구조의 가장 중요한 연산이다.
배열의 종류에 따라 이러한 연산을 어떻게 수행하는지 알아보자.
배열에 요소를 어떻게 저장할 것인가?
- Packed vs Unpacked
- 배열이 항상 가득 찬 것은 아니다. 사용하지 않는 자리가 있을 수도 있다.
- 빈 자리를 한 쪽으로 모을 것인가(Packed), 모으지 않을 것인가?(Unpacked)
- Sorted vs Unsorted
- Item들이 정렬된 상태를 유지할 것인가?
- Item(요소) : 자료구조에 저장되는 대상
Packed, Unsorted
Packed 배열의 경우, 유효하지 않은 값들을 뒤에 몰아놓고, 유효한 값의 갯수를 count라는 변수에 따로 저장해 둔다.
위 사진에서 count는 5이다. 이때, index가 5이상인 요소에는 아무 값이나 저장해도 된다.
- Search : O(n) (Linear Search만 가능)
- Insert : O(1)
- 만약 index 2에 9를 저장한다면, 원래 있던 7은 index 5로 옮기기만 하면 된다. (sorting을 고려할 필요 없으므로)
- count 변수를 1 증가시켜야 한다.
- Delete : O(1)
- index 2의 값을 삭제하려면, index 4에 있던 값을 index 2에 쓰고 count변수를 1 감소시킨다.
- 보통 Insert와 Delete를 하기 전에 Search를 먼저 한다. (ex insert시에 중복값을 허용 안하는 경우) 이때 Insert와 Delete에 걸리는 시간은 총 O(n)이 된다.
Packed, Sorted
- Search : O(logn) (Binary Search 사용 가능)
- Insert : O(n)
- Delete : O(n)
Insert, Delete 시에 sorting을 유지하기 위해 뒤의 모든 값을 옮겨야 한다.
Unpacked, Unsorted
빈 자리들이 흩어져 있으므로, count변수 하나로 사용되지 않는 Item을 파악할 수 없다. Item별로 사용 중인지 아닌지 표시하는 배열이 추가로 필요하다. 이 배열을 Mark라 하자.
- Search : O(n)
- Insert : 빈 자리가 어디 있는지 찾아야 하므로 O(n)이 걸림.
- 만약 index 1에 삽입한다면 원래 index 1에 있던 값은 다른 빈 자리에 옮겨야 함.
- 빈 자리를 index 0부터 linear search로 찾으면, 맨 마지막 자리만 빈 경우 Θ(n)시간이 걸림
- Delete : O(1)
- Packed, Unsorted와 비교하면, 값을 옮길 필요 없이 Mark배열만 수정하면 되므로 좀 더 빠르다.
- O(1)시간에 Insert하는 방법
빈 자리의 index를 head라는 변수에 따로 저장해 둔다. 빈 자리에는 아무 값이나 넣지 말고 다른 빈칸의 index를 넣는다.
- Insert를 할 때
- head에 적힌 index로 접근한다. head에 5가 적혀 있고 index 5의 값이 7이라면, head의 값을 7로 고치고 index 5에 insert를 한다.
- Delete를 할 때
- delete한 자리에 head의 값을 저장하고, head의 값은 delete한 자리의 index로 수정한다.
배열 원소로 포인터를 저장하는 것과 비슷한 원리이다.
가리키는 위치가 더이상 없다는 것은 -1로 표시하면 된다.
Unpacked, Sorted
- Search : 빈 칸이 섞여 있는 상황에서 어떻게 Binary Search를 쓸 것인가?
- 중간에 사용했다가 지워진 값이 있을 순 있지만, 한 번도 사용하지 않은 값들은 뒤에 몰아 넣는다.
- 값이 지워져도 그 값을 수정하지는 않는다. 지워진 값들은 Binary Search에 사용 가능.
- 이 방법을 사용하면 O(logn)이 걸린다. 단, 지워진 값도 포함해서 Search를 해야 하므로 packed, sorted보다 느리다.
- Insert
- Insert해야 할 위치 옆에 빈 자리가 있다면 빈 자리에 Insert하면 됨.
- 빈 자리가 없다면 빈 자리를 채울 때까지 뒤의 값들을 밀어냄.
- O(n)이 걸린다.
- Delete
- O(1)이 걸린다.
- 지울 때 값을 수정하지 않아야 Binary Search 가능. Mark배열만 수정하자.