📚 문제

개미 전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려 한다. 메뚜기 마을엔 여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져 있다. 각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다. 이 때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식랴창고가 공격받으면 바로 알아챌 수 있다. 따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다. 개미 전사를 위해 식량 창고 N개에 대한 정보가 주어질 때 얻을 수 있는 식량의 최댓값을 구하여라

📝 문제 해설

왼쪽부터 차례대로 식량창고를 털지 안 털지를 결정하는 경우와 특정한 i번째 식량창고에 대해서 털지 안 털지의 여부를 결정할 때, 단 2가지 경우에 대해서만 확인하면 된다.

1. (i-1)번째 식량창고를 털기로 결정한 경우 현재의 식량창고를 털 수 없다.
2. (i-2)번째 식량창고를 털기로 결정한 경우 현재의 식량창고를 털 수 있다.

따라서 1)과 2) 중에서 더 많은 식량을 털 수 있는 경우를 선택하면 된다. 여기서 알아둘 점은 왼쪽부터 (i-3)번째 이하의 식량창고에 대해서는 고려할 필요가 없다. 왜냐하면 한 칸 이상 떨어진 식량창고는 항상 털 수 있기 때문이다.  따라서 i번째 식량창고에 있는 식량의 양이 ki라고 했을 때 점화식은 다음과 같다.

💻 코드

package dynamicProgramming;

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

public class dp02 {
    public static int[] d = new int[100];

    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();
        }

        d[0] = arr[0];
        d[1] = Math.max(arr[0], arr[1]);
        for (int i = 2; i < n; i++) {
            d[i] = Math.max(d[i-1], d[i-2] + arr[i]);
        }

        System.out.println(d[n-1]);
    }
}

https://www.acmicpc.net/problem/2579

📚 문제

계단 오르는 데는 다음과 같은 규칙이 있다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.
각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오. 따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.
각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

📝 문제 해설

n번째의 계단을 밟는 경우의 수

1. (n-3)번째 계단을 밟고 (n-1)번째 계단을 밟는 경우
2. (n-2)번째 계단을 밟는 경우

규칙 2에 의해서 연속해서 3개의 계단을 밟는 것은 불가능하기 때문에 두가지 경우만 고려하면 된다.

테이블 정의

score[i] : 해당 계단의 위치까지의 최고 점수값 배열

점화식 세우기

마지막 칸의 계단은 무조건 밟아야 하므로 위의 경우 2가지 중 큰 값 + 현재 계단의 값을 더한 값이 해당 칸의 score가 된다.
따라서, score[n] = Math.max(score[n-3] + stair[n-1], score[n-2]) + stair[n]

초기값 정의

1번과 2번, 3번 계단의 경우는 n-3이 존재하지 않기 때문에 값을 직접 정의해줘야함

score[1] = stair[1];
score[2] = stair[1] + stair[2];
score[3] = Math.max(stair[1], stair[2]) + stair[3];

💻 코드

import java.util.Scanner;

public class BOJ2579 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        int[] stair = new int[301];
        int[] score = new int[301];
        for (int i = 1; i <= N; i++)
            stair[i] = sc.nextInt();

        score[1] = stair[1];
        score[2] = stair[1] + stair[2];
        score[3] = Math.max(stair[1], stair[2]) + stair[3];

        for (int n = 4; n <= N; n++) {
            score[n] = Math.max(score[n - 3] + stair[n - 1], score[n - 2]) + stair[n];
        }

        System.out.println(score[N]);
    }
}

https://www.acmicpc.net/problem/10989

📚 문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.
첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.
수의 범위가 작다면 카운팅 정렬을 사용하여 더욱 빠르게 정렬할 수 있습니다.

📝 문제 해결

수 정렬하기2와 비슷한 문제지만 메모리 제한이 8MB로 더 낮다.
따라서 문제 설명에 나와있는 카운팅 정렬(계수 정렬)을 사용해주었다.

카운팅 정렬(계수 정렬)이란?  🤔

💻 코드

import java.io.*;

public class BOJ10989 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int N = Integer.parseInt(br.readLine());

		int count[] = new int[10001];
		for(int i=0; i<N; i++) {
			count[Integer.parseInt(br.readLine())]++;
		}

		for(int i=0; i<count.length; i++) {
			while(count[i] > 0) {
				sb.append(i).append('\n');
				count[i]--;
			}
		}

		System.out.println(sb);
	}
}

기수 정렬  : 데이터가 모두 k 자릿수 이하의 자연수인 특수한 경우에 사용 가능

우선 가장 낮은 자릿수만 가지고 모든 수를 재배열(정렬)한다. 그런 다음 가장 낮은 자릿수는 잊어버리고 같은 방법으로 더 이상 자릿수가 남지 않을 때까지 계속한다.

시간 복잡도 : O(N)

계수 정렬  : 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능

⚠️  계수정렬은 직접 데이터의 값을 비교한 뒤에 위치를 변경하며 정렬하는 방식 (비교 기반의 정렬 알고리즘)이 아니다.

1) 가장 큰 데이터 + 1 크기의 모든 원소가 담길 수 있는 하나의 리스트를 생성

2)  처음에는 리스트의 모든 데이터가 0이 되도록 초기화한다.

3) 그 다음 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가

4) 입력 배열의 각 원소에 대해 count 리스트에 어느 인덱스에 들어가야하는지 조회

( 참고 애니메이션 : https://www.cs.miami.edu/home/burt/learning/Csc517.091/workbook/countingsort.html )

package sorting;

public class sorting04 {
    public static final int MAX_VALUE = 9;

    public static void main(String[] args) {
        int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2};
        int[] cnt = new int[MAX_VALUE + 1];

        for (int i = 0; i < arr.length; i++) {
            cnt[arr[i]] += 1; // 각 데이터에 해당하는 인덱스의 값 증가
        }
        for (int i = 0; i <= MAX_VALUE; i++) {
            for (int j = 0; j < cnt[i]; j++) {
                System.out.print(i + " ");
            }
        }
    }
}

시간 복잡도 : O(N+K)

데이터의 개수 : N, 데이터 중 최대값의 크기 : K

리스트의 각 인덱스에 해당하는 값들을 확인할 때 데이터 중 최댓값의 크기만큼 반복을 수행해야 함

따라서 데이터의 범위만 한정되어 있다면 효과적으로 사용할 수 있으며 항상 빠르게 동작한다.

현존하는 정렬 알고리즘 중에서 기수 정렬과 더불어 가장 빠름

공간 복잡도 

계수 정렬은 때에 따라서 심각한 비효율성을 초래함. (ex. 데이터 수는 적으나 최소 최대값의 차이가 클 때)

동일한 값을 가지는 데이터가 여러 개 등장할 떄 적합 (ex. 100점 맞은 학생이 여러 명인 성적 정렬)

반면에 앞서 설명한 퀵 정렬은 일반적인 경우에서 평균적으로 빠르게 동작하기 때문에 데이터의 특성을 파악하기 어렵다면 퀵 정렬을 이용하는 것이 유리함

즉, 계수 정렬은

1. 데이터의 크기가 한정되어 있고

2. 데이터의 크기가 많이 중복되어 있을 때 유리

정렬 라이브러리

package sorting;

public class sorting04 {
    public static final int MAX_VALUE = 9;

    public static void main(String[] args) {
        int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2};
        int[] cnt = new int[MAX_VALUE + 1];

        for (int i = 0; i < arr.length; i++) {
            cnt[arr[i]] += 1; // 각 데이터에 해당하는 인덱스의 값 증가
        }
        for (int i = 0; i <= MAX_VALUE; i++) {
            for (int j = 0; j < cnt[i]; j++) {
                System.out.print(i + " ");
            }
        }
    }
}

정렬 라이브러리는 항상 최악의 경우에도 O(NlogN)을 보장한다.

사실 우리가 직접 퀵 정렬을 구현할 때보다 더욱더 효과적임

(문제에서 별도의 요구가 없이 단순 정렬해야하는 경우  > 기본 정렬 라이브러리 사용

데이터의 범위가 한정되어 있으며 더 빠르게 동작해야 할 때 > 계수 정렬)

📚 실전문제 ) 위에서 아래로

수열을 내림차순으로 정렬하는 프로그램을 만드시오

package sorting;

import java.util.*;

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

        int n = sc.nextInt();

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

        Arrays.sort(arr, Collections.reverseOrder());

        for(int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

컬렉션이란? 자바에서 자료구조를 표현하는 인터페이스

Collection의 자료형에는 기본 타입은 올 수 없다.

더보기

자바의 자료형은 크게 기본 타입(primitive type)과 참조 타입(reference type)으로 나누어진다.

-기본 타입 : char, int, float, double, boolean 등

- 참조 타입 : String, Integer, Boolean, List 등 클래스 및 인터페이스

일반적으로 코딩 테스트에서 정렬 알고리즘이 사용되는 경우
1. 정렬 라이브러리로 풀 수 있는 문제 : 단순히 정렬 기법을 알고 있는지 물어보는 문제
2. 정렬 알고리즘의 원리에 대해서 물어보는 문제 : 선택/삽입/퀵 정렬 등의 원리를 알아야함
3. 더 빠른 정렬이 필요한 문제 : 퀵 정렬 기반의 정렬 기법으로는 풀 수 없으며 계수 정렬 등의 다른 정렬 알고리즘을 이용하거나 문제에서 기존에 알려진 알고리즘의 구조적인 개선을 거쳐야 풀 수 있다.