on
정글에서 살아남기 | WEEK05 | 이런 C
정글에서 살아남기 | WEEK05 | 이런 C
반응형
C 알파벳만 봐도 어질어질해짐... (사진은 기숙사 C동)
4주 간 알고리즘 던전에서 나왔더니 C언어의 지옥이 다가왔다...! 새로운 탐험 시작!!
운영진님들이 말하는 C언어란...
시작부터 겁을 주신다...ㅋㅋ 여하튼 C는 Assembly 언어와 매우 가까운 언어로, C를 사용하면서 조금 더 컴퓨터의 본질에 가까이 가는 것을 기대하신다고 한다.
그리고 이번 week05주 차의 키워드
WEEK05: 동적 메모리 할당, 포인터, 메모리 누수, 균형 이진 탐색 트리
저 단어들은 뭘까...? 뭐 알고리즘 할 때도 당연히 다 모르던 키워드들이었기 때문에 크게 신경쓰지 않았다. 결국엔 다 알게 될 것이기 때문에!!
1. 개발환경 설치
C언어 개발을 더 매끄럽게 하기 위해 Ubuntu 20.04 LTS (x86_64)환경에서 gcc 9.x 컴파일러를 사용하는 것을 권장하셨다.
나는 윈도우10 유저이기 때문에 윈도우에서 제공하는 WSL2(Window Subsystem for Linux 2)를 설치하였고, VScode에서 Remote-WSL 플러그인을 설치하여 비주얼스튜디오코드로 원격으로 ubuntu 환경에서 컴파일할 수 있게 했다. (쉽지 않았지만 그새 구글링 실력이 많이 늘어 있더라... 구글링으로 다 해결했으니...)
윈도우를 사용하는 동기들은 그래도 나름 수월하게 개발환경을 셋팅했지만, MacOS를 사용하는 동기들은 꽤 고생했다. 맥을 사용한 적이 없어서 잘 모르지만 윈도우에 비해 gcc 돌아가는 환경을 설정하는게 어려워 보였음... 난 평생 윈도우만 써야겠다...(그래도 사과달린 노트북 꼭 사용하고 싶음 언젠가)
2. C언어 기본 문법 공부
나는 4월부터 코딩을 공부하기 시작했다. 파이썬과 플라스크를 공부했고, 공부한지 얼마 되지 않아서 정글에 입학했기 때문에 C언어에 대해 무지했다.(아 유튜브로 하루 공부한 적 있다) 나뿐만 아니라 다른 분들도 C를 거의 처음 접해봐서 다들 파이썬과는 다른 언어에 매우 당황쓰..
아무튼! C언어 공부하면서 참고하면 좋은 사이트들(진짜 이분들 자료 있어서 매우 감사했다)
모두의 코드
코딩도장
당연히 어떤 학문이나 분야든 기초를 튼튼히 하는 것은 굉장히 중요하다. 지금 당장 기본 개념의 중요성이 떨어지더라도 장기적으로 일을 하다 보면 기초의 중요성이 점점 더 크게 느껴진다. 그렇기 때문에 만약 C를 공부하는 상황이 있다면 기초부터 차근차근 공부할 것을 매우 추천드린다(물론 나도 지속적으로 기본 개념들을 꾸준히 보면서 더 익혀야 한다ㅠㅠ)
아 그리고 모든 개념들이 중요한 것은 마찬가지지만 특히 포인터의 개념에 대해서 확실하게 잡는 것을 강조한다. 간단하게 얘기하자면 포인터는 메모리 상에 위치한 특정한 데이터의 (시작)주소값을 보관하는 변수이다.
현재 우리가 사용하는 컴퓨터는 대부분 64비트 운영체제이기 때문에 우리의 컴퓨터가 사용할 수 있는 주소값의 크기는 8byte이다. 즉 포인터가 가지는 크기도 8바이트!
(다만 포인터에도 여러 type들이 존재한다. int형 데이터의 주소값을 저장하는 포인터와 char형 데이터의 주소값을 저장하는 포인터가 다르다.)
포인터는 주소값을 보관하는 데이터의 형에 * 를 붙임으로써 정의되고, 특정한 데이터의 메모리 상의 주소값을 알고 싶다면 변수 앞에 & 를 붙이면 된다. 자세한 내용이 궁금하다면 위에서 추천한 사이트 추천!(그 외에도 구글링 하다 보면 충분히 이해하실거라 생각함!)
3. RBTREE 공부
이번 주를 정말 힘들게 했던 주인공 등장...! 위키백과에 의하면 Red-Black tree(레드-블랙 트리)는 자가 균형 이진 탐색 트리 로서, 대표적으로는 연관 배열 등을 구현하는 데 쓰이는 자료구조라고 한다. 레드-블랙 트리는 복잡한 자료구조지만, 실 사용에서 효율적이며 최악의 경우에도 O(logN) 시간복잡도를 보장할 정도로 안정(balanced)되었다.
즉 레드-블랙 트리는 실시간 처리와 같은 실행 시간이 중요한 경우에 유용하게 쓰이고 일정한 실행 시간을 보장하는 또 다른 자료구조를 만드는 데 좋다고 한다. 예를 들면 각종 기하학 계산에 쓰이는 많은 자료구조들이나 많은 SDK나 라이브러리 세트에서 검색 알고리즘으로 사용되고 있다고 한다.
글을 보면서도 잘 이해가 되지 않아서 많은 자료들을 찾아봤었다. 그니까 레드-블랙 트리도 이진탐색트리의 일종인데, 이진탐색트리는 탐색을 위해 사용되는 자료구조다. 자료를 이진트리로 구성하여 검색 구조로 삼는 이유는 단순한 구조이면서도 자료의 검색, 삽입, 삭제가 효율적이기 때문이다.
위의 이진트리 그림을 보면, 루트 노드부터 검색을 시작하게 되고 한 노드는 자식을 두 명까지 가질 수 있다. 또한 자신보다 작은 값의 노드는 왼쪽, 큰 값의 노드는 오른쪽에 두는 규칙을 가지고 있다. 때문에 탐색시 모든 노드를 고려할 필요가 없어서 효율적이다. 예를 들면 위의 트리에서 8을 찾는다고 하면 10->7->8로 두 번의 비교만으로 찾을 수 있다.
마냥 좋을 것 같은 이진탐색트리에도 단점이 있다.
위의 그림처럼 값이 한 쪽으로 쏠리게 들어왔을 경우 가장 아래에 있는 값을 검색하기 위해서는 결국 모든 경우를 고려해야 하고, 이는 일반적인 선형 검색의 시간복잡도 O(N)과 다를 게 없다. 그래서 어떤 상황에서도 O(logN)을 보장하는 RBtree가 많이 사용된다고 한다.
레드-블랙 트리는 각각의 노드가 레드나 블랙의 색상 속성을 가지고 있는 이진 탐색 트리
RBTREE 특성
좋은 효율을 보이는 레드-블랙 트리를 구현하기 위해서는 다음과 같은 조건이 필요하다.
1. 노드는 '레드' 혹은 '블랙' 중 하나이다.
2. 루트 노드는 '블랙'이다.
3. 모든 리프 노드(NIL)들은 '블랙'이다.
4. 노드가 '레드'일 때, 자식 노드 양쪽은 언제나 모두 '블랙'이다. (즉 레드 노드는 연달나 나타날 수 없다)
5. 각 노드에 대해 해당 노드에서 리프 노드를 제외한 자식 노드까지의 모든 경로들은 같은 수의 '블랙' 노드 개수를 가진다.
RBTREE 동작
레드-블랙 트리는 수행 시간을 보장하기 위해 트리를 수정한다. 그 결과 레드-블랙 트리의 특성을 위반하게 되기 때문에 몇몇 노드의 색을 바꾸거나(색상 전환) 포인터 구조를 바꿔야 하는데 이러한 작업을 로테이션이라고 한다. 노드를 삽입하고 삭제하는 과정에서 많은 case들이 존재하는데, 이런 경우들을 고려하여 구현해야 코드가 정상적으로 잘 돌아간다. 삽입과 삭제별로 이해하기 어려운 다양한 case들이 존재하지만, RBTREE에 대한 자세한 설명은 다음에 따로 정리하도록 하겠다.(워낙 내용이 많다... 지금은 malloc 구현하느다 바쁨 ㅠㅠ)
코드 구현
#include #include typedef enum { RBTREE_RED, RBTREE_BLACK } color_t; typedef int key_t; typedef struct node_t { color_t color; key_t key; struct node_t *parent, *left, *right; } node_t; typedef struct { node_t *root; } rbtree; rbtree *new_rbtree(void); void delete_rbtree(rbtree *); node_t *rbtree_insert(rbtree *, key_t); node_t *rbtree_find(const rbtree *, const key_t); node_t *rbtree_min(const rbtree *); node_t *rbtree_max(const rbtree *); int rbtree_erase(rbtree *, node_t *); int rbtree_to_array(const rbtree *, key_t *, const size_t); void *insert_fixup(rbtree *, node_t *); void *erase_fixup(rbtree *, node_t *); // nil 생성 node_t make_nil = { .color = RBTREE_BLACK, .left = NULL, .right = NULL, .parent = NULL }; node_t *nil = &make;_nil; // 트리 생성 rbtree *new_rbtree(void) { rbtree *p = (rbtree *)calloc(1, sizeof(rbtree)); // rbtree의 인자를 1개 메모리 할당(할당된 공간의 값을 모두 0으로 초기화) return p; } // RBtree 구조체가 차지했던 메모리 반환 void del_node(node_t * t) { if (t != NULL) { del_node(t->left); del_node(t->right); } free(t); } void delete_rbtree(rbtree *t) { del_node(t->root); free(t); } // 좌회전 함수 node_t *left_rotate(node_t *t, node_t *base) { node_t *y = base->right; base->right = y->left; if (y->left != NULL) { y->left->parent = base; // 왼쪽으로 돌리기 때문에 y의 작은 수는 base 자식으로 옮겨짐 } y->parent = base->parent; // 부모 노드 옮기기 if (base->parent == NULL) { // base->parent가 없다면 y가 root t = y; } else if (base == base->parent->left) { // base가 왼쪽에 위치한다면 base->parent->left = y; } else { base->parent->right = y; } y->left = base; base->parent = y; return t; } // 우회전 함수 node_t *right_rotate(node_t *t, node_t *base) { node_t *y = base->left; base->left = y->right; if (y->right != NULL) { y->right->parent = base; } y->parent = base->parent; if (base->parent == NULL) { t = y; } else if (base == base->parent->right) { base->parent->right =y; } else { base->parent->left = y; } y->right = base; base->parent = y; return t; } void *insert_fixup(rbtree *t, node_t *n) { node_t *y; while (n->parent != NULL && n->parent->color == RBTREE_RED) { // 부모 노드가 RED면 if (n->parent == n->parent->parent->left) { // 부모 노드가 조부모 노드의 왼쪽에 있다면 y = n->parent->parent->right; // 삼촌 노드 if (y != NULL && y->color == RBTREE_RED) { // 부모, 삼촌 다 RED n->parent->color = RBTREE_BLACK; y->color = RBTREE_BLACK; n->parent->parent->color = RBTREE_RED; n = n->parent->parent; // 균열이 생기는 지점(조부모 노드가 레드로 변하면서 조건을 깰 수 있기 때문!) } else { // 부모 노드 RED, 삼촌 노드 BLACK if (n == n->parent->right) { // 현재 노드가 오른쪽에 위치한다면(부모보다 큰 수) n = n->parent; t->root = left_rotate(t->root, n); } n->parent->color = RBTREE_BLACK; n->parent->parent->color = RBTREE_RED; t->root = right_rotate(t->root, n->parent->parent); } } else { // 부모 노드가 조부모 노드의 오른쪽에 있다면 y = n->parent->parent->left; // 삼촌 노드 if (y != NULL && y->color == RBTREE_RED) { // 부모, 삼촌 다 RED n->parent->color = RBTREE_BLACK; y->color = RBTREE_BLACK; n->parent->parent->color = RBTREE_RED; n = n->parent->parent; } else { if (n == n->parent->left) { // 현재 노드가 왼쪽에 위치한다면 n = n->parent; // 로테이션 할 기준 변경 t->root = right_rotate(t->root, n); } n->parent->color = RBTREE_BLACK; n->parent->parent->color = RBTREE_RED; t->root = left_rotate(t->root, n->parent->parent); } } } // t->root->parent = NULL; t->root->color = RBTREE_BLACK; // 루트 색은 검정! } node_t *rbtree_insert(rbtree *t, const key_t key) { node_t *y = NULL; node_t *x = t->root; // 새로 들어올 노드 생성 node_t *n = (node_t *)malloc(sizeof(node_t)); n->color = RBTREE_RED; n->key = key; n->left = NULL; n->right = NULL; while (x != NULL) { // 노드 n이 들어갈 위치 찾는 과정 y = x; // y는 n의 부모 노드 if (key < x->key) { x = x->left; } else { x = x->right; } } n->parent = y; if (y == NULL) { // x가 0이었다면(트리가 없었다면) t->root = n; } else if (key < y->key) { y->left = n; } else { y->right = n; } insert_fixup(t, n); return n; } node_t *rbtree_find(const rbtree *t, const key_t key) { node_t *find_node; find_node = t->root; while (find_node != nil) { if (key == find_node->key) { return find_node; } if (key < find_node->key) { find_node = find_node->left; } else if (key > find_node->key) { find_node = find_node->right; } return NULL; } } node_t *rbtree_min(const rbtree *t) { node_t *tmp = t->root; while (tmp->left != NULL) { tmp = tmp->left; } return tmp; } node_t *rbtree_max(const rbtree *t) { node_t *tmp = t->root; while (tmp->right != NULL) { tmp = tmp->right; } return tmp; } /*rbtree의 특성 유지 노드의 위치를 이동시키는 함수*/ void tree_transplant(rbtree *t, node_t *n1, node_t *n2) { if (n1->parent == NULL) { t->root = n2; } else if (n1 == n1->parent->left) { n1->parent->left = n2; } else { n1->parent->right = n2; } if (n2 != NULL){ n2->parent = n1->parent; // n1의 부모 노드와 n2의 부모 노드 연결 } } // node_nil: x가 없을 때, 더미노드 nil 반환 node_t *node_nil(node_t *x) { if (x == NULL) { return nil; } else { return x; } } // successor node_t *successor(rbtree *t, node_t *x) { if (x->right != NULL) { // x의 우노드가 존재할 때, 서브트리의 최소값 찾기 node_t *c = x->right; while (c->left != NULL) { c = c->left; } return c; } node_t *p = x->parent; while (p != NULL && x == p->right) { // x의 우노드가 없을 때, 위로 올라가다 처음 오른쪽 위로 꺾였을 때 첫 노드 x = p; p = p->parent; } return p; } // 노드 삭제 시 rbtree 특성 유지시키는 함수 void *erase_fixup(rbtree *t, node_t * x) { node_t *s; // x노드의 형제 노드 node_t *s_left, * s_right; // s노드의 좌, 우 자식 노드 while (x != t->root && x->color == RBTREE_BLACK) { if (x == x->parent->left) { // x노드가 왼쪽에 있다면 s = x->parent->right; if (s->color == RBTREE_RED) { // case1: 형제 노드가 red일 경우 s->color = RBTREE_BLACK; x->parent->color = RBTREE_RED; t->root = left_rotate(t->root, x->parent); s = x->parent->right; } s_left = node_nil(s_left); s_right = node_nil(s_right); if ((s_left->color == RBTREE_BLACK) && (s_right->color == RBTREE_BLACK)) { // case2: 형제 노드 'black', 형제 노드의 자식 노드 모두 'black' s->color = RBTREE_RED; // 색상 전환 x = x->parent; } else { if (s_right->color == RBTREE_BLACK) { // case3: 형제 노드 'black', 형제 좌노드 'red', 형제 우노드 'black' s_left->color = RBTREE_BLACK; s->color = RBTREE_RED; t->root = right_rotate(t->root, s); // 단일 회전 s = x->parent->right; } s->color = x->parent->color; x->parent->color = RBTREE_BLACK; s->right->color = RBTREE_BLACK; t->root = left_rotate(t->root, x->parent); x = t->root; } } else { s = x->parent->left; if (s->color == RBTREE_RED) { s->color = RBTREE_BLACK; x->parent->color = RBTREE_RED; t->root = right_rotate(t->root, x->parent); s = x->parent->left; } s_left = node_nil(s_left); s_right = node_nil(s_right); if ((s_right->color == RBTREE_BLACK) && (s_left->color == RBTREE_BLACK)) { s->color = RBTREE_RED; x = x->parent; } else { if (s_left->color == RBTREE_BLACK) { s_right->color = RBTREE_BLACK; s->color = RBTREE_RED; t->root = left_rotate(t->root, s); s= x->parent->left; } s->color = x->parent->color; x->parent->color = RBTREE_BLACK; s->left->color = RBTREE_BLACK; t->root = right_rotate(t->root, x->parent); x = t->root; } } } x->color = RBTREE_BLACK; } int rbtree_erase(rbtree *t, node_t *p) { node_t *y = p; // 삭제되거나 이동될 노드 node_t *x; // y의 원래 위치(삭제 or 이동되기 전 위치) color_t y_or_color = y->color; // y의 원래 색 if (p->left == NULL) { // p노드의 좌노드가 없을 때 x = node_nil(p->right); tree_transplant(t, p, x); free(p); } else if (p->right == NULL) { // p노드의 우노드가 없을 때 x = node_nil(p->left); tree_transplant(t, p, x); free(p); } else { // p노드가 자식노드 모두를 가지고 있을 때 y = successor(t, p); y_or_color = y->color; x = node_nil(y->right); if (y->parent == p) { x->parent = y; } else { tree_transplant(t, y, x); y->right = p->right; y->right->parent = y; } tree_transplant(t, p, y); y->left = p->left; y->left->parent = y; y->color = p->color; free(p); } if (y_or_color == RBTREE_BLACK) { erase_fixup(t, x); } // 루트가 nil이 될 경우가 발생하기 때문에 nil과 연결 끊기 if (t->root == nil) { t->root = NULL; } else if (nil->parent != NULL) { if (nil->parent->left == nil) { nil->parent->left = NULL; } else { nil->parent->right = NULL; } } nil->parent = NULL; return 0; }
4. TEST
일주일 동안 레드-블랙 트리를 구현하는데 정말 많은 어려움을 겪었다. 정글에서 5주를 보내면서 제일 벽을 느꼈던 시간이었다. 조원 형들과 다른 친구들에게 많이 물어보면서 겨우겨우 이해하고 코드를 짰다. 더군다나 테스트에서 요구하는 방식과 다른 방식으로 구현해서 테스트 케이스 통과가 되지 않았고, 결국 테스트 보기 하루를 남기고 처음부터 다시 구현하기도 했다 ㅠㅠ..
일단 rbtree를 구현했다면 테스트 통과는 크게 어렵지는 않았다. 다만 노드의 개수를 카운팅하는 문제도 있었는데 시험 시간 동안 망할 vscode의 설정 때문에 한 시간 시험 중 45분을 날려먹으면서 마지막 문제는 해결하지 못 했다.. 아직도 갈 길이 멀다 ㅠㅠ 지금보다 더 빡세게 할 필요성을 확연하게 느꼈다.
5. WEEK05 이슈들
복통
이번 주 내내 복통이 끊임 없이 날 괴롭혔다. 시도 때도 없이 아랫배에 통증이 있어서 스트레스가 매우 컸다. 여기 와서 매일 만족하며 살고 있었는데(물론 공부량이 매우 빡세지만, 그래도 공부에만 몰입할 수 있어서 좋다) 복통으로 하루에 화장실만 5번을 가다 보니 시간을 공부에 몰두하기 힘들었다. 그나마 다행인 것은 화장실 갔다 오면 통증이 수그러진다는 점...어떤 때는 아프지 않아서 그냥 넘어갔지만, 요즘도 격일로 배가 아프다 ㅠㅠ 내일은 진짜 병원에 다녀와야 할 듯 싶다.
협력사 설명회 - 채널 코퍼레이션
처음으로 협력사 기업과 얘기를 나누는 시간을 가졌고, 다시금 열정에 기름붓기 충분했다. 일단 채널 코퍼레이션의 최시원 대표님이 진짜 너무 멋있었다. 남자가 봐도 반하ㄱ...
여하튼 대표님 같은 경우 2010년부터 쭉 창업을 하셨고, 그러다 보니 사업의 본질, 즉 고객의 입장을 우선적으로 고려하시는 모습이 굉장이 인상적이었다. 나도 창업을 했을 때 항상 우리의 고객이 누구인지, 그들이 겪는 문제가 무엇인지, 그들에게 필요한 것이 무엇인지 등을 파악하기 위해 노력했지만 이게 진짜 쉽지 않다는 것을 잘 알기 때문에 항상 고객의 목소리에 귀를 귀울이시는 모습이 프로페셔널하게 보였고 그래서 지금 성공 차선 위를 달리고 있는 것 같다.
대표님의 설명 외에도 채널 코퍼레이션에 취업한 1기 선배님들에게도 많은 경험담과 조언을 들을 수 있었다. 함께 치킨, 피자를 먹으면서 많은 비하인드를 들었지만, 결론적으로 정글 커리큘럼을 잘 따라가기만 하면 충분히 잘 해낼 수 있다고 말해주셨다.(물론 그 커리큘럼을 따라가기 위해서는 지금보다 더 빡세게 집중하고 몰입할 필요가 있다!!!)
이번 5주 차를 하면서 느낀 점이 정말 많다. 정글에서 매일 10시간 이상 노트북을 두들기면서 나름 열심히 하고 있다고 생각했다 전보다 확실히 배운 것도 많고. 그러나 과연 이게 최선일까 하는 의문이 들었다. 단순히 열심히 하는 것 이상의 무언가가 필요하다고 느꼈다.
이 생각은 특히 이번 주 같은 조원 형 한 명을 보면서 느꼈다. 이 형님 같은 경우, 나와 마찬가지로 C언어에 대해 아예 무지한 상태였지만 아주 기초적인 개념부터 차근차근 공부를 했고, 조 회의 때마다 모르는 부분이나 궁금한 점이 있으면 언제든 적극적으로 잡아내서 끌고 왔다.
즉 '왜?'라는 질문을 당연하게 계속 던져 왔고, 그 때 나는 스스로에게 민망함을 느꼈다. 나는 과연 저 형이 궁금해 하는 부분을 제대로 알고 넘어갔을까? 그냥 조금이라도 더 편하려고 하지는 않았을까? 스스로에게 실망스러운 부분들이 많았다. 또한 이 형님은 마지막 날까지 다른 사람들이 이해하기 어려워 하거나 헤매는 부분들을 디테일하게 디버깅해주면서 많은 도움을 주는 수준까지 되었다. 그에 반해 나는 마지막까지 헤맸고, 이 형 도움으로 과제를 마무리할 수 있었다.
물론 기존의 배움과 경험의 차이가 있겠지만, 문제에 대해 얼마나 더 깊게 파고들었냐의 디테일에서 이런 차이가 보였다고 생각한다.
Anyway!! 이번 주 느낀 점 정리!
개념부터 확실하게 익히자! 코드 구현을 결국 개념을 바탕으로 만들어진다!! 모르거나 궁금한 것들은 무조건 짚고 넘어가자! 대충 넘어가면 남는 것도 없다. 타인과 회의하거나 아이디어를 공유하는 시간을 많이 가지자! 나 혼자만의 생각에서 벗어났을 때 성장할 수 있는 길이 넓어진다. 내 생각을 정리하여 다시 말하는 습관을 가지자! 내가 이해한 것을 정리하고 계속 밖으로 꺼낼 때마다 내 것이 될 가능성이 커진다. 어떤 상황에서도 적극적인 태도로 임하자!!
매순간 최선을 다하면 뭐든 할 수 있다!!!!! 다시 빡세게 해보자!!!
반응형
from http://dapsu-startup.tistory.com/63 by ccl(A) rewrite - 2021-09-12 21:00:45