[JAVA] 알고리즘 문제풀이 기초 - Sorting and Searching-1
Sorting and Searching
선택 정렬 (6-1)
-
설명 : N개이 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요. 정렬하는 방법은 선택정렬입니다.
-
입력 : 첫 번째 줄에 자연수 N(1<=N<=100)이 주어집니다. 두 번째 줄에 N개의 자연수가 공백을 사이에 두고 입력됩니다. 각 자연수는 정수형 범위 안에 있습니다.
-
출력 : 오름차순으로 정렬된 수열을 출력합니다.
-
작성 답안
import java.util.*;
public class Main {
public static void main(String[] args) {
Main t = new Main();
Scanner scan = new Scanner(System.in);
int num = scan.nextInt();
int[] arr = new int[num];
for(int i=0; i<num; i++){
arr[i] = scan.nextInt();
}
for (int i : t.solution(arr)) {
System.out.print(i+" ");
}
}
public int[] solution(int[] arr){
int[] result = arr;
int tmp;
for(int i=0; i<result.length; i++){
int min = result[i];
int idx = i;
for(int j=i+1; j<result.length; j++){
if(min>result[j]) {
min = result[j];
idx = j;
}
}
if(i!=idx) {
tmp = result[i];
result[i] = result[idx];
result[idx] = tmp;
}
}
return result;
}
}
- 풀이 답안 ``` java import java.util.*;
public class Main { public static void main(String[] args) { Main t = new Main(); Scanner scan = new Scanner(System.in); int num = scan.nextInt(); int[] arr = new int[num]; for(int i=0; i<num; i++){ arr[i] = scan.nextInt(); }
for (int i : t.solution(arr)) {
System.out.print(i+" ");
}
}
public int[] solution(int[] arr){
int[] result = arr;
int tmp;
for(int i=0; i<result.length; i++){
int idx = i;
for(int j=i+1; j<result.length; j++){
if(arr[idx]>result[j]) {
idx = j;
}
}
if(i!=idx) {
tmp = result[i];
result[i] = result[idx];
result[idx] = tmp;
}
}
return result;
} } ```
- 특징
- 선택정렬은 루프회차당 가장 작은수를 앞 인덱스로 옮기는 방식
- 선택정렬은 루프회차당 가장 작은수를 앞 인덱스로 옮기는 방식
버블 정렬 (6-2)
-
설명 : N개의 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요. 정렬하는 방법은 버블정렬입니다.
-
입력 : 첫 번째 줄에 자연수 N(1<=N<=100)이 주어집니다. 두 번째 줄에 N개의 자연수가 공백을 사이에 두고 입력됩니다. 각 자연수는 정수형 범위 안에 있습니다.
-
출력 : 오름차순으로 정렬된 수열을 출력합니다.
-
작성 답안
import java.util.*;
public class Main {
public static void main(String[] args) {
Main t = new Main();
Scanner scan = new Scanner(System.in);
int num = scan.nextInt();
int[] arr = new int[num];
for(int i=0; i<num; i++){
arr[i] = scan.nextInt();
}
for (int i : t.solution(arr)) {
System.out.print(i+" ");
}
}
public int[] solution(int[] arr){
int[] result = arr;
int tmp, chk=-1;
while (chk!=0){
chk = 0;
for(int i=1; i<result.length; i++){
if(result[i-1]>result[i]) {
tmp = result[i-1];
result[i-1] = result[i];
result[i] = tmp;
chk++;
}
}
}
return result;
}
}
- 풀이 답안
import java.util.*;
public class Main {
public static void main(String[] args) {
Main t = new Main();
Scanner scan = new Scanner(System.in);
int num = scan.nextInt();
int[] arr = new int[num];
for(int i=0; i<num; i++){
arr[i] = scan.nextInt();
}
for (int i : t.solution(arr)) {
System.out.print(i+" ");
}
}
public int[] solution(int[] arr){
int[] result = arr;
int tmp;
for(int i=0; i<arr.length-1; i++){
for(int j=1; j<result.length-i; j++){
if(result[j-1]>result[j]) {
tmp = result[j-1];
result[j-1] = result[j];
result[j] = tmp;
}
}
}
return result;
}
}
- 특징
- 나의 경우는 0~크기만큼 변화가 없을때까지 돌도록 했는데
- 그게 아니라 최초에돌때 최대값은 제일 뒤로 보내지기 때문에
- 이중for문을 돌면서 반복회차만큼 반복사이즈를 줄이는 방식으로 해야함(이미 정렬된 최대수는 또 검증안해도됨)
- 따라서 for(int i=0; i<arr.length-1; i++)로 차례를 카운트하고 for(int j=1; j<result.length-i; j++)에서 반복도는 규모를 줄여나감
- 나의 경우는 0~크기만큼 변화가 없을때까지 돌도록 했는데
삽입 정렬 (6-3)
-
설명 : N개의 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요. 정렬하는 방법은 삽입정렬입니다.
-
입력 : 첫 번째 줄에 자연수 N(1<=N<=100)이 주어집니다. 두 번째 줄에 N개의 자연수가 공백을 사이에 두고 입력됩니다. 각 자연수는 정수형 범위 안에 있습니다.
-
출력 : 오름차순으로 정렬된 수열을 출력합니다.
-
작성 답안
import java.util.*;
public class Main {
public static void main(String[] args) {
Main t = new Main();
Scanner scan = new Scanner(System.in);
int num = scan.nextInt();
int[] arr = new int[num];
for(int i=0; i<num; i++){
arr[i] = scan.nextInt();
}
for (int i : t.solution(arr)) {
System.out.print(i+" ");
}
}
public int[] solution(int[] arr){
int[] result = arr;
int tmp, chk=0;
for(int i=1; i<result.length; i++){
for(int j=i-1; j>=0; j--){
chk=0;
if(result[j]>result[j+1]) {
tmp = result[j];
result[j] = result[j+1];
result[j+1] = tmp;
chk = 1;
}
if (chk==0) break;
}
}
return result;
}
}
- 풀이 답안
import java.util.*;
public class Main {
public static void main(String[] args) {
Main t = new Main();
Scanner scan = new Scanner(System.in);
int num = scan.nextInt();
int[] arr = new int[num];
for(int i=0; i<num; i++){
arr[i] = scan.nextInt();
}
for (int i : t.solution(arr)) {
System.out.print(i+" ");
}
}
public int[] solution(int[] arr){
int[] result = arr;
for(int i=1; i<result.length; i++){
int tmp = arr[i], j;
for(j=i-1; j>=0; j--){
if(result[j]>tmp) {
result[j+1] = result[j];
} else break;
}
result[j+1] = tmp;
}
return result;
}
}
- 특징
- 나의 경우 계속해서 앞과 뒤를 비교하도록 해줬는데
- 그게 아니라 tmp에 기준값을 담아두고
- 기준값보다 큰 값들을 한칸씩 미루는 방식으로 진행하는게 연산이 적음
- 기준값보다 작지않은 값을 만나면 더이상 비교를 하지않고 break
- 그다음 최종 j+1 위치에 tmp값을 넣어줌
- j를 반복문 밖에서 사용하기에 선언을 밖에서 미리 해주는게 핵심
- 나의 경우 계속해서 앞과 뒤를 비교하도록 해줬는데
Least Recently Used (6-4)
- 설명 : 캐시메모리는 CPU와 주기억장치(DRAM) 사이의 고속의 임시 메모리로서 CPU가 처리할 작업을 저장해 놓았다가 필요할 바로 사용해서 처리속도를 높이는 장치이다. 워낙 비싸고 용량이 작아 효율적으로 사용해야 한다. 철수의 컴퓨터는 캐시메모리 사용 규칙이 LRU 알고리즘을 따른다. LRU 알고리즘은 Least Recently Used 의 약자로 직역하자면 가장 최근에 사용되지 않은 것 정도의 의미를 가지고 있습니다. 캐시에서 작업을 제거할 때 가장 오랫동안 사용하지 않은 것을 제거하겠다는 알고리즘입니다.
캐시의 크기가 주어지고, 캐시가 비어있는 상태에서 N개의 작업을 CPU가 차례로 처리한다면 N개의 작업을 처리한 후 캐시메모리의 상태를 가장 최근 사용된 작업부터 차례대로 출력하는 프로그램을 작성하세요.
-
입력 : 첫 번째 줄에 캐시의 크기인 S(3<=S<=10)와 작업의 개수 N(5<=N<=1,000)이 입력된다. 두 번째 줄에 N개의 작업번호가 처리순으로 주어진다. 작업번호는 1 ~100 이다.
-
출력 : 마지막 작업 후 캐시메모리의 상태를 가장 최근 사용된 작업부터 차례로 출력합니다.
-
작성 답안
import java.util.*;
public class Main {
public static void main(String[] args) {
Main t = new Main();
Scanner scan = new Scanner(System.in);
int size = scan.nextInt();
int cache = scan.nextInt();
int[] arr = new int[cache];
for(int i=0; i<cache; i++){
arr[i] = scan.nextInt();
}
for (int i : t.solution(arr, cache, size)) {
System.out.print(i+" ");
}
}
public int[] solution(int[] arr, int cache, int size){
int[] result = new int[size];
int chk = 0;
for(int i=0; i<cache; i++){
for(int j=0; j<size; j++){
if(arr[i]==result[j]) chk = j;
}
if(chk>0) {
while(chk>=1){
result[chk] = result[chk-1];
chk--;
}
} else {
int idx=size-1;
while(idx>=1){
result[idx] = result[idx-1];
idx--;
}
}
result[0] = arr[i];
}
return result;
}
}
- 풀이 답안
import java.util.*;
public class Main {
public static void main(String[] args) {
Main t = new Main();
Scanner scan = new Scanner(System.in);
int size = scan.nextInt();
int cache = scan.nextInt();
int[] arr = new int[cache];
for(int i=0; i<cache; i++){
arr[i] = scan.nextInt();
}
for (int i : t.solution(arr, cache, size)) {
System.out.print(i+" ");
}
}
public int[] solution(int[] arr, int cache, int size){
int[] result = new int[size];
for(int i=0; i<cache; i++){
int chk = 0;
for(int j=0; j<size; j++){
if(arr[i]==result[j]) chk = j;
}
if(chk>0) {
while(chk>=1){
result[chk] = result[chk-1];
chk--;
}
} else {
int idx=size-1;
while(idx>=1){
result[idx] = result[idx-1];
idx--;
}
}
result[0] = arr[i];
}
return result;
}
}
- 특징
- 풀이방식 작성답안과 동일하여 별도로 적지 않음
- 지정 사이즈만큼 배열을 만들어 주고 원소를 넣으면서
- 이중 반복을 돌아 같은 값이 있는지 체크하고, 있다면 인덱스 저장
- 동일값이 있는경우 해당 인덱스부터 한칸씩 앞의 값으로 당겨 채우고 첫 인덱스에 현재값 넣기
- 같은값이 없다면 끝인덱스부터 한칸씩 앞칸의 값으로 당겨 넣고 현 인덱스에 새로운 값 넣기
- 풀이방식 작성답안과 동일하여 별도로 적지 않음