알고리즘

[알고리즘] Sliding Window 알고리즘

Sliding Window 일정한 크기의 박스(윈도우)를 유지하면서 이동하는 알고리즘 알고리즘 설명 연속된 3수의 최대값을 찾는다고 해보자. 1 ) 크기가 3인 박스를 만든다. 2 ) 한 칸씩 이동하면서 3수의 합을 계산한다. 알고리즘 구현 구현은 다음과 같다.(자바) int max = 0; for(int i = 0; i < 3; i++) { max += arr[i]; } int answer = max; for(int i = m; i < n - 3; i++) { max -= arr[i-m]; max += arr[i]; answer = Math.max(answer, max); }

[알고리즘] 소수 알고리즘(에스토스테네스 체)

에스토스테네스 체 -> 소수를 구할 때 사용하는 가장 최적화된 알고리즘이다. 알고리즘 설명 1 ) 먼저 일차원 배열을 하나 만든다. 2 ) Ch[i] == 0이면 ch[i] = 1로 바꾸고 ch[i]의 배수도 모두 1로 바꾼다. Ex ) i = 2일 때, ch[2] == 0이다. 따라서 값을 1로 바꾸고 2의 배수인 4,6,8,10,12,14도 1로 바꾼다. i = 3일 때, ch[3] == 0이다. 따라서 값을 1로 바꾸고 3의 배수인 6,9,12도 값을 1로 바꾼다. i = 4일 때, ch[4] == 1이다. 즉 소수가 아니다. 따라서 그냥 넘어간다. 구현 코드 구현은 다음과 같다.(자바) int cnt=0; int[] ch = new int[n+1]; for(int i=2; i

[운영체제] 스케줄링 알고리즘(2)

지난 포스팅의 선입 선처리 스케줄링과 최단 작업 우선스케줄링에 이어 나머지 스케줄링 알고리즘에 대하여 알아보려고 한다. [라운드 로빈 스케줄링] 라운드 로빈 스케줄링에서 모든 프로세스들은 똑같은 cpu 작업 시간을 할당 받는다(Time Quantum) n개의 프로세스, q의 작업 시간을 갖는다고 하면 각 프로세스는 1/n의 cpu 작업 시간을 할당 받고 (n-1)q 이상 기다리지 않는다. 이 경우에 만약 한 프로세스가 q시간에 작업을 끝내지 못내도 다음 프로세스로 전환된다. 여기서 발생할 수 있는 문제점은 만약 q가 문맥 교환시간보다 작다면 overhead가 너무 커져버린다. 평균 대기 시간을 계산해보자. P1은 (10-4), P2는 4, P3는 7밀리초를 기다린다. 따라서 17 / 3 = 5.66 밀리..

[운영체제] 스케줄링 알고리즘

CPU 스케줄링은 준비 큐에 있는 어느 프로세스에 CPU 코어를 할당한 것인지를 결정한다. 이번에는 여러 가지 다른 CPU스케줄링 알고리즘들에 대하여 알아보자. [선입 선처리 스케줄링] CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당 받는 구조이다. 이 구조의 문제점은 평균 대기 시간이 대단히 길 수 있다는 점이다. 아래와 같은 경우를 생각해보자 프로세스 버스트 시간 P1 24 P2 3 P3 3 프로세스들이 P1,P2,P3순서로 도착하고 선입선출의 구조로 일처리가 된다고 하면 다음과 같은 결과를 얻는다. 프로세스 P1의 대기 시간은 0밀리초이며, 프로세스 P2는 24, P3는 27밀리초가 된다. 따라서 평균 대기 시간은 (0 + 24 + 27) / 3 = 17밀리초이다. 보통 CPU의 처리 속도는 ..