Manta Ray's

Comparable collecion 클래스에서 구성 요소를 정렬하는 기준을 정의하는 인터페이스입니다. Collection의 요소가 사용자 정의 클래스인 경우에는 Comparable 인터페이스를 상속받아 구현되어야 합니다. 상속 받은 뒤에는 정렬기준을 정의하는 compareTo 메소드를 구현해야 합니다.(오버라이드) 메소드 리턴 설명 compareTo(T o) int o와 객체가 가진 값이 같으면 0을 리턴 o보다 객체가 가진 값이 크면 양수를 리턴 o보다 객체가 가진 값이 작으면 음수를 리턴 public class Student implements Comparable{ int id ; int score; String name; public Student(int id, int score, String n..

힙의 형태 완전 이진 트리 : 각 노드의 자식 수가 2 이하이며, Root 노드부터 Leaf 노드까지 빠짐없이 채워져있는 트리 최대힙 Max-Heap 부모 노드 > 자식 노드 Root 노트의 값이 가장 크다. 최소힙 Min-Heap 부모 노드 < 자식 노드 Root 노드의 값이 가장 작다. 힙 배열 저장 방식 Root 노드는 배열의 첫 번째에 저장 각 노드들은 레벨 별로 저장 ▶ 부모 : 현재위치 / 2 ▶ 왼쪽 자식 : 현재위치*2 ▶ 오른쪽 자식 : 현재위치 *2+1 힙의 높이 O(logN) 힙 특성관리 Max-Heapify 노드가 입력으로 주어졌을 때 max-heap 특성이 유지되도록 바꾸는 연산 입력값이 흘러내리게 함. 시간복잡도 O(logN) 힙 구조 만들기 입력받은 트리에 Max-Heapify..

파티셔닝을 이용한 정렬방법 ① 기준값을 정한다. ② 첫번째부터 차례로 비교해나가면서 기준값보다 작으면 왼쪽 그룹의 끝자리+1과 위치를 바꾼다. 퀵 정렬의 수도코드 시간복잡도 Balanced Partitioning : 파티셔닝의 크기가 n/2로 줄어드는 경우 => 높이 logN * 각 층별 N번의 연산을 수행 => O(NlogN) UnBalanced Partitioning : 파티셔닝의 크기가 1과 n-1개로 줄어드는 경우 => 높이 N-1 * 각 층별 N-1번의 연산을 수행 => O(N²) * Unbalanced Partitioning(최악의 경우)를 피하기 위해 파티셔닝의 크기를 랜덤하게 가져가는 Randomized QuickSort가 등장함. 구현 JAVA package algorithm; impor..