인프런 워밍업 클럽 - CS Day 2
그림으로 쉽게 배우는 자료구조와 알고리즘(기본편)What is Data Structure?자료구조 : 데이터가 어떤 구조로 저장되고 어떻게 사용되는지를 나타낸다.변수 : 가장 단순한 자료구조배열 : 숫자나 문자열 등을 연속적으로 저장하는 자료구조인덱스를 통해 특정 숫자나 문자열에 접근할 수 있다.자료구조에 따라서 결과를 얻기 위한 처리 방법이 달라진다.What is Algorithm?어떤 문제를 해결하기 위한 확실한 방법문제를 해결할 수 있는 알고리즘은 하나만 존재하는 것이 아니라 여러가지 방법이 있을 수 있다.더 좋은 알고리즘이란?사용자에 따라 다를 수 있음메모리 사용률메모리를 더 사용하더라도 속도가 더 빠른 경우일반적으로 알고리즘 성능의 척도를 시간 복잡도로 표현한다.시간 복잡도란?특정 알고리즘이 어떤 문제를 해결하는 데 걸리는 시간Bit-Ω : 최선의 시간 복잡도Big-O : 최악의 시간 복잡도가장 많이 사용된다.Big-θ : 평균의 시간 복잡도코드에서 성능에 많은 영향을 주는 부분코드의 속도를 판가름 하는 부분→ 반복문특정 알고리즘의 성능을 평가할 때는 알고리즘의 반복문을 보고 성능을 평가한다.Big-O선형시간 알고리즘입력의 크기(n)에 대비해 걸리는 시간을 그래프로 그렸을 때 정확히 직선이 된다.시간 복잡도 : O(n)입력의 크기가 증가함에 따라 실행 시간이 일정한 비율로 증가하는 알고리즘상수시간 알고리즘입력의 크기와 관계없이 항상 일정한 시간 내에 실행되는 알고리즘시간 복잡도 : O(1) Big-O 표기법은 성능을 정확하게 표기할 수는 없다.→ 해당 알고리즘의 입력이 늘어날 때 단순히 계산량이 얼마나 늘어나는지를 표현하는 방법이기 때문→ 계산에 가장 많은 영향을 끼치는 연산만 표기한다.그림으로 쉽게 배우는 운영체제OS개인용 컴퓨터 : Windows, MacOS대형 컴퓨터 / 서버 : Linux, Unix스마트폰 / 태블릿 : Android, iOS내비게이션, 스마트 워치, 냉장고, 세탁기 등 : 임베디드 운영체제싱글 스트림 배치 시스템한 번에 하나의 작업만 실행한다.사용자는 컴퓨터와 직접 상호작용하지 않는다.작업은 일괄적으로 처리되며, 순차적으로 실행된다.작업 결과는 나중에 출력된다.시분할 시스템여러 사용자가 동시에 컴퓨터 자원을 공유할 수 있게 해주는 방식CPU 시간을 짧은 시간 단위로 나누어 여러 작업에 할당한다.사용자는 시스템과 상호작용할 수 있다.메모리 침범 이슈가 발생UNIXAT&T벨 연구소에서 탄생한 C언어 기반의 OS멀티 프로그래밍, 다중 사용자, 파일 시스템을 지원한 OSOS가 하는 일프로세스 관리프로세스를 관리하지 않는다면 여러 개의 프로그램들을 동시에 수행할 수 없다.메모리 관리모든 프로그램은 메모리에 올라가서 동작한다.H/W 관리사용자가 H/W에 대한 직접 접근을 막는다.File System 관리OS의 핵심 → Kernel커널은 프로세스와 메모리, 저장장치를 관리하는 핵심적인 기능을 담당한다.사용자는 OS의 커널에 직접 접근할 수 없고, Interface를 통해서 접근할 수 있다.Interface : GUI, CLIGUI(Graphic User Interface)Graphic을 통해서 사용자와 커널이 상호작용한다.CLI(Command Line Interface)Unix, Linux가 기본적으로 제공하는 인터페이스Text를 이용하여 사용자와 커널이 상호작용한다.System CallApplication이 커널과 상호작용하기 위한 인터페이스커널에서 제공하는 write()를 사용한다.→ OS가 저장장치의 빈 공간에 자동으로 저장한다.DriverH/W와 Kernel의 인터페이스각각의 H/W에 대한 프로그램을 커널이 전부 알고 있을 수 없음→ H/W 제조사에서 드라이버를 제작하여 커널에 제공한다.폰 노이만 구조현대 컴퓨터의 기본이 되는 중요한 아키텍처로, 그 단순성과 범용성으로 인해 여전히 널리 사용되고 있다.그 한계를 극복하기 위해 캐시 메모리, 병렬 처리 등 다양한 기술이 개발되어 적용되고 있다.CPU와 메모리를 Bus로 연결한다.Bus : 데이터를 전달하는 통로프로그램 내장 방식프로그램은 메모리에 올려서 실행된다.프로그램을 메모리에 내장했다고 하여 프로그램 내장 방식이라고 한다.주요 구성 요소중앙처리장치(CPU)메모리입출력 장치핵심 특징프로그램 내장 방식: 프로그램과 데이터를 동일한 메모리에 저장한다.순차적 처리: CPU가 메모리로부터 명령어를 순차적으로 읽어 실행한다.단일 버스 구조: CPU와 메모리 사이에 하나의 버스를 사용하여 데이터와 명령어를 전송한다.장점범용성: 하드웨어 변경 없이 소프트웨어만 교체하여 다양한 작업을 수행할 수 있음.편의성: 프로그램 변경이 용이하여 컴퓨터의 활용도를 크게 높임단점폰 노이만 병목 현상: 단일 버스 구조로 인해 CPU와 메모리 간의 데이터 전송에 병목 현상이 발생할 수 있다.순차 처리의 한계: 한 번에 하나의 명령어만 처리하므로 CPU 활용이 비효율적일 수 있다.최근의 컴퓨터 H/W메인보드다른 하드웨어를 연결하는 장치장치 간에 데이터를 전송하는 버스가 존재한다.CPUMemoryCPU(Central Processing Unit, 중앙 처리 장치) 구조Control Unit(제어 장치)모든 장치들의 동작을 지시하고 제어한다.ALU(Arithmetic and Logic Unit, 산술논리 연산장치)실제로 데이터 연산을 수행한다.Register프로그램 카운터메모리 주소 레지스터메모리 버퍼 레지스터명령어 레지스터CPU 내에서 계산을 위해 임시로 데이터를 저장한다.Memory 종류RAM(Random Access Memory)랜덤으로 데이터를 읽어도 저장된 위치와 상관 없이 동일한 읽는 속도를 갖는다.전력이 끊기면 데이터를 잃어버린다.메인 메모리로 사용된다.ROM(Read Only Memory)전력이 끊겨도 데이터를 보관할 수 있다.데이터를 한 번 쓰면 수정할 수 없다.BIOS를 저장하는데 주로 사용한다.Computer의 부팅 과정전원 인가ROM에 저장된 BIOS 실행BIOS가 컴퓨터에 연결된 장치들(CPU, RAM, 키보드, 마우스, 저장장치, etc...)에 이상이 없는지 체크한다.이상이 있으면 오류를 반환하면서 부팅이 이루어지지 않는다.H/W에 있는 마스터 부트 레코드에 저장된 부트로더를 메모리로 가져와서 실행시킨다.OS를 메모리로 올린다.CPU의 I/O 작업CPU는 입출력 작업이 들어오면 입출력 관리자에게 입출력 명령을 내린다.PollingCPU는 입출력 명령이 언제 완료될지 알 수 없기 때문에 입출력 관리자에게 주기적으로 신호를 보내어 종료 여부를 확인한다.→ 주기적으로 CPU가 확인해야 해서 성능이 좋지 않다.InterruptPolling 방식의 단점을 해결한 방식CPU가 입출력 관리자에게 명령을 내리고, CPU는 다른 작업을 수행한다.입출력 관리자는 입출력이 완료되었을 때 CPU에게 신호를 준다. CPU는 해당 신호를 받아서 ISR(인터럽트 서비스 루틴)을 실행시켜 작업을 완료한다.비동기적으로 동작하기 때문에 성능에 이점이 있다.ISR(Interrupt Service Routine)특정 인터럽트가 들어오면 해당 인터럽트를 처리하는 함수Interrupt의 종류H/W Interrupt외부 하드웨어 장치(키보드, 마우스, 타이머 등)에 의해 발생시스템 버스를 통해 CPU에 전달됨예기치 못한 상황에 대응하기 위해 사용S/W Interrupt사용자 프로그램에서 발생한 인터럽트프로그램 실행 중 특정 명령어에 의해 발생주로 시스템 콜(system call)을 구현하는 데 사용됨예외 처리나 오류 상황에 대응하기 위해 사용
