• 032 동전 개수 구하기
  • 단위 동전부터 최대한 많이 사용하는 것이 최소 동전 개수를 구하는 가장 효율적인 방법
  • 그리디 알고리즘의 핵심: 현재 상태에서 가장 최적인 선택을 반복해서 전체 문제의 최적해를 찾음
  1. 큰 금액 동전부터 탐색
  2. 해당 동전을 몇 개 쓸 수 있는지 판단 → k // coin
  3. 금액 차감 → k -= (coin * 사용개수)
  4. 동전 개수 누적
• 033 카드 정렬하기
  • 그리디 + 우선순위 큐
    • 매번 가장 작은 두 묶음을 선택해서 합치기
    • 두 묶음을 합친 후 다시 우선순위 큐에 넣는다
    • 이 과정을 묶음이 1개 남을 때까지 반복
• 034 수를 묶어서 최대값 만들기
  • 수들을 분류
    • 양수 중 1을 제외한 수 (곱하는 게 이득)
    • 1 (곱하지 말고 더하는 게 이득)
    • 음수
    • 0
  • 처리

    • 양수는 내림차순으로 정렬 후 2개씩 묶어서 곱함

    • 음수는 오름차순으로 정렬 후 2개씩 묶어서 곱함

      → 음수 * 음수 = 양수 이므로 이득

      → 음수 개수가 홀수면 1개 남는데 0이 있으면 곱해서 소거

    • 1은 무조건 더하기

  1. 수 입력 받기
  2. 우선순위 큐(힙) 두 개 사용
     • plusPQ: 양수 저장 (내림차순)
     • minusPQ: 음수 저장 (오름차순)
  3. 각각 2개씩 꺼내서 곱하고 더하기
  4. 1은 개수만큼 그대로 더함
  5. 음수 남은 게 있으면 0 있으면 소거 아니면 더함
• 035 회의실 배정하기
  • 그리디 알고리즘 사용
  • 끝나는 시간이 빠른 회의를 우선적으로 선택 (종료 시간 기준으로 오름차순 정렬)
  • 회의를 하나 선택하면 그 회의가 끝나는 시간 이후에 시작하는 회의 중에서 다시 선택
  1. 회의를 종료 시간 기준으로 정렬
  2. 현재 시각을 end로 설정 (처음에는 -1)
  3. 회의를 순회하면서 시작시간 ≥ end 이면 해당 회의를 선택하고 end를 업데이트
  4. 선택한 회의 수를 카운트

**추가 문제: 백준 1202번: 보석 도둑 (골드2), 백준 1339번: 단어 수학 (골드4), 백준 2512번

• 036 최솟값을 만드는 괄호 배치 찾기
  • "-" 기준으로 나누기
    • 입력 문자열을 기준으로 split()
  • 나뉜 부분 덧셈 처리
    • 각 나뉜 문자열 덩어리에서 +로 split하여 덧셈 수행
  • 결과 처리
    • 첫 번째 덩어리는 그냥 더하고
    • 나머지는 모두 뺌