with with

* 배열의 인덱스가 1부터 시작한다고 가정합니다. ([1] = 1번째 와 같이 이해하기 쉽도록) - 알고리즘 정의 주어진 배열을 정렬하는 알고리즘. 단, 정렬하는 방법이 Divide and Conqure 방식이다. 배열을 최대한 작게 쪼개고, 병합하는 과정에서 정렬하여 병합하는 방식이다. - Pseudocode public static void mergeSort (int n, keyType[] S) { if (n

- 정의 이전 두 항의 합이 다음항이 되는 수열이다. - Pseudocode // Iterative way public static int IterFib (int n) { index i; int[] f = new int[n+1]; if (n

* 배열의 인덱스가 1부터 시작한다고 가정합니다. ([1] = 1번째 와 같이 이해하기 쉽도록) - 알고리즘 정의 정렬이 된 배열에서 찾고자 하는 원소가 나올 때 까지 탐색하는 알고리즘. 탐색하는 방법은 low, high의 가운데, mid와 비교하여 찾고자 하는 값이 mid보다 크면 오른쪽, 작으면 왼쪽의 배열에서 다시 탐색한다. - Pseudocode // Iterative way public static index BinSearch (int n, keyType[] S, keyType x) { index location, low, high, mid; low = 1; high = n; location = 0; while (low

* 배열의 인덱스가 1부터 시작한다고 가정합니다. ([1] = 1번째 와 같이 이해하기 쉽도록) - 알고리즘 정의 찾고자 하는 원소가 나올 때 까지 인덱스의 처음부터 순차로 탐색하는 알고리즘. - Pseudocode public static index SeqSearch(int n, keyType[] S, keyType x) { index location = 1; while (location n) location = 0; return location; } 크기가 n인 배열 S에서 x를 찾는 알고리즘. location이 n보다 작거나 x를 발견하지 못할 경우 location을 1씩 증가하며 탐색 찾은 경우, 또는 배열의 끝까지 탐색한 경우 while문을 빠져나온다. 끝까지 탐색한 경우에는 location을 ..

재귀함수를 이용하여 구현된 알고리즘의 경우 시간 복잡도 함수를 구하다 보면 재귀식으로 이루어진 시간 복잡도 함수를 마주하게 된다. 이런 경우 재귀식을 일반식으로 수정해야 하는데, 그 방법을 알아보자. * 선형인 재귀식의 경우만을 다룹니다. - Homogeneous case f(n) = 0 인 형태의 식을 homogeneous라고 하는데, 이런 경우의 재귀식을 계산하는 법을 알아보자. 위 식을 생각해보자. tk 항으로 이루어진 재귀식이다. 이 경우 아래와 같은 특성 방정식(characteristic equation)으로 변환 가능하다. 여기서 두 가지 경우로 나뉘는데, (r-1)(r-2)(r-3) 처럼 중근을 갖지 않는 경우와 (r-1)(r-2)^2 처럼 중근을 갖는 경우로 나뉘게 된다. * 중근을 갖지 ..

Time complexity 시간 복잡도는 알고리즘이 수행되는 데 걸리는 시간을 의미하며, 시간 복잡도가 클 수록 알고리즘이 수행 되기까지 걸리는 시간이 길다는 것을 의미한다. 시간 복잡도를 계산하기 위해선 2개의 파라미터가 필요하다. - Input size 입력으로 들어온 값의 크기를 의미한다. 입력으로 들어온 값은 배열일 수도, 특정 값이나 문자열, 혹은 graph와 같이 vertices, edges가 들어올 수 있다. - Basic operation 알고리즘은 여러 줄의 코드로 이루어진다. 그 중 핵심이 되는 코드를 기본 연산으로 삼아서 시간 복잡도를 계산한다. 예로 들어 순차 탐색 알고리즘의 경우에는 배열의 특정 index와 찾고자 하는 값의 비교 연산이 이에 해당한다. 시간 복잡도 분석은 모든 ..

스케줄링의 개요 스케줄링은 크게 3단계로 나뉜다. 시스템의 부하를 고려하여 작업을 시작할지 말지, 즉, 시스템 내의 전체 작접 수를 조절하는 고수준 스케줄링 중지와 활성화로 활성화된 프로세스의 수를 조절하여 과부화를 막는 중간 수준 스케줄링 어떤 프로세스를 CPU에 할당하고 대기 상태로 보낼지 결정하는, 즉, 실제 스케줄링 작업을 수행하는 저수준 스케줄링으로 나뉜다. 이런 스케줄링의 목적은 다음과 같다. 공평성 모든 프로세스가 공평하게 CPU를 할당받도록 하기 위함 효율성 시스템 자원이 유휴시간 없이 사용되도록 하기 위함 안정성 우선순위를 사용하여 중요 프로세스가 먼저 작동하게 하거나, 시스템 자원을 점유하거나 파괴하려는 프로세스로 부터 자원을 보호하기 위함 확장성 프로세스가 증가해도 시스템이 안정적으로..

프로세스의 개요 프로그램이 실행을 위해 메모리에 올라온 동적인 상태를 프로세스라 한다. 이 때 프로그램은 프로세스 제어 블록(PCB)를 부여받아 운영체제에 의해 관리된다. 프로세스는 5가지의 상태를 가질 수 있다. 생성 상태 프로세스가 메모리에 올라와 실행 준비를 마친(PCB를 얻은) 상태 준비 상태 생성된 프로세스가 CPU를 얻을 때까지 대기하는 상태 실행 상태 CPU를 얻어 실제로 작업을 수행하는 상태 대기 상태 입출력 요청이 들어온 프로세스가 입출력이 완료될 때 까지 대기하는 상태 완료 상태 작업을 완료하여 PCB가 사라진 상태 dispatch: 준비 > 실행 timeout(interrupt): 실행 > 준비 block: 실행 > 대기 exit: 실행 > 완료 wakeup: 대기 > 준비 메모리가 ..