[코테 알고리즘] 그리디 / 관련 문제

본 글은 "나동빈"님의 [이것이 코딩 테스트다]를 참고하여 작성하였으며, 필자가 직접 문제를 풀며 관련된 문제들을 찾아 정리하였습니다.

시리즈 보기
[코테 알고리즘] 파이썬 기본 / 관련 문제
[코테 알고리즘] 파이썬 주요 라이브러리 / 관련 문제
[코테 알고리즘] 그리디 / 관련 문제
[코테 알고리즘] 구현 / 관련 문제
[코테 알고리즘] DFS, BFS / 관련 문제
[코테 알고리즘] 정렬 / 관련 문제
[코테 알고리즘] 다이나믹 프로그래밍 / 관련 문제
[코테 알고리즘] 최단 경로 / 관련 문제
[코테 알고리즘] 그래프 이론 / 관련 문제

 

그리디

• 현재 상황에서 지금 당장 좋은 것만 고르는 방법
• 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구
  • 단순히 현재 상황에서 가장 좋아보이는 것만 골라도 최적의 해가 나오는지 파악
• 가장 큰 순서대로 / 가장 작은 순서대로 와 같은 기준 제시하기도
  • 정렬과 함께 출제 많음
• 문제의 해법을 찾았을 때, 그 해법이 정당한지 검토 필요

그리디 알고리즘에서는 문제 풀이를 위한 최소한의 아이디어를 떠올리고
이것이 정당한지 검토할 수 있어야함

 

알고리즘 고민 절차

1. 그리디 알고리즘을 의심하면서, 문제 해결할 탐욕적 해결법이 있는지 고민
2. 방법이 없다면, DP나 그래프 알고리즘으로 고민

 

문제

행복 유치원

 

[백준] 13164번 파이썬 - 그리디, 정렬

• 정렬의 기준 고민해야한다.

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
kids = list(map(int, input().split()))

kids.sort()

diff = [0] * (n-1)

for i in range(n-1):
    diff[i] = kids[i+1] - kids[i]

diff.sort(reverse=True)

print(sum(diff[k-1:]))

 

회의실 배정

[백준] 1931번 파이썬 - 그리디

• 정렬의 기준 고민해야한다.

import sys
input = sys.stdin.readline

n = int(input())

table = [[0]*2 for _ in range(n)]

for i in range(n):
    start, end = map(int, input().split())
    table[i][0] = end
    table[i][1] = start

table.sort()
cnt = 0
end = -1

for i in range(n):
    if table[i][1] >= end:
        end = table[i][0]
        cnt += 1

print(cnt)