안녕하세요 오늘은 그리디 문제의 유형에 대해 분석해보는 시간을 갖도록 하겠습니다.
그리디 유형은 규칙성이 존재하는 집합에서의 최대 최솟값을 구하는 문제로 정의할 수 있습니다. 그리디 특성 상 단순한 규칙이 문제 전체를 관통하기 때문에 이 규칙을 구현하여 문제를 쉽게 풀 수 있습니다.
백준 11047(동전 0) 문제의 경우 N 종류의 동전을 사용하여 합을 K로 만들 때의 동전의 최솟값을 구하는 문제입니다. 특정 종류의 동전의 합을 이용하여 최솟값을 구할 경우 가장 큰 동전부터 사용하면서 합을 채우고 현재 동전을 사용 시 값이 초과된다면 이 동전보다 작은 값을 순서대로 대입하면서 값이 같아질때까지 진행하면 풀 수 있습니다.
백준 1931(회의실 배정) 문제의 경우 N개의 회의의 시작 시간과 끝 시간이 주어질 때 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 구하는 문제입니다. 종료 시간이 가장 빠른 순서대로 회의를 진행한다면 종료되며 새로운 회의가 가장 많이 추가될 수 있기 때문에 회의 수의 최댓값을 구할 수 있습니다. 여기서 주의할 점은 같은 시간에 끝날 경우 시작 시간이 빠른 시간 순으로 정렬하여야 한다는 점입니다. 현재 시간을 같이 저장하면서 현재 시간보다 시작 시간이 크거나 같을 경우에 회의가 추가가 가능하므로 종료 시간이 가장 빠르고 시작 시간이 그 다음으로 빠른 순으로 정렬된 자료구조를 탐색해야 데이터가 올바른 순서대로 추가됩니다.
백준 1541(잃어버린 괄호) 문제의 경우 주어진 식에 괄호를 적절히 배치해서 최솟값을 구하는 문제입니다. 최솟값을 구하기 위해선 더해진 값을 전부 빼주면 되기 때문에 더하기가 되어 있는 부분을 괄호를 쳐서 먼저 더한 후 빼는 방식으로 구현합니다. 이 때 split을 이용하여 '-' 기준으로 쪼갠 후 내부의 값을 '+' 기준으로 쪼개 다 더한 값을 가장 첫 값을 제외하면 전부 빼는 방식으로 구현합니다.
백준 2839(설탕 배달)의 경우 N킬로 설탕 배달 시 최소 몇 개의 봉지를 가져가야 하는지를 구하는 문제입니다. 최소의 봉지를 사용하기 때문에 5킬로를 먼저 사용한 후 3킬로를 이어서 사용합니다. 이 때 3킬로로만 만들어지는 경우도 있기 때문에 5킬로 봉지의 최댓값(N/5)부터 값을 1씩 감소시키면서 3킬로 봉지로 만들 수 있는지 체크하여 계산해줍니다.
백준 1339(단어 수학) 문제의 경우 N개의 단어가 주여졌을 때 수의 합을 최대로 만드는 문제입니다. 더 앞 자리수의 알파벳일수록 더 큰 수를 매칭하는 방식으로 구현할 수 있습니다. 알파벳 배열에 각 알파벳 별 자릿수의 총합을 더합니다. 이 후 알파벳 배열의 값을 내림차순으로 정렬하여 값을 참조하면서 9부터 순서대로 곱한 값을 총합에 더하는 방식으로 누적합을 구하면 풀 수 있습니다.
백준 1744(수 묶기) 문제의 경우 수를 묶어 수열의 합의 최댓값을 구하는 문제입니다. 이 문제는 크게 4가지로 수를 나누어야 합니다. 우선 1보다 큰 양수의 경우 큰 수끼리 곱하면 더 큰 값이 구해지기 때문에 큰 수 끼리 곱하고 나머지는 그대로 더해줍니다. 1의 경우 곱하면 더했을 때보다 1만큼 손해이기 때문에 곱하지 않고 1의 개수만큼 더해줍니다. 음수의 경우 음수끼리만 곱했을 때 최댓값이 나오게 되므로 작은 수 순서대로 곱합니다. 이 때 0이 존재한다면 나머지 값을 0과 곱해 없앨 수 있으며, 0이 없다면 나머지 값을 그대로 더해주면 최댓값을 구할 수 있습니다.
