2022. 10. 28. 12:26ㆍ책 정리 [ 내가 다시 보기위한 ]/책[코드없는 알고리즘과 데이터 구조] 정리
컴퓨터 메모리
컴퓨터 메모리는 컴퓨터가 처리중이거나 처리를 끝낸 데이터를 저장할 수 있는 공간.
계층적으로 구성되어 있고, 각 층을 이루는 메모리 유형마다 정해진 역할이 있다.
계층구조를 이상적으로 나타내면 피라미드 형태의 적층 구조이다.
| 레지스터 | 연산 처리속도가 굉장히 빠르고 CPU에 장착할 수 있을 만큼 크기가 작은 메모리. |
| L1 캐시 L2 캐시 |
캐시메모리, CPU가 가장 많이 사용하는 데이터를 저장. L1, L2 두가지 종류가 있는데 L1 캐시는 CPU 레지스터만큼 빠르고, L2 캐시는 L1 캐시보다 느리지만 RAM 보다는 빠르다. 캐시는 용량이 너무 크면 비효율적, RAM 보다 용량이 작아서 데이터를 쉽게 찾을 수 있는데 캐시 용량이 너무 커지면 연산 처리 속도에서 장점이 줄어듬. |
| 메인메모리 | RAM ,RAM 에 적재된 데이터는 CPU 칩에 내장된 캐시라는 메모리 유형에 적재된 후 결국 CPU가 처리중인 데이터를 저장하는 레지스터에 적재된다. |
| 하드디스크 | 최하단요소로 SSD, HDD 와 같은 저장장치를 디스크 저장장치, 하드디크스라고 한다. 하드디스크는 메인 메모리인 RAM에 적재되는 데이터를 저장한다. |
메모리 공간을 식별하기 위해 사용하는 메모리 주소.
가상 메모리 : 운영체제는 물리적 주소에 가상의 주소를 매핑하여 실제 메모리 보다 더 많은 메모리가 있다고 프로그램이 착각하게 만듬.
가상 주소 : 가상메모리에는 프로그램에 할당된 메모리상의 위치를 식별하기 위한 주소.
페이징 : 가상 메모리를 일정한 크키의 페이지로 나눠서 이용하는 것
페이지 테이블 : 페이지에 매핑된 주소를 물리적인 주소로 변환하는 것
페이징과 페이지 테이블은 특정 데이터가 물리적인 메모리 공간에 여러개로 나뉘어 저장 되어도 서로를 참조해 해당 데이터를 손실없이 안전하게 불러올수 있도록 도움. 혹은 메모리 공간을 효율적으로 사용하도록 도움.
선형 데이터 구조의 개요 (배열, 리스트, 스택, 큐)
선형 데이터 : 데이터 구조를 구성하는 요소들이 서로 인접해 순차적인 방식으로 정렬
배열 : 자료형이 같은 요소들을 저장, 저장된 각각의 자료를 요소, 요소에 매겨진 숫자를 배열의 인덱스 라고 한다.
리스트 : 배열의 특별한 유형. 배열 요소는 메모리에 순차적으로 저장되지만, 리스트 요소는 흩어진 상태로 메모리에 저장됨. 이때문에 연결리스트 (linked list ) 는 메모리를 더 효과적으로 사용할 수 있다.
< 리스트 >
리스트의 요소는 데이터 요소와 포인터(=참조) 의 쌍으로 구성된다.
포인터는 리스트내의 바로 다음 요소가 저장된 메모리 위치를 가리킨다.
따라서 어떤 데이터 요소에 접근 하려면 바로 이전 요소의 포인터를 사용 해야 한다.
연결리스트에서 데이터 요소와 다음 요소를 가리키는 포인터의 쌍을 노드 라고 한다.
연결 리스트에는 해당 리스트에 진입하는 지점이 있는데 이를 헤드 라고 한다.
단방향 연결 리스트에서 마지막 노드는 다른 노드를 가리키지 않으므로 포인터는 널값을 갖는다.
양방향 연결 리스트는 데이터를 삭제할 때나, 리스트를 양방향으로 순회 할 때 더 효율적인 연결 리스트 이다.
순환 연결 리스트는 마지막 노드가 첫번째 노드와 연결된다.
< 스택 >
추가된 요소를 사용 가능한 메모리의 가장 앞 주소에 배치하는 선형 데이터 구조의 한 종류.
스택에 요소를 추가하는 동작을 푸시
스택에서 요소를 삭제하는 동작을 팝
후입 선출 데이터 구조
생성 방식에 따라 데이터의 크기나 규모가 고정된 정적, 실행중 크기를 늘릴 수 있는 동적 스택 으로 나눌 수 있다.
< 큐 >
각 요소에 우선 순위를 부여하는 데이터 구조의 한 종류
큐에 요소를 추가하는 것을 인큐
큐에서 요소를 삭제하는 것을 데큐
선입선출 데이터 구조
<우선순위 큐>
기본적인 큐를 확장
키( 값을 식별하고 검색하는데 사용) 와 값( 실제 사용하는 데이터) 의 체계를 사용해 큐의 요소들을 정렬
우선순위 큐를 구현할 때는 연결 리스트나 배열과 같은 데이터 구조를 사용
우선 순위 큐에서 모든 요소는 우선 순위가 있으면 이는 키에 해당
우선순위가 높은 요소는 우선순위가 낮은 요소보다 먼저 큐에서 삭제됨
만약 우선순위가 같다면 큐에 먼저 추가된 요소부터 삭제됨.
우선순위 큐는 뒤쪽에 요소를 추가하고 큐 앞쪽에서 요소를 삭제함
* 스택의 후입 선출 구조와 큐의 선입선출 구조를 결합하면 좋은 프로그램과 데이터 구조를 만들 수 있다.
출처 : 코드없는 알고리즘과 데이터 구조
'책 정리 [ 내가 다시 보기위한 ] > 책[코드없는 알고리즘과 데이터 구조] 정리' 카테고리의 다른 글
| Part 2. 알고리즘 - 7장 정렬 알고리즘 (0) | 2022.10.30 |
|---|---|
| Part 2. 알고리즘 - 6장 선형 및 이진 탐색 (0) | 2022.10.30 |
| Part 1. 데이터 구조 - 4장 해시 데이터 구조 (0) | 2022.10.30 |
| Part 1. 데이터 구조 - 3장 트리 데이터 구조 (0) | 2022.10.30 |
| Part 1. 데이터 구조 - 1장 데이터 구조와 알고리즘, 자료형, 빅 오 표기법 (0) | 2022.10.28 |