[중간정리] 6주차 - C언어(포인터), 이진탐색트리/RB트리/AVL트리

C 코드(포인터) 문제 해결하기 (1)

#include <stdio.h> 
 
int main() 
{ 
    int numArr[5] = { 11, 22, 33, 44, 55 }; 
    int *numPtrA; 
    void *ptr; 
 
    numPtrA = &numArr[2]; 
    ptr = numArr; 
 
    printf("%d\n", /** 변수는numPtrA만을 사용하세요. **/); 
    printf("%d\n", /** 변수는 ptr만을 사용하세요. **/); 
 
    return 0; 
}

문제 요구사항

소스 코드의 빈 부분을 완성해 55와 22가 각 줄에 순서대로 출력되게 만들기

문제 해석

(1) numPtrA 는 int형 포인터(int*)이기 때문에 현재 위치(numArr의 2번 index)에서 4번 index까지 2만큼 이동해야 한다.

(2) ptr은 void형 포인터이기 때문에 포인터 연산을 수행하려면 (자료형 *) 주소값 으로 포인터 형변환을 수행해 해당 포인터에 자료형을 부여해야 한다. 그 다음, 포인터 연산을 통해 2번 index까지 1만큼 이동해야 한다.

정답 코드

#include <stdio.h> 

int main()
{
    int numArr[5] = { 11, 22, 33, 44, 55 };
    int* numPtrA;
    void* ptr;

    numPtrA = &numArr[2];
    ptr = numArr;

    printf("%d\n", *(numPtrA + 2));
    printf("%d\n", *((int*)ptr + 1));

    return 0;
}

 

 

C 코드(포인터) 문제 해결하기 (2)

#include <stdio.h> 

int main() {
    char* str[2];
    str[0] = "hello!";
    str[1] = "jungler";

    printf("1. %s\n", str[0] + 1);
    printf("2. %s\n", (str + 1)[0] + 2);

    return 0;
}

문제 요구사항

위 코드의 실행 결과 적기

문제 해석

printf의 %s 서식 지정자는 문자열의 시작 주소를 받아, 문자열 끝을 나타내는 '\0'이 나올 때까지 문자들을 차례로 출력한다.

(1) str[0] + 1의 경우, 첫 번째 문자열인 "hello!"의 두 번째 문자부터 시작해 끝까지 출력한다.

(2) (str + 1)[0] + 2의 경우, 두 번째 문자열인 "jungler"의 세 번째 문자부터 시작해 끝까지 출력한다.

정답 출력

1. ello!
2. ngler

 

 

데이터 삽입 후 구조 예측하기 (이진 탐색 트리, AVL 트리, RB 트리)

문제 요구사항

{ 7, 5, 11, 10, 2, 3, 6, 8, 15, 13 } 의 순서로 데이터를 각 자료구조에 삽입할 때, 이진 탐색 트리, AVL 트리, RB트리의 결과 트리 그리기

 

정답 트리

이진 탐색 트리(BST)

[그림1] BST 삽입 결과

AVL 트리

[그림2] AVL 트리 삽입 결과

RB 트리

[그림3] RB 트리 삽입 결과

 

 

RB트리의 삭제

문제 요구사항

위의 [그림3] RB 트리 삽입 결과에서 노드 10을 삭제했을 때의 결과 트리 그리기

※ 단, 자식 노드가 2개인 경우 전임자를 삭제할 것

문제 해석

삭제할 노드 10은 자식이 2개인 노드이다. 따라서 전임자를 찾아 삭제해야 하는데, 노드 10의 전임자는 8이다. 결국 전임자인 노드 8이 최종적으로 삭제되며, 이때 삭제되는 노드의 색은 Black이다.

 

전임자 노드 8은 자식이 없으므로, 해당 자리는 nil 노드가 대신하게 되고, 이 nil 노드는 삭제되는 색인 Black을 물려받는다. 그런데 nil 노드는 원래 Black이기 때문에, Black이 중첩되어 Doubly Black 상황이 발생하게 된다.

 

이러한 Doubly Black 상황에서, 형제가 Black이고 형제의 자식 Red가 할아버지까지 일자로 뻗어 있으므로, 이는 Case 4에 해당한다. 따라서 형제의 색을 할아버지의 색으로 복사하고, 할아버지와 형제의 자식 Red를 Black으로 만든 뒤, 기존 Doubly Black 방향(왼쪽)으로 회전해 문제를 해결한다.

정답 RB 트리

[그림4] 그림3에서 노드 10을 삭제한 후의 RB 트리

 

 

이진 탐색 트리, AVL 트리, RB 트리의 시간 복잡도

문제 요구사항

n개의 원소가 삽입되어 있는 이진 탐색 트리, AVL 트리, RB 트리에 새로운 원소를 삽입할 때, 최악의 경우에 대한 시간 복잡도를 빅 오(Big-O) 표기법으로 표현하기

문제 해석 및 정답

이진 탐색 트리는 균형을 보장하지 않으므로, 최악의 경우 선형적으로 데이터를 탐색하게 된다. 다만, AVL 트리와 RB 트리는 자가 균형 이진 탐색 트리이므로 최악의 경우에도 균형을 유지하기 때문에 로그 시간으로 데이터를 탐색할 수 있다.

• 이진 탐색 트리: O(N)
• AVL 트리, RB 트리: O(logN)

 

C 코드(포인터) 문제 해결하기 (3)

#include <stdio.h> 
void main() { 
  char arr_char[5]; 
  int arr_int[5]; 
  int64_t arr_int64[5]; 
  printf("char base : %p, %p\n", arr_char, &arr_char[2]); 
  printf("int base : %p, %p\n", arr_int, &arr_int[0]); 
  printf("int64 :%p, %p\n", arr_int64, &arr_int64[3]); 
}

// 출력
char base : 0x8004000fd3, ??? 
int base : 0x8004000fbc, ??? 
int64 : 0x8004000f90, ???

문제 요구사항

위의 C 코드를 실행했을 때 출력되어 나타나는 부분 중 세 개의 ??? 채우기

※ printf에서 %p는 포인터 변수가 가리키는 객체의 메모리 주소를 16진수 형태로 출력하게 해주는 format specifier이다. 

문제 해석

(1) char 배열은 한 칸당 주소가 1씩 증가한다. 따라서 2칸 이동하면 주소는 2만큼 증가해야 한다.

(2) int 배열은 한 칸당 주소가 4씩 증가하며, 배열의 시작 주소는 첫 번째 요소의 주소와 동일하다.

(3) int64 배열은 각 요소가 8바이트이므로, 한 칸당 주소가 8씩 증가한다. 따라서 3칸 이동하면 주소는 총 24만큼 증가한다.

※ 참고로, 출력문에서 주소는 16진수로 표현되기 때문에, 증가된 값 또한 16진수 방식에 맞춰 계산되어야 한다.

10진수의 16진수 표현

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	1	2	3	4	5	6	7	8	9	a	b	c	d	e	f

정답 출력

0x8004000fd5	// char base : 0x8004000fd3, ??? 
0x8004000fbc 	// int base : 0x8004000fbc, ??? 
0x8004000fa8	// Int64 : 0x8004000f90, ???