말감로그

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

📆2024.2.16 CSAPP 6장 뒷 부분 더 읽고 정리하였다. 백준 암기왕 풀면서 이진 탐색에 대해 다시 복습하게 되었고 set 함수도 분명 봤었는데 다시 또 까먹어서 복습.. set 함수는 중복된 값을 제거하거나, 데이터의 유무를 확인하는 데 주로 사용된다. 또한 순서가 없는 자료형이다. in 키워드는 어떤 값이 특정 시퀀스(리스트, 튜플, 문자열 등) 혹은 컬렉션(딕셔너리, 집합 등) 안에 존재하는지 검사하는 연산자이다. 백준 숫자 카드 2를 풀면서 파이썬 collections 모듈의 Counter를 알게 되었다. from collections import Counter Counter 생성자는 여러 형태의 데이터를 인자로 받는다. 먼저 중복된 데이터가 저장된 배열을 인자로 넘기면 각 원소가 몇 번..

10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,0 www.acmicpc.net 문제 숫자 카드는 정수 하나가 적혀 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, ..

2776번: 암기왕 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, www.acmicpc.net 문제 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, 연종이 하루 동안 본 정수들을 모두 ‘수첩1’에 적어 놓았다. 그것을 바탕으로 그가 진짜 암기왕인지 알아보기 위해, 동규는 연종에게 M개의 질문을 던졌다. 질문의 내용은 “X라는 정수를 오늘 본 적이 있는가?” 이다. 연종은 막힘없이 모두 대답을 했고, 동규는 연종이 봤다..

📆2024.2.15 가상메모리, DMA, demand zero memory DMA(Direct Memory Access) Direct Memory Access란? 직접 메모리 접근은 주변장치(하드디스크, 그래픽 카드 등)에서 CPU의 처리를 거치지 않고 직접 RAM이나 저장장치에 접근해서 필요한 데이터를 가져오는 기능이다. 중요한건 CPU habbn-unitystudy.tistory.com 가상메모리(Virtual Memory)와 페이징&세그먼트 가상 메모리를 보기 전에 물리적인 메모리, 논리적인 메모리가 뭔지 알아보고 가자. 💡물리적인 메모리 VS 논리적인 메모리 - 물리적인 메모리(Physical Memory 또는 RAM) : 컴퓨터의 실제 하드웨어에 habbn-unitystudy.tistory.co..

디스크 데이터를 저장하고, 읽고, 쓰는 역할을 하는 컴퓨터의 주요 저장장치 중 하나이다. 디스크들은 원판들로 구성되어있다. 각 원판들은 두 개의 옆면, 즉 표면으로 이루어져 있으며, 이들은 자성을 띤 기억 물질로 코팅되어 있다. 원판의 중심부에 있는 회전하는 축은 원판을 고정된 회전율로 돌려주며, 이 비율은 대개 분당 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 영역이 할당되었다는 최소한의 표시만 해두고) 우리에게 할당이 끝났다고 알려준다. -> 실제 메모리는 할당되지 않은 상태로 남아있..

가상 메모리를 보기 전에 물리적인 메모리, 논리적인 메모리가 뭔지 알아보고 가자. 💡물리적인 메모리 VS 논리적인 메모리 - 물리적인 메모리(Physical Memory 또는 RAM) : 컴퓨터의 실제 하드웨어에서 사용되는 메모리를 의미한다. 이는 RAM이라고도 불리며, CPU가 직접 액세스하여 데이터를 읽고 쓸 수 있는 메모리. 물리적인 메모리는 주 기억장치로써 프로그램 실행 중에 데이터와 명령어를 저장하는 역할을 한다. - 논리적인 메모리(Logical Memory 또는 Virtual Memory) : 프로그램이 실제로 사용하는 메모리 주소 공간을 나타낸다. 프로그램이 사용하는 메모리 주소는 가상의 주소로써, 프로그램이 실행될 때 논리적인 주소로 변환되어 물리적인 메모리와 매핑된다. 📍가상메모리란? ..