Today, I will

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

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. 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++ 규격을 준수하며, 다양한 플랫폼에서 실행 가능한 코..

1. Hello👋 CS:APP 안녕하세요! FlyDuck Dev🦢입니다. 오늘은 CS:APP 1장에 나온 용어들(프로세스, 프로세서, 운영체제) 간의 관계를 정확하게 이해하기 위해 찾아본 바를 정리해보는 식으로 포스팅을 진행해보고자합니다.😊 특히 프로세스의 실행과 종료 시점에서 운영체제와 프로세서의 역할의 차이점에 대해서 집중적으로 포스팅해보았습니다. CS:APP 소개: 컴퓨터 시스템은 하드웨어와 시스템 소프트웨어로 구성되며, 이들이 함께 작동하여 응용프로그램을 실행한다. 시스템의 구현방법은 시간에 따라 바뀔 수 있지만, 근본적인 개념들은 변하지 않는다. 모든 컴퓨터 시스템들은 유사한 기능을 수행하는 유사한 하드웨어와 소프트웨어 컴포넌트를 가지고 있다. 이 책은 프로그래머들로 하여금 이들 컴포넌트들이 어..

1. 백준 13334번(곱셈) https://www.acmicpc.net/problem/13334 안녕하세요! FlyDuck_Dev🦢 입니다. 오늘은 백준 13334번 철로 문제를 푸는 해결 과정을 정리하는 포스팅을 작성해보도록 하겠습니다. 2. 기존 풀이 left, right 투포인터를 잡고 각각 선분 d의 시작과 끝이라고 생각하고, left를 통근자들의 home 좌표 기준을 삼아 D만큼(백준 문제에서의 L) 밀면서 사실상의 완전탐색 형식으로 문제를 풀면 되겠다고 생각해서 아래와 같이 코드를 작성하였습니다. a = int(input()) dis = [] for i in range(a): dis.append(tuple(map(int, input().split()))) d = int(input()) di..

1. 백준 1629번(곱셈) 안녕하세요! FlyDuck_Dev🦢 입니다. 오늘은 백준 1629를 풀면서 겪었던 어려움과 문제 해결을 위해 이해한 합동식, 모듈러 연산에 대해 정리하는 포스팅을 작성해도록 하겠습니다. 2. 기존 풀이 factorial을 짜듯이 재귀를 활용해서 문제를 풀면 되겠다고 생각해서 아래와 같이 코드를 작성하였습니다. import sys a, b, c = map(int, sys.stdin.readline().strip().split()) def power(a,n): if n