본문 바로가기

분류 전체보기142

[Hash]35. Hashing 목차 1. Hashing 정의, 기본 개념 2. Hashing 충돌 관리 3. Separate Chaning 4. Linear Probing 5. Double Hashing 1. Hashing 정의, 기본 개념 Hashing은 데이터를 (key, value)화 시켜서 빠르게 저장하고, 빠르게 불러오는 방식을 말합니다. 사실 제가 활용하는 파이썬에서는 이미 딕셔너리가 hashing으로 구현되어 있지만, 그래도 한번 개념을 정리해보고 구현해보도록 하겠습니다. Hashing의 최종 목표는 골고루, 공평하게 데이터가 펼져디고록 배분하는 것이 최종 목표 입니다. 만일 정해진 규칙에 의하여 배분하였을 시 뒤에 서술하겠지만 충돌이 발생할 경우, 이를 해결하기 위한 방법을 마련해야 하기 때문입니다. Hashing의 기.. 2021. 3. 10.
[컴퓨터 구조]1. Computer Architecture 목차 1. Three Basic Components 2. Main Memory 구성 요소 1. Three Basic Components 컴퓨터를 구성하는 요소는 크게 3가지로 나눌 수 있습니다. 1) CPU - CPU는 계산하는 곳(일을 하는 곳)으로, 여러 논리연산들을 포함하고 있다. : +, -, *, /, AND, OR, ... 와 같은 논리 연산들 2) I/O - 프린터, 키보드, 마우스, 모니터 등 입력과 출력을 담당하는 여러 장치들을 말한다. 3) Memory - 저장 공간으로, Main Memory라고 부른다. - ROM을 제외하면 모두 변동성이 있으며, 여러 일처리를 이 공간에서 진행한다. 4) Second Storage - CPU와 연결은 되지 않는 추가적인 저장공간 - 우리가 흔히 아는.. 2021. 3. 7.
[OS]2. Resource Manager, RMA, Interrupt 목차 1. OS, resource manager(자원 관리) 2. 4가지 기본 규칙들 3. I/O operation, structure 4. DMA Operation 5. Interrupt 1. OS, resource manager(자원 관리) OS는 결국 컴퓨터의 자원을 관리하는 역할을 수행합니다. 우선 프로그램을 실행하려면, memory에서 수행을 하게 됩니다. 하지만 memory는 한정되어 있고, 이는 CPU와 다양한 I/O device들과 연결되어 있습니다. 따라서, 동작을 하기 위해서는 CPU와 I/O device끼리 memory를 차지하기 위해 서로 경쟁하게 되며, 이를 원활하게 관리할 수 있는 수단들 중 RMA와 Interrupt가 있습니다. 2. 4가지 기본 규칙들 컴퓨터 내용을 관리할 때.. 2021. 3. 7.
[OS]1. OS란? 목차 1. OS란? 2. OS의 역할 3. OS의 위치 4. OS의 목적 5. OS 재정의 1. OS란? OS(오퍼레이팅 시스템)는 사실 이것이 '무엇'이라고 정의하기 쉽지 않습니다. 그 이유는, 하는 일과 역할이 너무 다양하기 때문입니다. 하지만, OS의 역할들에 대해 살펴본다면, 대략적으로 OS에 대해 정의할 수 있을 것입니다. 후에 정리할 OS의 역할을 토대로 대략적으로 정리해 보자면, 1) OS는 프로그램이다! 2) 컴퓨터 하드웨어(CPU, 메모리, ...)를 관리하는 3) 다른 응용 프로그램의 수행을 제어하는 참고로 OS가 다루는 응용 프로그램을 확인하기 위해서는, 작업관리자를 켜보면 됩니다. 이때 앱과 백그라운드 프로세스에 뜨는 프로그램들 모두가, OS에서 현재 수행을 제어하는 응용 프로그램의.. 2021. 3. 7.
[DB]1. 데이터베이스란? 목차 1. 데이터베이스란? 2. 앞으로 정리할 것 1. 데이터베이스란? 데이터베이스(database)는 대용량의 구조화된 데이터의 모음을 의미합니다. 쉽게 말해서, 다량의 데이터를 저장하는 공간이라고 생각하면 됩니다. 데이터베이스 서비스를 제공해주는 회사는 다양하며, 대표적으로 MySQL, PostgreSQL, ORACLE 등이 있습니다. 이런 데이터베이스 서비스들을 DBMS이라고 하며, 사용자와 SQL문법을 활용하여 서로 소통하게 됩니다. 이 외에도 대용량 데이터들(빅데이터)를 관리하기 위해 사용하는 Spark, Hadoop 등이 있습니다. 2. 앞으로 정리할 것 앞으로의 게시물에서는 데이터베이스과 관련된 모델을, SQL문, db구성에서 시작하여 그 후에는 DB가 어떻게 동작하는지에 대해 정리할 예정입.. 2021. 3. 7.
[백준]10989. 수 정렬하기 3(카운팅 정렬) 위 문제는 N개 만큼 입력되는 수를 오름차순으로 정렬하도록 하는 문제입니다. 게시물의 제목에서도 알 수 있듯이, 이 문제는 카운팅 정렬을 통해 해결할 수 있습니다. `1. 문제 해결 방법? 카운팅 정렬을 사용하는 경우를 정리하면 다음과 같습니다. 1) 입력되는 수의 범위가 적으며, 전부 0보다 크거나 같다 2) 중복이 허용된다(사실 허용 안되어도 가능) 카운팅 정렬의 전반적인 아이디어는 다음과 같습니다. 1) 위의 문제처럼 입력되는 수의 범위가 1~10000이라면, 크기가 10001인 배열 c을 만든다. 2) 배열 c의 모든 요소에 0을 넣는다. 3) 새로운 수 tmp가 입력될 때 마다, 배열 c의 index를 i, 그 위치에 해당되는 값을 a라고 하면, 4) tmp == i 인 c[i]의 값을 +1 한.. 2021. 3. 3.
[Dictionary]34. Dictionaries 목차 1. Dictionary ADT 2. List-based Dictionary 3. Search Table 1. Dictionary ADT Dictionary는 후에 배울 Binary Search Tree, AVL Tree, ADT 등등 탐색할 수 있는 ADT라고 생각하면 됩니다. 1) 특징 - 입력되는 데이터가 하나의 key로 간주된다 - data의 순서는 명시되어 있지 않음 (필요에 의하다면 추가 가능) - 중복되는 key를 지닐 수 있다 2) 기능 - find(k): key k에 해당하는 위치를 반환 - put(k, o): 해당 위치에 새로운 값 입력 - erase(k): key k에 해당하는 값 제거 - size(), empty() 2. List-based Dictionary Dictionar.. 2021. 2. 28.
[Heap]33. Bottom-up Heap Construction 목차 1. Merging Two Heaps 2. Bottom-up Heap Construction 1. Merging Two Heaps Heap-sort도 충분히 빠른 수행이 가능한 강력한 방법이지만, heap을 구성하는 시간을 총 O(n)으로 단축할 수 있는 방법이 있습니다. 이는 두개의 node와 하나의 key값이 주어졌을 때, 이를 서로 합치는 Merging Two Heaps를 활용하여 해결할 수 있습니다. 순서는 1) 두개의 heap과 1개의 key값을 준비함 2) 1개의 key값을 root로 하고, 나머지 두개의 heap이 subtree가 되는 새로운 node를 만든다 3) root에서 downheap실행, heap의 규칙을 성립시킨다 2. Bottom-up Heap Construction Bo.. 2021. 2. 28.

티스토리툴바