말감로그

힙 정렬이란 ? 힙 정렬은 힙의 특성을 이용하여 정렬하는 알고리즘이다. 힙은 '부모의 값이 자식의 값보다 항상 크다'는 조건을 만족하는 완전 이진 트리이다. 이때 부모의 값이 자식의 값보다 항상 작아도 힙이라고 한다. 즉, 이러한 두 값의 대소 관계가 일정하면 된다. 완전 이진 트리란? 노드를 삽입할 때 왼쪽부터 추가하는 이진트리(모든 노드의 차수가 2이하로 구성된 트리) 모든 부모와 자식 관계는 항상 부모의 값 >= 자식의 값 성립 부모와 자식 관계는 일정하지만 형제 사이의 대소 관계는 일정하지 않다. 따라서 힙은 형제의 대소관계가 정해져 있지 않으므로 부분 순서 트리(partical ordered tree)라고도 한다. 시간복잡도 - O(n log n) 단순 선택 정렬의 시간 복잡도 O(n^2) 이러..

디스크 데이터를 저장하고, 읽고, 쓰는 역할을 하는 컴퓨터의 주요 저장장치 중 하나이다. 디스크들은 원판들로 구성되어있다. 각 원판들은 두 개의 옆면, 즉 표면으로 이루어져 있으며, 이들은 자성을 띤 기억 물질로 코팅되어 있다. 원판의 중심부에 있는 회전하는 축은 원판을 고정된 회전율로 돌려주며, 이 비율은 대개 분당 5,400번에서 15,000번 회전하는 비율을 갖는다. 디스크의 용량은 보통 바이트 단위로 표현된다. 1GB = 10^9바이트 , 1TB = 10^12바이트. 하드 디스크(HDD)와 솔리드 스테이트 드라이브(SSD), CD나 DVD와 같은 광디스크, 플로피 디스크와 같은 휴대용 디스크 등 다양한 종류의 디스크가 있다. HDD 금속 플래터에 자기를 이용해 데이터를 저장하고 읽어내는 장치이다...

Direct Memory Access란? 직접 메모리 접근은 주변장치(하드디스크, 그래픽 카드 등)에서 CPU의 처리를 거치지 않고 직접 RAM이나 저장장치에 접근해서 필요한 데이터를 가져오는 기능이다. 중요한건 CPU의 개입 없이 I/O장치와 저장장치 사이의 데이터를 전송하는 접근 방식이라는 점이다. PIO(Programmed Input/Output)은 CPU가 주변장치와 데이터를 주고받는 방식으로 효율이 떨어지는 방식이다. 기존의 방식으로 주변기기끼리 통신을 하려고 한다면 주변기기 측에서 CPU에 필요한 메모리에 대한 정보를 주고 이를 CPU가 확인해서 해당 기기에게 데이터를 달라고 명령하고 데이터를 받아서 요청한 기기에 전송하는 과정을 거쳐야 했으나, DMA를 사용할 경우 CPU를 거치지 않고 데이..

demand zero memory demand zero memory는 필요할 때 (demand) 할당하고 0으로 초기화해주는(zero) 메모리를 말한다. 리눅스의 메모리 시스템은 매우, 최대한 게으른 방식으로 작동하도록 되어있다. 어떤 자원을 요청하거나 동작을 요청했을 때, 그것이 정말 필요해질 때까지 실제 자원을 할당하거나 동작을 실행하지 않는다는 것을 의미한다. -> 메모리 사용 효율성이 향상되고, 시스템 자원을 절약할 수 있다. 즉, 우리(user program)가 kernel에게 메모리를 할당해달라고 요청하면(sbrk) kernel은 거의 아무것도 하지 않고(특정한 VM 영역이 할당되었다는 최소한의 표시만 해두고) 우리에게 할당이 끝났다고 알려준다. -> 실제 메모리는 할당되지 않은 상태로 남아있..