직접 풀어보자! 그리디 5문제

안녕, 나 코딩냥이다냥! 오늘 문제는 코드가 짧다냥. 다섯 개 다 열 줄 안쪽으로 끝난다냥.

그래서 더 조심해야 한다냥. 짧은 코드가 조용히 틀리기 때문이라냥. 답이 그럴듯하게 나오는데 기준이 잘못됐으면 알아채기 어렵다냥.

그리디 문제를 풀 때 순서

무엇을 기준으로 고를지 정한다 — 보통 정렬 기준이라냥
왜 그게 이득인지 한 문장으로 말해본다
말이 안 되면 다른 기준을 찾는다

2번을 건너뛰면 안 된다냥. 짧은 코드를 다 짜고 나서 기준이 틀렸다는 걸 알면 처음부터 다시라냥.

미션 1동전 거스름돈15분

동전으로 k 원을 만드는 최소 개수를 구한다냥.

문제 풀러 가기

큰 동전부터 최대한 쓴다냥. 나눗셈과 나머지로 한 번에 처리된다냥.

coins.sort(reverse=True)

cnt = 0
for c in coins:
    cnt += k // c     # 이 동전을 몇 개 쓸 수 있냥
    k %= c            # 남은 금액이라냥

하나씩 빼면서 세면 k 가 1억일 때 시간이 모자란다냥. 나눗셈으로 한 번에 처리하자냥.

동전이 정렬되어 주어지지 않는다냥.

공개된 두 예시 중 하나는 작은 것부터, 하나는 큰 것부터 들어온다냥. 직접 정렬하지 않으면 하나는 맞고 하나는 틀린다냥.

확인이 문제가 그리디로 풀리는 이유라냥

문제에 "큰 동전은 그보다 작은 동전의 배수" 라고 적혀 있다냥. 그 조건이 있어서 큰 것부터 집어도 손해가 안 나는 거라냥.

강의 3단계에서 본 1, 3, 4 동전에는 그 조건이 없었다냥. 그래서 6원을 만들 때 그리디가 3개, 정답이 2개로 갈렸다냥.

조건을 확인하고 그리디를 쓰는 습관을 여기서 들이자냥.

미션 2ATM 줄 세우기15분

모두가 기다린 시간의 합을 가장 작게 만든다냥.

문제 풀러 가기

짧은 사람부터 세운다냥. 앞자리일수록 여러 번 더해지기 때문이라냥.

times.sort()

run = 0
total = 0
for t in times:
    run += t          # 이 사람 차례가 끝난 시각이라냥
    total += run      # 그게 이 사람이 기다린 시간이라냥

변수가 두 개인 게 헷갈릴 수 있다냥. run 은 한 사람의 대기 시간, total 은 전부 합친 값이라냥.

정렬을 빼먹으면 틀린다냥.

정렬 없이도 코드는 잘 돌아가고 그럴듯한 숫자가 나온다냥. 그래서 더 위험하다냥. 숨겨진 테스트가 이걸 잡는다냥.

미션 3로프로 들어올리기20분

로프를 골라 병렬로 이어서 최대 중량을 든다냥.

문제 풀러 가기

핵심k개를 쓰면 가장 약한 로프가 기준이라냥

로프 k개로 무게 w 를 들면 하나당 w / k 를 버텨야 한다냥. 그러니 그중 가장 약한 로프가 견딜 수 있는 만큼만 들 수 있다냥.

가장 약한 게 x 라면 들 수 있는 무게는 x × k 라냥.

그럼 어떤 k개를 고르냥? 튼튼한 것부터 k개를 고르는 게 항상 이득이라냥. 그래야 그중 가장 약한 게 최대가 된다냥.

그러니 내림차순으로 정렬한 뒤, k 를 1부터 n 까지 다 해보면 된다냥.

ropes.sort(reverse=True)

best = 0
for i, w in enumerate(ropes):
    best = max(best, w * (i + 1))

i 번째까지 썼다는 건 i + 1 개를 썼다는 뜻이고, 그중 가장 약한 게 w 라냥. 정렬해뒀으니 그렇다냥.

흔한 두 가지 오답이라냥.

가장 튼튼한 로프 하나만 쓰기 — 여러 개를 쓰면 더 들 수 있다냥
로프를 전부 다 쓰기 — 약한 로프 하나가 전체를 끌어내린다냥

공개된 예시 10 15 가 첫 번째를 바로 잡는다냥. 답이 15 가 아니라 20 이라냥 (둘 다 써서 10 × 2).

숨겨진 테스트의 10 20 30 40 은 답이 60 이라냥. 하나만 써도 (40), 다 써도 (10 × 4 = 40) 안 나오는 숫자라냥.

미션 4회의실 하나에 몇 개25분

회의실 하나에 겹치지 않게 최대 몇 개를 넣는다냥.

문제 풀러 가기

끝나는 시각이 빠른 순으로 정렬한다냥.

회의실을 가장 빨리 비워주는 회의라서, 뒤에 더 많이 넣을 수 있다냥.

meetings.sort(key=lambda m: (m[1], m[0]))

end = -1
cnt = 0
for s, e in meetings:
    if s < end:
        continue
    cnt += 1
    end = e

함정그럴듯한데 틀린 기준 두 개라냥

강의 4단계에서 본 그거라냥. 숨겨진 테스트가 둘 다 잡는다냥.

시작이 빠른 순 — 공개된 첫 예시 (1,4) (2,3) (3,5) 에서 바로 틀린다냥. (1,4) 를 먼저 잡으면 나머지가 다 막혀서 1개라냥
짧은 회의부터 — 이건 첫 예시를 통과한다냥. 대신 숨겨진 (1,10) (9,12) (11,20) 에서 틀린다냥. 가운데 짧은 회의가 양쪽을 다 막아서 1개라냥

두 오답이 서로 다른 케이스에서 걸린다냥. 하나를 통과했다고 안심하면 안 된다냥.

한 회의가 끝나는 시각에 다른 회의가 시작하는 건 겹치는 게 아니라냥. 그래서 조건이 s < end 라냥. s <= end 로 쓰면 붙어 있는 회의를 놓친다냥.

미션 5회의실이 몇 개 필요하냥25분

모든 회의를 열려면 회의실이 최소 몇 개인지 구한다냥.

문제 풀러 가기

4번과 입력이 완전히 똑같다냥. 그런데 질문이 다르다냥.

4번은 회의실 하나에 몇 개를 넣냐, 5번은 전부 열려면 방이 몇 개냐라냥.

4번 코드를 그대로 내면 틀린다냥. 정렬 기준부터 다시 생각해야 한다냥. 숨겨진 테스트가 이걸 잡는다냥.

뼈대시작과 끝을 사건으로 쪼갠다냥

답은 어느 한 순간에 동시에 열려 있는 회의의 최대 개수라냥. 그만큼의 방이 있어야 하고, 그거면 충분하다냥.

회의 하나를 사건 두 개로 쪼개자냥 — 시작하면 방이 하나 필요해지고, 끝나면 하나 돌려준다냥.

events = []
for s, e in meetings:
    events.append((s, 1))     # 시작: 방 하나 더
    events.append((e, 0))     # 끝: 방 하나 반납

events.sort()

cur = 0
best = 0
for _, kind in events:
    cur += 1 if kind == 1 else -1
    best = max(best, cur)

(e, 0) 과 (s, 1) 의 숫자가 중요하다냥.

같은 시각에 하나가 끝나고 하나가 시작하면, 끝나는 걸 먼저 처리해야 한다냥. 그래야 방을 돌려받아서 다시 쓴다냥.

끝을 0, 시작을 1 로 두면 그냥 정렬만 해도 끝이 먼저 온다냥. 반대로 두면 방을 쓸데없이 하나 더 세게 된다냥.

확인4번과 답을 비교해보자냥

공개된 첫 예시 (1,4) (2,3) (3,5) 는 4번도 5번도 답이 2 라냥. 우연히 같다냥.

숨겨진 테스트의 회의 11개짜리는 4번이 4, 5번이 5 라냥. 같은 입력인데 답이 다르다냥. 두 문제가 정말 다른 문제라는 증거라냥.

다섯 개 다 풀었냥? 오늘 배운 건 결국 하나라냥 — 무엇을 기준으로 고를 거냥, 그리고 왜 그게 이득이냥.

코드는 짧지만 그 한 줄을 정하는 게 전부라냥. 그리고 확신이 안 서면 11장의 완전탐색으로 작은 입력을 맞춰보면 된다냥.

다음은 동적계획법이라냥. 그리디가 틀리는 문제도, 한 번 푼 걸 표에 적어두면 제대로 풀린다냥. 정말 수고했다냥~

직접 풀어보자! 그리디 5문제

안녕, 나 코딩냥이다냥! 오늘 문제는 코드가 짧다냥. 다섯 개 다 열 줄 안쪽으로 끝난다냥.

그래서 더 조심해야 한다냥. 짧은 코드가 조용히 틀리기 때문이라냥. 답이 그럴듯하게 나오는데 기준이 잘못됐으면 알아채기 어렵다냥.

그리디 문제를 풀 때 순서

무엇을 기준으로 고를지 정한다 — 보통 정렬 기준이라냥
왜 그게 이득인지 한 문장으로 말해본다
말이 안 되면 다른 기준을 찾는다

2번을 건너뛰면 안 된다냥. 짧은 코드를 다 짜고 나서 기준이 틀렸다는 걸 알면 처음부터 다시라냥.

미션 1동전 거스름돈15분

동전으로 k 원을 만드는 최소 개수를 구한다냥.

문제 풀러 가기

큰 동전부터 최대한 쓴다냥. 나눗셈과 나머지로 한 번에 처리된다냥.

coins.sort(reverse=True)

cnt = 0
for c in coins:
    cnt += k // c     # 이 동전을 몇 개 쓸 수 있냥
    k %= c            # 남은 금액이라냥

하나씩 빼면서 세면 k 가 1억일 때 시간이 모자란다냥. 나눗셈으로 한 번에 처리하자냥.

동전이 정렬되어 주어지지 않는다냥.

공개된 두 예시 중 하나는 작은 것부터, 하나는 큰 것부터 들어온다냥. 직접 정렬하지 않으면 하나는 맞고 하나는 틀린다냥.

확인이 문제가 그리디로 풀리는 이유라냥

문제에 "큰 동전은 그보다 작은 동전의 배수" 라고 적혀 있다냥. 그 조건이 있어서 큰 것부터 집어도 손해가 안 나는 거라냥.

강의 3단계에서 본 1, 3, 4 동전에는 그 조건이 없었다냥. 그래서 6원을 만들 때 그리디가 3개, 정답이 2개로 갈렸다냥.

조건을 확인하고 그리디를 쓰는 습관을 여기서 들이자냥.

미션 2ATM 줄 세우기15분

모두가 기다린 시간의 합을 가장 작게 만든다냥.

문제 풀러 가기

짧은 사람부터 세운다냥. 앞자리일수록 여러 번 더해지기 때문이라냥.

times.sort()

run = 0
total = 0
for t in times:
    run += t          # 이 사람 차례가 끝난 시각이라냥
    total += run      # 그게 이 사람이 기다린 시간이라냥

변수가 두 개인 게 헷갈릴 수 있다냥. run 은 한 사람의 대기 시간, total 은 전부 합친 값이라냥.

정렬을 빼먹으면 틀린다냥.

정렬 없이도 코드는 잘 돌아가고 그럴듯한 숫자가 나온다냥. 그래서 더 위험하다냥. 숨겨진 테스트가 이걸 잡는다냥.

미션 3로프로 들어올리기20분

로프를 골라 병렬로 이어서 최대 중량을 든다냥.

문제 풀러 가기

핵심k개를 쓰면 가장 약한 로프가 기준이라냥

로프 k개로 무게 w 를 들면 하나당 w / k 를 버텨야 한다냥. 그러니 그중 가장 약한 로프가 견딜 수 있는 만큼만 들 수 있다냥.

가장 약한 게 x 라면 들 수 있는 무게는 x × k 라냥.

그럼 어떤 k개를 고르냥? 튼튼한 것부터 k개를 고르는 게 항상 이득이라냥. 그래야 그중 가장 약한 게 최대가 된다냥.

그러니 내림차순으로 정렬한 뒤, k 를 1부터 n 까지 다 해보면 된다냥.

ropes.sort(reverse=True)

best = 0
for i, w in enumerate(ropes):
    best = max(best, w * (i + 1))

i 번째까지 썼다는 건 i + 1 개를 썼다는 뜻이고, 그중 가장 약한 게 w 라냥. 정렬해뒀으니 그렇다냥.

흔한 두 가지 오답이라냥.

가장 튼튼한 로프 하나만 쓰기 — 여러 개를 쓰면 더 들 수 있다냥
로프를 전부 다 쓰기 — 약한 로프 하나가 전체를 끌어내린다냥

공개된 예시 10 15 가 첫 번째를 바로 잡는다냥. 답이 15 가 아니라 20 이라냥 (둘 다 써서 10 × 2).

숨겨진 테스트의 10 20 30 40 은 답이 60 이라냥. 하나만 써도 (40), 다 써도 (10 × 4 = 40) 안 나오는 숫자라냥.

미션 4회의실 하나에 몇 개25분

회의실 하나에 겹치지 않게 최대 몇 개를 넣는다냥.

문제 풀러 가기

끝나는 시각이 빠른 순으로 정렬한다냥.

회의실을 가장 빨리 비워주는 회의라서, 뒤에 더 많이 넣을 수 있다냥.

meetings.sort(key=lambda m: (m[1], m[0]))

end = -1
cnt = 0
for s, e in meetings:
    if s < end:
        continue
    cnt += 1
    end = e

함정그럴듯한데 틀린 기준 두 개라냥

강의 4단계에서 본 그거라냥. 숨겨진 테스트가 둘 다 잡는다냥.

시작이 빠른 순 — 공개된 첫 예시 (1,4) (2,3) (3,5) 에서 바로 틀린다냥. (1,4) 를 먼저 잡으면 나머지가 다 막혀서 1개라냥
짧은 회의부터 — 이건 첫 예시를 통과한다냥. 대신 숨겨진 (1,10) (9,12) (11,20) 에서 틀린다냥. 가운데 짧은 회의가 양쪽을 다 막아서 1개라냥

두 오답이 서로 다른 케이스에서 걸린다냥. 하나를 통과했다고 안심하면 안 된다냥.

한 회의가 끝나는 시각에 다른 회의가 시작하는 건 겹치는 게 아니라냥. 그래서 조건이 s < end 라냥. s <= end 로 쓰면 붙어 있는 회의를 놓친다냥.

미션 5회의실이 몇 개 필요하냥25분

모든 회의를 열려면 회의실이 최소 몇 개인지 구한다냥.

문제 풀러 가기

4번과 입력이 완전히 똑같다냥. 그런데 질문이 다르다냥.

4번은 회의실 하나에 몇 개를 넣냐, 5번은 전부 열려면 방이 몇 개냐라냥.

4번 코드를 그대로 내면 틀린다냥. 정렬 기준부터 다시 생각해야 한다냥. 숨겨진 테스트가 이걸 잡는다냥.

뼈대시작과 끝을 사건으로 쪼갠다냥

답은 어느 한 순간에 동시에 열려 있는 회의의 최대 개수라냥. 그만큼의 방이 있어야 하고, 그거면 충분하다냥.

회의 하나를 사건 두 개로 쪼개자냥 — 시작하면 방이 하나 필요해지고, 끝나면 하나 돌려준다냥.

events = []
for s, e in meetings:
    events.append((s, 1))     # 시작: 방 하나 더
    events.append((e, 0))     # 끝: 방 하나 반납

events.sort()

cur = 0
best = 0
for _, kind in events:
    cur += 1 if kind == 1 else -1
    best = max(best, cur)

(e, 0) 과 (s, 1) 의 숫자가 중요하다냥.

같은 시각에 하나가 끝나고 하나가 시작하면, 끝나는 걸 먼저 처리해야 한다냥. 그래야 방을 돌려받아서 다시 쓴다냥.

끝을 0, 시작을 1 로 두면 그냥 정렬만 해도 끝이 먼저 온다냥. 반대로 두면 방을 쓸데없이 하나 더 세게 된다냥.

확인4번과 답을 비교해보자냥

공개된 첫 예시 (1,4) (2,3) (3,5) 는 4번도 5번도 답이 2 라냥. 우연히 같다냥.

숨겨진 테스트의 회의 11개짜리는 4번이 4, 5번이 5 라냥. 같은 입력인데 답이 다르다냥. 두 문제가 정말 다른 문제라는 증거라냥.

다섯 개 다 풀었냥? 오늘 배운 건 결국 하나라냥 — 무엇을 기준으로 고를 거냥, 그리고 왜 그게 이득이냥.

코드는 짧지만 그 한 줄을 정하는 게 전부라냥. 그리고 확신이 안 서면 11장의 완전탐색으로 작은 입력을 맞춰보면 된다냥.

다음은 동적계획법이라냥. 그리디가 틀리는 문제도, 한 번 푼 걸 표에 적어두면 제대로 풀린다냥. 정말 수고했다냥~