이진 탐색(Binary Search) 이진 탐색 혹은 이분 탐색이라고 부른다. 이미 정렬되어 있는 자료 구조에서 특정 값을 찾을 때, 탐색 범위를 절반씩 나눠가면서 해당 값을 찾아가는 것이다. 즉, 탐색 범위를 두 부분으로 분할하면서 찾는 방식이다. 처음부터 끝까지 돌면서 탐색하는 것보다 훨씬 빠르다는 장점을 가지고 있다. 시간 ...

운영체제의 개요 운영체제와 정보 기술의 원리라는 책을 읽고 정리한 내용입니다. 1장을 정리했습니다. 내용은 전반적으로 얕게 설명되어 있는 장입니다. 운영체제란? 운영체제(Operating System 이하 OS)란 컴퓨터 하드웨어 바로 윗단에 설치되는 소프트웨어를 말한다. 컴퓨터를 구성하는 요소 중 운영체제의 위상은 아래와 같다. OS 자...

우선순위 큐(Priority Queue) 일반적인 큐는 먼저 들어간 데이터가 먼저 나오는 구조이다. 이런 큐의 특성과 달리 우선순위 큐(Priority Queue)는 들어간 순서에 상관없이 일정한 규칙에 따라 우선순위를 선정하고 우선순위가 가장 높은 데이터가 가장 먼저 나오게 된다. 대표적인 예로는 병원의 응급 환자를 생각할 수 있으며, 은행의 업무...

시스템 콜(System Call) 먼저, 커널 모드와 사용자 모드에 대해서 알아보자. 1) 커널 모드 프로그램 카운터가 운영체제가 존재하는 부분을 가리키고 있다면, 현재 운영체제의 코드를 수행 중이며 CPU가 커널 모드에서 수행 중이라고 한다. 2) 사용자 모드 프로그램 카운터가 사용자 프로그램이 존재하는 메모리 위치를 가리킬 경우, 사용자 ...

스케줄러(Scheduler) 스케줄링 알고리즘을 알기 전에 스케줄러에 대해 알아보자 프로세스들은 자신이 종료될 때까지 수많은 큐들을 돌아다닌다. OS는 이 큐 안에 있는 프로세스 중 하나를 선택해야 하며, 이러한 일을 스케줄러(Scheduler)가 담당한다. 작업 큐(Job Queue) : 현재 시스템 내의 모든 프로세스의 집합 준비...

순열과 조합 순열 : 순서를 고려하여 뽑는다. 조합 : 순서와 상관없이 뽑는다. 순열 n,r을 입력으로 받아서 n개 중에서 r개를 뽑는 순열을 만들어보자. LinkedList와 boolean[] check 배열을 사용한다. [Code] import java.io.BufferedReader; import java.io.IOExcep...

순열 구하기 프로그래머스의 문제 중 [소수 찾기] 라는 문제를 풀다가 순열 알고리즘이 나와서 정리한 내용이다. 1,2,3와 같은 숫자들이 있다. 이것을 중복하지 않고 순서를 끌어내보자. 1,2,3 1,3,2 2,1,3 2,3,1 3,1,2 3,2,1 위와 같이 여섯가지의 방법이 존재한다. 1,2,3,4의 경우에는 그 숫자가 훨씬 많아...

선택 정렬(Selection Sort) 정렬 알고리즘은 다음과 같이 나눠볼 수 있다. 단순하지만 비효율적인 방법 : 선택 정렬, 삽입 정렬, 버블 정렬 복잡하지만 조금 더 효율적인 방법 : 퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬 그 중에서 이번에는 선택 정렬에 대해 알아보려 한다. 개념 해당 순서에 원소를 넣을 위치는 이...

삽입 정렬(Insertion Sort) 개념 손 안의 카드를 정렬하는 방법과 유사하다. 새로운 카드를 기존의 정렬된 카드 사이에 올바른 자리를 찾아 삽입한다. 2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘이다. 최선의 경우, ...

병합 정렬(Merge Sort) 합병 정렬이라고도 부르며, 분할 정복 방법을 통해 구현한다. 개념 빠른 정렬로 분류되며, Quick Sort와 함께 많이 언급되는 정렬 방식이다. Quick Sort와는 반대로 안정 정렬에 속한다. 시간복잡도 평균 최선 최악 ...