Legacy/Algorithm
-
캐시알고리즘 - LRU(Least-recently-used) Page ReplacementLegacy/Algorithm 2015. 4. 29. 14:33
출처 - http://egloos.zum.com/judoboyjin/v/4545185 LRU(Least-recently-used) Page Replacement 앞에서 언급한 최상의 OPT알고리즘이 실현 불가능하기 때문에 차선책으로 고안해낸것이 바로 이 알고리즘이다. Optimal 알고리즘이 앞으로 가장 적게 사용될것을 선택하는 것과는 달리 이 알고리즘은 과거에 가장 오랫동안 사용되지 않은 것을 선택하게 된다. 예) 다음의 reference string과 3 frames이 있다고 가정하고, Page fault를 체크해보자. 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 최초의 7 0 1 이 프레임에 들어가고 2가 프레임에 들어가기 위해서 7을 victim으로 선택하게 된다. 7 ..
-
소수 구하기 최적의 알고리즘(2)Legacy/Algorithm 2015. 4. 22. 03:56
출처 - http://marobiana.tistory.com/91 소수 구하기 최적의 알고리즘 1편에서 (http://marobiana.tistory.com/89) 주어진 수보다 작은 수의 소수들로 나누는게 성능이 좋다고 했었는데,그것보다 더 좋은 알고리즘을 찾아냈다.ㅋㅋ이것보다 더 좋은 방법은 아마도 없을 것이라 자신함 !! 만약 있다면 댓글 달아주시기 바람. 요번에는 c++로 구현해보았음. 1. 알고리즘 에라토스테네스의 체 (Sieve of Eratosthenes)라는 알고리즘이다.아래 그림을 보면 무엇인지 알 수 있다. 120까지의 모든 소수를 구한다고 해보자. 2부터 120까지 배열에 모두 넣은 후소수가 아닌 것들을 모두 체크해버리는 것이다. 2를 제외한 모든 2의 배수를 체크한다.3을 제외한 모..
-
소수 구하기 최적의 알고리즘(1)Legacy/Algorithm 2015. 4. 22. 03:55
출처 - http://marobiana.tistory.com/89 한달 전에 면접에서 소수를 손코딩하라는 명을 받았다. (인성면접이라는 훼이크에 당해버렸음 @_@) 소수에 대해서는 깊이 생각해본적이 없었는데..이번일을 계기로 더더욱 최적의 방법을 생각하는 버릇을 들이겠다는 다짐을 하게되었다. 1. 소수(Prime Number)란 무엇인가? 2, 3, 5, 7, 11, 13, 17.... 약수가 1과 자기 자신 뿐인 수이다. 2. 소수를 어떻게 구할까? (알고리즘) 약수가 1과 자신뿐인 것을 확인해야한다. 그러려면??? 즉, 자기 자신보다 작은 수들을 나누어봐서, 하나라도 나누어지면 소수가 아닌 것이다.(어떤 수의 배수이면 안된다는 것) 보통은 여기까지만 생각하고 코딩을 시작할 것이다.그런데 조금만 더 생..