그리디 알고리즘을 쌈싸먹어 보자!

그리디 알고리즘

특징

• 결정해야 할 때 그 순간 제일 좋다고 생각되는 걸 선택하면서 답을 찾는 알고리즘
  • 졸리면 자고~ 배고프면 밥 먹고~
• 즉 그 순간엔 최적이라도, 최종적으로는 답이 최적이 아닐 수 있다

유형

• 거스름돈 문제
  • 동전도 지페도 아주 많을 때, N원을 최소 개수의 지폐, 동전을 이용해서 거슬러주려면 어떻게 해야 하는가?
    • 가장 큰 액면가를 가진 지폐 / 동전부터 거슬러주자!
• 즉, 지금 순간에 제일 최적인 걸 골라야 할 때 사용하는 알고리즘...! 🤔

문제 예제 (1) : 백준 동전 0

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

내 풀이

• 가치의 합은 최대인데, 사용해야 하는 동전 개수는 최소
  • 즉 K원을 만들기 위해 숫자를 쪼갰을 때 가장 적게 쪼갤 수 있는 기준(배수)를 찾아야 한다.
• 주어진 동전의 가치가 오름차순이니까, 뒤에서부터 내려와야 한다.
  • 뒤에서 내려오면서 만약 현재 동전 가치가 K보다 크다면 넘기고, 작다면 쪼개는 과정을 반복하면 될 듯?

    // DESCRIBE: 동전 개수 찾기
    for (int i = N-1; i >= 0; i--) {
      if (array[i] <= K) {
        answer += (K/array[i]);
        K %= array[i];
      }
    }

• 옹ㅎㅎ 맞았다
  

해설

• (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)
  • 요 조건 덕분에 그리디 알고리즘이 성립하게 된다
  • 돈을 1원짜리로 전부 바꾼 다음, 그 다음 동전의 가치가 항상 이전 동전의 배수를 만드는지 확인해서 항상 성립하는지 확인하자.

문제 예제 (2) : 백준 회의실 배정

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

내 풀이

• 이 문제가 그리디 유형인걸 어떻게 알 수 있을까?
  • N개 중 어떤 것을 선택하느냐에 따라 결과가 달라지는 문제다.
  • 즉 일종의 거스름돈 문제인거지..!
    • 거스름돈은 최대 액면가를 가진 동전/지폐부터 골랐다면, 이 문제에서는 어떤 회의를 우선적으로 골라야 할까?
      • 평범하게 생각해보면 회의 시간이 짧거나, 일찍 시작하는 회의를 고르면 될거다. 하지만 시작 시간을 기준으로 잡으면 안된다. 다음 회의랑 겹칠 수 있으니까!
        • (1 4, 3 5, 0 6이 있을 때 시작 시간 기준으로 잡으면 1 4, 0 6이지만 종료 시간을 고려하면 겹치는 회의다)
        • 따라서 종료 시간을 기준으로 잡고, 시작 시간이 앞에서 잡은 종료 시간보다 같거나 큰 경우를 우선적으로 고르면 될거다
      • 위의 흐름에서, 회의를 선택하는 기준은 (1) 회의 종료 시간이 빠르면서 (2) 전체 회의 시간이 짧은 친구를 우선적으로 골라내야 한다.
• 그럼 어케 풀까?
  • 일단 회의 종료 시간을 기준으로 입력 회의들을 오름차순 정렬한다.
  • 첫번째 인덱스부터 시작해서, 만약 다음 인덱스의 시작 시간이 이전 인덱스의 종료 시간보다 같거나 큰 경우만 카운트한다.
    • 이렇게 하면, 만약 시작 시간이 동일하더라도 종료 시간이 더 빠른 친구가 먼저 선택되니까 굳이 회의 전체 시간을 따로 계산해 줄 필요가 없다!
      • 테케에서 (5,7) (5,9)가 해당. 시작 시간이 동일하다고 가정했을 때, 종료 시간을 기준으로 오름차순 정렬했으니 자연스럽게 전체 회의 시간이 짧은 (5, 7)이 카운트된다.
        

    // DESCRIBE: 종료 시간 기준으로 오름차순 정렬. 만약 동일하다면 시작 시간 오름차순으로 
    Arrays.sort(array, (o1, o2) -> {
      if(o1[1] == o2[1]) {
        return o1[0] - o2[0];
      }else {
        return o1[1] - o2[1];
      }
    });

    // DESCRIBE: 현재 인덱스의 시작 시간이 이전 인덱스의 종료 시간보다 크거나 같다면 카운트
    int prevEndTime = array[0][1];
    for (int i = 1; i < N; i++) {
      if (array[i][0] >= prevEndTime) {
        result += 1;
        prevEndTime = array[i][1];
      }
    }

• 맞았다! (2차원 배열 정렬 연습 좀 해야할듯^^^^)
  

해설

• 오 회의 시간이 짧은 경우는 아예 기준이 될 수 없구나..!
  • 기준 세우고 반례 고민하는 연습을 해야 할 것 같다.
    • 나는 풀 때 어? 정렬해두고 보니 회의 시간 짧은건 따로 계산 안해도 되네? 하고 풀었는데, 사실은 아예 고려하면 안되는 대상이었던 것..! 🤔
    • 이건 맞은게 아니라 틀렸다고 봐야 할 것 같다. 걍 얻어 걸린거니까... 😇

문제 예제 (3) : 백준 ATM

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

내 풀이

• 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값 = 누적합이 최소
  • 즉 돈을 뽑는데 걸리는 시간이 작은 사람 순으로 고르면 된다.
    • ex. 3 1 4 3 2 -> 3 + (3+1) + (3+1+4) + (3+1+4+3) + (3+1+4+3+2) = 39
    • ex. 1 2 3 3 4 -> 1 + (1+2) + (1+2+3) + (1+2+3+3) + (1+2+3+3+4) = 32
• 입력값을 오름차순으로 정렬하고, 이후 누적합을 구하자.

    // DESCRIBE: 오름차순 정렬
    Arrays.sort(array);

    // DESCRIBE: 누적합 구하기
    int waitTime = 0;
    int totalWaitTime = 0;
    for (int i = 0; i<N; i++) {
      waitTime += array[i];
      totalWaitTime += waitTime;
    }

• 맞았다 ^~^
  

해설

• 오름차순 = 비내림차순으로 정렬! 동일한 접근
  • (증명) 오름차순으로 정렬하고 결과값(S)을 구했을 때, 인덱스를 바꿔서 다시 계산(S')해보면 값이 같거나 커지게 된다.
  • (증명) S-S' = (i-j)(pj-pi)
  • (i-j)가 <= 0 이므로 항상 음수가 된다. 즉 S'는 언제나 S보다 같거나 크다.
    • 따라서 오름차순으로 정렬하는게 최적해가 된다.
• 우억 이렇게 증명할 생각은 안하고 그냥 냅다 응 당연히 오름차순이지~ 하고 풀었는데.. 이렇게 풀면 이제 실전에서 테케에 갈려나가는거겠지?! 🔨
  • 구상한 풀이를 먼저 증명한 후 구현하는 연습이 필요하다! 그냥 이럴 것 같아~ 하고 풀지 말자!