본문 바로가기

#자바#JAVA#알고리즘#DoIt#기본 알고리즘#

[자바 Do It! 알고리즘]Chapter07 집합 (1)(배열로 집합 만들기) [배열로 집합 만들기] 1. 배열을 사용하여 집합을 표현하려면 집합의 요소 개수와 배열의 요소 개수는 항상 같아야 합니다. 즉, 집합의 상태를 표현할 데이터가 필요합니다. ※ 집합관련 메소드들입니다. ​ max 집합의 최대 크기를 나타내는 필드입니다. ​ num 집합의 요소개수입니다. 집합의 요소는 배열의 앞쪽부터 0~num-1까지 넣습니다. ​ set 집합을 저장할 배열입니다. 배열의 메모리 확보는 생성자에서 합니다. ​ 생성자 IntSet 집합은 처음에는 비어있기 때문에 0을 대입합니다. 생성자의 매개변수 capacityh를 max 에 복사하고 집합의 요소 개수가 max가 되도록 배열 set을 생성합니다. ​ 집합의 최대 개수를 반환하는 capacity 메서드 집합이 가질 수 있는 가장 큰 값을 반환.. 더보기
[자바 Do It! 알고리즘]Chapter06 정렬 (도수 정렬) 도수 정렬은 요소의 대소 관계를 판단하지 않고 빠르게 정렬할 수 있는 알고리즘 입니다. ​ [도수 정렬] 1. 도수 정렬 알고리즘은 도수분포표 작성, 누적도수분포표 작성, 목적 배열 만들기, 배열 복사의 4단계로 이루어집니다. 1) 1단계 도수분포표 만들기 (1) 배열 a를 바탕으로 '각 점수에 해당하는 학생이 몇 명인지를 나타내는 도수분포표 작성 (2) 도수분포표를 나타내기 위해 배열 f를 사용 (3) 먼저 배열 f의 모든 요소의 값을 0으로 초기화 (4) 그런 다음, 배열 a를 처음부터 스캔하면서 도수분포표를 만들면 됩니다. 2) 2단계 누적도수분포표 만들기 (1) '0점부터 점수 n까지 몇 명의 학생이 있는지' 누적된 값을 나타내는 도수분포표 만들기 예를들어, f[4]의 값(6)은 0~4점을 받은 .. 더보기
[자바 Do It! 알고리즘]Chapter06 정렬 (힙 정렬) 갈수록 난이도가 올라가네요.. 따라쓰고 따라 치고 있지만.. 잘하고 있는건지.. 하는것에 의의를 둡니다.. ​ 힙 정렬은 선택 정렬을 응용한 알고리즘인 힙 정렬입니다. ​ [힙이란?] 1. 힙 정렬(heap sort)은 힙(heap)을 사용하여 정렬하는 알고리즘입니다. 힙은 '부모의 값이 자식의 값보다 항상 크다'는 조건을 만족하는 완전이진트리입니다. 이때 부모의 값이 자식보다 항상 작아도 힙이라고 합니다. 2. 힙의 요소를 배열에 저장하면 부모와 자식의 인덱스 사이에 다음과 같은 관계가 성립합니다. 1) 부모는 a[(i-1) / 2] 2) 왼쪽 자식은 a[i*2 + 1] 3) 오른쪽 자식은 a[i * 2 + 2] ​ [힙 정렬] 1. 힙 정렬은 '가장 큰 값이 루트에 위치'하는 특징을 이용하는 정렬 알.. 더보기
[자바 Do It! 알고리즘]Chapter06 정렬 (병합 정렬-Arrays.sort로 퀵 정렬과 병합정렬하기) [Arrays.sort로 퀵 정렬과 병합 정렬하기] 1. 이진 검색에 사용했던 binarySearch 메서드는 java.util.Araays 클래스의 클래스 메서드로 제공합니다. 이 클래스는 배열을 정렬하는 클래스 메서드 sort도 제공합니다. 1 static void sort(byte[] a) 2 static void sort(byte[] a, int fromIndex, int tolndex) 3 static void sort(char[] a) 4 static void sort(char[] a, int fromIndex, int tolndex) 5 static void sort(double[] a) 6 static void sort(double[] a, int fromIndex, int tolndex).. 더보기
[자바 Do It! 알고리즘]Chapter06 정렬 (병합 정렬) 언젠가 이해되는 날이 오겟죠.. ​ 병합정렬은 배열을 앞부분과 뒷부분으로 나누어 각각 정렬한 다음 병합하는 작업을 반복하여 정렬을 수행하는 알고리즘입니다. ​ [정렬을 마친 배열의 정합] 1. 각 배열에서 선택한 요소의 값을 비교하여 작은 값의 요소를 꺼내 새로운 배열에 넣는 작업을 반복하여 정렬을 마치는 배열을 만듭니다. 1) 배열 a에서 선택한 요소(a[pa])와 배열 b에서 선택한 요소 (b[pb])를 비교하여 작은 값을 c[pc]에 저장합니다. 그런 다음 커서 pb,pc를 한 칸 옮기고 커서 pa는 그대로 둡니다. 커서 pa,pb가 가리키는 값을 비교하여 작은 값을 c[pc]에 대입하고 커서 pa,pbpc를 진행하는 작업을 반복합니다. 커서 pa가 배열 a의 끝에 다다르거나 커서 pb가 배열 b의.. 더보기
[자바 Do It! 알고리즘]Chapter06 정렬 (비재귀적인 퀵 정렬) [비재귀적인 퀵 정렬] 1. 05장의 recur 메서드는 데이터를 임시 저장하기 위해 '스택'을 사용했습니다. 이번 퀵 정렬도 마찬가지로 '스택'을 사용합니다. 1) lstack : 나눌 범위의 왼쪽 끝 요소의 인덱스를 저장하는 스택입니다. 2) rstack : 나눌 범위의 오른쪽 끝 요소의 인덱스를 저장하는 스택입니다. 3) 두 스택의 용량은 right - left + 1 입니다. (나눌 배열의 요솟수 ) 2. 스택의 변화 1) lstack 에 left 를, rstack에 right를 푸시합니다. a에서 볼 수 있듯이 lstack에 푸시되는 값은 0, rstack 에 푸시되는 값은 8입니다. 2) lsatck 에서 팝한 값을 left에 대입한 다음 그 left의 값을 다시 pl에 대입합니다.(rstac.. 더보기
[자바 Do It! 알고리즘]Chapter06 정렬 (퀵 정렬) [퀵 정렬] 1. 퀵 정렬은 가장 빠른 정렬 알고리즘 중의 하나입니다. 2. 퀵정렬 순서 1) 배열을 두 그룹으로 나누기 (1) 피벗을 x, 왼쪽 끝 요소의 인덱스 pl을 왼쪽 커서, 오른쪽 끝 요소의 인덱스 pr을 오른쪽 커서라고 하겠습니다. 5(pl) 7 1 4 6(x,pivot) 2 3 9 8(pr) (2) 그룹을 나누려면 피벗 이하의 요소를 배열 왼쪽으로, 이상의 요소를 배열 오른쪽으로 옮겨야 합니다. ☞ a[pl] >= x 가 성립하는 요소를 찾을 때 까지 pl을 오른쪽으로 스캔합니다. ☞ a[pr] pr + 1 인 경우에는 다음과 같은 그룹이 생길 수 있습니다. ☞ 피벗과 일치하는 값을 가지는 그룹 : a[pr + 1], ..., a[pl -1] 2) 1)의 과정을 그룹을 나누는 방식으로 세분.. 더보기
[자바 Do It! 알고리즘]Chapter06 정렬 (셸 정렬) 하면 할수록 이해가 안가네요.. 그래도 하는 것에 의의를.. ​ [셸 정렬] 1. 셸 정렬은 단순 삽입 정렬의 장점은 살리고 단점은 보완하여 좀 더 빠르게 정렬하는 알고리즘입니다. 2. 단순 삽입 정렬의 특징은 다음과 같습니다. 1) 정렬을 마쳤거나 정렬을 마친 상태에 가까우면 정렬 속도가 매우 빨라집니다.(장점) 2) 삽입할 위치가 멀리 떨어져 있으면 이동(대입)해야 하는 횟수가 많아집니다.(단점) 3. 셸 정렬은 단순 삽입 정렬의 장점은 살리고 단점은 보완한 정렬 알고리즘입니다. 1) 먼저 정렬한 배열의 요소를 그룹으로 나눠 각 그룹별로 단순 삽입 정렬을 수행하고 그 그룹을 합치면서 정렬을 반복하여 요소의 이동 횟수를 줄이는 방법입니다. ​ ​ (내용은 이해가 됐는데 코드가 이해가 안가네요 ㅎㅎ..).. 더보기

티스토리툴바