Today, I will

1. 백준 14719번(빗물) 풀이 방법 모노톤 스택 알고리즘을 활용하여 풀 수 있습니다. Monotonic stack 모노톤 스택 알고리즘은 다음과 같은 방법으로 동작합니다. 스택이 비어 있거나, 스택의 맨 위에 있는 원소가 현재 원소보다 큰 경우, 현재 원소를 스택에 push 합니다. 스택의 맨 위에 있는 원소가 현재 원소보다 작은 경우, 스택에서 원소를 꺼내면서 빗물의 양을 계산합니다. 이 때, 빗물의 양은 스택에서 꺼낸 원소와 현재 원소 사이에 고일 수 있는 빗물의 양입니다. 빗물의 양을 계산한 후, 스택에 현재 원소를 push 합니다. 이 과정을 모든 원소에 대해 반복하면, 스택에는 모노톤한 부분 수열이 저장되고, 빗물의 양을 계산할 수 있습니다. 모노톤 스택 알고리즘은 시간 복잡도가 O(n)으..

1. 들어가며 안녕하세요! FlyDuck Dev🦢 입니다. 카이스트 문지캠퍼스의 벚꽃 주간에 정글에서는 C언어의 시간이 펼쳐졌습니다. 4주차까지의 알고리즘 주간이 끝나고, 정글사관학교 5주차부터 6주차 동안 C언어로 구현하는 링크드리스트, 더블링크드리스트를 이해하였고, 5주차 레드블랙트리 구현과 6주차 malloc 랩 과제를 하고 있습니다. 정글 벚꽃 주간에 C언어를 익히고 쓰는 과정들 속에서 느꼈던 이모저모와 생활 패턴 및 생각의 변화들을 포스팅해볼까 합니다. 2. week05, 벚꽃과 C언어 5주차에는 C언어로 레드블랙트리를 구현해야 했습니다. 저는 C언어를 얕게 공부해본 경험이 있었지만, 정글에 온 김에 C언어 책을 한권을 제대로 씹어먹어 보자는 생각을 하였습니다. 이번 기회가 아니면 제대로 C언..

1. Explicit Free Lists 구현해보기 안녕하세요! FlyDuck Dev🦢입니다. 오늘은 Explicit Free Lists를 구현한 것을 토대로, 주요 로직 사항을 정리해보고자 합니다. 묵시적 가용 리스트와 다른 주요한 차이점은 (1) 포인터 2개가 추가되고, 그만큼 프리 블록의 최소크기가 커진다는 점, (2) coalesced block을 free list의 맨 앞에 삽입해야 한다는 점입니다(LIFO 순서로 리스트를 유지하는 방법을 취하였기 때문) 2. Implicit Free Lists vs Explicit Free Lists 암시적 프리 리스트는 구현이 비교적 간단하지만, 블록 할당 시간이 힙 블록의 총 수에 선형적으로 비례하기 때문에, 일반적인 목적의 할당자에 적합하지 않습니다. (..

* 본 포스팅은 책 의 말록랩 구현 실습을 위해 책을 요약하고, 더울어서 코드에서 비롯되는 의문점들을 보기 쉽게 정리하기 위한 목적으로 작성되었습니다. 1. 가용 리스트 조작을 위한 기본 상수 및 매크로 정의 가용리스트에서 헤더와 푸터를 조작하는 것은 어려울 수 있는데, 많은 양의 캐스팅과 포인터 연산을 사용해야 하기 때문입니다. 그래서 가용 리스트에 접근하고 방문하는 작은 매크로들을 정의하는 것이 도움이 됩니다. /* Basic constants and macros */ #define WSIZE 4 /* Word and header/footer size (bytes) */ #define DSIZE 8 /* Double word size (bytes) */ #define CHUNKSIZE (1

9.9.6 Implicit Free Lists 실제 할당기는 블록 경계를 구별하고 할당된 블록과 빈 블록을 구별하는 데이터 구조가 필요합니다. 대부분의 할당기는 이 정보를 블록 자체에 내장합니다. 이 경우 블록은 한 워드 헤더, 페이로드 및 추가 패딩으로 구성됩니다. Figure 9.35에서는 할당 블록과 비할당 블록을 식별하는 헤더를 보여줍니다. 헤더에는 블록의 크기와 할당 비트가 포함됩니다. 할당 비트는 블록이 할당되었는지 여부를 나타냅니다. Figure 9.36에서는 메모리 블록이 연속된 할당 및 비할당 블록 시퀀스로 구성된 것을 보여줍니다. 비할당 블록은 헤더의 크기 필드에 의해 암묵적으로 연결됩니다. 이러한 암시적 비할당 블록 목록의 장점은 간단함입니다. 단점은 할당 블록을 배치하는 데 필요한 ..

1. 레드블랙트리 삭제로직 살펴보기 안녕하세요! FlyDuck Dev🦢입니다. 지난 포스팅에 이어서 레드블랙트리 삭제로직을 살펴보도록 하겠습니다. 참고 영상: https://youtu.be/lU99loSvD8s 2. 삭제로직 레드 블랙 트리에서 삭제연산을 진행할 때 크게 고려할 세가지 케이스는 -1- 왼쪽 차일드노드가 NIL일때, -2- 오른쪽 차일드노드가 NIL일때, -3- 양쪽 차일드노드가 모두 NIL이 아닐 때, 입니다. -1- 왼쪽 차일드노드가 NIL -2- 오른쪽 차일드노드가 NIL -3- 양쪽 차일드노드가 모두 NIL이 아님 (1) rbtree_erase 수도코드와 c코드를 살펴보겠습니다. int rbtree_erase(rbtree *t, node_t *z) { node_t *y = z; co..

1. 레드블랙트리 구현해보기 안녕하세요! FlyDuck Dev🦢입니다. 오늘은 레드블랙트리를 구현해보기 위해 삽입 로직을 정리해보고자 합니다. 레드-블랙 트리(Red-Black Tree)는 이진 탐색 트리(Binary Search Tree)의 일종으로, 검색, 삽입, 삭제의 연산에서 최악의 경우에도 시간 복잡도 O(log n)을 보장하는 자료구조입니다. 이를 위해 노드마다 "레드(red)" 또는 "블랙(black)"의 색을 지정하고, 색의 규칙에 따라 노드의 위치와 색을 조정함으로써 트리의 균형을 유지합니다. 레드-블랙 트리의 속성 모든 노드는 레드 또는 블랙 중 하나의 색을 갖습니다. 루트 노드는 블랙입니다. 모든 리프 노드(NIL 또는 NULL)는 블랙입니다. 레드 노드의 자식 노드들은 모두 블랙입니..

0. Today I Learned 안녕하세요! FlyDuck Dev🦢입니다. 오늘은 비트마스킹을 활용해야 하는 DP 문제(외판원 순회)를 풀기 위해서, 비트연산에 대해서 알아보는 시간을 가졌습니다. TIL 목적상, 문어체로 작성하게 됨을 미리 밝힙니다! 🔭오늘의 공부 자료 (1) 큰돌의터전님의 블로그 및 강좌 (2) 주니온 연구소님의 강좌 1. 비트 연산자 & 비트단위로 AND 연산을 한다. | 비트단위로 OR 연산을 한다. ^ 비트단위로 XOR 연산을 한다. ~ 피연산자의 모든 비트를 반전시킨다. 피연산자의 비트 열을 오른쪽으로 이동시킨다. 비트연산자 기초 &, | &는 true & true = true (1 & 1 = 1)고 나머지는 모두 false를 반환한다. 0 & 0 0 0 & 1 0 1 & 0..

0. Today I Learned 안녕하세요! FlyDuck Dev🦢입니다. 오늘은 전산학의 기본이 되는 레지스터 공부를 하기 위해서, SASM을 통해서 기초 어셈블리 언어를 작성해았습니다. 또한, 윈도우 프로그래머용 계산기를 가지고 놀면서 컴퓨터에서 자주 쓰이는 데이터를 이해해보는 시간을 가졌습니다. TIL 목적상, 문어체로 작성하게 됨을 미리 밝힙니다! 🔭오늘의 공부 자료 (1) Rookiss님의 c++ 프로그래밍 입문 강좌 (2) [CS:APP] 컴퓨터 시스템 1장, 3장 1. 컴퓨터 상식 (레지스터) 컴퓨터가 꺼지면 하드디스크에 있는 내용은 비교적 영구적으로 보존이 되지만, 메인 메모리의 내용은 보존이 되지 않고 데이터가 휘발성이다. cpu에 가까우면 가까울수록 접근 속도도 월등하게 빨라진다.(레..

0. Hello👋 어셈블리어 안녕하세요! FlyDuck Dev🦢입니다. 오늘은 CS:APP 3장 프로그램의 기계수준 표현에 나온 용어들(gcc, gnu, gdb)과 어셈블리어를 이해하기 위해 찾아본 바를 정리해보는 식으로 포스팅을 진행해보고자합니다.😊 특히 아래의 어셈블리어 코드를 읽고 이해하는 것을 목표로 본 포스팅을 진행하였습니다. 1. gcc gcc는 GNU Compiler Collection의 약자로, C, C++, Objective-C, Fortran, Ada 등 여러 언어로 작성된 소스 코드를 컴파일하는 데 사용되는 컴파일러입니다. gcc는 오픈 소스이며, 리눅스와 같은 유닉스 기반 운영 체제에서 흔히 사용됩니다. gcc는 표준 C 및 C++ 규격을 준수하며, 다양한 플랫폼에서 실행 가능한 코..