다락방

정보는 비트와 컨텍스트로 이루어진다. 모든 시스템 내부의 정보 - 디스크 파일, 메모리상의 프로그램, 데이터, 네트워크를 통해 전송되는 데이터- 는 비트들로 표시된다. 서로 다른 객체들을 구분하는 방법은 이를 바라보는 컨텍스트에 의해서다. 다른 컨텍스트에서는 동일한 일련의 바이트가 정수, 부동소수, 문자열 또는 기계어 명령을 의미할 수 있다. 프로그램은 다른 프로그램에 의해 다른 형태로 번역된다. GCC 컴파일러 드라이버는 소스파일을 읽어서 실행파일로 번역한다. 번역은 4개의 단계를 거쳐서 실행된다. 이 네 단계를 실행하는 프로그램들(전처리기, 컴파일러 ,어셈블러, 링커)을 합쳐서 컴파일 시스템이라고 한다. 전처리 단계 : 전처리기(cpp)는 본래의 C프로그램을 #문자로 시작하는 디렉티브(directiv..

CSAPP 3.4 3.4 정보 접근하기 x86-64 주처리 장치 CPU는 64비트를 저장할 수 있는 범용 레지스터 16개를 보유한다 레지스터는 정수 데이터와 포인터를 저장하는데 사용한다. 인스트럭션들은 16개의 레지스터 하위 바이트들에 저장된 다양한 크기의 데이터에 대해 연산 할 수 있다. 바이트 수준 연산은 가장 덜 중요한 바이트에 대해 연산, 16비트 연산은 덜 중요한 2바이트, 32비트는 4바이트 , 64비트 연산은 레지스터 전체에 접근한다. 일반적인 프로그램에서 서로 다른 레지스터들은 서로 다른 목적으로 이용한다. 스택 포인터 %rsp는 런타임 스택 끝 부분을 가리키기 위해 사용된다. 일부 인스트럭션들은 특별히 이 레지스터를 읽고 쓴다. 다른 15개의 레지스터는 사용이 저금 더 자유롭다. 3.4...

B-Tree B트리는 이진트리에서 발전되어 모든 리프노드들이 같은 레벨을 가질 수 있도록 자동으로 밸런스를 맞추는 트리다. 정렬된 순서를 보장하고, 멀티 레벨 인덱싱을 통한 빠른 검색이 가능하다. B트리는 이진트리와 다르게 하나의 노드에 많은 수의 정보를 가지고 있을 수 있다. 최대 M개의 지식을 가질 수 있는 B트리를 M차 B트리라고하며 다음과 같은 특징을 가진다. 노드는 최대 M개부터 최소 M/2개 까지의 자식을 가질 수 있다. 노드에는 최대 M-1개 부터 최소 [M/2]-1개의 키가 포함 될 수 있다. 노드의 키가 x라면 자식의 수는 x+1개 이다. 최소차수는 자식수의 하한값을 의미, 최소차수가 t라면 M=2t-1를 만족한다. Key 검색과정 루트노드에서 시작하여 하향식으로 검색을 수행한다(검색하고..

위상정렬(Topological Sorting) 순서가 정해져 있는 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘. 사이클이 없는 방향, 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것. 진입차수와 진출차수 진입차수(Indegree) : 특정한 노드로 들어오는 간선의 개수 진출차수(Outdegree) : 특정한 노드에서 나가는 간선의 개수 동작과정 큐를 이용해 구현한다. 진입차수가 0 인 노드를 큐에 넣는다. 큐가 빌 때까지 다음의 과정을 반복한다 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다 새롭게 진입차수가 0이 된 노드를 큐에 삽입한다. 위상정렬을 수행할 수 있는 그래프는 사이클이 없는 방향 그래프(DAG)이여야 한다. 위상정렬의 특징 위상정렬은 사..

DFS(Depth-First Search) 깊이 우선 탐색 알고리즘 특정한 경로를 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문 한 후 다시 돌아가 다른 경로로 탐색하는 알고리즘 DFS는 스택 자료구조를 이용한다(보통 재귀함수를 이용해 DFS를 구현한다.) 동작과정 탐색 시작노드를 스택에 삽입 후 방문 처리를 한다. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접노드를 스택에 넣고 방문처리를 한다. 방문하지 않은 인접노드가 없으면 최상단 노드를 꺼낸다. 2를 수행할 수 없을때까지 반복한다. def DFS(graph,v,visit): visited[v] = True print(v) for i in graph[v]: if not visited[i]: DFS(graph,i,vi..

그래프(Graph) 그래프의 정의와 특징 정의 그래프는 정점(vertex)와 그 정점을 연결하는 간선(Edge)으로 구성된다. 이러한 정점과 간선의 집합으로 이루어진 자료구조를 그래프라고 한다. 그래프 용어 정점(Vertex) : 노드(Node) 라고도 하며 데이터가 저장되는 그래프의 기본 원소이다. 간선(Edge) : 링크(Link) 라고도 하며 정점간의 관계를 나타낸다. 인접정점(Adjacent Vertex) : 하나의 정점에서 간선에 의해 직접 연결된 정점을 뜻한다. 차수(Degree) : 정점에 연결된 간선의 수, 무방향 그래프에서 하나의 간선은 두개의 정점에 인접하기에 간선 수에 2배를 해주면 된다. 방향 그래프의 경우 외부에서 오는 간선의 수를 진입차수(in-degree)라고 하며, 외부로 향..

벌써 1주가 또 지났다. 배운 것, 공부한 것은 많은 느낌이지만 내 것이 안됐다. 지식들이 머리속에서 붕 떠있다는 느낌이 든다. 빠르게 캐치해서 내 것으로 만들지않는다면 그대로 날아가지 않을까 생각한다. 조금 더 공부할 때 집중해서, 효율을 늘려봐야겠다. 시간은 이미 많이 투자하고 있으니 집중의 정도를 늘려 효율의 향상을 기대해보는게 맞지 않을까..? CSAPP 정보는 비트와 컨텍스트로 이루어진다. 모든 시스템 내부의 정보 - 디스크 파일, 메모리 상의 프로그램 , 데이터, 네트워크를 통해 전송되는 데이터는 - 비트들로 표시된다. 서로 다른 객체들을 구분하는 방법은 이를 바라보는 컨텍스트에 의해서 결정된다. 다른 컨텍스트에서는 동일한 일련의 바이트가 정수, 부동소수, 문자열 또는 기계어 명령을 의미 할 ..

24.01.17 분할정복, 병합정렬, 코어타임 코테가 바로 내일이여서 백준 문제를 많이 풀려고 노력했다. 쉽지않다. 흑흑.. Algorithm 분할정복(Divide and Conquer) 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방식 대표적인 예 퀵정렬 합병정렬 이진탐색 선택문제 고속 푸리에 변환 분할정복의 설계 Divide - 원래 문제가 분할하여 비슷한 유형의 더 작은 하위 문제로 분할 가능할때까지 나눈다. Conquer - 각 하위 문제를 재귀적으로 해결한다. 하위 문제의 규모가 나눌 수 없는 단위가 되면 탈출 조건을 설정하고 해결한다. Combine - Conquer한 문제들을 통합하여 원래 문제의 답을 얻어 해결한다. Divide를 제대로 나누면 Conquer 과정은 ..

병합정렬(Merge Sort) 하나의 리스트를 두개의 균일한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법. 동작과정 Divide - 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다 Conquer - 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면(left < right) 순환호출을 이용해 다시 분할 정복 방법을 적용한다. Combine - 정렬된 부분 배열들을 하나의 배열에 병합한다. def merge_sort(arr): def sort(low, high): if high - low < 2: return mid= (low + high) // 2 sort(low, mid) sort(mid, high) me..

분할정복(Divide and Conquer) 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방식 대표적인 예 퀵정렬 합병정렬 이진탐색 선택문제 고속 푸리에 변환 분할정복의 설계 Divide - 원래 문제가 분할하여 비슷한 유형의 더 작은 하위 문제로 분할 가능할때까지 나눈다. Conquer - 각 하위 문제를 재귀적으로 해결한다. 하위 문제의 규모가 나눌 수 없는 단위가 되면 탈출 조건을 설정하고 해결한다. Combine - Conquer한 문제들을 통합하여 원래 문제의 답을 얻어 해결한다. Divide를 제대로 나누면 Conquer 과정은 자동으로 쉬워진다. 그래서 Divide를 잘 설계하는 것이 중요하다. 분할정복 알고리즘은 재귀 알고리즘이 많이 사용되는데, 이 부분에서 분할정복..