정글에서의 5주차

현집·2023년 4월 9일
4

SW사관학교 정글

목록 보기
7/13
post-thumbnail

두둥탁! 드디어 c언어가 등장했다. 내가 또 전공 c수업 A+이 아니던가! (포인터 전까지 배웠음ㅋ)
난 두려울 것이 없다. 가보자고.

WEEK05 : Red-Black Tree

C언어 포인터의 개념, gdb 디버거 사용법 등을 익혀봅니다. 또한, Segmentation fault 등 새로운 에러들을 마주해봅니다! 🙂

엉엉... 마지막에 웃는 이모티콘이 나를 더 마음아프게 했다. 저 안내 멘트에서 내가 할 수 있는 것은 새로운 에러들을 마주하는 것 뿐이었다.

그래도 언제나! 항상! 그랬던 것 처럼! 차근 차근 공부를 시작했다.

"자 이 짤을 이해했으니 포인터에 대한 이해는 끝난 것이다." 라는 생각과 함께 냅다 rbtree를 구현하러 들어갔다.

그리고 바로 다시 나왔다.

red-black tree의 근원부터 공부하기 시작했다.
뭐 간략히 설명하자면, 편향된 이분 그래프를 해결하기 위해 나왔다고 한다.

왼쪽 처럼 되기 싫으면 rbtree활용해 오른쪽 처럼 만들면 된다.

(글 하단 github README에 자세히 설명해두었다.) 아직 readme가 설명이 안되어있다고? 그럼 일주일 후에 다시 들어와보길 추천한다. 지금 눈앞에 구현할게 산더미라 readme수정은 짬날때 하려고 한다..ㅋ

introduction to algorithms에 의사코드가 매우 친절하게 나와있어 의사코드로 먼저 이해를 하고 키보드에 손을 올렸다. 코치님께서 답을 먼저 보는 건 절대 좋은 방법이 아니라고 하셨지만, 삭제 그걸 어떻게 생각해 낸단 말인가...
그래도 내 핑계를 한번 들어나 보싈? 나도 대충 아 이렇게 회전하고 저렇게 회전하고 이런경우엔 이러코 저런경우엔 저렇구나~ 이렇게 생각은 했다. 진짜다. 바로 답을 본건 아니다. 정말로.

linked list를 먼저 구현해보고 들어가서 인지 c언어라서 어렵다기 보다는 그냥 rbtree를 구현해내는 알고리즘 자체가 어려웠던 것 같다.

그래도 영차영차 rbtree 구현을 끝내긴 끝냈다. 의사코드가 날 멱살잡고 이끌었다.
코드 한줄 한줄에 엄청난 주석을 달아두었다. 정말 초등학생이 봐도 이해를 할 수 있을 정도로.
아 물론 정보올림피아드를 준비하는 초등학생 말이다.

궁금하다면?
여기를 눌러서 킹갓제너럴 내 코드를 구경하러 와!

이제 나는 rbtree에서 아무렇지 않게 쓰던 malloc을 구현하러 가야한다. 하... 누가 나 좀 붙잡아줘... 엉엉

0개의 댓글