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

1. 선택 정렬

N개의 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요.

정렬하는 방법은 선택정렬입니다.

 

입력

첫 번째 줄에 자연수 N(1<=N<=100)이 주어집니다.

두 번째 줄에 N개의 자연수가 공백을 사이에 두고 입력됩니다. 각 자연수는 정수형 범위 안에 있습니다.

 

출력

오름차순으로 정렬된 수열을 출력합니다.

예시 입력 1 

6
13 5 11 7 23 15

예시 출력 1

5 7 11 13 15 23

<코드>

import java.util.Scanner;

public class Main {
    public int[] solution(int n, int[] arr) {
        for(int i=0; i<n-1; i++)
        {
            int idx=i;
            for(int j=i+1; j<n; j++)
            {
                if (arr[j] < arr[idx])
                    idx=j;
            }
            int tmp=arr[i];
            arr[i]=arr[idx];
            arr[idx]=tmp;
        }
        return arr;
    }

    public static void main(String[] args) {
        Main T = new Main();
        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 x : T.solution(n,arr))
        {
            System.out.print(x+" ");
        }
    }
}

 

2. 버블 정렬

-간단한 개념

버블 정렬은 이웃한 두 숫자를 비교한다. 제일 큰 숫자가 배열의 끝에 위치하게 된다.

예를 들어, 다음과 같은 숫자가 있다고 하자.

13 5 21 7 23 15

반복문을 돌면서, 처음에는 23이 배열의 끝에 위치하고, 그 다음에는 21이 23 옆에 위치할 것이다.

제일 큰 숫자를 확인하며 반복문을 돌게 되는 것이다. 

이와 관련된 예제를 한 번 살펴보자.

 

-문제

N개이 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요.

정렬하는 방법은 버블정렬입니다.

 

입력

첫 번째 줄에 자연수 N(1<=N<=100)이 주어집니다.

두 번째 줄에 N개의 자연수가 공백을 사이에 두고 입력됩니다. 각 자연수는 정수형 범위 안에 있습니다.

 

출력

오름차순으로 정렬된 수열을 출력합니다.

예시 입력 1 

6
13 5 11 7 23 15

예시 출력 1

5 7 11 13 15 23

<코드>

import java.util.Scanner;

public class Main {
    public int[] solution(int n, int[] arr) {
        for(int i=0; i<n-1; i++)
        {
            for(int j=0; j<n-i-1; j++)
            {
                if(arr[j]>arr[j+1])
                {
                    int tmp=arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp; 
                }
            }
        }
        return arr;
    }

    public static void main(String[] args) {
        Main T = new Main();
        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 x : T.solution(n,arr))
        {
            System.out.print(x+" ");
        }
    }
}

 

3. 삽입정렬

- 간단한 개념

1. 현재 타겟이 되는 숫자와 이전 위치에 있는 원소들을 비교한다. (첫 번째 타겟은 두 번째 원소부터 시작한다.)

2. 타겟이 되는 숫자가 이전 위치에 있던 원소보다 작다면 위치를 서로 교환한다.

3. 그 다음 타겟을 찾아 위와 같은 방법으로 반복한다.

 

-문제

N개이 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요.

정렬하는 방법은 삽입정렬입니다.

 

입력

첫 번째 줄에 자연수 N(1<=N<=100)이 주어집니다.

두 번째 줄에 N개의 자연수가 공백을 사이에 두고 입력됩니다. 각 자연수는 정수형 범위 안에 있습니다.

 

출력

오름차순으로 정렬된 수열을 출력합니다.

예시 입력 1 

6
11 7 5 6 10 9

예시 출력 1

5 6 7 9 10 11

<코드>

import java.util.Scanner;

public class Main {
    public int[] solution(int n, int[] arr) {
        for(int i=1; i<n; i++)
        {
            int tmp=arr[i], j;
            for(j=i-1; j>=0; j--)
            {
                if(arr[j]>tmp)
                    arr[j+1]=arr[j];
                else break;
            }
            arr[j+1]=tmp;

        }
        return arr;
    }

    public static void main(String[] args) {
        Main T = new Main();
        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 x : T.solution(n,arr))
        {
            System.out.print(x+" ");
        }
    }
}

 

4. LRU(Least Recently Used)

캐시메모리는 CPU와 주기억장치(DRAM) 사이의 고속의 임시 메모리로서 CPU가 처리할 작업을 저장해 놓았다가

필요할 바로 사용해서 처리속도를 높이는 장치이다. 워낙 비싸고 용량이 작아 효율적으로 사용해야 한다.

철수의 컴퓨터는 캐시메모리 사용 규칙이 LRU 알고리즘을 따른다.

LRU 알고리즘은 Least Recently Used 의 약자로 직역하자면 가장 최근에 사용되지 않은 것 정도의 의미를 가지고 있습니다.

캐시에서 작업을 제거할 때 가장 오랫동안 사용하지 않은 것을 제거하겠다는 알고리즘입니다.

캐시의 크기가 주어지고, 캐시가 비어있는 상태에서 N개의 작업을 CPU가 차례로 처리한다면 N개의 작업을 처리한 후

캐시메모리의 상태를 가장 최근 사용된 작업부터 차례대로 출력하는 프로그램을 작성하세요.

 

입력

첫 번째 줄에 캐시의 크기인 S(3<=S<=10)와 작업의 개수 N(5<=N<=1,000)이 입력된다.

두 번째 줄에 N개의 작업번호가 처리순으로 주어진다. 작업번호는 1 ~100 이다.

 

출력

마지막 작업 후 캐시메모리의 상태를 가장 최근 사용된 작업부터 차례로 출력합니다.

예시 입력 1 

5 9
1 2 3 2 6 2 3 5 7

예시 출력 1

7 5 3 2 6

<내 풀이>

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    public ArrayList<Integer> solution(int n, int s, int[] arr) {
        ArrayList<Integer> a = new ArrayList<>();
        for(int i=0; i<n; i++)
        {
            int tmp = arr[i];
            if(a.contains(tmp)) // HIT이라면...
            {
                int index = a.indexOf(tmp);
                a.remove(index); // 해당 인덱스 삭제
                a.add(tmp);
            }
            else // fault라면...
            {
                if (a.size() < s)
                    a.add(tmp);
                else // 크기가 똑같다면
                {
                    a.remove(0);
                    a.add(tmp);
                }
            }
        }
        Collections.reverse(a);
        return a;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);

        int s = sc.nextInt();
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i=0; i<n; i++)
            arr[i] = sc.nextInt();

        for(int x : T.solution(n,s,arr))
        {
            System.out.print(x+" ");
        }
    }
}

 

<정석 코드>

import java.util.Scanner;

public class Main {
    public int[] solution(int n, int s, int[] arr) {
        int[] cache = new int[s];
        for(int x : arr)
        {
            int pos= -1; // 인덱스 번호(위치)
            for(int i=0; i<s; i++) // cache 에서 탐색
            {
                if(x== cache[i])
                    pos = i; // HIT일 때
            }

            if (pos == -1) // MISS일 때
            {
                for (int i=s-1; i>=1; i--)
                {
                    cache[i] = cache[i-1];
                }
            }

            else // HIT일 때
            {
                for (int i=pos; i>=1; i--)
                {
                    cache[i] = cache[i-1];
                }
            }
            cache[0]=x;
        }
        return cache;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);

        int s = sc.nextInt();
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i=0; i<n; i++)
            arr[i] = sc.nextInt();

        for(int x : T.solution(n,s,arr))
        {
            System.out.print(x+" ");
        }
    }
}

 

5.  좌표 정렬(Comparable 구현)

Comparable 인터페이스에는 compareTo 메소드 하나가 선언되어 있다. 우리가 만약 Comparable을 사용하려 한다면, compareTo 메소드를 오버라이딩하여 사용해주어야 한다.

반면, Comparator를 보면 선언된 메서드는 다양하지만, 우리가 실질적으로 구현해야 하는 것은 compare(T o1, T o2)이다.

이들은 객체를 비교할 수 있도록 해준다. 둘의 차이는 무엇일까 ? 

 

Comparable은 자기 자신과 매개변수로 들어오는 객체를 비교하는 것이고,

Comparator은 자기 자신의 상태에 상관없이 매개변수로 들어오는 두 객체를 비교하는 것이다.

또한, Comparable은 lang 패키지에 있기 때문에 따로 import를 하지 않아도 되지만,

Comparator는 util 패키지에 있다.

 

이 문제에서는 compareTo에서는 음수값이 return되게 해야 한다. 즉, 자기 자신의 객체 값이 매개변수로 들어오는 객체의 값보다 작아야 하는 것이다.

 

이러한 개념을 미리 알고, 문제를 풀어보도록 하자.

---

N개의 평면상의 좌표(x, y)가 주어지면 모든 좌표를 오름차순으로 정렬하는 프로그램을 작성하세요.

정렬기준은 먼저 x값의 의해서 정렬하고, x값이 같을 경우 y값에 의해 정렬합니다.

 

입력

첫째 줄에 좌표의 개수인 N(3<=N<=100,000)이 주어집니다.

두 번째 줄부터 N개의 좌표가 x, y 순으로 주어집니다. x, y값은 양수만 입력됩니다.

 

출력

N개의 좌표를 정렬하여 출력하세요.

예시 입력 1 

5
2 7
1 3
1 2
2 5
3 6

예시 출력 1

1 2
1 3
2 5
2 7
3 6

<코드>

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

class Point implements Comparable<Point> {
    public int x,y;
    Point(int x, int y)
    {
        this.x=x;
        this.y=y;
    }
    @Override
    public int compareTo(Point o) // 정렬 기준 오버라이딩
    {
        if(this.x == o.x)
            return this.y-o.y; // 오름차순으로 정렬
        else
            return this.x-o.x;

        // 내림차순으로 하고 싶다면 아래와 같이 해주면 된다.
//        if(this.x==o.x)
//            return o.y-this.y;
//        else
//            return o.x-this.x;
    }
}
public class Main {

    public int[] solution(int n, int s, int[] arr) {
        int[] cache = new int[s];

        return cache;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        ArrayList<Point> arr = new ArrayList<>();
        for(int i=0; i<n; i++)
        {
            int x = sc.nextInt();
            int y = sc.nextInt();
            arr.add(new Point(x,y));
        }
        Collections.sort(arr);
        for(Point o : arr)
            System.out.println(o.x+ " "+ o.y);
    }
}

 

6. 이분검색

임의의 N개의 숫자가 입력으로 주어집니다.

N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면

이분검색으로 M이 정렬된 상태에서 몇 번째에 있는지 구하는 프로그램을 작성하세요. 단 중복값은 존재하지 않습니다.

 

입력

첫 줄에 한 줄에 자연수 N(3<=N<=1,000,000)과 M이 주어집니다.

두 번째 줄에 N개의 수가 공백을 사이에 두고 주어집니다.

 

출력

첫 줄에 정렬 후 M의 값의 위치 번호를 출력한다.

예시 입력 1 

8 32
23 87 65 12 57 32 99 81

예시 출력 1

3

<코드>

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public int solution(int n, int m, int[] arr) {
        int answer=0;
        Arrays.sort(arr);

        int lt=0, rt=n-1;
        while(lt<=rt)
        {
            int mid = (lt+rt)/2;
            if(arr[mid] == m)
            {
                answer=mid+1;
                break;
            }
            if(arr[mid] >m) rt=mid-1;
            else lt=mid+1;
        }
        return answer;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);

        int n= sc.nextInt();
        int m = sc.nextInt();
        int[] arr = new int[n];
        for(int i=0; i<n; i++)
            arr[i] = sc.nextInt();

        System.out.println(T.solution(n,m,arr));
    }
}

 

7. 뮤직비디오(결정알고리즘)

- 간단한 개념

Arrays.stream(배열 이름) : 배열을 순회하는 스트림 객체를 만들 수 있다.이것을 쓰게 되면 다양한 함수를 사용할 수 있다.예를 들어, 배열의 최소값을 int 형으로 받고 싶다면 다음과 같이 처리해주면 된다.

int lt = Arrays.stream(arr).max().getAsInt();

배열의 합을 구하고 싶을 때는 다음과 같이 써주면 된다. 이때, sum()은 해당 type에 자동으로 맞춰지기 때문에 위처럼 따로 getAsInt() 를 붙여주지 않아도 된다.

int rt = Arrays.stream(arr).sum();

 

- 문제

지니레코드에서는 불세출의 가수 조영필의 라이브 동영상을 DVD로 만들어 판매하려 한다.

DVD에는 총 N개의 곡이 들어가는데, DVD에 녹화할 때에는 라이브에서의 순서가 그대로 유지되어야 한다.

순서가 바뀌는 것을 우리의 가수 조영필씨가 매우 싫어한다. 즉, 1번 노래와 5번 노래를 같은 DVD에 녹화하기 위해서는

1번과 5번 사이의 모든 노래도 같은 DVD에 녹화해야 한다. 또한 한 노래를 쪼개서 두 개의 DVD에 녹화하면 안된다.

지니레코드 입장에서는 이 DVD가 팔릴 것인지 확신할 수 없기 때문에 이 사업에 낭비되는 DVD를 가급적 줄이려고 한다.

고민 끝에 지니레코드는 M개의 DVD에 모든 동영상을 녹화하기로 하였다. 이 때 DVD의 크기(녹화 가능한 길이)를 최소로 하려고 한다.

그리고 M개의 DVD는 모두 같은 크기여야 제조원가가 적게 들기 때문에 꼭 같은 크기로 해야 한다.

 

입력

첫째 줄에 자연수 N(1≤N≤1,000), M(1≤M≤N)이 주어진다.

다음 줄에는 조영필이 라이브에서 부른 순서대로 부른 곡의 길이가 분 단위로(자연수) 주어진다.

부른 곡의 길이는 10,000분을 넘지 않는다고 가정하자.

 

출력

첫 번째 줄부터 DVD의 최소 용량 크기를 출력하세요.

예시 입력 1 

9 3
1 2 3 4 5 6 7 8 9

예시 출력 1

17

힌트

설명 : 3개의 DVD용량이 17분짜리이면 (1, 2, 3, 4, 5) (6, 7), (8, 9) 이렇게 3개의 DVD로 녹음을 할 수 있다.

17분 용량보다 작은 용량으로는 3개의 DVD에 모든 영상을 녹화할 수 없다.

<코드>

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public int count(int[] arr, int capacity) // dvd 몇 장이 필요한지를 return 한다.
    {
        int cnt=1; // dvd 장 수(최소 1장부터 시작)
        int sum=0; // 현재 사용되고 있는 dvd에 몇 곡의 노래가 있는지를 의미함.
        for(int x : arr)
        {
            if(sum + x > capacity) // 한 장의 용량을 넘어가 버린다면...
            {
                cnt++;
                sum=x;
            }
            else sum+=x;
        }
        return cnt;
    }

    public int solution(int n, int m, int[] arr) {
        int answer=0;
        int lt = Arrays.stream(arr).max().getAsInt();
        int rt = Arrays.stream(arr).sum();

        while(lt<= rt)
        {
            int mid = (lt+rt)/2;
            if(count(arr, mid) <= m)
            {
                answer=mid;
                rt = mid-1; // 최적의 검색을 위해 다시 반복문 수행
            }
            else
                lt = mid+1;
        }
        return answer;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);

        int n= sc.nextInt();
        int m = sc.nextInt();
        int[] arr = new int[n];
        for(int i=0; i<n; i++)
            arr[i] = sc.nextInt();

        System.out.println(T.solution(n,m,arr));
    }
}

 

8. 마구간 정하기(결정알고리즘)

N개의 마구간이 수직선상에 있습니다. 각 마구간은 x1, x2, x3, ......, xN의 좌표를 가지며, 마구간간에 좌표가 중복되는 일은 없습니다.

현수는 C마리의 말을 가지고 있는데, 이 말들은 서로 가까이 있는 것을 좋아하지 않습니다. 각 마구간에는 한 마리의 말만 넣을 수 있고,

가장 가까운 두 말의 거리가 최대가 되게 말을 마구간에 배치하고 싶습니다.

C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가

최대가 되는 그 최대값을 출력하는 프로그램을 작성하세요.

 

입력

첫 줄에 자연수 N(3<=N<=200,000)과 C(2<=C<=N)이 공백을 사이에 두고 주어집니다.

둘째 줄에 마구간의 좌표 xi(0<=xi<=1,000,000,000)가 차례로 주어집니다.

 

출력

첫 줄에 가장 가까운 두 말의 최대 거리를 출력하세요.

예시 입력 1 

5 3
1 2 8 4 9

예시 출력 1

3

< 코드 >

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public int count(int[] arr, int dist)
    {
        int cnt=1; // 말의 마릿 수
        int ep = arr[0];
        for(int i=1; i<arr.length; i++)
        {
            if(arr[i] - ep >= dist)
            {
                cnt++;
                ep=arr[i];
            }
        }
        return cnt;
    }

    public int solution(int n, int c, int[] arr) {
        int answer=0;
        Arrays.sort(arr);
        int lt=1;
        int rt = arr[n-1];
        while(lt <= rt)
        {
            int mid = (lt+rt)/2;
            if(count(arr, mid) >= c)
            {
                answer=mid;
                lt = mid+1;
            }
            else
                rt = mid-1;
        }

        return answer;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);

        int n= sc.nextInt();
        int c = sc.nextInt();
        int[] arr = new int[n];
        for(int i=0; i<n; i++)
            arr[i] = sc.nextInt();

        System.out.println(T.solution(n,c,arr));
    }
}