알고리즘

페이지 부재 프로세스 실행 시 참조할 페이지가 주기억장치에 없는 현상 페이지 부재 빈도(PFF;Page Fault Frequency)는 페이지 부재가 일어나는 횟수를 의미 페이지 부재 빈도 방식 페이지 부재율(Page Fault Rate)에 따라 주기억장치에 있는 페이지 프레임의 수를 늘리거나 줄여 페이지 부재율을 적정 수준으로 유지하는 방식 페이지 교체 알고리즘 페이지 부재가 발생했을 때 가상 기억장치의 필요한 페이지를 주기억장치에 적재해야 하는데, 이때 주기억장치의 모든 페이지 프레임이 사용중이면 어떤 페이지 프레임을 교체할지 결정하는 기법 OPT (OPTimal Replacement, 최적교체) 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 기법 (실현 가능성이 희박하다) FIFO (Firs..

알고리즘 분석어떤 응용 프로그램에 어느 클래스가 더 좋을지 결정하는 한 가지 방법은 둘 다 시도해보고 각각 얼마나 걸리는지 알아보는 것인데, 이러한 접근법을 프로파일링(profiling)이라고 하는데 여기에는 몇 가지 문제점이 존재한다. 알고리즘을 비교하려면 사전에 그것을 모두 구현해봐야 한다. 결과는 사용하는 컴퓨터 성능에 의존한다. 결과는 문제 크기나 입력으로 사용하는 데이터에 의존하기도 한다. 알고리즘 분석(analysis of algorithm)을 사용하여 이러한 문제점을 해결할 수 있다. 알고리즘 분석은 그것을 구현하지 않고도 알고리즘을 비교할 수있도록 하는데 몇 가지 가정을 해야만 한다. 알고리즘을 이루는 더하기와 곱하기, 숫자 비교 등의 기본 연산을 식별한다. 그리고 각 알고리즘에 필요한 연..

팩토리얼(Factorial) 구하기재귀적 방법을 사용하지 않는 팩토리얼 구현을 작성하라. Factorial(n) = 1 * Factorial(n-1);재귀 팩토리얼12345public long recursiveFactorial(int n) { if(n

FizzBuzz문제 구현하기 1에서 n까지의 숫자를 출력하되 3의 배수는 Fizz라는 문자열을 출력하고, 5의 배수는 Buzz라는 문자열을 출력하고 15의 배수는 FizzBuzz라는 문자열을 출력하는 알고리즘을 작성하라. 12345678910111213141516public static List fizzBuzz(final int n){ List result = new ArrayList(n); for(int i=0; i

이진탐색(Binary Search)효율적인 검색(탐색)기법인 이진탐색에 대해 알아보겠습니다.탐색시 리스트가 정렬되어 있지 않으면 리스트 검색 시 주어진 값을 찾기위해 모두를 찾아봐야한다는 단점이 있습니다. 하지만 정렬된 리스트가 있거나 검색전에 정렬을 수행한 경우 이진 탐색(binary Search)을 사용하면 매우 효과적으로 원하는 값을 얻을 수 있습니다. => 이진탐색은 원소를 일일이 비교하지 않고도 주어진 원소를 찾을 수 있으며, 백만 개의 원소가 있어도 20번 미만의 비교로 주어진 원소를 찾을 수 있습니다. O(logn) 12345678910111213141516171819202122package algorithm; import java.util.List; public class BinarySea..

병합정렬, 합병정렬(Merge Sort)분할정복(divide-and-conquer)의 한 종류인 합병정렬에 대해 알아보겠습니다.컨셉은 리스트를 두개로 나누고 각 하위 리스트를 정렬 후 하나로 합치는 방법입니다.설명보다 그림을 보는게 이해가 더 빠를 듯 싶어서 이해가 쉽게될 만한 그림을 가져왔습니다. (그림 출처 : http://blog.naver.com/k97b1114/140163896337) 병합 정렬의 성능은 O(nlogn)이고 각각의 병합시간은 O(n)이며 각 재귀 호출은 주어진 리스트 숫자의 절반만큼만 발생합니다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647package sort; impo..

#9 정수 배열(int array)이 주어지면 0이 아닌 정수 순서를 유지하며 모든 0을 배열 오른쪽 끝으로 옮기시오. 단, 시간복잡도는 O(n), 공간복잡도는 O(1)여야 합니다. 예제)Input: [0, 5, 0, 3, -1]Output: [5, 3, -1, 0, 0] Input: [3, 0, 3]Output: [3, 3, 0] 0을 오른쪽으로 옮기는 문제이다. 일단, 0이 아닌 수가 들어갈 index를 저장해 둔다.(배열 첫번째인 0부터 시작) 그 후 for문을 돌면서 0이 아닌 숫자가 나오면 해당 index의 숫자와 0이 아닌 숫자와 교환 후 index를 증가시킨다.(숫자가 0일 때는 index를 증가시키지 않아, index가 0의 위치를 가리키게 한다.) 1234567891011121314151..

#8 정수 배열(int array)이 주어지면 두번째로 큰 값을 프린트하시오. 예제)Input: [10, 5, 4, 3, -1]Output: 5 Input: [3, 3, 3]Output: Does not exist. for문을 한번 사용해서 풀어야 한다. 2번 째로 큰 수가 존재하지 않는 경우는 2가지가 존재한다. 원소가 2개가 안될 경우와 모든 원소가 같을 경우이다. 이 부분만 잘 처리를 해주면 쉽게 풀어갈 수 있다. 1234567891011121314151617181920212223public static int solution(int[] array) { if(array.length

퀵정렬(Quick Sort) 정렬 알고리즘 중 가장 효율적이고 빠른방식 입니다. 동작방식(아이디어)은 아래와 같습니다. 1. 기준점이 되는 pivot을 구한다. 2. pivot을 기준으로 left(pviot보다 작은 값) 리스트와 right(pivot 보다 큰 값)리스트를 구합니다. 3. 나눠진 left와 right 리스트를 정렬이될 때까지 분할처리 합니다. => 재귀사용(자기자신을 호출) (설명 및 그림참고 : 네이버 지식백과(퀵정렬)) 퀵정렬은 버블 정렬이나 삽입 정렬보다 훨씬 더 효율적인 성능을 발휘합니다. 퀵정렬의 평균 시간복잡도는 O(nlogn)이며, 최악의 경우에는 여전히 O(n^2)의 시간복잡도를 갖습니다. 이 성능차이는 pivot의 선택에 따라 좌우되게 되는데, 아래코드와 같이 가장앞에 있..

#7 주어진 string 에 모든 단어를 거꾸로 하시오. 예제)Input: “abc 123 apple”Output: “cba 321 elppa” Input의 문자열을 문자단위로 나눈 후, 각 단어를 거꾸로 만들어서 새로운 문자열에 추가하면 쉽게 풀 수 있다.코딩테스트시 제공되는 편리한 API(함수) 사용이 제한이 될 수 있다하여, split와 문자열을 거꾸로 출력하는 reverse를 별도로 구현하여 만들었다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152package everyProgramming; import java.util.ArrayList; public class Ch07 ..