WEB/자료구조

1. 힙정렬이란?힙정렬(heap sort)은 힙(heap)을 사용하여 정렬하는 알고리즘.힙은 '부모의 값이 자식의 값보다 항상 크다'는 조건을 만족하는 완전이진트리이때 부모의 값이 자식보다 항상 작아도 힙이라고 합니다. (부모와 자식 요소의 관계만 일정하면 됨) 힙의 요소를 배열에 저장하면 부모와 자식의 인덱스 사이에 다음과 같은 관계가 성립합니다. 1) 부모는 a[(i-1)/2] 2) 왼쪽 자식은 a[i*2+1] 3) 오른쪽 자식은 a[i*2+2] 이제 힙정렬 해보겠습니다. 이런방법으로 계속 진행됩니다. 이제는 정렬되지 않은 배열을 힙으로 만들어보겠습니다.bottom-up 방식) - 힙 정렬의 시간 복잡도힙정렬은 선택정렬을 응용한 알고리즘입니다. 힙정렬에서는 첫 요소를 꺼내는 것만으로 가장 큰 값이 구..

1. 퀵 정렬(quick sort)- 리처드 호어(C. A. R. Hoare)가 붙인 이름- 분할 정복 알고리즘과 재귀 호출을 사용한 퀵 정렬 - 작업수행 절차 A. 스캔 1) a[pl] >= x가 성립하는 요소를 찾을 때까지 pl을 오른쪽으로 스캔 2) a[pr] 스택의 용량 : 분할시 요소의 개수가 적은 배열일수록 적은 획수로 분할을 종료할 수 있다. 그리고 스택에 쌓여 있는 데이터의 최대 개수를 줄일수 있따. 만약 배열의 요소 개수가 $n$개라면 스택에 쌓이는 데이터의 최대 개수는 $log{n}$보다 적다.-> 피벗 선택 : 만약 데이터가 a[0] ~ a[8]개 있다면 a[0] = left, a[8] = right, a[4] 는 마지막 요소인 a[8]보다 1개 적은 a[7]과 데이터를 교환하고 pl..

- 내부 정렬 : 정렬한 모든 데이터를 하나의 배열에 저장할 수 있는 경우에 사용하는 알고리즘- 외부 정렬 : 정렬할 데이터가 너무 많아서 하나의 배열에 저장할 수 없는 경우에 사용하는 알고리즘- 정렬 알고리즘의 핵심 요소 : 교환, 선택, 삽입이며 대부분의 정렬 알고리즘은 이 세 가지 요소를 응용한것1. 버블정렬(bubble sort) : 이웃한 두 요소의 대소관계를 비교하여 교환을 반복 2. 단순 선택 정렬(straight selection sort) : 가장 적은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘 3. 단순 삽입 정렬(straight insertion sort) : 선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 '삽입하는' 작업을 반복하여 정렬하는 알고리즘 - 시간복잡..

1. 큐- 스택과 마찬가지로 데이터를 일시적으로 쌓아 두기 위한 자료구조- 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(queue) 구조- 큐에 데이터를 넣는 작업을 인큐(enqueue)- 데이터를 꺼내는 작업을 디큐(dequeue)- 데이터를 꺼내는 쪽을 프런트(front)- 데이터를 넣는 쪽을 리어(rear)- IntQueue.java - IntQueueTester.java 실행결과) 2. 재귀의 기본- 재귀란?: 어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될떄 재귀적(recursive)이 라고 한다. - 팩토리얼(factorial) - 유클리드 호재법(Euclidean method of mutual division) - 재귀 알고리즘의 분석하기 위한 하향식(top dow..

1. 스택- 스택은 데이터를 일시적으로 저장하기 위한 자료구조로, 가장 나중에 넣은 데이터를 가장 먼저 꺼냅니다.- 데이터의 입력과 출력 순서는 후입선출(LIFO, Last In Fisrt Out)- 스택에 데이터를 넣는 작업을 푸시(push)- 스택에 데이터를 꺼내는 작업을 팝(pop)- 푸시와 팝을 하는 위치를 꼭대기(top)- 스택의 가장 아랫부분을 바닥(bottom) - 스택 만들기 1) 스택 본체용 배열 (stk) : 푸시된 데이터를 저장하는 스택 본체의 배열 2) 스택 용량 (max) : 스택의 용량(스택에 쌓을 수 있는 최대 데이터 수)을 나타내는 필드 3) 스택 포인터 (ptr) : 스택에 쌓여 있는 데이터 수를 나타내는 필드. 스택 포인터(statck pointer) 4) 생성자(IntS..