1) 선택 정렬
설명
package com.company.sortingandsearching;
import java.util.Scanner;
public class SelectionSort {
public static void main (String [] args) {
SelectionSort selectionSort = new SelectionSort();
Scanner in = new Scanner(System.in);
int count = in.nextInt();
int [] arr = new int[count];
for (int i=0; i<count; i++) {
arr[i] = in.nextInt();
}
selectionSort.solution(count, arr);
}
void solution(int count, int [] arr) {
int temp;
for (int i=0; i<count; i++) {
int index = i;
for (int j=i+1; j<count; j++) {
if(arr[j] < arr[index]) {
index = j;
}
temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
}
}
for (int i : arr) {
System.out.println(i);
}
}
}
Java
복사
2) 버블정렬
설명
package com.company.sortingandsearching;
import java.util.Scanner;
public class BubbleSort {
public static void main (String [] args) {
BubbleSort bubbleSort = new BubbleSort();
Scanner in = new Scanner(System.in);
int count = in.nextInt();
int [] arr = new int[count];
for (int i=0; i<count; i++) {
arr[i] = in.nextInt();
}
bubbleSort.solution(count, arr);
}
void solution(int count, int [] arr) {
for (int i=0; i<count-1; i++) {
for (int j=0; j<count-i-1; j++) {
if (arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
for (int i : arr) {
System.out.println(i);
}
}
}
Java
복사
3) 삽입정렬
설명
package com.company.sortingandsearching;
import java.util.Scanner;
public class InsertSort {
public static void main (String [] args) {
InsertSort insertSort = new InsertSort();
Scanner in = new Scanner(System.in);
int count = in.nextInt();
int [] arr = new int[count];
for (int i=0; i<count; i++) {
arr[i] = in.nextInt();
}
insertSort.solution(count, arr);
}
void solution(int count, int [] arr) {
for (int i=1; i<count; i++) {
int temp = arr[i],j;
for (j=i-1; j>=0; j--) {
if (temp < arr[j]) {
arr[j+1] = arr[j];
} else {
break;
}
}
arr[j+1] = temp;
}
for (int i : arr) {
System.out.print(i);
}
}
}
Java
복사
4) Least Recently Used
설명
package com.company.sortingandsearching;
import java.util.Scanner;
public class LeastRecentlyUsed {
public static void main (String [] args) {
LeastRecentlyUsed leastRecentlyUsed = new LeastRecentlyUsed();
Scanner in = new Scanner(System.in);
int cashMemoryCount = in.nextInt();
int [] cashMemory = new int[cashMemoryCount];
int inputDataCount = in.nextInt();
int [] inputData = new int[inputDataCount];
for (int i=0; i<inputDataCount; i++) {
inputData[i] = in.nextInt();
}
leastRecentlyUsed.solution(cashMemoryCount, cashMemory, inputDataCount, inputData);
}
void solution(int cashMemoryCount, int [] cashMemory, int inputDataCount, int [] inputData) {
for (int i=0; i<inputDataCount; i++) {
int pos = -1;
for (int j=0; j<cashMemoryCount; j++) {
if (inputData[i] == cashMemory[j]) pos = j;
}
if (pos == -1) {
for(int j=cashMemoryCount-1; j>=1; j--) {
cashMemory[j] = cashMemory[j-1];
}
cashMemory[0] = inputData[i];
} else {
for(int j=pos; j>=1; j--) {
cashMemory[j] = cashMemory[j-1];
}
cashMemory[0] = inputData[i];
}
}
for (int i1 : cashMemory) {
System.out.println(i1);
}
}
}
Java
복사
8) 이분검색 ⇒ 뮤직비디오(결정알고리즘)
설명
•
이분 검색 최소값 찾기의 포인트는 배열의 범위안에 내가 원하는 값이 있을때 사용한다.
•
포인트는 lt, rt, mid 를 사용해서 범위를 축소 시키는 것이다.
•
오른쪽을 자를 때 ⇒ rt = mid +1, 왼쪽을 자를 떄 ⇒ lt = mid -1
package com.company.sortingandsearching;
import java.util.Arrays;
import java.util.Scanner;
public class DecisionAlgorithm {
public static void main (String [] args) {
DecisionAlgorithm decisionAlgorithm = new DecisionAlgorithm();
Scanner in = new Scanner(System.in);
int count = in.nextInt();
int albumCount = in.nextInt();
int [] arr = new int[count];
for (int i = 0; i < count; i++) {
arr[i] = in.nextInt();
}
decisionAlgorithm.solution(count, albumCount, arr);
}
void solution(int count, int albumCount, int [] arr) {
int lt = Arrays.stream(arr).max().getAsInt();
int rt = Arrays.stream(arr).sum();
int answer = 0;
while (lt <= rt) {
int mid = (lt+rt) / 2;
// 중요 포인트!!!
int maxAlbumCount = calcAlbumCount(arr, mid);
if(maxAlbumCount <= albumCount) {
//용량을 줄인다.
answer = mid;
rt = mid -1;
} else {
//용량을 늘린다.
lt = mid + 1;
}
}
System.out.println(answer);
}
int calcAlbumCount(int [] arr, int capacity) {
int cnt = 1, sum = 0;
for (int i : arr) {
if (sum + i > capacity) {
cnt++;
sum = i;
} else {
sum += i;
}
}
return cnt;
}
}
Java
복사