#자바#JAVA#알고리즘#DoIt#기본 알고리즘# 썸네일형 리스트형 [자바 Do It! 알고리즘]Chapter04 스택과 큐(큐) [큐] 1. 스택과 마찬가지로 데이터를 일시적으로 쌓아 두기 위한 자료구조입니다. 2. 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO; First In First Out)인 점이 스택과 다릅니다. 3. 큐에 데이터를 넣는 작업을 인큐(enqueue) 라고 하고 데이터를 꺼내는 작업을 디큐(dequeue) 라고 하고 데이터를 꺼내는 쪽을 프런트(front) 데이터를 넣는 쪽을 리어(rear) 라고 합니다. 4. 큐를 배열로 디큐흐면 que[0]에 저장된 값을 꺼낸 다음 두 번째 이후의 요소를 모두 맨앞으로 옮겨야 합니다. 이 처리의 복잡도는 O(n)이며 데이터를 꺼낼 때마다 이런 처리를 하게 되면 효율이 떨어집니다. 그래서 링 버퍼로 만듭니다. [링 버퍼(ring buffer)로 큐 만들.. 더보기 [자바 Do It! 알고리즘]Chapter04 스택과 큐(스택)(2) ☞ 검색 메서드 indexOf 스택 본체의 배열 stk에 x와 같은 값의 데잉터가 포함되어 있는지, 포함되어 있다면 배열의 어디에 들어있는지를 조사하는 메서드입니다. 검색은 꼭대기 쪽에서 바닥 쪽으로 선형 검색을 수행합니다.(먼저 팝이 되는 데이터를 찾기 위해서) 즉, 배열 인덱스가 큰 쪽에서 작은 쪽으로 스캔합니다. 검색에 성공하면 찾아낸 요소의 인덱스를 반환하고, 실패하면 -1을 반환합니다. ☞ 스택의 모든 요소를 삭제하는 메서드 clear clear 메서드는 스택에 쌓여 있는 모든 데이터를 삭제하는 메서드입니다. ※ 스택에 대한 푸시와 팝 등 모든 작업은 스택 포인터를 바탕으로 이루어집니다. 따라서 스택의 배열 요솟갑승ㄹ 변경할 필요가 없습니다. 모든 요소의 삭제는 스택 포인터 ptr 값을 0으.. 더보기 [자바 Do It! 알고리즘]Chapter04 스택과 큐(스택) [스택] 1. 스택은 데이터를 일시적으로 저장하기 위한 자료구조로 , 가장 나중에 넣은 데이터를 가장 먼저 꺼냅니다. ( LIFO, Last In First Out, 후입선출) 2. 스택에 데이터를 넣는 작업을 푸시 (push) 라 하고, 스택에서 데이터를 꺼내는 작업을 팝 (pop) 이라 합니다. 3. 푸시와 팝을 하는 위치를 꼭대기 (top) 라 하고, 스택의 가장 아랫부분을 바닥 (bottom) 이라 합니다. 4. Java 프로그램에서 메서드를 호출하고 실행할 때 프로그램 내부에서는 스택을 사용합니다. ☞ 스택 본체용 배열 : stk 푸시된 데이터를 저장하는 스택 본체의 배열입니다. 인덱스 0인 요소가 스택의 바닥(bottom)입니다. 가장 먼저 푸시된 데이터를 저장하는 곳은 stk[0] 입.. 더보기 [자바 Do It! 알고리즘]Chapter03 검색 알고리즘(자연정렬X 배열검색) [자연 정렬로 정렬되지 않은 배열에서 검색하기] 1. 자연 정렬로 정렬되지 않은 배열에서의 검색은 제너릭 메서드(generic method)로 하면 됩니다. 2. 제너릭 메서드의 첫 번째 매개변수 a 는 검색 대상입니다. 3. 제너릭 메서드의 두 밴째 매개변수 key 는 키 값입니다. 즉, 매개변수로 전달하는 자료형은 Integer, String, 신체검사 데이터용 클래스 PhyscData 등 어떤 것을 전달해도 좋습니다. 4. 하지만 배열의 요소가 어떤 순서로 줄지어 있는지, 각 요소의 대소 관계를 어떻게 판단할 것인지에 대해서는 binarySearch 메서드에 알려주어야 합니다. 이 정보는 세 번째 매개변수 c에 전달합니다. 5. 세 번째 매개변수 c 에는 comparator를 전달합니다. compa.. 더보기 [자바 Do It! 알고리즘]Chapter03 검색 알고리즘(객체배열 검색, 자연정렬 배열 검색) [객체의 배열에서 검색하기] static int binarySearch(Object[] a, Object key) 1. 자연정렬이라는 방법으로 요소의 대소 관계를 판단합니다. 따라서 정수 배열, 문자열 배열에서 검색할 때 적당합니다. static int binarySearch(T[] a, T key, Comparator 더보기 [자바 Do It! 알고리즘]Chapter03 검색 알고리즘(Arrays.binarySerach에 의한 이진 검색, 클래스 메서드와 인스턴스 메서드) 에 의한 이진검색 1. Java는 배열에서 이진 검색을 하는 메서드를 표준 라이브러리로 제공합니다. 2. 이진 검색 표준 라이브러리의 메서드로는 java.util.Arrays 클래스의 binarySearch 메서드가 있습니다. 3. binarySearch의 메서드는 다음과 같은 장점이 있습니다 1) 이진 검색 메서드를 직접 코딩할 필요가 없다. 2) 모든 자료형 배열에서 검색할 수 있다. ※ API 문서를 참조하면 더 자세히 알 수 있습니다. 4. 각 경우에 따른 인덱스 반환값 1) 검색에 성공한 경우 (1) key와 일치하는 요소의 인덱스를 반환합니다. (2) 일치하는 요소가 여러 개 있다면 무작위의 인덱스를 반환합니다. 2) 검색에 실패한 경우 (1) 반환값은 삽입 포인트를 x라고 할 때 -x -1을.. 더보기 [자바 Do It! 알고리즘]Chapter03 검색 알고리즘(복잡도-선형검색, 이진검색) 1. 프로그램의 실행속도는 프로그램이 동작하는 하드웨어나 컴파일러 등의 조건에 따라 달라집니다. 2. 알고리즘의 성능을 객관적으로 평가하는 기준을 복잡도(Complexity)라고 합니다. 3. 복잡도는 아래의 두 가지 요소를 가지고 있습니다. 1) 시간 복잡도(time Complexity) : 실행에 필요한 시간을 평가한 것 2) 공간 복잡도(space complexity) : 기억 영역과 파일 공간이 얼마나 필요한 가를 평가한 것 단계 코드 실행 횟수 복잡도 1 int i = 0; 1 O(1) 2 while(i 더보기 [자바 Do It! 알고리즘]Chapter03 검색 알고리즘(이진검색) 정말 어렵네요.. 솔직히 이해 잘안되고 안보고 코드 못칩니다 ㅎ... [이진검색] 1. 이진검색 알고리즘을 적용하는 전제조건은 데이터가 키 값으로 이미 정렬(sort)되어 있다는 것입니다. 2. 요소가 오름차순 또는 내림차순으로 정렬되어 있어야 합니다. 3. 선형 검색보다 좀 더 빠르게 검색할 수 있습니다. 4. 이진 검색 알고리즘의 종료조건은 아래 조건 중 하나만 성립하면 됩니다. - 조건 1 : a[pc]와 key 가 일치하는 경우 - 조건 2 : 검색 범위가 더 이상 없는 경우 5. 이진 검색은 검색을 반복할 때마다 검색범위가 절반이 되므로 검색에 필요한 비교 횟수의 평균값은 log n 입니다. 6. 검색에 실패한 경우는 [log(n+1)]회, 검색에 성공한 경우는 대략 log n -1회 입니다.. 더보기 이전 1 2 3 4 5 다음
