면접 스터디 썸네일형 리스트형 원형 큐 선형 큐의 문제점 - rear가 배열의 마지막 위치에 있을때 앞에 빈자리가 있는 경우에도 포화 상태로 인식하고 삽입 연산을 하지 않는다. 큐의 빈자리를 사용하려면 앞으로 이동시켜 위치를 조정시켜야 하는데 복잡하여 큐의 효율성을 떨어뜨린다. 이런 문제를 해결하기 위해 원형 큐(Circular Queue)를 사용한다. 초기 공백 상태일때는 front와 rear 값이 0이 되고, 공백 상태와 포화 상태를 쉽게 구분하기 위해서 자리 하나를 항상 비워둠. 원형큐의 공백 조건 상태는 front=rear가 된다 rear는 앞으로 이동하면서 원소를 삽입하고 front는 rear가 이동한 방향으로 따라가면서 원소를 삭제 배열의 인덱스가 n-1 다음에 다시 0이 되어야 하므로 사용할 다음 인덱스를 정하기 위해서 나머지 연.. 더보기 Queue는 무엇인가? - Queue는 '선입선출(first-in fisrt out) 자료구조를 구현한 자바 인터페이스이다. - java.util에서 제공 http://www.jroller.com/VelkaVrana/resource/java16collections/queues090524-final.png http://www.jroller.com/velkaVrana/entry/java_1_6_collections_class - Iterable과 Collection의 기능을 가지고 있다는게 Queue의 특징 - Queue의 기능을 활용한 클래스 중 대표적인 클래스로 LinkedList가 있음 @Test public void queueInsertion() { Queue queue = new LinkedList(); queue.add.. 더보기 리스트 - 리스트는 특정 타입 값들이 순차적으로 정렬된 컬렉션이다. 자바에서는 LinkedList나 ArrayList 클래스를 일반적으로 사용 - 어떤 경우에는 LinkedList보다 ArrayList가 더 적합하며 반대일 수 도있다. - 사용하기 전에 리스트는 애플리케이션의 성능이나 메모리 사용량과 밀접한 관계가 있기 때문에 반드시 고민을 해봐야 한다. - 리스트를 사용하려면 메서드와 생성자 매개변수는 필드 정의로 List 인터페이스를 사용함. 배열과 리스트의 관계 public void arrayDefinitions() { int[] interger = new int[3]; boolean[] bools = {false, true, true, false}; String[] strings = new String[.. 더보기 이진 검색 public static boolean binarySearch(List numbers, Integer value) { if (numbers == null ||numbers.isEmpty()) { return false; } Integer comparison = numbers.get(numbers.size() /2); if (value.equals(comparison)) { return true; } if (value < comparison) { return binarySearch(numbers.subList(0, numbers.size() / 2), value); } else { return binarySearch(numbers.subList(numbers.size() /2 + 1, numbers.siz.. 더보기 병합정렬 알고리즘 public static List mergesort(List values) { if (values.size() < 2) { return values; } List leftHalf = values.subList(0, values.size() /2); List rightHalf = values.subList(values.size() / 2, values.size()); return merge(mergesort(leftHalf), mergesort(rightHalf)); } private static List merge(List left, List right) { int leftPtr = 0; int rightPtr = 0; List merged = new ArrayList(left.size() + right.. 더보기 퀵 정렬 알고리즘 public static List quickSort(List numbers) { if (numbers.size() < 2) { return numbers; } Integer pivot = numbers.get(0); List lower = new ArrayList(); List higher = new ArrayList(); for(int i=1; i < numbers.size(); i++) { if (numbers.get(i) < pivot) { lower.add(numbers.get(i)); } else { higher.add(numbers.get(i)); } } List sorted = quickSort(lower); sorted.add(pivot); sorted.addAll(quickSort(hig.. 더보기 삽입 정렬 알고리즘 public static List insertSort(List numbers) { List sortedList = new LinkedList(); originalList: for (Integer number : numbers) { for(int i=0; i < sortedList.size(); i++) { if (number < sortedList.get(i)) { sortedList.add(i, number); continue originalList; } } sortedList.add(sortedList.size(), number); } return sortedList; } - 삽입 정렬은 새로운 리스트를 생성하고 해당 리스트를 반환 - ArrayList 클래스를 사용 했다면 중간에 원소를 추가할 경우.. 더보기 버블정렬 알고리즘 - 인접한 두 수를 비교해서 큰 수 (작은 수)를 뒤로 보내는 알고리즘 public class BubbleSort { public static void main(String[] args) { int[] index = {8, 4, 7, 3, 1, 6, 5, 2}; int i, j, temp; for(i = 0; i index[j + 1]) { temp = index[j]; index[j] = index[j + 1]; index[j + 1] = temp; } } } for (i = 0; i < index.length; i++) { System.out.pr.. 더보기 리스트 정렬하기 - 자바는 정렬을 돕기 위해 Comparable과 Comparator라는 두 가지 인터페이스를 제공 Comparable과 Comparator 인터페이스 차이는 무었인가? - 두 인터페이스 모두 public으로 접근 변경자로 선언하기 때문에 모든 용도의 자료를 담을 수 있다. - Comparable 인터페이스는 자연스러운 순서로 정렬할 때 사용하고, Comparator는 원하는 대로 정렬 순서를 지정하고 싶은 곳에 사용 Comparable Interface - 객체들 사이의 오름차순, 내림차순 등 일반적인 순서를 결정할 때 사용 - CompareTo 메소드가 있음 Prameter Comparable Comparator Sorting logic 소팅 로직은 어떤 오브젝트를 정렬하려면 같은 클래스에 있어야 한.. 더보기 리스트 정렬하기 - 자바는 정렬을 돕기 위해 Comparable과 Comparator라는 두 가지 인터페이스를 제공 Comparable과 Comparator 인터페이스 차이는 무었인가? - 두 인터페이스 모두 public으로 접근 변경자로 선언하기 때문에 모든 용도의 자료를 담을 수 있다. - Comparable 인터페이스는 자연스러운 순서로 정렬할 때 사용하고, Comparator는 원하는 대로 정렬 순서를 지정하고 싶은 곳에 사용 Comparable Interface - 객체들 사이의 오름차순, 내림차순 등 일반적인 순서를 결정할 때 사용 - CompareTo 메소드가 있음 참고 사이트 - http://www.nextree.co.kr/p11101/ 더보기 이전 1 2 3 다음 목록 더보기
