임시) 그리디

그리디 알고리즘

 

• 그리디를 썼을 때 최적의 해를 도출해 낼 수 있는 문제가 있고 아닌 게 있음
  • ⇒ 이 문제에 그리디 쓸 수 있는지 판단해야 함
• 뭔가 문제 보니까 최소, 최대를 구하는 문제가 많네
• 그리디 알고리즘은 또 우선순위 큐와 자주 쓰이네
  • 또는 정렬하는 로직이 자주 쓰이네

 

문제 32, 동전 개수의 최솟값 구하기

 

• 그리디 썼을 때 반례 안 생기는 지 한번 따져봐야 함
  • (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)
  • 즉 2 4 8처럼 배수 관계란 소리 → 그냥 현재 상태에서 가장 큰 동전부터 차례대로 나눠주면 되는 게 성립이 되는 것임
  • 반례) 동전 1 6 7 있고, 금액 12를 맞춘다면
    • 그리디 알고리즘 → 7이 1개, 1이 5개
    • 그러나 동전 최소값은 → 6이 2개
    • 배수 형태가 아니면 이런 반례가 생김

 

문제 33, 카드 정렬하기

• 카드 개수가 작은 묶음부터 순서대로 합치는 것이 전체 비교 횟수를 줄일 수 있는 방법임
  • 현재 데이터 중 가장 작은 카드의 개수를 가진 묶음 2개를 뽑아야 하고, 이 2개를 기준으로 합친 새 카드 묶음을 다시 데이터에 넣고 정렬해야 함
  • 즉 데이터의 삽입 삭제, 정렬이 자주 일어난다는 뜻 ⇒ 우선순위 큐를 이용해야 함

 

문제 34, 수를 묶어서 최댓값 만들기

• 가능한 큰 수끼리 묶어야 결과값이 커진다는 걸 알 수 있음
• 음수끼리 곱하면 양수로 변하는 성질을 추가로 고려
• PriorityQueue<Integer> plusPq = new PriorityQueue<>(Collections.reverseOrder());
  • Collections.reverseOrder() 이런 게 있구나, 내림차순으로 정렬되도록 하는 것
• plusPq.size()

 

문제 35, 회의실 배정하기

• 현재 회의의 종료 시간이 빠를수록 → 다음 회의와 겹치지 않게 시작하는 데 유리함
  • ⇒ 그렇기에 종료 시간이 빠른 순서대로 정렬해 겹치지 않는 회의실을 적절하게 선택하면 됨

Arrays.sort(A, new Comparator<int[]>() {
      @Override
      public int compare(int[] S, int[] E) {
        if (S[1] == E[1]) { // 종료 시간이 같을 경우
          return S[0] - E[0];
        }
        return S[1] - E[1];
      }
    });

 

문제 36, 최솟값 만드는 괄호 배치

• 가장 작은 최솟값을 만들기 위해서 가능한 큰 수를 빼야 함
  • 수식이 더하기와 빼기로만 이뤄져 있기에,
  • 더하기에 해당하는 부분에 괄호를 쳐서 먼저 모두 계산 후 빼기를 실행하면 문제 해결됨
•  String[] str = example.split("-");
  • "55-40+55" 입력받으면 -> ["55", "45+55"] 문자열 배열을 반환
•  String temp[] = a.split("[+]");
  • a.split("+")는 에러남
  • 그냥 써도 되는 부호: ! # % & @ ` ' : ; - , . < > ~ 
  • []로 씌우거나 앞에 \\를 붙여야 하는 게 있음 => a.split("[+]") or a.split("\\+")