[TIL] 4주차 - (5) : RB-tree 구현 / 포인터의 모든 궁금증들

오늘은 작성한 내용이 많아 목차를 작성해 놓겟다.

 

1. 변수의 const 설정

2. Call by value / Call by reference

3. 포인터에 대한 궁금증

    1. 포인터란 무엇인가?

    2. 포인터는 왜 사용하는가?

    3. 이중 포인터

    4. 포인터를 사용할 시 주의점

 

---

변수의 const 설정

 

RB tree 를 구현하다보니, const를 사용한 변수에서 const를 사용한 이유가 궁금해져 const에 대해서 공부해 보았다.

 

const는 '변함없는' 이라는 의미가 있는 constant의 약자로,

변수 앞에 붙이면 선언 이후 값을 변경하지 못하도록 하며 해당 변수를 상수로 취급하게 된다.

 

그럼 이 const는 왜 쓰는 걸까?

 

바로 변수의 선언과 동시에 그 초기 값을 변하지 못하도록 할 때 사용할 수 있다.

그래서 해당 값을 변경하려 하면 컴파일 오류를 출력하며 해당 값의 변환을 막는다.

 

굿 .. !

 

 

---

 

 - test에서 함수를 const로 설정해 놓은 이유

 

void test_to_array(rbtree *t, const key_t *arr, const size_t n) {
  assert(t != NULL);

  insert_arr(t, arr, n);
  qsort((void *)arr, n, sizeof(key_t), comp);
  for (int j = 0; j<n;j++){
    printf("arr[%d] = %d\n",j,arr[j]);
  }
  key_t *res = calloc(n, sizeof(key_t));
  rbtree_to_array(t, res, n);
  for (int i = 0; i < n; i++) {
    assert(arr[i] == res[i]);
  }
  free(res);
}

 

해당 테스트 함수를 실행하기 위해 rbtree_to_array 문을 작성하려고 보니,

작성 틀에 인자들이 전부 const로 되어있었다.

 

tree를 나타내는 인자 t를 건들지 않고, 해당 rbtree를 array로 복사하라는 의미였다.

 

 

 

하지만 나는 다르게 생각해서 처음에 tree의 최소 노드를 찾고, arr에 넣은 뒤 해당 노드를 지우는 방식을 반복하여 arr로 옮기려고 했는데

이를 const 변수가 tree를 건들이지 못하도록 막아주었다.

 

int rbtree_to_array(const rbtree *t, key_t *arr, const size_t n) {
	//처음 실수했던 로직
  node_t *insert_node_to_arr;
  for(int i=0;i<n;i++){
    insert_node_to_arr = rbtree_min(t);
    arr[i] = insert_node_to_arr -> key;
    rbtree_erase(t,insert_node_to_arr);
  }
  return 0;
}

 

이 코드가 트리를 지워가며 arr로 옮기는 코드이다.

 

아무튼 해당 코드는 tree를 삭제하기 때문에 사용할 수 없고,

순차적으로 작은 키를 탐색하려면 중위순회를 하는 dfs 로직을 구현하는 것이다.

 

로직을 어떻게 구현해야 할 지에 대한 생각을 해보았다.

C언어에서는 append() 메소드로 편리하게 배열에 값을 차곡차곡 쌓을 수 없기 때문에, index를 기억해야 했다.

 

그 상황을 해결하려 고민하다가

마지막 알고리즘 DP 를 공부하면서 `외판원 순회` 문제에서 깊게 재귀하며 들어 간 뒤 해당 값을 return 하고

재귀 함수의 return값을 전달 변수에 대입하며 memoization을 했던 로직이 떠올랐다.

 

 

 

그래서 index를 전달하며 순회하는 방식으로 코드를 짜 보았다.

int dfs_tree(const rbtree *t, node_t *n,key_t *arr, int index){
  if(n->left != t->nil){
    index = dfs_tree(t,n->left,arr,index);
  }

  arr[index] = n->key;
  index ++;

  if(n->right != t->nil){
    index = dfs_tree(t,n->right,arr,index);
  }

  return index;
}

 

 

코드 로직이 너무 부실해서 내가 원하는 기능대로 작동할 수 있을지,

내가 고려하지 못한 특정 상황이 있진 않을지 걱정했는데 잘 작동되었다.

 

 

+++++ 포인터를 전역변수처럼 사용하기

 

팀원분이 배열과 Tree 변환하는 함수를 구현했는데,

내가 구현한 방식과 다르게 포인터의 장점을 활용했다.

이 방식은 배열의 저장한 인덱스를 포인터로 기억한 방식인데

인상깊어서 정리해놓겠다.

 

int rbtree_to_array(const rbtree *t, key_t *arr, const size_t n) {
	int index = 0;
	dfs_tree(t,t->root,arr,&index);
	return 0;
}

void dfs_tree(const rbtree *t, node_t *n,key_t *arr, int *index){
  if(n->left != t->nil){
    dfs_tree(t,n->left,arr,index);
  }

  arr[*(index)] = n->key;
  *(index) ++;

  if(n->right != t->nil){
    dfs_tree(t,n->right,arr,index);
  } 
}

 

위 코드는 내가 dfs로 중위순회하면서도 index를 변화시키며 배열에 저장하는 또 다른 방식이다.

 

해당 코드를 살펴보면 dfs_tree함수에서 인자를 index라는 변수의 주소로 받은 뒤,

주소를 통해 값을 변화시키고 참조함으로써, 모든 재귀 함수들이 변수들을 공유할 수 있게 했다.

 

포인터를 이용해서 전역변수로서 활용한 것이다.

 

물론 전역변수를 직접 선언하는 방법도 있겠지만, 코드의 가독성을 위해 이런 방식을 통해 로직을 구현한 것이 인상깊었다.

 

 

---

 

Call by value / Call by reference

프로그래밍에서 인자를 가진 함수의 호출 방법은 두가지가 있다.

 

바로 Call by Value (값에 의한 호출) 와 Call by Reference (참조에 의한 호출) 이다.

 

 

Call by Value ( 값에 의한 호출 )

Call by Value는 우리가 평소에 알고리즘을 공부하며, 또는 코드를 작성하며 자주 쓰던 변수를 이용한 방식이다.

 

콜바벨(Call by Vale)은 인자로 받은 값을 복사하여 처리한다.

따라서 메모리의 사용량이 증가되고, 함수 내에서 변환된 데이터는 실제 데이터에 반영되지 않는다.

 

void call_by_value(int v){
	v = 4;
}

int main(){

	int v = 0;
    	call_by_value(v);
    	printf("%d",v);
    	// 결과값 : 0
  	
    	return 0;
}

 

이와 같은 케이스를 콜바벨에 의한 함수 호출이라 할 수 있다.

 

call_by_value 함수 내에서 변경된 v 값은 해당 함수 프레임 내에서만 변경된 것이기에,

실제 값이 반영되지는 않는다.

 

 

 

 

Call by Reference ( 참조에 의한 호출 )

 

콜바레(call by reference)는 C언어에서는 Call by Address 방식으로 구현하지만,

Call by reference와 동일한 결과를 가져와서 그냥 Call by reference 라고 부른다고 한다.

 

콜바레는 인자의 실제 데이터를 복사하는 일련의 행위를 하지 않고 직접 참조하므로 속도가 상대적 빠르다.

 

 

void call_by_reference(int *v){
	*v = 4;
}

int main(){

	int v = 0;
    	call_by_reference(&v);
    	printf("%d",v);
    	// 결과값 : 4
  	
    	return 0;
}

 

위 코드를 보면 call_by_reference 에 v의 주소를 인자로 받고,

함수 내부에서 *포인터 연산자를 통해 직접 참조로 데이터를 수정했다.

 

이는 메인 함수에서도 수정된 데이터가 반영되어 4의 값이 출력되는 것을 확인할 수 있다.

 

 

---

 

포인터에 대한 모든 궁금증

 

1. 포인터란 무엇인가?

포인터는 메모리 주소를 저장하는 변수이다.

 

일반 변수들과 마찬가지처럼 포인터도 int,long,short,char,float와 같은 데이터 타입이 존재한다.

 

하지만 실제 포인터는 모두 8바이트(64bit 시스템에서)이고,

데이터 타입은 참조한 주소안의 실제 값과 일치시킨다.

 

 

C언어에서 포인터를 선언할 때는 변수 타입 뒤에 '*' 기호를 붙여서 나타낸다.

 

다음의 포인터 선언에 대한 예시 코드를 보자.

 

int num = 10; // 정수형 변수 num을 선언하고 10으로 초기화
int *ptr; // 포인터 선언 (*ptr은 정수형 변수의 주소를 저장할 수 있는 포인터)
ptr = # // ptr에 num 변수의 주소를 할당

printf("%c",ptr);
printf("%d",*ptr);

 

실제 다음 코드를 출력해보면,

첫 출력은 형태를 알 수 없는 문자와 숫자의 조합이고,

두번째는 10이 출력된다.

 

이는 포인터 변수 안의 주소를 출력한 결과와 포인터 주소를 통해 참조한 실제 데이터의 차이다.

 

포인터의 선언 시에 사용하는 '*' 는 이 변수가 주소값을 가지는 데이터라는 것을 뜻하고,

실제 포인터 변수이름 앞에 '*'을 붙여 연산에 사용하면, 해당 주소로 간접 접근(Indirect Access)하여 실제 데이터를 사용하는 행위로

서로 다른 의미라는 것에 주의해야 한다.

 

그리고 간접 접근 연산자인 '*' 실제 다른 모든 연산자들보다 후순위로 연산되므로

우선순위를 잘 파악하여 괄호를 적절히 사용해야 한다.

 

---

 

포인터를 왜 사용하나요?

 

포인터를 학습하면서 가장 큰 의문이다.

 

왜 이렇게 어려운 포인터를 사용하는가?

 

C언어를 사용하는 가장 큰 이유이자 가장 큰 장벽이다.

 

포인터를 사용했을 때의 장점을 코드 구현의 측면과 시스템의 측면으로 나눠서 정리해보았다.

 

 

- 포인터의 장점 : 코드 구현의 측면

 

1. 간접 접근(Indirect Access)

포인터를 사용하면 간접적으로 변수의 값을 변경하거나 읽을 수 있다.

이는 위에서도 설명했지만 재귀함수의 호출 상황과 같은 서로 다른 프레임에서 동일한 데이터를 다뤄야 할 때, 그 것을 가능하게 한다.

 

간접 접근을 통해 함수 호출 시 변수의 값을 변경하거나 여러 변수에 접근할 수 있다는 것은

알고리즘 구현 측면에서도 아주 간편히 코드의 유동성을 가지게 하는 것 같다.

 

 

2. 동적 메모리 할당(Dynamic Memory Allocation)

포인터를 사용하여 메모리를 동적으로 할당하고 해제할 수 있다.

 

실제 정적 배열 데이터는 선언 시 랜덤으로 액세스되는 주소값을 받아 물리적으로 연결되있는 데이터 저장 기차를 만든 것과 같다.

이 상황에서 만약 더 큰 기차가 필요해지면 현재 가지고 있는 기차 뒤에 새로운 기차공간을 붙이고 싶지만,

현재 내 기차 뒤에는 출처를 모르는 다른 기차들이 빽빽히 붙어있기 때문에 그것이 불가능하다.

 

하지만 포인터를 사용한 malloc함수를 통해 메모리 사용을 효율적으로 관리하여 프로그램의 유연성을 높인다.

 

 

 

- 포인터의 장점 : 시스템의 측면

 

1. 메모리 효율성

 

포인터를 사용하여 복사된 데이터의 메모리를 공유할 수 있다.

 

재귀함수와 같은 상황에서 만약 매번 새로운 데이터를 선언한다면,

재귀한 만큼 똑같은 변수를 위한 데이터가 할당되어야 한다.

 

또한 배열과 같은 데이터 기차를 전달하는 상황에서,

배열의 시작 부분의 주소만 주고받으면서 배열의 전체 데이터를 참조하도록 하는 것으로 메모리를 효율적으로 사용하여 전달할 수 있다.

 

이렇게 포인터를 통해서 메모리 사용을 최적화하고 시스템 자원을 절약할 수 있다.

 

2. 데이터 구조의 유연성

 

포인터를 사용하면 동적으로 데이터 구조를 조작할 수 있다.

 

데이터 자료구조와 같은 경우에는 데이터의 양을 정해놓고 만들지 않는다.

 

이때, 정적 배열과 같은 데이터 구조를 사용한다면,

추가적으로 데이터가 필요할 경우 새로운 메모리에 값을 덮어써야 하는 수고로움이 필요하다.

 

따라서 연결 리스트, 트리 등과 같은 동적인 데이터 구조를 구현할 때 유용하다.

 

 

이중 포인터 ?

 

이중 포인터란 주소 값을 가지고 있는 데이터의 주소를 가진 데이터를 말한다.

따라서 간접 참조를 하면 주소값이 출력된다.

 

이 이중 포인터라는 놈은 그럼 왜 쓸까?

 

보통은 다차원의 배열을 위해서 사용한다.

 

배열 데이터 저장소는 주소를 통해 값을 참조할 수 있는데,

이 주소들을 배열로 저장한다면 2차원의 배열 구조를 생성할 수 있다.

 

 

 

위 그림에서 arr[]는 각 arr1,arr2,arr3의 주소를 저장하는 배열이다.

따라서 arr는 이중 포인터인 셈이다.

 

 

이처럼 이중 포인터를 사용하면 동적 다차원 배열의 생성과 해제를 할 수 있다.

 

int** createMatrix(int rows, int cols) {
    int** matrix = (int**)malloc(rows * sizeof(int*));
    for (int i = 0; i < rows; ++i) {
        matrix[i] = (int*)malloc(cols * sizeof(int));
    }
    return matrix;
}

void freeMatrix(int** matrix, int rows) {
    for (int i = 0; i < rows; ++i) {
        free(matrix[i]);
    }
    free(matrix);
}

 

이중 포인터에 malloc을 통해 주소를 저장하는 동적 메모리를 할당한 뒤,

malloc 동적 배열의 주소를 각각 집어 넣고, 해제하는 것이 가능하다.

 

 

또한 함수 내에서 동적으로 할당된 메모리를 직접 변경할 수도 있다.

void allocateMemory(int** ptr) {
    *ptr = (int*)malloc(sizeof(int));
    **ptr = 42;
}

int main() {
    int* dynamicValue;
    allocateMemory(&dynamicValue);
    printf("%d", *dynamicValue); // 출력: 42
    free(dynamicValue);
    return 0;
}

 

동적으로 할당된 메모리는 이미 포인터 이므로, 해당 값을 간접 참조하기 위해선 이중 포인터를 사용해야 한다.

위 코드는 그러한 상황의 예시를 나타내고 있다.

 

 

마지막으로 동적으로 선언된 배열의 크기를 다른 함수에서 재 할당하기 위해

이중 포인터를 통해 포인터 변수를 간접 접근할 수 있다.

void resizeArray(int** arr, int newSize) {
    *arr = (int*)realloc(*arr, newSize * sizeof(int));
}

int main() {
    int* dynamicArray = (int*)malloc(5 * sizeof(int));
    // ... (기존 배열에 값 채우기)
    resizeArray(&dynamicArray, 10); // 배열 크기를 10으로 확장
    // ... (새로운 배열 크기로 작업)
    free(dynamicArray);
    return 0;
}

 

 

---

 

포인터(Pointer) 사용 시 주의점

 

1. 포인터 변수 선언 시 초기화 하기

만약 포인터가 선언만 되고 초기화되지 않았다면 포인터는 쓰레기 값을 가지게 된다.

이 상태에서 포인터 연산자를 통해 쓰레기 값을 주소로 하는 메모리 영역을 간접 접근하게 된다면 어떻게 될까?

만약 우연히 그 메모리 영역이 중요한 자료나 컴퓨터의 정보가 들어있다면 전체 시스템을 다운 시킬 수도 있다.

 

따라서 포인터는 단순히 선언만 하지 말고 선언 시 초기화를 사용하거나 NULL 포인터로 만들어 주는 것이 바람직하다.

 

 

2. NULL 포인터의 사용

 

1번에서 포인터 변수를 선언 시 아무것도 가리키지 않는다는 의미로 NULL 포인터로 선언하는 것이 바람직하다고 소개했다.

NULL은 <stdio.h> 헤더 라이브러리에 0으로 정의되어 있다.

0의 주소는 CPU가 사용하는 영역이어서 일반 프로그램이 접근할 수 없기에 안정성이 높다.

 

 

3. 포인터 자료형과 변수의 자료형 일치

 

만약 포인터의 자료형이 변수의 자료형보다 크다면 어떻게 될까?

 

그렇게 되면 포인터를 통해 간접 접근한 변수의 바이트 범위를 넘어가

이웃 바이트를 덮어쓰게 되어 문제가 생길 수 있다.

 

따라서 포인터의 자료형은 변수의 자료형과 반드시 일치시켜야 한다.

 

 

4. 절대 주소 사용 금지

 

절대 주소란 실제 사용자가 타이핑한 값으로 포인터 변수에 주소를 대입하는 방식을 말한다.

이 절대주소는 아두이노와 같은 임베디드 시스템에서만 사용한다.

 

그 이유는 PC는 윈도우와 같은 운영체제가 프로그램을 관리하기 때문에 프로그래머가 사용하고자 하는 주소가 어떠한 용도로 사용되는지 모르기 때문이다.

 

PC를 실행할 때마다 운영체제가 할당하는 주소가 매번 다르기 때문에 절대 주소는 '절대' 사용하면 안된다.