잔잔한 물결로 파도 만들기

RB 트리의 삽입 연산에 이어 삭제 연산 ! RB트리의 연산을 이해할 때는 색깔이라는 속성이 특정 노드에 귀속적인 게 아니라, 자유롭게 날아갈 수도 있는 속성임을 이해하는게 중요하다. 색깔은 말 그대로 노드의 구조를 파악하고 컨트롤하기 위해 붙여놓은 인덱스같은 거다. 색깔을 붙인 것도 우리 마음대로였고, 색깔을 바꾸거나 하는 것도 RB트리의 속성 유지에 도움이 된다면 아무렇게나 해도 된다. 그저 약속일 뿐이다. 우리가 배우는 방법론은 그 중 효율적인 방법일 뿐이다. 바로 들어가기에 앞서 RB 트리의 5가지 속성을 다시 복기하자: 모든 노드의 색은 red 또는 black 이다. 루트 노드는 black이다. nil 노드는 black이다. nil 노드: null과 통하는 의미라고 생각하면 된다. 특정 노드가 ..

Computer Science/자료구조 (Data Structure) 2023. 11. 6. 14:51

라는 논문 결과 (2004년 스탠퍼드대 연구) (논문 링크: https://web.stanford.edu/~blp/papers/libavl.pdf) Abstract 1. 논문 작성 당시, BST(이진 검색 트리) 기반 자료구조의 선택을 돕는 경험적 연구가 부족함 2. 현실세계의 시나리오를 가정한 후, 해당 환경에서 20가지의 BST 변형 성능을 측정하고 비교함 3. 결론 입력이 무작위 순서로 제공되는게 확실할 경우, unbalanced한 일반적인 BST가 우수 입력이 무작위 순서로 제공되고 가끔 정렬된 순서가 있는 경우 RB 트리가 우수 정렬된 순서로 삽입 후 무작위 접근이 필요할 때는 AVL 트리가 우수 삽입 후 순차적 또는 군집된(clustered) 접근에는 splay 트리가 우수 응용 사례를 위주..

Computer Science/자료구조 (Data Structure) 2023. 11. 5. 21:55

1. 동적 메모리 할당(Dynamic Memory Allocation)이란? 프로그램이 실행되는 동안 메모리의 크기가 변할 수 있는 변수나 데이터 구조에 메모리를 할당하는 과정을 동적 메모리 할당이라 한다. 이를 통해 런타임에 필요한 메모리 양을 결정하고, 더 이상 필요하지 않은 메모리를 반환하여 재사용할 수 있게 한다. 동적 할당을 통해 메모리 사용을 최적화하고, 프로그램 유연성을 개선할 수 있다. 우선 개념적인 얘기부터 보고, 그 다음에 실제로 어떻게 구현하는지 살펴보자. 동적 vs 정적 메모리 할당 역사적으로 볼 때, 정적 메모리 할당이 먼저 있었고, 프로그램의 요구사항과 컴퓨팅 환경이 발전함에 따라 동적 메모리 할당이 필요해지고 후행적으로 등장했다고 볼 수 있다. 초기에는 정적 메모리 할당이 더 ..

Computer Science/컴퓨터 구조 (Computer Architecture) 2023. 11. 4. 16:19

구조체는 C언어에서 복잡한 데이터를 관리하고, 의미있게 정보를 조직화하는데 있어 필수적인 도구다. C에서 구조체(structure)는 하나 이상의 서로 다른 타입의 변수들을 묶어 새로운 타입을 정의할 수 있게 해준다. 이는 관계있는 서로 다른 데이터들을 하나의 단위로 처리할 수 있게 한다. 구조체는 Java의 클래스와 거의 유사하다. 다만 메서드를 포함하지 않고 필드만 지닌다는 점? 그리고 객체지향적 개념들이 포함되지 않아 훨씬 단순한 구조라고 볼 수 있다. 이번에 알아본 것은 다음과 같다. struct, 구조체 변수 선언 및 멤버 접근, 구조체가 메모리에 할당되는 방식, 구조체를 함수 인자로 전달하기, 구조체 배열, 구조체 포인터, 중첩 구조체, typedef 1. 구조체 기본 문법 구조체 선언: st..

프로그래밍 언어/C 2023. 11. 4. 13:25

gcc로 컴파일하기 $ gcc -g -o ... $ gcc -g -o hello hello.c 자주 사용되는 컴파일 옵션 -g → gdb 디버깅 정보포함 -I → include 경로 -Wall → all warning enable -O → optimization for code ( = -O1) 참고 https://80000coding.oopy.io/d5fa7c87-192f-4c68-95eb-aa4af5b9dbf5 https://jangpd007.tistory.com/220 vi 명령어 vi 명령어 동작 i 현재 커서 위치에 삽입 (입력모드로 넘어감) a 현재 커서 바로 다음 위치에 삽입 (입력모드로 넘어감) o 현재 줄 다음 위치에 삽입 (입력모드로 넘어감) x 커서가 위치한 곳의 글자 1개 삭제. (5..

프로그래밍 언어/C 2023. 11. 3. 15:52

RB 트리를 C 프로그래밍으로 구현한 과제 링크: https://github.com/Vacayy/Red-Black-Tree GitHub - Vacayy/Red-Black-Tree: C 프로그래밍으로 Red-Black Tree를 구현하는 과제입니다. C 프로그래밍으로 Red-Black Tree를 구현하는 과제입니다. Contribute to Vacayy/Red-Black-Tree development by creating an account on GitHub. github.com 절대 완벽한 코드는 아니지만 만약 이 포스팅을 보는 분 중에 RB 트리 내부 구조가 궁금하신 분은 들어가보시면 참고가 될 듯! C 언어를 처음 다뤄봤는데, 복잡한 자료구조를 직접 구현해보면서 C언어에도 익숙해질 수 있었던 과제였다..

Computer Science/자료구조 (Data Structure) 2023. 11. 3. 15:46

오늘 시험을 마지막으로 자료구조/알고리즘 주차가 끝이났다 ! ! 입소식이 엊그제 같은데, 어느새 미니프로젝트와 알고리즘 주차를 지나왔다. 고생했다 나! 아직 한달도 채 되지 않았지만, 들어오기 전과 비교하면 굉장히 많은 지식들을 가져가는 것 같아 기쁘다. 단순히 양만 많은 게 아니라, 코치님들의 가이드 하에 양질의 지식들 위주로 학습하고 있어 의미가 깊다. 뭐랄까 약간이나마 CS 공부가 왜 중요한지를 직접 체감하고 있다. 가장 피부로 와닿는 점은, 어느새 동료들과 시간 복잡도, 공간 복잡도 측면에서 토론을 하는 것이 자연스러워졌고, 각 자료구조의 특성들도 고려하면서 코드를 고민하게 되었다는 점이다. 이게 의식적으로 하는 게 아니라 자연스럽게 이루어지고 있다. 이렇게 성장에만 집중할 수 있는 환경을 만나기..

일상기록장/크래프톤 정글 일지 2023. 11. 2. 20:04

리틀 엔디안 vs 빅 엔디안 메모리에 데이터를 저장할 때, 바이트 저장 순서에 따라 리틀 엔디안, 빅 엔디안으로 나눌 수 있다. 리틀 엔디안 (Little Endian): 낮은 주소에 최하위 바이트(LSB, Least Significant Bit)부터 저장한다 - 사람이 읽고 이해하기엔 직관적이지 않을 수 있다. - 0x1A2B3C4D라는 4바이트 정수를 저장한다고 하면 아래와 같다. (MSB = 0x1A, LSB = 0x4D) 0x103: 0x1A (MSB) 0x102: 0x2B 0x101: 0x3C 0x100: 0x4D (LSB) - 무조건 낮은 메모리 주소에 최하위 바이트(LSB)가 위치하므로, 메모리 주소를 다루기가 쉽다. 낮은 주소(0x100)에서 시작해서 데이터를 읽으면, 그 값이 바로 LSB..

Computer Science/컴퓨터 구조 (Computer Architecture) 2023. 11. 1. 20:56