자바 자료구조론

초보 벗어나기  프로젝트 제2탄

자료구조와 알고리즘 공부하기

대학교때 심한 결석과 무분별한 땡땡이로 공부를 안한터....

너무나 소홀히 했던 기초다듬기을 해야겠다는 생각이 들어서..시작한 웹표준이 이어 두번째 공부

가.배열(Array)

1. 모두 같은 자료형에 순서가 있게 구성된 집합.
2. 인덱스로 접근가능.
3. 연산속도
   3-1.중복을 허용할경우 검색은N번 비교,중복을 허용안할땐 N/2번 비교
   3-2.중복을 허용할경우 삽입은1번 옮김,중복을 허용안할땐 1번 옮김
   3-3.중복을 허용할경우 삭게은N번 비교후 N/2번 이상 옮김,중복을 허용안할땐 N/2번
        비교후 N/2번이상 옮김.

나.리스트(List)

1. 고정된 길이의 자료들을 순차적으로 나열해 놓은 집합을 가리키는 자료구조의 추상적인개념
2. 배열과 연결리스트(LinkedList)방식이 있음(흔한 말하는 리스트는 후자를 말함)
   2-1.배열은 인덱싱이 O(1)이고 연결리스트O(n)이다.
   2-2.배열의 자료삽입은 O(n),연결리스트는 O(1)이다.
   2-3.배열의 자료삭제는 O(n),연결리스트는 O(1)이다.
   2-4.배열의 지역성은 좋다,연결리스트는 나쁨.(연결성이란 밀집도를 뜻함.)
3. 연결리스트의 종류
   3-1.단순연결리스트(singly linked-list):헤더를 기준으로 노드가 존재하며 각 노드에는
        데이터와 포인터로 구성되어있으며 단방향성을 가지고 있음.
   3-2.이중말단연결리스트(double-ended linked-list):단순연결리스트와 별다른점이 없으나
        헤더에 첫노드와 마지막노드의 포인터가 있음.
   3-3.이중연결리스트(double linked-list):단순연결리스트의 단점인 단방향을 제거하기 위해
       각노드에 앞노드,뒤노드의 포인터를 가지고 있음

다.스택과 큐(stack and queue)

1. 스택(stack):후입선출방식(Last-In-First-Out)의 데이터구조
2. 큐(queue):선입선출방식(First In First Out)의 데이터 구조
3. 원형큐(circular queue):큐를 사용시 입력후 삭제하면 데이터의 공간이 생기는데 그것을 재사용하기에 힘듬.그래서 삭제된 공간을 재사용하기 위한 나온 큐.
4. 데크(deque(double-ended queue)):스텍이나 큐와 다르게 이것은 앞뒤로
   입력과 출력이 가능.
5. 우선순위 큐(priority queue):순서가 있는 큐.

라.탐색(search)

1. 선형탐색
   1-1.일일이 탐색하기 때문에 시간이 양에 완전 비례한다.
   1-2.양이 작을때 유용.
2. 이진탐색
   2-1.분할을 한다음에 찾기때문에 시간이 많이 단축됨.(log2n)
   2-2.하지만 순서대로 있어야 하기 때문에 삭제나 수정시 엄청난 수고가 필요.
3. 이진트리탐색
4. 그래프탐색

라.기본정렬(sorting)

1. 버블정렬(bubble sort)
   1-1.처음항목에서 차례로 앞에 항목과 비교하여 정렬하는방법.
   1-2.제일 편한방식이긴하나 성능이 제일떨어짐
2. 선택정렬(selection sort)
   2-1.하나의 기준으로 차례로 비교하여 정렬하는 방식
   2-2.버블정렬과 속도는 비슷하나 자리바꿈의정도가 적다.
3. 삽입정렬(insert sort)
   3-1.어느정도 정렬된 상태에서 중간에 값이 나오면 일단 뒤에 항목을 뒤로 밀고 앞에
   끼워넣는 방법
   3-2.제일 효율적인 방법이나 어느정도 정렬된 상태에서 유리함.

ps.정렬테스트 페이지

라.개선된정렬(sorting)

1. 쉘정렬(Shell Sort)
   1-1.삽입정렬의 단점을 극복하고 장점을 살린방법
   1-2.일정한 간격(크누스간격)을 두고 여러개의 배열을 구성하여 먼저 순서를정렬한다음에
        삽입정렬로 마무리하는것.
2. 퀵정렬(Quick Sort)
   2-1.피벗이란 하나의 대표되는 수를 정하여 좌측엔 피벗보다 작은것들 오른쪽에는 높은걸들을 배치한다.
   2-2.그다음에 또다른 피벗을 정하고 재귀적은 호출로 계속하여 정렬한다.
   2-3.가장 빠른 정렬이다 하지만 중간값을 정확히 구하는게 관건
3. 기수정렬(Radix Sort)
   3-1.음수가 아닌 숫자로만 이루어진 데이터구조에서 각자리를 비교하여 정렬하는 방식
   3-2.정렬시 숫자들을 정렬테이블을 이용하기 때문에 메모리 사용이 많음.

마.재귀(recursion)

1. 자신의 함수를 다시 호출하는것
2. 장점:간단히 표현가능,소스 보기 편함
3. 단점:함수를 여러번 사용하기 때문에 메모리가 오버플로우가 생길수 있음.
4. 참고문헌:재귀적 지역정렬을 이용한 프로그램 표절 탐색