크래프톤 정글 회고: 4주차

정글 회고 목차

Week 0
Week 1
Week 2
Week 3
Week 4

4주차

3주차가 즐거웠다면, 4주차는 정말 많이 성장한 느낌이었다.

슬슬 동기들과 친해져서(하루종일 같이 있는데도 친해지기 위해 4주나 걸린 사람이 접니다) 서로 별명을 지어주기 시작했다. 3주차때 같이 조를 했던 종문님은 진짜 실력도 실력인데 학습하는 태도가 너무 좋아서 어느새 ‘더 정글’, ‘타이거’ 등으로 부르고 있었는데 이번 주에 같이 한 예림님은 우리 조를 캐리했기 때문에 ‘선장님’과 ‘캡틴’이라는 이명을 지어드렸다. 또 한명의 조원 강민님은 우리가 읽어야 했던 CS:APP을 정말 잘 파악하셔서 나처럼 책 내용을 따라가기 어려웠던 사람에게는 같은 조라는 것이 천운으로 작용했다.

사실 이 때 이 두명이 같은 조가 아니었으면 어땠을까 종종 상상해본다. 아마 망하지 않았을까? 정글에서 내가 얻은 모든 성과는 이 조를 경험했기 덕분이라고 생각한다.

예림님은 전공자이기도 하고, C를 워낙 잘 다뤄서 팀으로 무언가를 구현하는 이번 주차에서는 굉장히 든든했다. 솔직하게 회고해보자면, 내가 굉장히 많이 이것저것 물어봐서 굉장히 귀찮았을 법도 했는데 다 이해가 쏙쏙되게 알려주셨다. 얼마나 심각했냐면, 나는 도트연산자와 화살표연산자도 몰랐었다…(!) 4주차에 들어가기 전에 설 연휴가 있어 이 때 C관련 Exercise를 했는데도 진짜 어려웠다…

강민님은 이 때 나와 같이 선원 역할을 해서 우선 내가 외롭지 않았다. 배에 선장이 둘인데 선원이 하나면 얼마나 서럽겠는가? 물론 이것은 구현 단계에서의 얘기이고, CS:APP 챕터들에 대해 서로 설명해주는 코어타임때는 정말 많이 의지했다. 해당 주차에 구현해야 하는 것은 Red-Black 트리였는데, 코드와 별개로 논리적인 부분은 죄다 강민님한테 들은 설명으로 지금까지 기억에 남아있는 것 같다.

Red Black Tree

Red-Black Tree Lab

RB트리를 직접 구현해보는 랩과정을 진행했다.

RB트리는 균형 잡힌 이진 트리의 한 종류이다. 삭입, 삭제, 검색 연산의 시간 복잡도가 O(log n)으로 굉장히 빠르다. RB트리의 특징으로는, 몇개의 주요 규칙들을 따라 스스로 균형을 잡아서 탐색 속도를 보장한다. RB트리의 주요 규칙들은 다음과 같다:

1. 모든 노드는 빨간색(Red) 또는 검정색(Black)이다.
2. 루트 노드는 검정색이다.
3. 빨간색 노드의 자식은 항상 검정색이어야 한다.
4. 특정 노드에서부터의 모든 리프 노드로의 경로에는 같은 개수의 검정색 노드가 있어야 하며, 이를 “Black-Height”라고 부른다.

RB트리에서의 삽입 연산과 삭제 연산 시 단순히 노드를 삽입/삭제하는 것 뿐만이 아니라 트리의 균형을 유지하기 위해 리밸런싱을 해야한다. RB트리에서의 삽입과 삭제는 모두 리프 노드에서 이루어지며, 여러 가지 과정을 거친다.

삽입과 삭제를 할 때는 규칙들이 위반되지 않도록 재조정을 해주어야 하며, 이 재조정 과정을 거친 후에 트리는 균형이 잡혀있음으로 자동으로 균형이 잡히는 이진 트리가 된다.

예를 들어, 삽입된 노드는 빨간색으로 설정이 되며, 만약 이 때 부모 노드가 빨간색이라면 3번 규칙에 의거하여 부모 노드를 검정색으로 변경해주어야 한다거나, 형제 노드가 빨간색인 경우에는 회전을 하고 색상을 변경해야 한다.

RB트리 관련해서는 별도 포스트로 정리할 예정이다.

마치며

RB트리의 구현 방식에 대해서는 Thomas H. Cormen의 Introduction to Algorithms라는 서적에 꽤나 자세히 나와있다.

삽입 수도코드

회전 수도코드

주어진 수도코드를 참고하여 최대한 이해한 후에 구현했다.

C언어를 처음 써본 주였다. 포인터 개념이 처음에는 꽤나 헷갈렸으며, 지금도 완벽하게 참조 및 역참조를 이해한다고 할 수는 없지만 그럭저럭 사용할 정도는 되는 것 같다.