sorting and searching(정렬, 이분검색과 결정 알고리즘)

상태

완료

담당자

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
복사