전체 글

동기식 입출력: I/O 요청 후 입출력 작업이 완료된 후에야 제어가 사용자 프로그램에 넘어감 구현 방법 1 입출력이 끝날 때까지 CPU 낭비 -> 매 시점 하나의 입출력만 일어날 수 있음 구현 방법 2 입출력 완료까지 해당 프로그램에게서 CPU 빼앗음 입출력 처리를 기다리는 줄에 그 프로그램을 줄 세움 다른 프로그램에게 CPU를 줌 비동기식 입출력: I/O 시작 후 입출력 작업이 끝나기 기다리지 않고 제어가 사용자 프로그램에 즉시 넘어감 두 경우 모두 I/O의 완료는 인터럽트로 알려줌 서로 다른 입출력 명령어 메모리에 접근하는 인스트럭션, I/O 수행 인스트럭션 따로 Memory Mapped I/O: 메모리에 접근하듯이 I/O 수행 저장장치 계층 구조 윗 계층일수록 빠르며, 가격이 높아 용량이 적다 pr..

CPU: 매 클럭마다 메모리에서 인스트럭션(기계어)을 차례로 읽어 실행하는 작업 반복 레지스터: 메모리보다 빠른 작은 정보 저장 공간 다음 인스트럭션의 주소를 담고 있음 mode bit: 실행중인 프로세스가 OS인지 사용자 프로그램인지 구분해준다 1 (사용자 모드): 사용자 프로그램 수행 -> 제한된 인스트럭션만 수행 가능 (보안) 0 (모니터 모드): OS 코드 수행 (=커널모드) -> I/O 관련된 인스트럭션까지 모두 수행 가능 interrupt line: CPU는 매 인스트럭션을 읽기 전에 interrupt line이 세팅되어 interrupt될 사항이 있는지 체크한다 CPU에 인터럽트가 걸리면 실행중인 프로그램에서 OS로 CPU 제어권이 넘어간다 프로그램 실행 중에 I/O 장치의 관여가 필요하다면..

운영체제: 컴퓨터 하드웨어 바로 위에 설치되어 사용자 및 다른 모든 소프트웨어와 하드웨어를 연결하는 소프트웨어 계층 좁은 의미(커널): 운영체제의 핵심 부분으로 메모리에 상주하는 부분 넓은 의미: 커널 뿐 아니라 각종 주변 시스템 유틸리티(ex. 파일 복사 프로그램)를 포함한 개념 운영체제의 목적 컴퓨터 시스템의 자원(하드웨어 + 소프트웨어)을 효율적으로 관리 (효율성 + 형평성) & 사용자/운영체제 보호 컴퓨터 시스템을 편리하게 사용할 수 있는 환경 제공 동시 사용자/프로그램들이 각각 독자적인 컴퓨터에서 수행되는 것 같은 경험 제공 하드웨어를 직접 다루는 복잡한 부분 대행 운영체제의 분류 동시 작업 가능 여부 단일 작업(single tasking) 예)MS-DOS 다중 작업(multi tasking) ..

해시 테이블(해시 맵): 키를 값(해시)에 매핑할 수 있는 구조인, 연관 배열 ADT를 구현하는 자료구조 대부분의 연산이 분할 상환 분석에 따라 시간 복잡도가 O(1) 해시 함수: 임의 크기 데이터를 고정 크기 값(해시)으로 매핑하는 데 사용할 수 있는 함수 해시 함수가 값을 매핑할 때 충돌을 최소화하는 것이 무엇보다 중요함 로드 팩터: 해시 테이블에 저장된 데이터 개수를 버킷의 개수로 나눈 것 해싱: 해시 테이블을 인덱싱하기 위해 해시 함수를 사용하는 것 개별 체이닝: 충돌 발생 시 연결리스트로 연결 오픈 어드레싱: 충돌 방생 시 탐사를 통해 빈 공간을 찾는 방식 전체 슬롯 개수 이상 저장 불가, 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장이 없음 데이터들이 고르지 않고 뭉치는 ..

운영체제의 기능 CPU 스케쥴링 대부분의 프로그램은 CPU(기계어 실행) ↔ 입출력 디바이스(디스크, 키보드, 프린터, 모니터 등) 과정 반복 실행 FCFS(First Come First Served): 어떤 프로세스가 먼저 왔냐에 따라 평균 대기 시간이 비효율적 SJF(Shortest Job First): CPU 사용시간이 가장 짧은 프로세스 순으로 스케쥴 -> 최소 평균 대기 시간 보장 Starvation(기아 현상) 발생 가능: 이론적으로 영원히 CPU를 사용하지 못하는 프로세스가 생길 수도 있다 RR(Round Robin): 각 프로세스에 동일한 CPU 사용시간 할당 할당 시간 종료 후 인터럽트(하드웨어 관여) 발생 -> CPU를 빼앗기고 CPU 큐의 맨 뒤에 줄을 섬 대기 시간이 프로세스의 CP..

운영체제(OS): 컴퓨터 하드웨어 바로 위에 설치되어 사용자 및 다른 모든 소프트웨어와 하드웨어를 연결하는 소프트웨어 계층 목표: 컴퓨터 시스템의 자원(CPU, 메모리, 입출력 장치 등)을 효율적으로 관리 (+형평성) 실행중인 프로그램들에게 짧은 시간씩 CPU를 번갈아가며 할당, 메모리 공간을 적절히 분배 동시 사용자/프로그램들이 각각 독자적인 컴퓨터에서 수행되는 듯한 경험 제공 하드웨어를 직접 다루는 복잡한 부분을 대행 출처: http://www.kocw.net/home/cview.do?lid=5a0205590631eece

- 데크 (double-ended queue): 양 쪽에서 삽입 및 삭제 가능 - ADT는 이중연결리스트로 구현 641. design circular deque - 이중 연결 리스트로 구현(빈 head, tail) * 배열은 첫 인덱스에 삽입 시 O(n) - 우선순위 큐: 특정 조건에 따른 우선순위가 가장 높은 순으로 추출 (ex. 최댓값 추출) -> 정렬 알고리즘으로 구현 가능 - 다익스트라 알고리즘이나 힙 자료구조와 관련이 깊음 23. merge k sorted lists - 파이썬 heapq 모듈 (최소 힙): 이진 트리 기반 1. 원소들이 정렬된 상태(키 기준)로 삽입, 삭제 2. 가장 작은 원소가 첫 인덱스에 위치 3. 모든 원소들은 자식 원소들보다 작거나 같게 위치 * 두번째로 작은 값 확인하..

- 스택: lifo, 큐: fifo - 파이썬 리스트는 스택과 큐의 모든 연산 수행 가능 - 그러나 성능을 고려한다면 큐는 데크를 사용해야 좋음 - 스택 ADT에서는 차곡차곡 쌓이지만, 실제 연결리스트로 구현 시 무작위로 배치되고 포인터로 처리 ※ 참고: 클래스의 메소드에서 self는 인스턴스 자체, 인스턴스로 메소드 호출하면 자동으로 인스턴스(self) 인자로 넣음 20. valid parentheses - 딕셔너리 활용 - 스택에 왼 괄호 쌓기 316. remove duplicate letters - 재귀(분리 가능하냐로 접근) - 스택에 문자 쌓으면서 비교 - collections.Counter() 739. daily temperatures * [0] * len(T) - 스택에 인덱스 쌓으면서 온도..

234. palindrome linked list - 리스트로 변환 - 데크 - 런너 * 다중할당: 동시에 일어남 21. merge two linked lists - 재귀 (함수 안에서 다시 함수 호출) - 괄호가 연산순위 제일 높음 206. reverse linked list - 재귀 - 반복 - 내 풀이: 런너 2. add two numbers - 연결 리스트 만들때 더미 노드 생성 필수 - 전가산기 응용 - divmod() * map() * functools 모듈(reduce 메소드) * operator 모듈(add, mul 메소드) ※ b가 a를 참조할 때, a가 가변객체인 경우(list, set, dict) b에서 값을 조작하면 두 객체 모두에게 적용 (불변객체인 경우 b는 더이상 a를 참조하지..

1. two sum - brute force - in - enumerate - 투포인터로는 인덱스 엉망 42. trapping rain water - 투포인터 - 스택(변곡점) 15. 3 sum - brute force (x) - 투포인터 ※ 투포인터는 주로 정렬된 배열을 대상으로 두개의 포인터가 좌우로 자유롭게 움직이며 풀이 561. array partition 1 - 오름차순 - 슬라이싱 238. product of array except self - 왼쪽 곱셈 결과 저장 후 오른쪽 곱셈 결과 차례로 곱하기 121. best time to buy and sell stock - brute force(x) - sys.maxsize, float('inf') - 저점과 현재값 차이 카운팅