100세까지 코딩

원리 분할 정복 방식을 이용하여 하나의 리스트를 두 개의 리스트로 분할 각각의 분할된 리스트를 정렬한 후에 합해서 정렬된 하나의 리스트로 만듦 코드 public class MergeSort{ public static int[] sorted; public static void main(String[] args) { int[] arr = new int[] {4,2,5,1,3,7,8,9}; sorted = new int[arr.length]; mergeSort(arr,0,arr.length-1); for(int data : arr){ System.out.println(data); } } public static void merge(int[] arr,int first,int middle,int last){ in..

원리 리스트 안에 한 요소(피벗)를 선택 피벗을 기준으로 피벗보다 작은 요소는 모두 왼쪽, 큰 요소는 오른쪽으로 피벗을 제외한 왼쪽 리스트, 오른쪽 리스트를 다시 정리 코드 public class QuickSort{ public static void main(String[] args) { int [] arr = {1,5,33,6,7,12,23}; QuickSort(arr,0,arr.length-1); for(int data : arr){ System.out.println(data); } } public static void QuickSort(int[] arr,int first,int last){ int pivot = first; int left = pivot+1; int right = last; if(f..

원리 현재 비교하고자 하는 타깃과 그 이전에 정렬돼 있는 원소들과 비교하며 자리 교환하는 방법 과정 현재 타깃과 타깃 앞에 위치한 원소들을 비교 (첫 번째 타깃은 두 번째 원소부터 시작) 타깃이 되는 숫자가 앞에 위치한 원소들 중 정렬에 맞는 적절한 위치 찾기 적절한 위치 뒤에 있는 원소들은 +1 하여 뒤로 밀어주기 다음 타깃으로 이동하여 같은 방법 반복 코드 public class InsertionSort { public static void main(String[] args) { int[] arr = {1,5,7,20,11,12,13,14,158,9,10}; for(int i = 1; i < arr.length; i++) { int target = arr[i]; int j = i - 1; while(..

문제 설명 풀기 전 생각 선택 정렬은 O(N^2)의 시간 복잡도를 가짐 전체 round는 (배열크기 - 1)만큼 진행 배열의 가장 앞부분을 최댓값으로 미리 정함 arr [i] i+1부터 비교해 나가며 미리 정한 최댓값보다 큰 값이 나오면 최댓값 교체 가장 앞자리와 최댓값 swap i++ 해가며 차례대로 정렬 코드 import java.util.*; public class Baek1427 { public static void main(String[] args){ Scanner sc = new Scanner(System.in); String str = sc.next(); int[] arr = new int[str.length()]; for(int i = 0; i < arr.length; i++){ arr[i..

문제 설명 풀기 전 생각 버블 정렬은 O(N^2)의 시간복잡도를 가짐 전체 round는 (배열크기 - 1)만큼 진행 각 round에서 비교 횟수는 (배열 크기 -1 - 현재 round) 이유는, round가 지날수록 뒤쪽부터 이미 정렬돼 있는 상태이기 때문 코드 import java.util.Scanner; public class Baek2750 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int[] arr = new int[N]; for(int i = 0; i < N ; i++){ arr[i] = sc.nextInt(); } for(int i = 0; i < N-1;..

문제 설명 풀기 전 생각 반복 규칙은 간단하니 우선순위 큐의 정렬 기준을 만드는게 핵심 절대값을 추출하여 절대값이 작은 것을 우선 절대값이 같으면 음수를 우선 큐를 정의한 후, 입력이 = 0일때 pq가 비어있으면 '0'출력 아니면 큐에서 한개 출력 입력이 0이 아니면 큐에 삽입 import java.util.PriorityQueue; import java.util.Scanner; public class Baek11286{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); StringBuilder sb = new StringBuilder(); PriorityQueue pq = n..