[정글] WEEK 05 | C언어라니???

C언어라니.
외면했던 건 부메랑처럼 다시 돌아오는군.

 

WEEK 05 키워드
동적 메모리 할당, 포인터, 메모리 누수, 균형 이진 탐색 트리

 

🎰 오늘 하루, C언어에 배팅

Storage Class

Class	Description
auto	기본값, 지역변수
register	변수를 메모리가 아닌 레지스터에 저장해달라고 요청, 안될때도 있음
static	static 지시자를 사용해서 생성한 지역 변수는 함수를 빠져나가도 값을 유지
extern	다른 파일에서 정의된 전역 변수나 함수에 접근 가능, 초기화는 안됨

 

오답노트

• gets()는 공백이 있는 문자열을 읽을 수 있지만 %s가 포함된 일반 scanf()는 읽을 수 없음
• gets()를 사용하면 할당된 버퍼가 오버 플로우될 위험이 있음, 줄 바꿈 "\n"을 찾거나 EOF를 만날 때까지 계속 읽기 때문에 주어진 버퍼의 한계를 초과할 수 있음
• C에서 함수는 배열과 함수를 제외한 모든 유형 반환 가능, 배열에 대한 포인터나 함수에 대한 포인터를 반환하면 됨

 

assert 함수

• 디버깅 모드에서 개발자가 오류가 생기면 치명적일 것 같은 곳에 넣는 에러 검출용 코드
• 이 함수에 걸리게 되면 버그 발생위치, call stack 등 여러 정보를 알 수 있음
• 디버그 모드에서만 컴파일이 되기 때문에 다른 코드에 영향을 주지 않는 코드만 넣어야 함

void main() {
    int score;
    
    while (1) {
        printf("Input score: ");
        scanf("%d", &score);
 
        //0보다 작은 score가 들어오게되면 assert error가 발생
        assert(score >= 0);
        printf("=> score : %d\n", score);
    }
}

// Assertion failed: score >= 0

 

 

C함수

sprintf(str, "문자열")					// str 문자열에 "문자열"이 저장됨 (단순저장, 출력X)
sprintf(str, "%d", 10)					// str 문자열에 문자열 10이 저장됨 (단순저장, 출력X)

fprintf(stdout,"Hello World\n");			// 해당 문자열 출력

FILE* fp = fopen("output.txt", "w");			// 파일 지정
fprintf(fp, "Hello World\n");				// 파일에 해당 문자열 쓰기

strcmp(str1, str2)					// 문자열 비교

// str1 == str2 -> 0, str1 > str2 -> 1, str1 < str2 -> -1

 

구조체 정의

#include <stdio.h>
#include <string.h>

typedef struct _Person {    		// 구조체 이름 _Person
    char name[20];      		// 구조체 멤버1
    int age;            		// 구조체 멤버2
} Person;               		// 구조체 별칭 Person

void main() {
    Person p1;      			// 구조체 별칭으로 Person 정의

    strcpy(p1.name, "Jiwon");
    p1.age = 25;

    printf("이름: %s, 나이: %d\n", p1.name, p1.age);
}

 

공용체 정의

#include <stdio.h>
#include <string.h>

union Person {          		// 공용체 이름 Person
    int age;            		// 공용체 멤버1
    double grade;       		// 공용체 멤버2
};

void main() {
    union Person p1 = {25};
    printf("나이: %d\n", p1.age);						// 25
    
    p1.grade = 4;
    printf("학년: %lf\n", p1.grade);						// 4

    printf("다시 나이를 출력해본다면?: %d\n", p1.age);				// 0
}

 

Geeks Quiz

#include <stdio.h>
// Assume base address of "GeeksQuiz" to be 1000
int main() {
   printf(5 + "GeeksQuiz");			// Quiz 출력
   return 0;
}

int fun(int n);						// 앞에서 선언해주어야

int main() {
    // ptr is a pointer to function fun()
    int (*ptr)(int ) = fun;				// 여기서 사용할 수 있음

    // fun() called using pointer 
    (*ptr)(3);
    return 0;
}

int fun(int n) {
  for(;n > 0; n--)
    printf("GeeksQuiz ");
}

 

동적 메모리 할당 (Malloc / Free)

• 메모리를 얼마나 사용할 지 모르는 상황에, 너무 많이 선언해 놓으면 메모리 낭비가 일어남
• 이럴 때 동적으로 메모리를 할당하여 사용
• 다만 할당 메모리는 반드시 free 함수를 통해 메모리 해제를 해주어야 함
• 메모리 해제를 해주지 않았을 경우 메모리 누수가 (Memory Leak) 발생하는 것
• 메모리 영역 = 코드 영역 + 데이터 영역 + 스택 영역 + 힙 영역

동적 할당 함수는 힙 영역으로부터 공간을 확보함

#include <stdio.h>
#include <stdlib.h>

void main() {
    int* pPoint;
 
    int nCount = 0;
 
    printf("malloc size: ");
    scanf("%d", &nCount);
 
    pPoint = (int*)malloc(sizeof(int) * nCount);
    
    ...
    free(pPoint);
}

 

Malloc() VS Calloc()

malloc()

• 지정된 크기의 메모리를 할당하고 블록의 시작 부분에 대한 포인터를 반환
• 할당된 메모리를 초기화하지 않음
• 메모리를 초기화하지 않고 읽으려고 하면 정의되지 않은 동작이 호출됨 (가비지값)
• calloc()보다 빠르며 시간 효율성이 높음

 

calloc()

• 메모리를 할당하고 할당된 메모리의 모든 바이트도 0으로 초기화함
• 메모리를 초기화하지 않고 할당된 메모리의 값을 읽으려고 하면 calloc()에 의해 이미 0으로 초기화됨으로 0 리턴
• malloc()보다 느리며 시간 효율성이 낮음

#include <stdio.h>
#include <stdlib.h>
 
int main() {
    int* allocated_with_malloc = malloc(5 * sizeof(int));
    int* allocated_with_calloc = calloc(5, sizeof(int));
 
    printf("Values of allocated_with_calloc: ");

    for (size_t i = 0; i < 5; ++i) {
        printf("%d ", allocated_with_calloc[i]);
    }
    putchar('\n');
 
    int* failed_malloc = malloc(1000000000000);
    if (failed_malloc == NULL) {
        printf("%p", (void*)failed_malloc);
    }
 
    free(allocated_with_malloc);
    free(allocated_with_calloc);
}

---

🎲 Makefile는 뭐지?

• 컴파일 해야할 코드 개수가 많아졌을 때 gcc 방식으로 커맨드 라인에 해당 파일들을 다 열거하는 것은 매우 번거로운 일
• 이러한 불편함을 해결하여 쉽게 컴파일하기 위해 사용하는 방법이 make
• make는 유틸리티명이며 이는 Makefile이라는 파일의 내용을 읽어 target file을 만듦

// 실제 파일명 아닌 target 의미
// 1) 실제 파일명과의 충돌을 해결
// 2) 성능개선
.PHONY: test

// gcc 컴파일 옵션을 넣어줌
// 1) -Wall: 모호한 코드에 대해서 경고를 보냄 (Warning으로 경고 보내줌)
// 2) -g: 디버그 정보를 추가함
CFLAGS=-I ../src -Wall -g #-DSENTINEL

// make test 입력 시 아래의 작업(명령) 진행함
test: test-rbtree
	./test-rbtree
    // valgrind: 메모리 누수 등의 문제를 찾을 수 있는 명령어
	valgrind ./test-rbtree

// 목적 파일을 만들기 위해 test-rbtree.o와 ../src/rbtree.o가 필요하다는 의미
test-rbtree: test-rbtree.o ../src/rbtree.o

../src/rbtree.o:
	// ../src 디렉토리를 통해서 rbtree.o 파일을 만들어라
	$(MAKE) -C ../src rbtree.o

// 위에서 만든 오브젝트 파일과 실행파일 삭제
clean:
	rm -f test-rbtree *.o

---

🧩 Red-Black Tree

 

레드 블랙 트리란

• 자가 균형 (Balancing) 이진 탐색 트리
• BST의 Worst Case의 단점을 개선함
• 실 사용에서 효율적이고 최악의 경우에도 상당히 우수한 실행 시간을 보임, O(log N)

 

Nil 노드

• 존재하지 않는 노드, 자녀가 없을 때 자녀를 nil 노드로 표기함
• 값이 있는 노드와 동등하게 취급함 (Nil Node = Leaf Node)

 

트리 속성

• 모든 노드는 Red, Black 둘 중 하나
• 루트 노드는 항상 Black
• 모든 nil 노드들도 항상 Black
• Red 노드의 자식은 언제나 Black
• 임의의 노드에서 자손 nil 노드까지 가는 경로들의 black 수는 모두 같음 (자기 자신 제외)

 

5번 속성 관련

• 따라서 존재하는 모든 경로에 대해 최장 경로의 거리는, 최단 경로의 거리의 두 배 이상이 될 수 없음
• 노드 X의 black height - 노드 X에서 임의의 자손 nil 노드까지 내려가는 경로에서의 black 수

 

삽입

• 삽입 후 RB 트리 속성 위반 여부 확인, 위반했다면 재조정
• 삽입하는 노드는 항상 Red
• 삽입하는 노드가 항상 Red인 이유는 삽입 후에도 5번 속성을 만족하기 위해
• 해당 노드의 두 nil 노드의 색은 Black으로 고정
• 2번 속성 위반 시 루트 노드 Black으로 변경
• 4번 속성 위반 시 회전

 

삭제

• 삭제 후 RB 트리 속성 위반 여부 확인, 위반했다면 재조정
• 속성 위반여부를 확인할 때 어떤 색의 노드가 삭제되는지가 매우 중요함

 

삭제되는 색

• 삭제하려는 노드의 자녀가 없거나 하나라면, 삭제되는 색은 삭제되는 노드의 색임
• 여기서 자녀는 유효한 값을 가지는 자녀, 즉 nil 노드는 해당되지 않음
• 삭제하려는 노드의 자녀가 둘이라면, 삭제되는 색은 해당 노드의 Successor의 색
• 여기서 Successor란 해당 노드의 오른쪽 자식 노드들 중 가장 작은 값
• 삭제되는 색이 Red 라면, 어떠한 속성도 위반하지 않음
• 삭제되는 색이 Black 이라면, 2, 4, 5번 속성을 위반할 수 있음

 

삭제 시 위반 사항 해결

• 2번 속성 위반일 경우 - 루트 노드를 Black으로 변경
• 4, 5번 속성 위반일 경우 - 삭제된 색의 위치를 대체한 노드에 Extra Black을 부여하면 됨

 

Red n Black, Doubly Black

• Extra Black을 부여받은 노드는 Doubly Black이 되거나, Red n Black이 되거나
• 해결 기준 - Double Black의 형제 노드 색과 그 형제의 자녀 노드 색
• 삭제되는 색이 Black일 때 원래 있던 위치를 대체한 노드에 Extra Black을 부여
• 대체한 노드가 Red n Black이 됐다면, Black으로 바꿔줌
• 대체한 노드가 Doubly Black이 됐다면, Case 1, 2, 3, 4 중에 하나로 해결

---

🐥 5주차 과제를 마치며

 

레드 블랙 트리에서 삽입은 삼촌 노드를 이용하여 세 개의 Case를 나누고, 삭제는 형제 노드를 이용하여 네 개의 Case를 나눈다. 처음에는 이렇게 케이스를 나누는 방식이 레드 블랙 트리를 구현하는 가장 간단한 방식이 맞는지 의심했다. 그래서 유투브 강의를 찾아 들었는데, 그래도 여전히 이해가 완전히 되지는 않았다.

그러다 트리의 삽입, 삭제 과정을 직접 손으로 그리게 되었는데, 그려보니 감을 찾게 되었다. 그제서야 삽입에서 삼촌 노드를 활용하는 것, 삭제에서 형제 노드를 활용하는 방식을 이해할 수 있게 되었다. 여기서 하나 깨닫은 것이, 내가 강의를 듣는다고 해서 그 강의를 100% 다 이해한 것이 아니고 배운 것을 내가 직접 그려보고 구현해봐야 비로소 그 강의를 이해할 수 있게 된다는 것이다.

고등학생 때 처음으로 C언어를 배웠고, 오랜만에 다시 공부하게 되었는데 당시에 포인터를 잘 이해하지 못해 힘들어 했었다. 그 당시에 완전히 이해하지 못하고 넘어갔었는데, 몇 년 뒤에 다시 C언어 포인터를 공부하려 하니 여전히 어려운 개념이다. 내가 확실히 이해하지 않고 넘겼던 것들은 다시 나에게 돌아오게 된다는 것을 또 한번 깨닫게 되는 과제였다. 하지만 일주일 동안 C언어의 감을 다시 찾았으니 남은 2주 동안 열심히 임하자 다짐했다.

 

“C언어는 F1 레이스 카와 비슷하다. 그 무엇보다도 빠르고 성능 좋지만, 아무나 운전할 수 없고, 아무나 운전하도록 두어서도 안된다.”
“C 프로젝트를 망가뜨리고 싶다면, 초짜를 프로젝트 멤버로 투입하면 된다. 수 개월 안에 찾을 수 없는 버그가 생길 것이다”

 

프로젝트 바로가기