💻

큐 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조 ex. 공항에서 입국소속 하는 줄 FIFO(First in First Out) 먼저 들어간 원소가 먼저 나옴 성질 원소의 추가 / 제거 O(1) 스택 - top: 원소가 추가되고 제거되는 곳/ 원소가 위 아래로 배치된 것 큐 - rear: 추가되는 곳(뒤쪽), front: 제거되는 곳(앞쪽) 제일 앞 / 뒤의 원소 확인 O(1) 제일 앞 / 뒤가 아닌 나머지 원소들의 확인 / 변경 원칙적으로 불가능 구현 배열(더 쉬움) 연결 리스트 const int MX = 1000005; int dat[MX]; int head = 0, tail = 0; head와 tail은 0번지에서 시작해 계속 증가 dat 배열에서 dat[head] ~ dat[..

스택 한쪽 끝에만 원소를 넣거나 뺄 수 있는 자료구조 Restricted Structure: 스택, 큐, 덱 ex. 프링글스 통, 엘리베이터 FILO(First In Last Out) 자료구조 먼저 들어간 원소가 나중에 나오는 구조 성질 원소의 추가 / 제거 O(1) 제일 상단의 원소 확인 O(1) 제일 상단이 아닌 나머지 원소들의 확인 / 변경이 원칙적으로 불가능 구현 시 배열 기반으로 구현 구현 배열(더 쉬움) 연결리스트 const int MX = 1000005; int dat[MX]; int pos = 0; 원소를 담은 큰 배열 1 개, 인덱스 저장할 변수 1개 {13, 21, 30}이 담겨있는 스택 나타내기 -> dat[0], dat[1], dat[2]에 각각 13, 21, 30, pos = 3 ..

연결리스트 원소들을 저장할 때 그 다음 원소가 있는 위치를 포함하는 방식으로 저장하는 자료구조 ex. 메모장 성질 k번째 원소를 확인 / 변경 -> O(k) 필요 첫 번째부터 순차적으로 방문해야 함 (첫 번째 원소의 주소만 알고 있음) N개의 원소 -> 평균적으로 2/N 시간 => O(N) 임의의 위치에 원소 추가 / 임의 위치의 원소 제거 -> O(1) 다음 원소의 주소만 변경해주면 됨 (추가하고 싶은 위치의 주소를 알고 있는 경우) 원소들이 메모리 상에 연속 X -> Cache hit rate ↓ But, 할당 다소 쉬움 배열 vs. 연결리스트 -> 선형 자료구조 vs. 비선형 자료구조: 트리, 그래프, 해쉬 종류 단일 연결 리스트(Singly Linked List) 각 원소가 다음 원소의 주소를 들..

배열 메모리 상에 원소를 연속하게 배치한 자료구조 성질 O(1)에 k번째 원소를 확인 / 변경 가능 임의의 위치에 원소 추가 / 제거 O(N) 추가하는 위치가 끝에 가까울수록 시간 ↓ => 평균적으로 N/2개 밀어야 함 추가적으로 소모되는 메모리의 양(= overhead)가 거의 X Cache hit rate ↑ 캐시 적중률(Cache hit rate) = 적중횟수/ 총 접근횟수, 컴퓨터의 성능 나타내는 척도 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림 시간복잡도 O(1) 임의의 위치에 있는 원소 확인/ 변경 원소 끝에 추가 마지막 원소 제거 O(N) 임의의 위치에 원소 추가 / 임의의 위치의 원소 제거 void insert(int idx, int num, int arr[], int& le..

Chapter 08 입출력장치1. 장치 컨트롤러와 장치 드라이버장치 컨트롤러/ 장치 드라이버 CPU와 메모리의 데이터 전송률 ↑, 입출력장치의 데이터 전송률 ↓전송률(transfer rate): 데이터를 얼마나 빨리 교환할 수 있는지를 나타내는 지표 => 컴퓨터에 직접 연결 X, 장치 컨트롤러 ~> 컴퓨터 내부와 정보 주고받음장치 컨트롤러(device controller) = 입출력 제어기(I/O controller) = 입출력 모듈(I/O module)CPU와 입출력장치 간의 통신 중개오류 검출데이터 버퍼링(buffering)전송률이 높은 장치와 낮은 장치 사이에 주고 받는 데이터 -> 버퍼(buffer)라는 임시 공간에 저장 => 전송률 비슷하게 맞추는 방법/ 버퍼에 데이터를 조금씩 모았다가 한꺼번에..

Chapter 07 보조기억장치1. 다양한 보조기억장치하드 디스크/ 플래터/ 데이터 접근 시간/ 플래시 메모리/ 페이지/ 블록 보조기억장치: 하드 디스크, 플래시 메모리(ex. USB 메모리, SD 카드, SSD)하드 디스크(HDD; Hard Disk Drive) = 자기 디스크(magnetic disk)자기적인 방식으로 데이터를 저장하는 보조기억장치트랙(track): 플래터를 여러 동심원으로 나눴을 때 그중 하나의 원섹터(sector)트랙을 여러 조각으로 나눈 것 중 한 조각하드 디스크의 가장 작은 전송 단위블록(block): 하나 이상의 섹터실린더(cylinder)여러 겹의 플래터 상에서 같은 트랙이 위치한 곳을 모아 연결한 논리적 단위연속된 정보는 한 실린더에 기록 -> 디스크 암을 움직이지 x 바..