[TIL][Krafton Jungle] 4주차 - (1) : RB Tree 구현 시작

금일은 새로운 발제 내용이 나오는 목요일이다.

새로운 조가 형성되고 새로운 과제가 주어지는데, 항상 설레는 날인 것 같다.

 

오전에 시험을 봤는데 어제 공부한 알고리즘과 비슷한 문제가 나와서 시간이 부족해 다 풀진 못했지만,

나름 목표 만큼은 맞춰서 뿌듯했다.

 

아무튼 이번주는 C언어로 돌입한다.

 

4주차 시작

 

이번주 과제는 알고리즘 문제 풀이가 아닌, Python에서 쉽게 가져다 쓴 자료구조를 직접 C 코드로 구현하는 것이다.

구현 자료구조는 블랙레드 트리 (BR tree).

 

먼저 이 자료구조가 어떻게 생겨먹은 놈인지 뜯어보고, 어떻게 구현할지를 생각해봐야 하기 때문에 코어타임 때 이론 내용 공부를 통해 부족한 부분을 채워나가기로 했다.

 

그리고 환경 설치를 위해서 터미널을 다뤘는데, 터미널 관련 명령어들에 대한 자료가 있어서 여기에 저장해 두겠다.

 

출처 : Jungle

 

더 자세한 편집기 명령어들은 https://blockdmask.tistory.com/25 여기에서 참고하자.

 

---

과제에 대한 이해 및 마킹

 

Red-Black Tree 를 구현해야 한다.

구현하는 추상 자료형(ADT)는 ordered set, multiset 이라고 한다.

 

`ordered set` 은 집합(set)의 확장된 형태로, 요소들이 정해진 순서로 유지된다.

우리가 많이 사용하던 python의 heapify된 힙 구조와 같은 것들이 ordered set 이다.

 

`multiset`은 집합(set)과 유사하지만, 중복된 요소를 허용하는 자료구조를 말한다.

 

 

 

 

주어진 과제는 자료 구조 객체 생성, 메모리 완전 삭제, 데이터 삽입, 데이터 탐색, 데이터 삭제, 최소값 탐색, 최대값 탐색, 배열로 전환 이다.

 

특히 delete_tree(tree) 함수에서는 메모리를 반환하면서 valgrind로 나타나지 않아야 한다고 한다.

 

여기서 valgrind가 무엇인지 몰라서 알아봤다.

 

valgrind

valgrind는 C, C++ 등의 프로그래밍 언어로 작성된 프로그램들을 디버깅하는 도구이다.

주로 메모리 누수(memory leak)와 잘못된 데이터 접근(out-of-bounds-access)과 같은 메모리 관련 오류를 찾기 위해 사용된다고 한다.

 

valgrind는 리눅스와 유닉스 기반 시스템에서 사용할 수 있으며, 프로그램이 실행되는 중에 메모리를 추적하고 프로그램이 할당하고 해제한 메모리 블록을 추적한다.

 

또한 사용되지 않는 메모리를 감지하며 앞서 말한 메모리 누수나 잘못된 데이터 접근을 식별 및 검출한다.

 

또 반대로 프로그램의 성능과 메모리 사용을 분석해서 최적화할 수 있는 정보가 있다면 제공하기도 한다.

그래서 프로그램의 성능을 향상시키고 안정성을 향상시키고 싶다면 유용하게 사용할 수 있을 것 같다.

 

터미널에서 실행할 수 있는데, 명령줄에서 프로그램을 Valgrind와 함께 실행시키면 된다고 하니 디버깅을 할 때 사용해 보며 삭제되는 데이터가 검출되는지 확인해야 할 것 같다.

 

 

 

 

Sentinel node라는 것을 사용하여서 구현할 수도 있다는 힌트가 될 수 있을 것 같다.

공부하며 방향성에서 Sentinel node가 있다면 고려해 볼만할 것 같다.

 

 

---