Java/Java 알고리즘 (37) 썸네일형 리스트형 [알고리즘] 1. 정렬 1. 정렬 알고리즘 버블 정렬 데이터를 인접 요소끼리 비교해, swap 연산을 수행하면서 정렬 선택 정렬 대상에서 크거나 작은 데이터를 찾고, 선택을 반복하면서 정렬 삽입 정렬 대상을 선택해 정렬된 영역에서 선택 데이터의 위치를 찾아 삽입하면서 정렬 퀵 정렬 pivot 값을 선정해 해당 값을 기준으로 정렬 병합 정렬 이미 정렬된 부분들을 효율적으로 병합해 전체를 정렬 기수 정렬 데이터의 자릿수를 바탕으로 비교해 정렬 2. 정렬 알고리즘 구현 (1) 버블 정렬 : 루프를 돌면서 인접한 데이터간 swap 연산으로 정렬 N(정렬할 수 개수) A(정렬할 배열 선언) for(i : 0 ~ N - 1) { for(j : 0 ~ N - 1 - i) { 현재 A 배열의 값보다 1칸 오른쪽 배열의 값이 더 작으면 두 수.. [알고리즘] 4-2. 클래스 이진트리 1. Node Class protected static class Node { protected E data; protected Node left; protected Node right; public Node(E data) { this.data = data; left = null; right = null; } public String toString() { return data.toString(); } } 2. BinaryTree Class public class BinaryTree { protected static class Node { protected E data; protected Node left; protected Node right; public Node(E data) { this.data .. [알고리즘] 4-1. 검색 트리 트리와 이진 트리 1. 트리 : 계층적 구조를 표현 [조직도, 디렉토리와 서브 디렉토리, 가계도] 루트 노드 : 맨 위의 노드 리프 노드 : 자식이 없는 노드 내부 노드 : 리프노드가 아닌 노드 노드 연결 선 : link, edge, branch 부 트리 : 노드와 그 노드의 자손으로 이루어진 트리 루트 노드를 제외한 모든 노드는 유일한 부모 노드를 갖는다. 부모-자식 관계와 조상-자손 관계 -> 부모 자식은 1촌, 조상 자손은 n촌 트리의 성질 1. 레벨은 1부터 시작한다. 2. 노드가 N개인 트리는 항상 N-1개의 링크를 갖는다. 3. 루트에서 어떤 노드로 가는 경로는 유일 4. 임의의 두 노드간의 경로도 유일 이진 트리의 성질 1. 각 노드가 최대 2개의 자식을 갖는다. 2. 각각의 자식 노드는 부.. [알고리즘] 3-5. 자바의 정렬 1. 기본 타입 int [] data = new int [capacity]; Arrays.sort(data); //int 배열이 모두 꽉 차있을 경우 Arrays.sort(data, 0, size); //int 배열이 size-1까지 size개만 있을 경우 2.객체의 문자열 정렬 String [] fruits = new String[] {"Pineapple", "Apple", "Oragne", "Banana"}; Arrays.sort(fruits); for(String name : fruits) System.out.println(name); 3.ArrayList의 문자열 정렬 List fruits = new ArrayList(); fruits.add("Pineapple"); fruits.add("Appl.. [알고리즘] 3-4. 분할 정복을 이용한 정렬 (3) 비교 정렬 1. 데이터 간 상대적 크기 관계를 이용해 정렬 2. 데이터 간 크기 관계가 정의되어 있을 경우 적용 가능 3. 버블정렬, 삽입정렬, 합병정렬, 퀵정렬, 힙정렬 논-비교 정렬 1. 정렬할 데이터에 대한 사전지식 이용 2. Bucket Sort (버킷 정렬) 3. Radix Sort (기수 정렬) 하한 1. 입력된 데이터 한번씩 보기 위해 O(n) 시간복잡도 필요 2. 합병정렬과 힙정렬 알고리즘 시간복잡도 : O(nlog2n) 3. O(nlog2n)이 가장 빠른 비교정렬 결정 트리 1. Leaf 노드 수 : n!개 2. 최악의 경우 시간복잡도 (트리의 높이) :height >=log2n!=O(nlog2n) 선형 시간 정렬 알고리즘 Counting Sort (세는 정렬) -> 배열의 각 정수의 개.. [알고리즘] 3-3. 분할 정복을 이용한 정렬 (2) 힙정렬 1. 최악의 경우 시간복잡도 : O(nlog2n) 2. sorts in place : 추가 배열 불필요 [공간 복잡도 이득] 3. 이진 힙 자료구조 이용 힙의 정의 힙 : 완전이진트리이면서 힙 속성 만족 [힙은 동일 데이터를 가진 서로 다른 힙이 존재 가능하며, 유일하지 않다] [최대 힙 : 부모는 자식보다 크거나 같다.] [최소 힙 : 부모는 자식보다 작거나 같다.] 전이진 트리 : 모든 레벨에 노드들이 꽉 차있는 형태 완전이진트리 : 마지막 레벨 제외하면 완전히 차있고, 마지막 레벨에 가장 오른쪽부터 연속된 노드가 비어있을수있음 힙의 표현 1. 일차원 배열로 표현 : A[1...n] 2. 루트 노드 : A[1] 3. A[i]의 부모 : A[i/2] 4. A[i]의 왼쪽 자식 : A[2i] 4... [알고리즘] 3-2. 분할 정복을 이용한 정렬 분할 정복법 -> 작은 크기의 동일 문제로 분할 후 순환적으로 해결 -> 작은 문제의 해를 합쳐 원래 문제의 해를 구한다. 합병정렬 1. 데이터가 저장된 배열을 절반으로 나눈다 2. 각각을 순환적으로 정렬 3. 정렬된 두 개의 배열을 합쳐서 전체를 정렬 mergeSort(A[], p, r) { if (p [알고리즘] 3-1. 기본 정렬 버블, 삽입, 선택 정렬 간단하지만, 느리다 퀵, 병합, 힙 정렬 빠르다 기수 정렬 (radix) O(N) 정렬 1. 최대 원소 찾기 2. 최대 원소와 맨 오른쪽 원소와 교환 3. 맨 오른쪽 원소 제외 4. 하나의 원소만 남을 때까지 반복 //선택정렬 selectionSort (A[], n) { for last 이전 1 2 3 4 5 다음