BEYOND SW 캠프 15기 / 8주차 회고

TIL(This week I Learned)

1. 정렬 알고리즘
2. 탐색 알고리즘
3. 탐욕 알고리즘
4. Dynamic Programming

Facts

1. 알고리즘을 활용한 코딩 테스트 문제 풀이

새로운 알고리즘을 배울 때마다 해당 알고리즘을 적용할 수 있는 코딩 테스트 문제를 풀었다. 문제 에 적용해야 하는 알고리즘이 지정된 상태에서 풀다보니 많이 어렵지 않다고 느꼈던 것 같다. 하지만 막상 새로운 문제가 주어졌을 때 곧바로 어떤 알고리즘을 적용하는 것이 좋을 지 생각이 나지 않았다. 수업시간 내에 주어진 문제를 해결하는 것도 물론 중요하지만 각각의 알고리즘에 대해서 이해를 하고나서 문제에 적용시켜야 방법이 주어지지 않았을 때도 문제를 해결할 수 있을 것 같다.

Findings

이전에 백준 코딩테스트에서 풀었던 문제를 수업시간에 새로운 알고리즘을 적용해서 해결하는 법을 배웠다.

문제 ) 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다.
봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.
상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

풀이 방법 1) - 내가 푼 방법

1. 문제에서 설탕의 무게 N은 3 <= N <= 5000 으로 주어진다. 따라서 3 or 5로 나눌 수 없는 값인 4, 7을 입력받았을 때 설탕 봉지의 개수를 담는 변수 count의 값을 -1로 변경한다.

2. 봉지의 수를 최소화하려면 5kg 설탕으로만 배달을 해야 한다. 그러므로 입력받은 N이 5로 나누어 떨어질 경우 N을 5로 나눈 값을 출력한다.

3. N을 5로 나누었을 때 그 나머지가 1이거나 3이면, 5n + 6 or 5(n+1) + 3 이므로 N을 5로 나눈 값에 +1을 한 값을 출력한다.

4. N을 5로 나누었을 때 그 나머지가 2이거나 4이면, 5n + 12 or 5(n+1) + 9 이므로 N을 5로 나눈 값에 +2 한 값을 출력한다.

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());
    int count = 0;
    /* 3 or 5로 절대 나눠지지 않는 경우 */
    if (n == 4 || n == 7) count--;
    /* 무게가 5키로 짜리로만 채울 수 있는 경우 */
    else if (n % 5 == 0) count = n / 5;
    /* 5의 배수 + 1 or 5의 배수 + 3 */
    else if (n % 5 == 1 || n % 5 == 3) count = (n / 5) + 1;
    /* 5의 배수 + 2 or 5의 배수 + 4 */
    else if (n % 5 == 2 || n % 5 == 4) count = (n / 5) + 2;
    System.out.println(count);
}

풀이 방법 2) - 탐욕 알고리즘 적용

매 단계마다 최적화된 선택을 반복해서 전체 문제의 답을 구하는 알고리즘을 탐욕 알고리즘, greedy 라고 한다.

1. 무게가 5kg으로 나누어 떨어지지 않는 경우 3kg 짜리 봉지의 수를 담는 변수 count에 1을 더하고, 주어진 무게 N에서는 3kg를 뺀다.

2. 만약에 N이 5로 나누어 떨어질 경우 N을 5로 나누고 그 값에 count를 더해 반환한다.

3. N이 0이 될 때까지 순환이 끝나지 않았을 경우 count를 반환한다.

static int count ;
public static int solution(int n) {
    count = 0;

    while(true) {
        /* 5kg 봉지로만 처리 */
        if(n % 5 == 0) return n / 5 + count;
        else if(n < 0) {
            return -1;
        } else if(n == 0) { // 3키로 봉지만 해결
            return count;
        }

        /* 5 키로로 나누어 떨어지지 않는다면 3키로 봉지 사용 */
        n = n - 3;
        count++;
    }
}

풀이 방법 3) - dynamic programming

DP - Bottom up 방식을 적용해 문제를 해결한다.

주어진 문제를 부분으로 나눠 문제를 작은 문제부터 순차적으로 해결해 그 결과를 테이블(dp[])에 저장한다.(Tabluation)

1. 1 ~ 주어진 무게 N키로에 필요한 봉지의 개수를 저장하기 위해 n+1 크기의 배열을 선언한다.

2. 가장 적은 개수가 필요하므로 배열의 모든 값을 Infinity 값으로 초기화한다.

3. 무게가 6kg 일 때부터 Nkg 일 때까지 반복하면서 현재 무게 보다 3kg 적을 때와 5kg 적을 때의 봉지 수를 비교해 최소값을 찾고 해당 봉지수에 +1 한 값을 저장한다.

4. 반복문이 종료된 후 인덱스가 n인 배열에 저장된 봉지의 개수가 Infinity일 경우 3 or 5로 나눠지지 않거나 두 수의 각각의 곱의 합으로 구할 수 없으므로 -1을 반환하고, 값이 있을 경우 그 값을 반환한다.

static final int INF = 9999;

public static int solution(int n) {

    /* dp 배열의 인덱스 값이 곧 해당 무게의 봉지 개수가 될 수 있도록 저장한다. */
    int[] dp = new int[n + 1];

    /* 배열의 모든 값 초기화 */
    Arrays.fill(dp, INF);   // 값 확인을 위한 초기화

    /* n으로 전달되는 숫자가 작으면 인덱스 범위를 벗어날 수 있기 대문에
    *  초기값 설정 시 확인하고 반복문은 그 뒤부터 전개한다. */

    if(n >= 3) dp[3] = 1;
    if(n >= 5) dp[5] = 1;

    for(int i = 6; i <= n; i++) {
        // 3 이전 또는 5 이전 인덱스 봉지 개수 +1
        // INF가 아닌 값으로 처리하기 위해 Math.min()으로 확인
        dp[i] = Math.min(dp[i-3], dp[i-5]) + 1;
    }

    return dp[n] >= INF ? -1 : dp[n];
}

같은 문제에도 다양한 알고리즘을 적용할 수 있다. 실제 코딩 테스트 도중에는 성능 테스트가 불가능하지만 공부할 때 어떤 방식을 적용하는 게 더 높은 성능을 내는지 파악해서 실제 문제에도 적용할 수 있도록 해야 겠다.

Future

코딩 테스트를 통과하려면 다양한 문제를 풀어보면서 알고리즘에 대한 이해도를 높여야 하므로 동기들과 알고리즘 스터디를 진행하기로 했다. 문제 해결에 초점을 맞추기 보다는 이해해서 응용 하는데에 초점을 맞춰서 차근차근 풀어나가야 겠다.

For Me🍀

천 리 길도 한 걸음부터