인프런 워밍업 클럽 - CS Day 13
Algorithm한 번 정렬이 진행될 때마다 피벗이 정렬되고 정렬될 배열을 좌우로 나눠 재귀호출하여 모든 원소를 정렬한다.Quick Sort구현 방법피벗 선택배열에서 피벗으로 사용할 요소를 선택일반적으로 첫 번째, 마지막, 또는 중간 요소를 선택분할 (Partition)피벗을 기준으로 배열을 두 부분으로 나눈다.피벗보다 작은 요소들은 왼쪽으로, 큰 요소들은 오른쪽으로 이동재귀 호출분할된 두 부분 배열에 대해 Quick Sort를 재귀적으로 적용한다.종료 조건부분 배열의 크기가 1 이하가 될 때까지 재귀를 반복한다.결합정렬된 부분 배열들이 자동으로 하나의 정렬된 배열로 합친다.시간 복잡도평균 케이스: O(n log n)최악의 케이스: O(n^2)최선의 케이스: O(n log n)장점공간 효율성: 추가 메모리 공간을 거의 필요로 하지 않는 제자리 정렬 알고리즘캐시 친화적: 지역성이 좋아 캐시 성능이 우수병렬화 가능: 분할 정복 접근 방식으로 인해 병렬 처리에 적합단점불안정 정렬: 동일한 키 값을 가진 요소들의 상대적 순서가 보존되지 않을 수 있다.최악의 경우 성능: 피벗 선택이 잘못되면 O(n^2)의 시간 복잡도를 가질 수 있다.재귀적 특성: 재귀 호출로 인해 스택 오버플로우가 발생할 수 있다.OS주변 장치여러 주변장치는 메인보드 내의 버스로 연결된다.- 기존에는 하나의 버스로 연결되었음→ CPU가 I/O 작업을 수행할 때 다른 작업을 할 수 없음→ I/O Controller(입출력 제어기)와 여러 개의 버스가 추가되었다.입출력 제어기입출력 버스에서 온 데이터를 메모리로 옮긴다.→ 메모리는 CPU의 명령으로 움직인다.→ 입출력 제어기가 메모리에 접근하기 위해선 CPU가 필요하다.→ 입출력 제어기가 CPU의 도움이 필요 없도록 DMA(Direct Memory Access) 제어기가 추가되었다.DMA 제어기를 통해 데이터를 직접 메모리에 저장하거나 가져올 수 있다.CPU와 DMA가 사용하는 메모리가 겹치지 않도록 구분한다.(=Memory Mapped I/O)입출력 버스세부적으로 느린장치와 빠른장치를 구분하기 위해 두개의 채널로 나뉜다.고속 입출력 버스저속 입출력 버스→ 속도 차이로 인한 병목현상을 해결한다.시스템 버스고속으로 작동하는 CPU와 메모리가 사용한다.입출력 버스주변장치가 사용한다.그래픽 카드매우 대용량의 데이터를 다룬다.→ 고속 입출력 버스도 감당할 수 없다.→ 시스템 버스에 바로 연결해 사용한다.내부 구조메인보드에 있는 버스로 연결된다.하나의 버스는 Address 버스, Data 버스, Control 버스로 구성되어 있다.→ I/O 디바이스는 세 세가지 버스를 따로 받을 수 있다.H/W에 맞게 외부 인터페이스가 존재한다.레지스터 : 입출력 작업을 할 때 데이터를 저장하는 역할을 수행CPU 작업을 위해 메모리로 값이 이동하기도 한다.데이터의 전송단위에 따른 분류캐릭터 디바이스 상대적으로 적은 양의 데이터를 전송한다.마우스, 키보드, 사운드 카드, 직렬/병렬 포트, etc..블록 디바이스많은 양의 데이터를 전송한다.HDD, SSD, 그래픽 카드, etc...광학 마우스마우스 하단부의 작은 카메라가 초당 1500회 이상의 사진을 찍어 마우스의 디바이스 컨트롤러 내의 DSP(Digital Signal Processor)로 전송한다.DSP는 사진을 분석해 마우스의 x, y축 움직임을 캐치한다.DSP가 마우스의 움직임과 클릭같은 데이터를 감지하면 디바이스 컨트롤러는 CPU에게 인터럽트를 보내고 마우스 드라이버가 동작해서 데이터를 읽어간다.마우스 드라이버는 OS에게 이벤트를 주고, OS는 이벤트를 Foreground 애플리케이션으로 전달한다.키보드사용자가 키보드를 누르면 키보드의 디바이스 컨트롤러가 어떤 키를 입력받았는지 알아낸다.디바이스 컨트롤러가 CPU에게 인터럽트를 보낸다.키보드 드라이버는 OS에게 이벤트를 보낸다.OS는 이벤트를 Foreground 애플리케이션으로 전달한다.HDD블록 디바이스의 한 종류구조Spindle : 막대Platter : 자기화된 원판여러 개의 track으로 구성표면에 자성이 있다.N극 : 0S극 : 1→ 자석을 갖다대면 데이터가 손상된다.일반적으로 플래터 수는 2개 이상Read/Write Head : 플래터의 표면을 읽는다. Cylinder : 여러 개의 플래터에 있는 같은 트랙의 집합Track : Platter를 구성하고 있는 부분Sector : Track을 구성하는 부분HDD의 가장 작은 단위Disk Arm : Read/Write Head가 붙어 있는 장치데이터를 읽는 방법User Process가 HDD의 특정 섹터에 접근 요청실린더 C로 가서 트랙 B에 있는 섹터 D를 읽어들여라.Seek 동작 수행디스크 암은 헤드를 실린더 C로 이동시킨다.Seek Time 헤드를 실린더로 이동시키는 걸리는 시간→ HDD가 느린 이유트랙B의 섹터D가 Read/Write Head에 닿을 때 까지 스핀들을 회전시킨다.헤드에 섹터D가 읽히면 작업 완료Flash Memory(SSD)블록 디바이스의 종류전기적으로 데이터를 읽어들인다.특정한 지점에 데이터를 쓰면 덮어쓰기가 불가능하다.데이터를 지우기 가능한 횟수가 정해져있다.→ 같은 지점에 지우기를 자주 사용하면 망가져 사용할 수 없다.
