크래프톤 정글 6주차 WIL

C로 구현하는 자료구조

여태껏 제가 레드-블랙 트리를 배우게 되리라고는 생각을 한 적이 없었습니다. 더구나 C로 짜리라고는 상상도 못해봤습니다. 제게 레드-블랙 트리란 실제 리눅스, 자바 등 현업에서 쓰이는 복잡한 자료구조이다, 정도의 희끄무레한 이미지만이 있었습니다 (이게 BST의 일종이라는 것도 몰랐지요).

그런데 결국 이걸 공부하고, 구현하고, 테스트까지 끝냈습니다. 그리고 의외로 할만했다는 점에서 저는 또 다시 놀랐습니다. 이번 6주차에 저희 정글은 CS:APP 교재 7,8,9장, 그리고 C언어로 레드-블랙 트리를 구현하였습니다. 저번 주 목요일의 차주발제 시간에 저희가 일주일간 구현해야 할 과제가 레드-블랙 트리라는 것을 들었을 때, 그리고 저게 어떤 물건인지 웹을 통해 찾았을 때, 이걸 진짜로 내가 할 수 있을까라는 생각이 앞섰습니다. 특히 저희 교육과정 홈페이지에 올라온 아래 영상 두 편을 접하며 여러 생각이 들었습니다.

세상에. 뭔가요? 자료구조 하나에 70분 그것도 배속으로 겨우 끊는 강의라니...

저희가 최초에 받았던 `rbtree.c` 파일입니다.

RBT 프로젝트 경로구조입니다.

구현은 둘째 치고 일단 테스트 코드 구동부터가 하나의 장벽이었습니다. 이전까지 돌렸던 C 코드들은 전부 gcc (소스코드) -o (실행파일명) 식으로 입력하면 됐는데 여기서는 그게 먹히지 않았습니다.

지금 생각해보면 CS:APP 7장 (링커)는 바로 이를 위한 것이었습니다. 여태까지는 gcc에 대해 '소스 코드를 실행 파일로 변환시켜준다' 정도의 애매모호한 생각에 그쳐도 괜찮았지만, 이번 RBT 프로젝트는 그 정도 이해로는 테스트 구동조차도 불가능했기 때문입니다.

2021년

이번 6주차를 시작하면서 레드-블랙 트리 관련하여 특별히 받았던 주문이 하나 있었습니다. "다 상관없으나 LLM을 이용하지 말 것"이었습니다. 마치 2021년처럼 검색하고, 구현하고, 디버깅하라는 것이 저희의 과제였습니다. 그리고 저는 이왕 이렇게 된 거, 최대한 수도코드를 보지 않고 구현하자는 개인적인 목표도 세웠습니다.

큰 문제일수록 작은 것부터

팀원들과 함께 위 경로구조를 보며 무엇부터 시작해야 하는지를 고민했습니다. 우선은 프로젝트 최상위의 README.md를 읽었고, 각 .c 파일에 무엇이 들었는지, 그 다음은 .h에 무엇이 들었는지 보았습니다. 이를 통해 우리는 각 폴더에 존재하는 Makefile부터 공부해야 함을 알게 되었고, 이후 src와 test 폴더내 .c와 .h 파일들이 전부 다 의존성 순서에 맞추어 컴파일되어야만 한다는 는 결론을 내리게 되었습니다. 그리고 이를 위한 명령어인 make를 공부할 수 있었습니다. 이로써 테스트 코드 구동을 위한 마지막 퍼즐인 make -C 명령어를 얻어내었고, 첫 구동에 성공했습니다.

테스트 구동에는 성공했지만 그렇다고 그게 레드-블랙 트리를 짜주지는 않았습니다. 저 동영상 강의는 한없이 길었고, 배속편집본인지 말이 엄청나게 빠르고, 집중은 힘들었습니다.

책

Introductions to Algorithms. 위 이미지는 3판.

그런 저희를 구해준 것은 의외로 책이었습니다. 세월아 네월아 듣던 강의를 끄고 위 책을 펴 레드-블랙 트리 챕터의 글을 읽으며, 저는 레드-블랙 트리에 대하여 이해하기 시작하였습니다. 그도 그럴 것이, 영상 강의는 집중하기 힘들고, 온라인 블로그에 올라오는 글들은 단편적일 뿐더러 신뢰할 수 없었습니다. 저는 대학에서 하던 것과 마찬가지로 결국 책을 읽었고, 이를 바탕으로 구현하기 시작했습니다. 책과 온라인 영상 강의는 상호 보완적으로, 책만으로는 이해하기 힘든 트리의 움직임을 애니메이션으로 접하며, 원리를 이해하는 데에 시너지 효과를 일으켰습니다.

디버깅에 왕도는 없다

구현은 구현이고 디버깅은 디버깅이었습니다. 삽입은 시작 처리, 반복 케이스 3개, 종료 처리, 그리고 삭제는 시작 처리, 반복 케이스 4개, 종료 처리. "책에서 시키는 대로 짜면 되겠네" 했는데, 말은 쉽지, 막상 잘 돌아갔냐면, 그렇지가 않았습니다. 대표적인 예시로 위와 같은 것이 있었습니다. 테스트 코드의 마지막 관문인 랜덤 키 삽입, 검색 및 삭제에서 위와 같은 오류가 발생했습니다.

결국 찾았던 문제는 노드 삭제 후 fixup하는 과정인 restoreEraseOrder에 있었습니다. 제 코드에는 반복문 진입 전에 '대상이 NIL이면 즉시 리턴'하는 부분이 있었는데, 사실 이게 문제였던 것입니다. 그 if문 하나가 “me가 NIL 노드인 순간 아무것도 안하고 돌아가” 버리기 때문에, 책에서 제시된 삭제 후 fixup 알고리즘이 요구하는 “더블 블랙 전파” 과정을 아예 스킵해버립니다. 그 결과 nil 노드(즉 me == t->nil)가 갖고 있어야 할 부모 포인터 참조나 루트까지 올라가서 검정 수를 재조정하는 로직이 수행되지 않으므로 segmentation fault가 일어나는 것이었습니다.

그나마 다행이었던 점은, 제가 포인터 관련 글을 4개씩 써가며 정리하여 관련 개념을 익힌 덕분에, 그나마 C 문법이나 메모리 관련 이슈에 어려움을 덜 겪었다는 사실일 것입니다. 가뜩이나 RBT 자체도 어려운데 이에 더해 메모리쪽 문제들까지 잡아야 했다면... 상상만으로도 쉽지 않습니다. 

이것 말고도 디버깅에서 수많은 난관이 있었지만 결국 내린 결론은 하나였습니다. 디버깅에는 왕도가 없었습니다. 심지어 챗GPT도 이를 도와주지 못했습니다. 고작해야 Visual Studio Code의 launch.json과 tasks.json을 잘 작성해서 GUI로 디버깅하는 것이 저희가 쓸 수 있는 유일한 '쉬운 길'이었습니다. 이는 사실 현업에서 대규모 코드를 접할 때도 크게 다르지 않다는 점에서 (LLM을 사용하기 어려울 정도로 코드베이스가 크거나, 망분리 환경이거나 등), 어떤 의미로 현장감을 다시 느끼게 해주는 경험이었습니다.

현대의 컴퓨팅이란 실로 대단한 것입니다. 원본 테스트 코드에는 10000개의 노드를 랜덤으로 생성, 삽입, 검색, 삭제하는데, 저는 이를 1억 개로 바꾸어 작동시켜봤습니다. 그리고 결과는 위와 같습니다. 이게 된다니, 적잖이 놀랐습니다. 전체 코드는 여기서 확인하실 수 있습니다.

결론

레드-블랙 트리 과제를 처음 마주했을 때의 막막함은 기억에 선명합니다. 하지만 그 어려움 속에서 오히려 배움이 깊어진다는 사실을 이번 프로젝트로 알게 되었습니다. 이론적으로나 실제로나 '복잡하다'고 막연히 생각했던 그 자료구조를 직접 구현하고 디버깅하는 과정에서, 무엇이 진정한 학습인지 다시 한번 생각하게 되었습니다.

특히, 이번 과제는 마치 시계를 2021년으로 돌린 듯한 경험이었습니다. 익숙해진 챗GPT 없이 직접 책을 읽고, 문제를 찾아가며 디버깅했던 시간들은, AI나 자동화의 편리함에 익숙해진 제게 신선한 자극이 되었습니다. 무언가에 깊이 몰두하고, 책, 영상 강의, 동료들과의 교류로써 어려움을 돌파하는 경험은, 이전과 마찬가지로 제가 가진 한계를 스스로 뚫어내게 한 값진 시간이었습니다.

무엇보다 중요한 깨달음은, 어떤 어려운 문제라도 결국 작은 것부터 해결하는 것이 유효하다는 점이었습니다. Makefile 작성부터, 작은 버그 하나하나를 잡아가는 과정까지, 큰 문제를 작은 문제로 나누어 해결하는 방법론은 저번 1-4주차의 백준 알고리즘에서만 적용되는 것이 아니라는 것을 다시 깨닫게 해주었습니다. 또한 현대 컴퓨팅의 위대함과 동시에, 그 위대함을 만들어가는 건 결국 기본에 충실하고 꾸준히 한 걸음씩 나아가는 개발자의 태도라는 것을 다시금 느끼게 되었습니다. 어렵지만, 그만큼 의미 있고, 성장했던 시간이었습니다.