[자료구조 - C언어] 자료구조 제19강: 시간복잡도 분석 예(2)

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎

 

1. 정렬된 두 배열 합치기

1-1. 하나의 배열 복사 후 다른 배열 insert

• 정렬된 두 배열 a와 b에 저장된 m개와 n개의 데이터를 배열 c에 정렬된 상태로 저장하는 것

void merge_sorted_arrays(int m, int a[], int n, int b[], int c[]){
    for(int i=0; i<m; i++)   //먼저 배열 a의 데이터를 그대로 배열 c로 복사
        c[i] = a[i];    
    for(int j=0; j<n; j++)   //배열 b의 데이터 각각을 배열 c에 insert
        insert_to_ordered_array(m+j, c, b[j]);
}

• void insert_to_ordered_array(int n, int data[], int item)

//뒤에서부터 검사하면서 삽입하려는 값 보다 크면 shift하기
void insert_to_ordered_array(int n, int data[], int item){
    //reallocate는 제외
    int i= n-1;
    for(; i>=0 && data[i]>item; i--)
        data[i+1] = data[i];
    data[i+1] = item;
}

• 첫 번째 for문에서 m 시간 소요
• 두 번째 for문에서 (m+1) + (m+2) + … + (m + n-1) 시간 소요
• = m + nm + n(n-1)/2 = O(nm) 시간 복잡도(최악의 경우)

1-2. two-way-merging

• 정렬된 두 배열 a와 b의 최솟값을 비교하면서 배열 c에 삽입하는 방법

void merge_sorted_arrays_linear(int m, int a[], int n, int b[], int c){
    int i=0, j=0, k=0;
    while(i<m && j<n){   //한 쪽의 데이터가 모두 이동할 때 까지
        if(a[i]<b[j])      //이미 정렬되어 있는 배열이기 때문에 ~ 더 작은 쪽을 복사
            c[k++] = a[i++];
        else
            c[k++] = b[j++];
    }
    while(i<m) c[k++] = a[i++];   //남은 값 이동
    while(j<n) c[k++] = b[j++];   //while문은 둘 중 하나만 실제로 실행된다
}

• 최악의 경우 결과적으로 while문을 n번, m번 실행하기 때문에 = O(m+n) 의 시간 복잡도

 

2. 정렬된 두 연결 리스트 합치기

2-1. 하나의 연결 리스트 복사 후 다른 배열 insert (첫 번째 노드부터 다시 반복)

//각각의 연결 리스트는 이미 정렬되어 있음
Node *merge_two_ordered_list(Node *first, Node *second){
    //first 연결 리스트에 second 연결 리스트 노드 삽입하기
    Node *p = second;
    Node *q = first;
	
    while(p!=NULL){
        Node *the_node = p;
        p = p->next;    //p는 항상 second 연결 리스트의 첫번째 노드
        first = insert_to_ordered_linked_list(first, the_node);
    }
    return first;
}

• Node *insert_to_order_linked_list(Node *head, int item)

//함수에서 head가 지역변수라 head를 수정하면 함수 밖에서 변화가 적용되지 않기 때문에
//첫 번째 노드의 주소를 리턴
Node *insert_to_order_linked_list(Node *head, int item){
    Node *new_node = (Ndoe *)malloc(sizeof(Node));
    new_node->data = item;
    new_node->next = NULL;
	
    //최악의 경우 while문을 n번 반복해야 하기 때문에 O(n)의 시간 복잡도를 갖는다.
    Node *p = head, *q = NULL;
    while(p!=NULL && p->data < item){
        q = p;
        p = p->next;
    }
	
    //첫 번째 값이 이미 item 보다 커졌다: add_first
    if(q==NULL){
        new_node->next = head;
        head = new_node;    /head 노드 수정
    }
    else{    //add_after
        new_node->next = p;
        q->next = new_node;
    }
    return head;
}

• 최악의 경우 second 길이만큼 first를 순회한다 = second 길이만큼 first 길이를 반복 = O(mn)

2-2. two-way-merging

• 정렬된 두 연결 리스트의 첫 번째 노드값을 비교하는 방법

Node *merge_two_ordered_list2(Node *first, Node *second){
	Node *head = NULL, *tail = NULL;    //합치는 연결 리스트의 노드
	Node *tmp;
	while(first != NULL && second != NULL){  //한 쪽이 모두 소진될 때 까지
		if(first->data <= second->data){
			tmp = first;
			first = first->next;
		}
		else{
			tmp = second;
			second = second->next;
		}
		tmp->next = NULL;

		if(tail==NULL)    //empty list
			head = tail = tmp;
		else{
			tail->next = tmp;
			tail = tmp;
		}
	}
	
	//first 또는 second에 노드가 남아 있다면 - while문 2개 중 1개만 실행
	if(first != NULL)
		tail->next = first;
	else if(second != NULL)
		tail->next = second;
	
	return head;
}

• 최악의 경우 결과적으로 while문을 (n+m)번 실행하기 때문에 = O(m+n) 의 시간 복잡도

2-3. 하나의 연결 리스트 복사 후 다른 배열 insert (처음부터 traverse X, 그 이후부터)

• 보통 반복문 1번 → O(n)
  • 반복문 안에 반복문 → O(n^2)
• 아래 코드는 반드시 그렇지는 않다는 것을 보여줌(2-1 수정 버전)

Node *merge_two_ordered_lists3(Node *first, Node *second){
	//insert nodes of second into first
	Node *p = second;
	Node *q = first, *pre_q = NULL;

	while(p!=NULL){
		Node *the_node = p;
		p = p->next;

		//p, q, the_node는 어떤 경우에도 후진하지 않는다 - 무조건 전진만
		while(q != NULL && q->data < the_node->data){
			pre_q = q;    //이전 노드의 주소를 알아야 그 다음에 삽입할 수 있기 때문에
			q = q->next;
		}
		if(pre_q == NULL){    //add p at the front
			the_node->next = first;
			first = the_node;
		}
		else{    //add after pre_q
			the_node->next = q;
			pre_q->next = the_node;
		}
		pre_q = the_node;  //내부의 while문을 거치지 않고 내려온 경우에 대비해서 한 칸 전진
	}
	return first;
}			

• 반복문이 두 번 중첩되어 있지만
  • 삽입하고 항상 처음부터 다시 순회하는 2-1(m을 n번 수행하는 O(mn))과 다르게
  • 다시 처음부터 순회하지 않고, 삽입한 노드(= the_node)의 위치부터 다시 삽입할 위치를 탐색
  • = m번 안에서 총 n만큼 수행 = 최악의 경우 시간 복잡도는 O(m+n)

 

3. 연결 리스트 뒤집기

Node *inverse_list(Node *head){
	//empty list 이거나 list의 길이가 1인 경우는 뒤집을 수 없기 때문에 
	if(head==NULL || head->next=NULL)
		return head;
	Node *q = NULL;
	Node *p = head;
	Node *r = p->next;    //q, p, r 순서
	
	while(p!=NULL){
		p->next = q;   //뒤집고
		q = p;         //앞으로 전진
		p = r;
		if(r!=NULL)
			r=r->next;
	}
	return q;
}

• head부터 리스트의 길이(n) 만큼 순회 =  시간 복잡도는 O(n)

 

4. 연결 리스트에서 특정 조건을 만족하는 모든 노드 삭제하기

//배수 삭제하기
Node *remove_all_divisible(Node *head, int divisor){
	Node *p = head;
	Node *q = NULL, *deleted = NULL;
	while(p!=NULL){
		if(p->data % divisior == 0){
			if(q==NULL)
				head = p->next;
			else
				q->next = p->next;
			deleted = p;
			p = p->next;
			free(deleted);
		}
		else{
			q = p;
			p = p->next;
		}
	}
	return head;
}

• 연결 리스트를 한 번 순회하면서 삭제 = 시간 복잡도는 O(n)

 

5. 미로 찾기

5-1. 스택을 이용한 미로 찾기

int main(){
    Stack s = create();    
    Position cur;              
    cur.x = 0;
    cur.y = 0;
 
    while(1)
    {
        maze[cur.x][cur.y] = VISITED;       
        if(cur.x == n-1 && cur.y == n-1){   
            printf("Found the path.\\\\n");
            break;    //break가 있기 때문에 시간 복잡도 분석이 까다로움
        }
        
        bool forwarded = false;   
				//많아봤자 동서남북 4가지 방향만 반복하기 때문에 시간 복잡도에 큰 영향 X  
        for(int dir = 0 ; dir<4; dir++){ 
						//어떤 셀도 2번 방문 X, movable에 의해 4번 이상 검사되지 않음          
            if(movable(cur, dir)==1){    
                push(s, cur);               
                cur = move_to(cur, dir);    
                forwarded = true;          
                break;
            }
        }
        if(!forwarded){ 
            maze[cur.x][cur.y] = BACKTRACKED;    
            if(is_empty(s)){
                printf("No path exists.\\\\n");
                break;
            }
            cur = pop(s);  
        }
    }
}

• 시간 복잡도는 O(n^2)이지만 이는 데이터의 개수 자체가 n x n개 이기 때문에 선형시간이다.

5-2. 큐를 이용한 미로 찾기

int main(){
    Queue q = create();
    Position cur;    
    cur.x = 0;
    cur.y = 0;
    
    enqueue(q, cur);  
    maze[0][0] = -1;
    
    
    //출구에 도달할 때 까지 = 큐가 빌 때 까지
    //출구가 없는 미로라도 큐가 비면 종료
    while(!is_empty(q)){
        Position cur = dequeue(q);    
        //많아봤자 동서남북 4가지 방향만 반복하기 때문에 시간 복잡도에 큰 영향 X  
        for(int dir = 0; dir<4; dir++){
            if(movable(cur, dir)){
                Position p = move_to(cur, dir);
                maze[p.x][p.y] = maze[cur.x][cur.y] -1;
                if(p.x == n-1 && p.y == n-1){
                    printf("Found the path.\\\\n");
                    break;
                }
                enqueue(q, p);  //어떤 셀도 2번 이상 큐에 들어가지 않는다
            }
        }
    }
}

• 시간 복잡도는 O(n^2)이지만 이는 데이터의 개수 자체가 n x n개 이기 때문에 선형시간이다.

 

 

 

 

---

부경대학교 권오흠 교수님의 [c로 배우는 자료구조 및 여러 가지 예제 실습] 강의 정리입니다. 감사합니다.

https://youtu.be/fg8sdBck2ds