Study Note

Binary Tree: child노드가 최대 2개까지 붙은 트리 Binary Search Tree: 왼쪽 노드와 그 이하 child노드들은 현재 노드보다 작아야 하고, 오른쪽 노드와 그 이하 child노드들은 현재 노드보다 커야함. 큰 값을 찾고 싶으면 오른쪽으로만 가면되고, 작은 값을 찾고 싶으면 왼쪽으로 가면됨. 발란스가 맞다는 지나치게 치우쳐있지 않으면 발란스가 맞다고 한다. 모든 노드들이 왼쪽부터 채워져 있으면 Coplete Binary Tree이다. 마지막 레벨을 제외한 모든 서브트리의 레벨이 같아야 하고, 마지막 레벨은 왼쪽부터 채워져 있음. 하나의 chlid 노드를 가지고 있는 노드가 하나도 없는 트리를 Full Binary Tree라고 한다. 자식 노드를 하나도 가지지 않거나 두개를 가지는..

힙 최대값이나 최솟값을 빠르게 구하기 위해 고안된 완전 이진트리를 기본으로 한 자료구조 최소힙: 작은 값을 부모노드에 있게 하고, 최상단에는 가장 작은 값을 가짐 최대힙: 큰 값을 부모노드에 있게 하고, 최상단에는 가장 큰 값을 가짐 최소 힙에 노드 삽입하기 완전트리에 맨 끝에 노드 추가 정렬을 위해 자신과 부모노드를 비교해서 자신의 값이 작으면 자리 교환 (노드가 root에 도착했거나 부모노드가 자신보다 작을 때까지 반복) 완전 이진 트리에서 이루어 지므로 O(logN)이 걸린다. 최소 힙에 노드 꺼내오기 root 를 꺼내온 후에 완전 이진트리의 맨 마지막 노드를 가져와서 루트에 채운다. 정렬이 안된 상태 이므로 자신의 자식노드와 비교해서 더 작은 값을 올린다. (자식이 자기보다 크거나 마지막 노드에 ..

계수정렬(Counting Sort) 크기를 기준으로 갯수를 세는 알고리즘 갯수를 세는 배열(counting)을 정렬하고자 하는 배열(arr)의 사이즈를 최대값으로 담기도록 설정한다. 배열을 탐색하면서 해당 값을(arr[i]) counting배열에서 인덱스로 하는 갯수를 센다. import java.util.Scanner; public class p07_countingSort { public static void countingSort(int[] arr, int max){ int[] counting = new int[max+1]; // 배열의 사이즈를 최대값이 담기도록 잡는다. for(int i = 0; i < arr.length; i++){ counting[arr[i]]++; } for(int i = 1..

병합 정렬 (Merge Sort) 시간 복잡도 항상 O(NlogN) 정렬하는데 필요한 시간은 two pointer알고리즘을 사용하므로 수행시간은 N이다. 합치는 개수는 2배씩 증가하므로 2^3 = 8 로 3단계가 필요하다. 따라서 단계의 크기는 데이터의 갯수가 N개일 때 logN을 유지하게 된다. 따라서 항상 시간복잡도가 O(NlogN)을 유지한다. import java.util.Scanner; public class p05_mergeSort { public static void mergeSort(int[] arr) { sort(arr, 0, arr.length); } private static void sort(int[] arr, int low, int high) { if (high - low < 2)..

오름차순 import java.util.Scanner; public class quickSort { public static void swap(int[] arr, int p1, int p2){ int tmp = arr[p1]; arr[p1] = arr[p2]; arr[p2] = tmp; } // 분할 public static int partition(int[] arr, int start, int end){ int key = start; int lt = start + 1; int rt = end; while(lt rt) { // 현재 엇갈린 상태이면 키 값과 교체 swap(arr, rt, key); } else { // 엇갈리지 않았다면 lt와 rt의 값 교체 swap(arr, lt, rt); } } re..

이분 탐색 탐색 범위를 두 부분으로 분할 하면서 검색하는 방식 알고리즘 오름차순 정렬 배열 포인터 인덱스 start, end, mid 값 설정 mid와 내가 구하고자 하는 값과 비교 같으면 mid가 답 구할 값이 mid 보다 작으면 start = mid + 1 작으면 end = mid - 1 start > end가 될 때까지 반복 public class binarySearch { public int solution(int n, int m, int[] arr){ Arrays.sort(arr); int start = 0; int end = n -1; int mid = 0; while(start

2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입 하여 정렬하는 알고리즘 public class p03_insertSort { // 오름차순 public static int[] solution(int n, int[] arr){ for(int i = 1; i = 0; j--){// i번째 이전을 순회하면서 삽입 대상을 어디에 삽입할지 선택 if(arr[j] > tmp) arr[j+1] = arr[j]; else break; // arr[j] < tmp 이면 j이전 인덱스의 값들이 tmp보다 작은 ..

거품 정렬 (Bubble Sort) 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘 끝에서 부터 정렬이 이루어진다. public class p02_bubbleSort { // 오름 차순 public static int[] solution(int n, int[] arr){ for(int i = 0; i arr[j+1]){ int tmp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = tmp; } } } return arr; } // 내림 차순 public static int[] solution2(int n, int[] arr){ for(..

스택(Stack) 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 구조 후입 선출 LIFO (Last In First Out) top으로 정한 곳을 통해서만 접근할 수 있다. 자료는 top이 가리키는 가장 맨 위에 쌓이며, 자료를 삭제할 때도 top을 통해서만 삭제가 가능하다. 삽입 연산: push, 삭제 연산: pop 활용사례 웹 브라우저 방문기록(뒤로 가기) 실행 취소 (undo) 역순 문자열 만들기 후위 표기번 계산 큐(Queue) 먼저 들어오는 것이 먼저 나가는 구조 선입 선출 (First In First Out) 삽입 연산: Enqueue, 삭제 연산: Dequeue 삽입 연산이 이루어지는 곳을 리어(rear), 삭제 연산이 이루어지는 곳을 front라고 부른다. 활용사례 은행 업무 서비스 센터..

투포인터(Two Pointer) 리스트에 순차적으로 접근해야 할 때 두개의 점의 위치를 기록하면서 처리하는 알고리즘 예제 (연속 부분 수열) 어떤 숫자들의 리스트가 주어질 때, 해당 리스트의 연속 수열의 합이 특정 값(m)을 가지는 경우의 public class p04 { public static int solution(int n , int m, int[] arr){ int answer = 0; int lt = 0; int sum = 0; for(int rt = 0; rt = m) { lt++; sum -= arr[lt]; if(sum == m) answer++; } } return answe..