해시테이블 {key, value}로 데이터를 저장하는 자료구조로 원하는 값을 빠르게 검색할 수 있는 자료구조이다. 이러한 속도가 가능한 이유는 해시테이블이 내부 적으로는 배열로 구현되어있고 이러한 배열에 엑세스할 수 있는 인덱스를 해시 함수를 통해 산출해내기 때문에 검색의 대부분의 경우는 매우 빠르다. 해시함수 입력값이 있을 때 함수 f에 넣었 을때...

힙(Heap) 이전에 포스팅했던 완전 이진 트리(Complete Binary Tree)의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다. 큰값이 위에 오는지 작은 값이 위에 오는지 종류에 따라 최대 힙과 최소 힙으로 나눈다. 힙 트리에서는 중복된 값을 허용되는데 ...

트리 점이 있고 이 점이 선으로 연결된 형태를 그래프라고 한다. 이러한 점은 각각 노드, 정점, vertex라고 불리며 연결한 선은 edge 혹은 간선이라고 부른다. 트리는 기본적으로 이러한 그래프에서 파생된 것이다. 순환이 없는 그래프라고 봐도 무방한데 순환이 없는 형태라면 필연적으로 한 개의 노드에서 모든 가지가 나오는 형태로 만들어진다. 이때...

스택과 큐 이번에는 스택과 큐에 대해서 알아보도록 하겠다. 스택 스택은 FILO(First In Last Out) 구조의 자료구조로 책 더미를 생각하면 편하다. 스택에서 데이터 삽입하는 것을 PUSH, 데이터를 빼는 것을 POP이라고 한다. 먼저 들어간 것이 가장 아래에 쌓이기 때문에 가장 나중에 들어간 것이 먼저 나오게 된다. 큐 스택과는 ...

배열과 연결리스트 컴퓨터의 자료구조에 대해서 배울때 처음 언급되는 것은 변수 이후에는 배열이다. 이러한 배열은 메모리 동적할당에 대해서 배우고 나서 연결리스트와 구분되어 한번 말이 나오게된다. 다음의 그림을 보자 배열은 간단히 말해서 메모리상에서 연속되어 할당되는 것이고 연결리스트는 메모리에서는 떨어져서 할당되나 특정 링크를 통해 연결되어 있...

컴퓨터 기초 컴퓨터 기초가 좀 부족한가 싶어서 관련 내용 포스팅을 시작할까 한다. 사실 다 알고있는 내용이지만 그걸 막힘없이 설명할 수 있냐고하면 또 대답하기 애매해지는터라 파인만 선생님의 가르침에 따라 해당 내용을 전혀 모르는 사람도 이해할 수 있는 형태로 포스팅을 진행 해 볼까 한다. 목차 파트는 잦은 업데이트가 있을 예정이다, 또한 항목...

페이징 및 세그멘테이션 설정 이전에 페이징과 세그멘테이션에 대한 포스팅을 진행한 적이 있다. 페이징과 세그멘테이션을 소프트웨어적인 방법으로 구현하여 사용할 수도 있겠지만 으레 그러하듯 하드웨어적으로 구현된 것 보단 성능이 떨어진다. 그렇기 때문에 아키텍처 자체에서 페이징과 세그멘테이션을 지원한다. 페이징과 세그멘테이션을 활성화하기 위해서 우리가 살펴...

32bit kernel 리얼모드에서 부트로더를 이용해서 32bit 커널을 로드해서 구동했다면 32bit에서는 64bit 커널을 로드해오고 몇가지 필요한 설정들을 바꿔야한다. 이전에 모드에 대한 설정을 할때 32bit 보호모드의 경우 아래와 같은 특성이 있다고 설명했다. 윈도우나 Linux가 구동되는 기본 모드이다. 멀티태스킹, 세그멘테이션,...

스케줄링 Task의 실행 순서를 정하는 것을 스케줄링이라고 한다. 가장 크게 나누면 두 개로 나눌 수 있다. 바로 선점형과 비선점형 스케줄링이다. 선점형 vs 비선점형 프로세스가 끝나기전에 다른 프로세스가 먼저 실행 할 수 있다면 선점형 현재 실행 중인 프로세스가 종료되기 전에 다른 프로세스가 먼저 실행될 수 없다면 비 선점형이다. 비선점형 스케줄링...

멀티 태스킹 부트로더 다음에 바로 32bit kernel로 넘어가자니 멀티태스킹에 대해서 미리 언급해야 할것 같아서 포스팅한다. 물론 이 책에서는 64bit Kernel까지 넘어가서야 멀티태스킹에 대해서 논하지만 겹치는 부분이 좀 있기 때문에 이 부분을 먼저 언급하고자한다. 우리가 일상에서 멀티태스킹한다는 단어는 많이 사용한다. 멀티태스킹이라는 단어...