배열(Array) - 정의와 4가지 형태의 배열에 대하여

배열이란

: "같은 형태"의 데이터(자료형)가 "연속적"으로 붙어서 저장되어 있는 자료 구조.

특징

• 검색이 빠르다(여러 기법들 이용)
• 탐색이 빠르다(O(1)만에 찾을 수 있음(컴퓨터 특성))
• 삭제, 삽입이 느리다(연속된 메모리를 차지하는 특성상 그렇다)
• 사이즈가 고정적이다

4가지 형태의 배열(packed, sorted를 기준으로)

<용어>
packed : 사용하는 인덱스만 왼쪽으로 몰아놨다.
sorted : 인덱스 순으로 값이 정렬되어 있다. (여기선 오름차순)

1. Packed, Unsorted(가장 간단한 형태)

index	0	1	2	3	4	5	6	7
value	3	7	4	10	2	-	-	-

 

가장 보편적으로 알고 있는 형태.
여기에 추가로 값이 몇 개 저장되어있는지 세는 변수가 있다고 하자.

counter(C)
5

• Search : 하나 하나 처음부터 뒤져봐야 한다. O(N)
• Insert : 맨 뒤에 삽입한다면 모르겠지만, 그 외에는 삽입하면 나머지 값들을 뒤로 밀어야 한다.
  1. 맨 뒤 삽입: O(1) : C가 있기 때문에, arr[C]에 삽입하면 바로 된다.
  2. 그 외: 중간에 삽입하면, 그 뒤로 다 밀어야 해서 최대 O(N) + O(1) = O(N)
• Delete : 값을 찾아서(O(N)) 삭제하고(O(1)) 빈자리를 없게 하기 위해 당겨준다(O(N))
  1. 맨 뒤 삭제: O(1) : C가 있기 때문에, arr[C-1] 바로 삭제하고 끝.
  2. 그 외: 인덱스로 지운다면 찾는 과정 없이 O(N+1), 값으로 찾아서 지운다면 위처럼 O(2N+1) = O(N)

2. Packed, Sorted

index	0	1	2	3	4	5	6	7
value	2	3	4	7	10	14	-	-

• Search : 정렬된 배열이기에, 이진 탐색(Binary Search)이 가능하다. O(logN)
• Insert : 맞는 자리를 찾아(정렬된 상태 유지 때문에)가야 하니까 자리 탐색 O(logN) 후 빈자리 만들어 주기 위해서 뒤로 밀고(O(N)) 삽입(O(1)), O(N+logN+1) = O(N)
• Delete : 값을 찾아서(O(logN)) 삭제하고(O(1)) 빈자리 없게 당겨주기(O(N))
  1. 맨 뒤 삭제: 당겨주는 작업 없음, O(logN + 1) = O(logN)
  2. 그 외: 인덱스로 지운다면 바로 지우고 당겨주기만, O(1 + N) = O(N), 값으로 지우면 위처럼 O(logN + 1 + N) = O(N)

=> 삽입, 삭제가 빈번하면 비효율적이다.

3. Unpacked, Unsorted

index	0	1	2	3	4	5	6	7
value	3	7	5	10	2	7	11	-
mark	O	O	X	O	X	X	O	X

 

Unpacked는 mark라고 이 인덱스가 쓰이는지 안쓰이는지 알려주는 것이 필요하다.

• Search : 그저 선형 탐색이다. O(N)
• Insert : 일단 넣을 수 있는지 검사를 하고(O(N)) 넣기 O(1) = O(N+1) = O(N)
  => 그런데 어떠한 기술을 적용하면 O(1)만에 할 수 있다.
  Free List를 만드는 것. (빈(X표시) 공간을 가리키는 연결 리스트)
  
  (실제로 이런 구조를 사용하는게 NTFS(윈도우 파일 시스템)의 Free BlockList File System 기능이다)
• Delete : 인덱스로 삭제 = O(1)(packed와 다르게 당길 필요가 없다), 값으로 삭제는 탐색(O(N))후 삭제(O(1))로 O(N+1) = O(N)

4. Unpacked, Sorted

index	0	1	2	3	4	5	6	7	8	9
value	3	7	5	10	2	7	11	-	-	-
mark	O	O	X	O	X	X	O	X	X	X

 

Sorted니까 이진 탐색(Binary Search)를 쓰고 싶은데, Unpacked라 안될 것 같다.
하지만 방법이 있다. "어차피 한번 썼으면 정렬이 되있긴 하니까" 아이디어다.

배열을 크게 '한번 이상 썼던 칸'과 '한번도 안쓴 칸(예시에서 7이상 index)'으로 나눈다.
그러면 생각해보자, 한번 이상 썼던 칸에서는 이진 탐색을 하면, 문제없다는 것을 발견할 것이다.
위에서 말했듯이 "어차피 한번 썼으면 정렬이 된다"가 한번도 안쓴 칸을 배제하면 성립하기 때문이다.
그렇다면 이제, 이진 탐색이 가능하다고 하고 시간복잡도를 계산해보겠다.

• Search : Binary Search, O(1)
• Insert : 정렬 상태를 유지하면서 넣을 수 있는 자리 탐색(O(logN), 이진 탐색법으로 그런 일을 할 수 있다), 그 자리에 넣고(O(1)) 다음 빈칸(mark=X)까지만 밀기(O(N)) = O(logN + N + 1) = O(N)
• Delete : 찾고(O(logN)) 지우기(O(1)) = O(logN + 1) = O(logN)