👀 finalfrontier

proxy-lab에서 소켓통신을 구현하기 위한 reading 10. 시스템 수준 입출력 입출력은 메인메모리, 터미널, 디스크와 같은 장치들 간에 메모리를 복제하는 것이다. C에서는 printf, scanf같은 것들이 사용자 수준 입출력을 제공한다. 하지만 Unix에서 사용되는 시스템 콜 수준의 입출력 (Unix I/O)을 알아야 한다. 사용자 수준 입출력은 문제가 많다. 따라서 네트워크 프로그래밍에 쓸 수 없다. Unix I/O를 이해하면 다른 시스템을 이해할 수 있다. 10.1. Unix I/O 네트워크, 디스크, 터미널을 모두 '파일'로 볼 수 있다. (파일로 모델링된다?) 네트워크를 대상으로 한 파일 입출력이 결국 통신.. 이다. 👀 Unix 파일 시스템의 종류 ext가 파일 시스템이다. 여러 버전..

9.9 동적 메모리 할당 동적 메모리 할당을 하면 어떤 일이 일어나는가: 런타임 메모리 이미지에 있는 heap영역이 위로 상승하는 형태로 늘어난다. 이때 힙의 탑 부분을 가리키는 포인터를 brk라고 한다. 동적 메모리 할당기의 구분: 명시적 할당기가 있고 묵시적 할당기가 있다. 명시적 할당기는 코드 내에서 특정한 양의 메모리를 할당받고 해제할 때 사용한다. (c에서의 malloc, free와 c++의 new, delete가 이에 해당한다.) 묵시적 할당기는 프로그램이 종료될 때와 같이 블록들을 더이상 사용하지 않을 때 자동으로 할당 해제해 준다. 다른 말로는 garbage collector라고 한다 9.9.1. malloc과 free함수 01) malloc과 free malloc은 C의 표준 라이브러리에..

책을 읽으며 흐름을 정리.. 가상메모리 Virtual Memory 가상메모리는 '사용자가 하나의 큰 메인메모리를 사용하는 것 같도록 느끼게끔' 실제 사용가능한 저장 자원을 추상화하는 메모리 관리 기법이다. 메인 메모리를 디스크에 저장된 주소공간의 캐시로 취급하여 메인 메모리 내 활성화된 영역만 유지하고, 데이터를 디스크와 메모리 간에 필요한 경우에만 전달한다. 각 프로세스에 통일된 주소공간을 제공하여 메모리 관리를 단순화한다. 각 프로세스의 주소공간을 다른 프로세스에 의한 손상으로부터 보호한다. 9.1. 물리 및 가상주소 방식 01) 물리주소 방식 메모리에 접근하는 것은 물리주소 방식이 있고 가상주소 방식이 있다. 물리주소 방식은 메모리의 주소를 그대로 사용하는 것으로, 주소 0에 1바이트..

Red Black Tree 1. Concept [revisited] 다음과 같은 성질을 만족하는 이진 검색 트리 BST 모든 노드는 red or black root 노드는 black leaf (nil)노드는 black red 노드의 자식은 black 한 노드에서 leaf(nil)로 가는 각 경로에 포함된 black 노드의 개수는 모두 같다. 2. Operations typedef enum {RBTREE_BLACK, RBTREE_RED} color_t; typedef int key_t; typedef struct node_t { key_t key; color_t color; struct node_t* parent; struct node_t* left; struct node_t* right; } typede..

Red Black Tree 다음과 같은 성질을 만족하는 이진 검색 트리 모든 노드는 레드나 블랙 루트는 블랙 리프(NIL)는 블랙 레드 노드의 자식은 모두 블랙 한 노드로부터 그 자손인 리프 노드로까지 가는 경로에 포함된 블랙 노드의 개수가 같음 레드 블랙 트리는 이진 검색 트리로서, 각 노드 당 한 비트의 추가 메모리에 노드의 색깔(레드, 블랙)을 저장한다. 루트에서 리프까지의 경로에 나타나는 노드의 색을 제한함으로써 그러한 경로 중 어떠한 것도 다른 것보다 두 배 이상 길지 않음을 보장할 수 있다. 이로써 근사적으로 균형을 이룬 트리 가 된다. 경계노드 sentinel 각 노드마다 리프노드를 모두 NIL로 붙여주는 대신, 이를 표현하는 하나의 노드만을 사용할 수 있는데 이를 경계노드(sentinel)..

2023.09.03 sun 4주차를 지나면서 더 많이 아는 것은, 이미 알고 있(다고 생각하)는 것으로부터 출발하게 된다. 왜냐하면 내가 전혀 모르고 있는 대상이라면, 그것이 무엇인지 모르기 때문에 알 수 없기 때문이다. 주소값을 모르는데 접근하려고 하는 것과 비슷하다.. 대신, 이미 알고 있는 것을 구체화하고/명료화하고/무엇보다 언어화해야 한다. (그 언어가 글이든 그림이든 무엇이든) 그러다 보면 내가 알고 있는 한 정합적인 지식체계 안에서, 다른 결론들을 도출할 수 있게 된다. 그게 결국 개념의 확장이고 지식의 획득일 수 있겠다.. 그런 생각이 들었다. 결국 내가 포인터가 무엇인지 이해하는 것과 동적할당이 무엇인지 이해하는 것, 가상메모리를 이해하고 컴퓨터를 이해하는 것이 모두 한 체계 안에서 일어난..

리스트 구현 방식 Sequantial List 순차 리스트 = array 고정된 크기의 배열. 연속적으로 구현되어 있어 순차적/임의 접근이 가능하다. 따라서 순차적으로 요소를 삽입하거나 탐색하는 데는 용이하지만 중간 요소의 삽입/삭제/수정이 어렵다. 또 고정된 크기로 존재하여 가변 크기의 배열을 저장할 경우 공간 낭비가 될 수 있다. Linked List 연결 리스트 Link로 연결된 가변 크기의 배열. 데이터와 다음 요소를 가리키는 포인터(=link) 를 포함하고 있는 자기참조 구조체로 구현한다. 요소의 삽입/삭제/수정이 용이하고 가변크기의 배열을 저장하는 데 효율적이다. 반면 인덱스를 통한 임의접근이 어려워 탐색에 비효율적일 수 있다. Linked List 개념 Linked List의 각 요소는 da..

Traveling Salesman problem 백준 2098 외판원 순회는 Traveling Salesman problem 줄여서 TSP라고 하며, 모든 노드를 거쳐 출발점으로 되돌아오는 최소 비용을 구하는 문제이다. 구현 방향 지금 노드와 방문 기록을 인자로 넘김 만약 방문을 모두 완료한 경우 현재노드에서 시작노드로 가는 경로 유무 체크 있으면 그 weight 반환 없으면 inf 반환 현재 노드에서 방문기록이 이미 dp에 저장되어있음 Return dp(curr, visit) Curr 와 인접한 모든 노드 i에 대해 i를 방문 처리함 i 까지 가는 최소경로 = +tsp(i, visit+{i})의 최소 점화식 $i$에서 $i$, $src$를 포함하지 않는 집합 $A$의 노드들을 단 한 번씩만 거쳐서 $s..

2진수 표현에서 1의 개수는 일반적으로 2로 나누어주고, 그 나머지를 카운팅하며 셀 수 있다. 시간복잡도 $O(logN)$ def func(N): cnt = 0 while N: cnt += N % 2 N //= 2 return cnt bitwise 연산자를 사용하면 이와 유사한 방법으로 1의 개수를 셀 수 있다. 주어진 수 N의 가장 오른쪽 비트가 1인지 확인하고, N을 하나씩 right shift하면서 1의 개수를 센다. 이는 N의 비트수만큼 시간이 걸린다. 시간복잡도 $O(logN)$ def func(N): cnt = 0 while N: cnt += N & 1 # 현재 가장 오른쪽 비트가 1인지 확인 N >>= 1 # N을 오른쪽으로 1 비트씩 이동하여 다음 비트 확인 return cnt 이보다 더 ..

01) 문제 백준이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다. 예를 들어 백준이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 백준이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오. 입/출력 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수..