💬 문제 설명한 개의 회의실이 있고 `N`개의 회의가 주어질 때 회의들이 겹치지 않게 하면서 가장 많은 회의를 진행하려 한다.각 회의는 시작 시간과 끝나는 시간이 주어진다.한 회의가 끝나는 것과 동시에 다른 회의를 시작할 수 있다.회의의 수 `N` (1 ≤ `N` ≤ 100,000) 📌 주의 사항회의 끝나는 시간 기준으로 오름차순 정렬해야 한다.단 끝나는 시간이 같을 경우 시작 시간이 빠른 순으로 정렬해야 한다.회의 시간을 기준으로 정렬하면 안 된다! 👌 문제 풀이회의 정보를 `(시작시간, 끝시간)`으로 입력받는다.끝나는 시간 기준 오름차순 정렬을 하되 끝나는 시간이 같다면 시작 시간이 빠른 순으로 정렬앞에서부터 회의를 선택하며 `현재 회의 시작시간 ≥ 이전 회의 끝시간`일 경우 선택선택한 회의 수..

1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net ** 문제 유형 그리디 ** 풀이 모든 박스를 배로 옮기는데 드는 시간의 최솟값 계산 매 분마다, 모든 크레인에 대하여 옮길 수 있는 박스를 선택하여 옮기도록 함 박스를 무게 기준으로 내림차순 정렬한 뒤에, 무거운 것부터 옮기도록 함 시간 복잡도 O(NM)에 문제 해결 가능: 크레인 개수 N, 박스 개수 M import sys n = int(input()) cranes = list(map(int, input().split())) m = int(i..

2012번: 등수 매기기 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다. 예상 등수는 500,000 이하의 자연수이다. www.acmicpc.net ** 문제 유형 그리디 ** 풀이 예상 등수와 실제 등수의 차이를 최소화해야 함 그 방법으로 예상된 등수를 오름차순으로 정렬하면 됨 n = int(input()) array = [] # 예상 등수 answer = 0 # 불만도의 합 for _ in range(n): array.append(int(input())) array.sort() # 오름차순 정렬 수행 for i in range(1, n + 1): answer += abs(i - array[i - 1]) prin..

1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net ** 문제 유형 그리디 ** 풀이 문자열에 있는 숫자를 모두 0 또는 모두 1로 만들어야 함 문자열의 길이는 100만 이하이므로, 시간 복잡도는 O(N)에 해결해야 함 data = input() states = [0] * 2 # states[0-1]: 0-1이 연속으로 오는 집합 수 states[int(data[0])] += 1 for i in range(1, len(data)): if data[i] != data[i - 1]: # 0과 1이 바뀔 때 state..

5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사 www.acmicpc.net ** 문제 유형 그리디 ** 풀이 거스름 돈의 최소 개수 계산 가장 기초적인 탐욕 알고리즘 문제 유형으로, 단순히 '큰 화폐 단위' 순서대로 잔돈을 거슬러 주면 최적의 해를 구할 수 있음 changes = 1000 - int(input()) cnt = 0 for i in [500, 100, 50, 10, 5, 1]: cnt += changes // i changes %= i print(cnt)

탐욕 알고리즘(Greedy algorithm)탐욕 알고리즘은 문제를 해결할 때마다 그 순간 가장 최적인(가장 좋아 보이는) 선택을 하는 알고리즘 전략전체적인 최적의 해를 보장하진 않지만 계산량을 줄이면서 근삿값 또는 국소 최적해(local optimum)를 빠르게 구할 수 있음 탐욕 알고리즘의 핵심 원칙Greedy Choice Property (탐욕 선택 속성)매 순간 가장 좋아 보이는 선택이 전역 최적해(global optimum)를 만든다.Optimal Substructure (최적 부분 구조)전체 문제의 최적 해결책은 하위 문제의 최적 해결책으로 구성된다.예제 1: 동전 문제 (Coin Change Problem)문제 설명4720원을 500원, 100원, 50원, 1원 동전으로 가장 적은 수로 지불..