잔잔한 물결로 파도 만들기

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

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

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

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언어에도 익숙해질 수 있었던 과제였다..

리틀 엔디안 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..

오버헤드(overhead) 공부하다 보면 함수의 오버헤드가 발생했다, 메모리 오버헤드가 발생했다 등등 overhead 라는 용어가 자주 등장한다. 여기서 말하는 (컴퓨터과학 관점에서의) overhead는 특정 작업을 수행하기 위해 필요하지만, 실제 유용한 작업에 직접 기여하지는 않는 추가적인 리소스나 시간을 의미한다. 즉 특정 작업을 수행할 때, 그 핵심 동작을 위한 비용은 아니지만 괜히 간접적으로 낭비되는, 따라서 더 최적화할 여지가 있는 비용이라는 거다. GPT한테 물어보니 다음과 같은 예시를 준다. 함수의 오버헤드: 함수 호출 시 발생하는 추가적인 처리입니다. 함수를 호출하면, 인자를 전달하고, 리턴 주소를 저장하고, 필요한 경우 스택 프레임을 설정하는 등의 작업이 필요합니다. 이러한 작업들은 함수..

그리디 알고리즘 그리디 알고리즘의 기본 아이디어는 각 단계에서 현재의 상황에서 최적의 선택을 하는 것이다. 이러한 선택은 문제 해결에 있어서 전역적으로 최적이며, 각 단계에서의 선택은 이후 단계에 대한 선택을 제한하지 않는다. DP와 마찬가지로, 그리디 알고리즘은 일반적으로 최적화 문제를 해결하기 위해 사용된다. 또한, 그리디 알고리즘은 해를 찾기 위해 반복적인 선택을 해야 하는 문제에도 적용된다. 탐욕 알고리즘이 잘 작동하는 문제는 대부분 탐욕스런 선택 조건(greedy choice property)과 최적 부분 구조 조건(optimal substructure)이라는 두 가지 조건이 만족된다. (...) 이러한 조건이 성립하지 않는 경우에는 탐욕 알고리즘은 최적해를 구하지 못한다. 하지만, 이러한 경우..

다이나믹 프로그래밍 다이나믹 프로그래밍(동적 계획법, 이하 DP)은 복잡한 문제를 작은 하위 문제로 나누어 해결하고, 이를 조합하여 원래의 문제를 해결하는 알고리즘 설계 기법이다. 핵심 아이디어 자체는 분할정복과 동일하다. 1950년대에 리처드 벨먼이라는 응용수학자가 개발했으며, Dynamic 이라는 단어는 그저 멋있어서😂 붙인거고, Programming은 컴퓨터 코드가 아니라 테이블을 이용한 방법을 일컫는 거라고 한다. 개인적으로 DP는 적용 상황을 판단하는 것도 쉽지 않고, 문제 풀이 단계에서 정확한 점화식을 도출하는 게 쉽지않은 것 같다. . 모두 연습만이 살길 !! 어떤 문제에 DP를 적용하는가? 목적을 따지자면, 일반적으로 최적화 문제(optimmization problem)에 DP를 적용한다...

CSAPP 1장의 각 소단원을 읽으면서 주요 내용과 추가적으로 알아본 정보들을 기록하는 포스팅😎 1장은 컴퓨터 시스템 전반을 얕고 넓게 훑는 챕터이다. 글자색이 다른 부분은 내가 따로 추가한 생각 혹은 정보이다 (= 틀릴 수도 있다) 1.1 정보는 비트와 컨텍스트로 이루어진다 소스 프로그램은 byte(= 8 bit) 단위로 구성된다. 대부분의 컴퓨터 시스템은 text 문자를 아스키 표준을 사용하여 표시한다. 아스키 표준은 각 문자를 byte 길이의 정수 값으로 나타낸다. 텍스트 파일: hello.c 처럼 아스키 문자들로만 이루어진 파일 바이너리 파일: 텍스트 파일을 제외한 다른 모든 파일 컨텍스트(context) 모든 시스템 내부의 정보는 bit들로 표시됨. 서로 다른 객체들을 구분하는 유일한 방법은 이..

우선순위 큐는 대표적으로 다익스트라 알고리즘에서 사용된다. (또 A* 알고리즘, 허프만 코딩 알고리즘 등에서도 쓰인다고 한다) 큐, 데큐가 선형 자료구조인 것과 달리, 우선순위 큐는 주로 힙(Heap)으로 구현되는 경우가 많기 때문에 비선형으로 분류된다. 우선순위 큐를 구현하는데 필요한 힙(Heap)이라는 자료구조가 무엇인지 알아보고, 우선순위 큐에 대해서 알아보자. 힙(Heap) Heap은 완전 이진 트리의 일종으로, 1) 최소 힙 또는 2) 최대 힙으로 나뉜다. 힙 속성(Heap Property) 최소 힙(Min-Heap): 각 노드의 값이 그 자식 노드의 값보다 작거나 같음 (루트 노드가 최소값) 최대 힙(Max-Heap): 각 노드의 값이 그 자식 노드의 값보다 크거나 같음 (루트 노드가 최대값)..