사진과 음악을 좋아하는 개발자 지망생의 블로그

1. 프로세스의 개념Program이 Memory에 적재되어 CPU에 의해 실행(연산)되는 것 ⇒ 프로세스 = 실행중인 프로그램   2. Multi-Process1) 정의2개 이상의 프로세스가 동시에 실행되는 것이때 프로세스들은 CPU와 메모리를 공유하게 되며 이를 자원 공유라 함‘동시에’라는 말은 동시성(Concurrency)과 병렬성(Parallelism) 두 가지를 의미함동시성(Concurrency)CPU core가 1개여러 process가 짧은 시간동안 번갈아 가면서 연산을 하게되는 시분할 시스템(time sharing system)으로 실행되는 것병렬성(Parallelism)CPU core가 여러개각각의 CPU core가 각각의 Process를 연산함으로써 Process가 동시에 실행되는 것  2..

1. 비교 모델에서의 정렬1) 비교모델이란?데이터 항목 간의 비교 연산만을 이용해 정렬을 수행하는 방식병합, 퀵, 힙 등 전통적인 정렬 알고리즘이 비교모델에 속함  2) 비교모델의 탐색과 정렬의 하한탐색 하한탐색의 경우 최악의 경우 $\log n$번의 비교가 필요함이유탐색 알고리즘은 이진 결정 트리(Binary Decision Tree)로 표현할 수 있음결정 트리의 각 내부 노드는 항목 간의 비교를 나타내며, 루트에서 리프까지의 경로는 탐색 과정임탐색 가능한 n개의 항목을 모두 포함하려면 트리의 최소 깊이는 $\log n$이 됨 정렬 하한정렬 문제는 최소 $n \log n$번의 비교가 필요함증명정렬된 배열의 경우의 수(모든 가능한 결과)는 $n!$(순열의 개수)임n!개의 리프를 포함하는 결정 트리의 최소..

1. 운영체제(Operating System)운영체제란?정의: 하드웨어와 사용자 및 각종 어플리케이션들을 연결해주는 소프트웨어 계층좁은 의미: 커널 – 운영체제의 핵심 부분으로, 전원 투입 시 메모리에 항상 상주넓은 의미: 커널을 포함한 다양한 시스템 유틸리티(메모리에 상주하지 않는 프로그램 포함)  운영체제의 역활운영체제 ↔ 하드웨어자원 관리성능을 최대화함과 동시에 사용자(또는 어플리케이션) 간 형평성을 고려하여 컴퓨터 시스템의 자원 관리자원하드웨어 자원: 프로세서, 기억장치, 입출력 장치소프트웨어 자원: 프로세스, 파일, 메시징성능만 추구하면 특별 소프트웨어 및 사용자가 차별받는 상황이 발생할 수 있음⇒ 형평성을 고려하여 컴퓨터 시스템의 자원 관리사용자 및 운영체제 자신의 보호편리한 사용자 환경 제공..

1. 선택 정렬(Selection Sort)정의각 단계에서 남은 부분 중 가장 작은 원소를 선택해, 해당 위치에 배치하는 정렬 알고리즘제자리 정렬(In-place Sort)로 추가 메모리 공간을 거의 사용하지 않고, 배열 내에서 정렬함안정 정렬이 아니기 때문에 동일한 값의 순서가 변경될 수 있음  시간 복잡도최악/최선/평균: $O(N²)$  정렬 단계가장 작은(또는 큰) 원소 선택배열에서 아직 정렬되지 않은 부분 중에서 가장 작은(또는 큰) 원소를 찾음가장 앞의 원소와 교환찾은 원소를 현재 정렬되지 않은 부분의 첫 번째 원소와 교환함다음 위치로 이동다음 위치로 이동하여 1~2단계를 반복전체 배열이 정렬될 때까지 반복배열이 모두 정렬될 때까지 위 과정을 반복  장점 및 단점장점알고리즘이 직관적이고 구현이 ..

1. 컴퓨터 시스템 구조1) 개요컴퓨터: CPU + 메모리메모리CPU의 작업 공간CPU는 매 순간 메모리에서 기계어(instructions)를 읽어서 실행하게 됨I/O Deviceinput: 데이터가 컴퓨터가 들어가는 것 → 마우스, 키보드 등output: 컴퓨터에서 데이터를 처리 후 외부로 내보내는 것 → 디스플레이, 프린터, 스피커 등  2) 상세Mode Bit사용자 프로그램의 잘못된 수행으로 다른 프로그램 및 운영체제에 피해가 가지 않도록 하기 위한 보호 비트Mode bit을 통해 하드웨어적으로 두 가지 모드 operation 지원1: 사용자 모드, 사용자 프로그램 수행0: 모니터 모드(= 커널 모드, 시스템 모드), OS코드 수행보안을 해칠 수 있는 중요한 명령어는 모니터 모드에서만 수행 가능한 ..

1. 스택(Stack)시간 순서상 가장 최근에 추가한 데이터가 가장 먼저 출력되는 후입선출(LIFO, Last In First Out) 형식으로 데이터를 다루는 자료구조데이터를 추가하는 것을 push, 데이터를 꺼내는 것을 pop이라고 한다활용 예시: 후위 표기법 연산, 괄호 유효성 검사, 웹 브라우저 방문기록(뒤로 가기), 깊이우선탐색(DFS)  1) 리스트(list) 기반 구현python에서 stack을 가장 간단히 구현하는 방법은 list를 이용하는 것이다.append 메소드를 사용하면 맨 뒤에 데이터가 추가 되고, pop을 하게 되면, 맨 앞의 데이터가 나온다시간복잡도: $O(1)$# stack 선언s = []# push - O(1)s.append(1) # [1]s.append(2) # [1, 2..

1. 투 포인터 기법1) 개요두 개의 포인터(slow, fast)를 이용하여 연결 리스트의 사이클을 탐지하는 방법slow 포인터는 한 번에 1칸씩 이동하고, fast포인터는 한 번에 2칸씩 이동  2) 사이클이 없는 경우만약 연결 리스트에 사이클이 없는 경우, fast포인터는 리스트의 끝(None)에 도달함예를 들어, A -> B -> C -> D -> None의 리스트에서, fast 포인터는 한 번에 두 칸씩 이동하면서 끝에 도달함slow 포인터: A -> B -> C -> Dfast 포인터: A -> C -> None  3) 사이클이 있는 경우사이클이 있을 경우, fast 포인터가 slow포인터를 따라잡고 만나게 되는 지점이 생김마치 원이 있는 트랙에서 두 사람이 달릴 때, 빠르게 달리는 사람이 결국..

1. Array미리 할당된 공간에 연관된 데이터를 연속적이며 순차적으로 저장하는 자료구조1) 정적 배열(Static Array)미리 할당된 크기를 가지며 연속적으로 순차적으로 데이터를 저장하는 자료구조특징고정된 크기를 갖는다저장 공간을 미리 확보해야 한다메모리 상에 데이터가 서로 인접한(연속적인) 메모리 위치에 저장된다 → 논리적 저장 순서와 물리적 저장 순서가 같다시간 복잡도삽입과 삭제 → 삽입 및 삭제로 인해 데이터들이 한칸 씩 움직여야 하기 때문에 $O(N)$을 갖음탐색메모리 시작 주소에 + N 만 하면 되기 때문(랜덤 접근, Random Accesss)에 시간 복잡도 $O(1)$을 갖음Random Access(Direct Access)데이터 접근 시, 어떤 순서로든, 어느 위치에 있는 데이터라도 ..