자료구조 및 알고리즘 3 - Arrays for Search, Insert, Delete

자료구조 수업을 바탕으로 저의 생각을 정리하는 글 입니다.

 

0. Array

 

배열에서 요소의 탐색(* Search), 삽입(* Insert), 삭제(* Delete)는 매우 중요한 이슈입니다. 

이에 그 배열이 Packed 되었는지 Unpacked 인지, Sorted 되었는지 Unsorted 되었는지에 따라 SID 의 성능의 차이가 발생합니다.

 

이에 Packed 의 유무와 Sorted 의 유무에 따라 4 가지 경우의 Array 들을 따져보겠습니다.

(* 편의를 위해 중복된 값은 허용하지 않는다고 가정합니다.)

 

 

 

1. Packed, Unsorted

 

아마도 가장 간단한 방법이 아닐까 싶습니다. 

index	0	1	2	3	4	5	6
value	5	2	3	8	11

 

1.1 Search

 

해당 배열이 정렬이 되어있지 않기 때문에 이진 탐색은 불가능하고, 선형 탐색으로 수행합니다.

Search 의 성능은 O(n) 입니다.

 

1.2 Insert

 

해당 배열에 삽입 하고싶은 요소가 이미 존재하는지 확인하기 위해 Search 를 한 번 돌리고, 없으면 삽입을 해야합니다.

삽입을 하는 경우는 그냥 뒤에 추가하면 되니 상수시간이 필요합니다.

Insert 의 성능은 O(n) + O(1) 입니다.

 

1.3 Delete

 

Insert 와 마찬가지로 삭제하고 싶은 요소가 존재해야 삭제가 가능하기 때문에 Search 를 한 번 돌리고, 있으면 삭제를 해야합니다.

이때 해당 자료구조는 Packed 되어야하니 중간 값이 삭제가 되면 비어있는 자리를 채워야합니다.

만약 해당 자리를 채우기 위해 뒤에 있는 값들을 앞으로 한 칸 씩 모두 당긴다면 O(n) 의 시간이 걸립니다.

하지만 Sorted 할 필요가 없으니 그냥 가장 뒤에 값을 빈 자리에 채우는 방식으로 Packed 를 유지하면 O(1) 의 시간이 걸립니다.

Delete 의 성능은 O(n) + O(1) 입니다

 

이를 구현해 보면 다음과 같습니다.

int arr[100];
int count = 0;

int search(int target){
	for(int i=0; i<count; i++){
    	if(arr[i] == target)
        	return i;
    }
    return -1;
}

int insert(int item){
	int result = search(item);
    
    if(result != -1)
    	return -1;
    
    arr[count] = item;
    count++;
    return 0;
}

int delete_item(int item){
	int result = search(item);
    
    if(result == -1)
    	return -1;
        
    arr[result] = arr[count];
    count--;
}

int main(){
	char c;
    while(1){
    	std::cin >> c;
        if(c == 'i'){
        	int item;
            std::cin >> item;
            insert(item);
       	}
        else if(c == 'd'){
        	int item;
            std::cin >> item;
            delete_item(item);
        }
        else if(c == 'q'){
        	return 0;
        }
        else
        	std::cout << "???" << std::endl;
    }
}

 

 

 

 

 

2. Packed, Sorted

 

탐색을 할 때 이진탐색을 사용할 수 있습니다.

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

 

2.1 Search

 

이진 탐색을 수행하니 O(logn) 이 소요됩니다.

 

2.2 Insert

 

이진 탐색을 수행한 후 item 의 값이 존재하지 않을 때 Insert를 수행합니다. Insert 를 배열의 중간에 한다면 뒤에 있는 값들은 Sorted 를 유지하면서 뒤로 한 칸 씩 밀어줘야합니다. 이는 O(n) 이 소요됩니다.

Insert 의 성능은 O(logn) + O(n) 입니다.

 

2.3 Delete

 

이진 탐색을 수행한 후 item 의 값이 존재할 때 Delete 를 수행합니다. Delete 를 배열의 중간에 한다면 뒤에 있는 값들은 Sorted 를 유지하면서 앞으로 한 칸 씩 당겨줘야합니다. 이는 O(n) 이 소요됩니다.

Delete 의 성능은 O(logn) + O(n) 입니다.

 

이를 구현해보면 다음과 같습니다.

int arr[100]
int count = 0;
int lef, rig;

int search(int target){
	int l, r, m;
    l = 0;
    r = count - 1;
    
    while(l <= r){
    	m = (l + r) / 2;
    	if(arr[m] == target){
        	// 값을 찾은 경우 lef 와 rig, m 은 모두 같은 값이다.
            lef = rig = m;
            return m;
        }
        else if(arr[m] < target)
        	l = m + 1;
        else
        	r = m - 1;
    }
    
    // 못 찾은 경우 l 이 r 보다 더 커졌고, l 과 r 사이가 새로운 값이 들어갈 자리이다.
    lef = r;
    rig = l;
    return -1;
}

int insert(int item){
	int result = search(item);
    
    if(result != -1)
    	return -1;
        
    for(int i=count; i>rig; i--){
    	arr[i] = arr[i-1];
    }
    
    arr[rig] = item;
    count++;
    return 0;
}

int delete_item(int item){
	int result = search(item);
    
    if(result == -1)
    	return -1;
        
    for(int i=rig; i<count - 1; i++){
    	arr[i] = arr[i+1];
    }
    
    count--;
    return 0;
}

int main(){
	char c;
    while(1){
    	std::cin >> c;
        if(c == 'i'){
        	int item;
            std::cin >> item;
            insert(item);
       	}
        else if(c == 'd'){
        	int item;
            std::cin >> item;
            delete_item(item);
        }
        else if(c == 'q'){
        	return 0;
        }
        else
        	std::cout << "???" << std::endl;
    }
}

 

 

 

 

 

3. Unpacked, Unsorted

 

빈 자리들이 흩어져 있는 Unpacked 배열입니다. mark 를 통해 사용하는 데이터인지 확인합니다.

index	0	1	2	3	4	5	6	7
value	5	3	9	6	4	8	11	1
mark	o	o	x	o	o	x	o	x

 

3.1 Search

 

배열이 정렬되어있지 않기 때문에 이진 탐색은 불가능하고 선형 탐색을 수행합니다.

Search 의 성능은 O(n) 입니다.

 

3.2 Insert

 

배열의 빈 곳, 즉 mark 가 x 값인 index 를 찾아서 넣어주면 되니, x 를 찾는 시간인 O(n) 이 필요합니다. 하지만 특별한 잔기술을 통해 O(1) 로 시간을 줄여줄 수 있습니다.

freeheadlist 를 만들면 됩니다.

 

3.2.1 FreeHeadList

 

배열의 빈 곳을 가르키는 리스트입니다. 그리고 각각의 빈 곳의 value는 다음 빈 곳의 index를 가르킵니다. 마지막 원소는 -1을 가르킵니다.

 

FreeHeadList 값이 1 인 경우를 예로 들어보겠습니다.

index	0	1	2	3	4	5	6	7
value	5	3	9	6	4	1	-1	10
mark	o	x	o	x	o	o	x	o

 

어떤 요소를 Insert 할 때, FreeHeadList 값에 넣습니다. 그리고 FreeHeadList 가 index 인 value 를 새로운 FreeHeadList 로 설정합니다. 이런식으로 반복하다가 FreeHeadList 가 -1 이면 더 이상 빈 곳은 없다는 의미입니다.

 

FreeHeadList 는 FileSystem 에 사용됩니다.

 

 

 

FreeHeadList 를 만들었다는 가정하에 Insert 의 성능은 O(n) + O(1) 입니다.

 

3.3 Delete

 

해당 값의 index 를 search 를 통해 찾아준뒤 mark 만 x 로 바꿔주면 되니 상수 시간이 소요됩니다.

Delete 의 성능은 O(n) + O(1) 입니다.

 

이를 구현해보면 다음과 같습니다.

int arr[100]
int mark[100]
int freeheadlist = -1;

// 배열의 값들을 초기화 해줍니다.
int init(){
	freeheadlist = 0;
    for(int i=0; i<99; i++){
    	arr[i] = i+1;
    }
    arr[99] = -1;
}

int search(int target){
	for(int i=0; i<100; i++){
    	if(arr[i] == target && mark[i] == 'o')
        	return i;
    }
    return -1;
}

int insert(int item){
	int result = search(item);
    
    if(result != -1)
    	return -1;
        
    int newFreehead;
    newFreehead = arr[freeheadlist];
    arr[freeheadlist] = item;
    mark[freeheadlist] = 'o';
    freeheadlist = newFreehead;
    
    return 0;
}

int delete_item(int item){
	int result = search(item);
    
    if(result == -1)
    	return -1;
       
    mark[result] = 'x';
    arr[result] = freeheadlist;
    freeheadlist = result;
    
    return 0;
}

int main(){
	char c;
    init();
    while(1){
    	std::cin >> c;
        if(c == 'i'){
        	int item;
            std::cin >> item;
            insert(item);
       	}
        else if(c == 'd'){
        	int item;
            std::cin >> item;
            delete_item(item);
        }
        else if(c == 'q'){
        	return 0;
        }
        else
        	std::cout << "???" << std::endl;
    }
}

 

 

 

 

 

 

4. Unpacked, Sorted

 

가장 구현이 어려운 배열입니다.

index	0	1	2	3	4	5	6	7	8
value	3	5	6	8	10	13	17	20	23
mark	o	o	x	o	o	o	x	x	o

 

4.1 Search

 

mark 값이 o 인 것들에 대해서만 이진 탐색을 수행하기는 어렵습니다. 따라서 mark 상관없이 이진 탐색을 수행한 후, 해당 mark 가 o 이면 존재하는 것, x 이면 존재하지 않는 것으로 생각합니다.

하지만 어디까지 정렬 되어있었던 요소인지 체크하는 size 라는 변수가 필요합니다.(* 아래 코드에서는 count 입니다.)

이진 탐색이 가능하기 때문에 성능은 O(logn) 입니다.

 

4.2 Insert

 

5가지 경우의 수가 있습니다.

1. 이미 그 값이 존재하는 경우
2. 존재 하지 않았을 때, lef 와 rig 값이 모두 빈 자리인 경우
3. 존재 하지 않았을 때, lef 값이 빈자리, rig 값이 빈 자리가 아닌 경우
4. 존재 하지 않았을 때, lef 값이 빈자리가 아니고 rig 값이 빈 자리인 경우
5. 존재 하지 않았을 때, lef 와 rig 값이 모두 빈 자리가 아닌 경우

하지만 이때 삽입해야하는 index가 0 이어서 mark[lef] 를 하면 index 오류가 발생할 수 있습니다. 또한 rig 값이 리스트의 길이를 초과하는 경우 size 가 늘어나기 때문에 이 경우도 고려 해야합니다.

Insert 의 성능은 O(logn) + O(n) 입니다.

 

4.3 Delete

 

Delete 는 Search 를 진행한 후 해당 값의 mark 만 x 로 바꿔주면 됩니다.

Delete 의 성능은 O(logn) + O(1) 입니다.

 

이를 구현하면 아래와 같습니다.

int arr[100];
int mark[100];
int lef, rig;
int count = 0;

int search(int target){
	int l, r, m;
    
    l = 0;
    r = count - 1;
   
    while(l <= r){
   		m = (l + r) / 2;
    	if(arr[m] == target && mark[m] == 'x'){
        	rig = lef = m;
            return m;
        }
        else if(arr[m] < target)
        	l = m + 1;
        else
        	r = m - 1;
    }
    
    rig = l;
    lef = r;
    return -1;
}

int insert(int item){
	int result = search(item);
    
    if(result != -1)
    	return -1;
        
    if(lef < 0){
    	if(mark[rig] == 'x')
        	arr[rig] = item;
        else{
        	int emptyindex = -1;
            for(int i=rig; mark[i] == 'o'; i++){
            	emptyindex = i;
            }
            emptyindex++;
            
            if(emptyindex >= count)
            	count++;
         	
            for(int i=emptyindex; i>rig; i--){
            	arr[i] = arr[i-1];
            }
            mark[emptyindex] = 'o';
            arr[rig] = item;
        }
    }
    else if(rig >= count){
        count++;
        arr[rig] = item;
        mark[rig] = 'o';
    }
    else{
        if(mark[lef] == 'x' && mark[rig] == 'x'){
            arr[rig] = item;
            mark[rig] = 'o';
        }
        else if(mark[lef] == 'x' && mark[rig] == 'o'){
            arr[lef] = item;
            mark[lef] = 'o';
        }
        else if(mark[lef] == 'o' && mark[rig] == 'x'){
            arr[rig] = item;
            mark[rig] = 'x';
        }
        else{
            int emptyindex = lef;
            for(int i=rig; mark[i] == 'o'; i++){
            	emptyindex = i;
            }
            emptyindex++;
           
            if(emptyindex >= count)
            	count++;
         	
            for(int i=emptyindex; i>rig; i--){
                arr[i] = arr[i-1];
            }
            mark[emptyindex] = 'o';
            arr[rig] = item;
        }
    }
    return 0;
}

int delete_item(int item){
	int result = search(item);
    
    if(result == -1)
    	return -1;
    
    if(result == count - 1)
    	count--;
        
    mark[result] = 'x';
}

int main(){
	char c;
    while(1){
    	std::cin >> c;
        if(c == 'i'){
        	int item;
            std::cin >> item;
            insert(item);
       	}
        else if(c == 'd'){
        	int item;
            std::cin >> item;
            delete_item(item);
        }
        else if(c == 'q'){
        	return 0;
        }
        else
        	std::cout << "???" << std::endl;
    }
}