그리디 알고리즘

(C++) 백준 1541번 - 잃어버린 괄호

문제 링크 : https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 문제 풀이 그리디 알고리즘을 사용한 풀이이다. '-' 이후로 오는 수는 모두 빼기 처리해 주면 최솟값을 구할 수 있다. #include #include using namespace std; string raw, num; int result; int main() { cin >> raw; bool isMinus = false; for(int i = 0; i

(C++) 백준 1026번 - 보물

문제 링크 : https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 문제 풀이 그리디 알고리즘을 활용한 문제이다. 여러 수들의 곱의 최솟값을 구하고 싶다면 최댓값에 최솟값을 곱해주면 되고, 곱의 최댓값을 구하고 싶다면 최댓값끼리 곱해주면 된다. 그렇기에 우선 오름차순으로 정렬을 진행하고, 한 배열에선 값이 작은 앞의 원소를, 다른 배열에서는 값이 큰 뒤의 원소를 차례대로 곱하면 최솟값을 구할 수 있다. #include #include usin..

(C++) 백준 2217번 - 로프

문제 링크 : https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 문제 풀이 그리디 알고리즘을 활용한 문제이다. 최대 중량을 들기 위해선 더 무거운 중량을 들 수 있는 로프를 우선으로 사용해야 한다. 그렇기에 우선 오름차순으로 정렬을 진행하고, k개의 로프들을 사용해 봄으로써 들 수 있는 가장 높은 중량을 계산한다. #include #include using namespace std; int ropes[100005]; int n, mx; ..

(C++) 백준 1931번 - 회의실 배정

문제 링크 : https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 풀이 그리디 알고리즘을 활용한 문제이다. 회의실을 사용할 수 있는 회의의 개수를 최대로 하기 위해선 종료 시간이 가장 이른 순으로 사용하게 하면 된다. 그렇기에 회의가 종료되는 시간의 오름차순으로 정렬을 해놓고 시작 시간이 지나지 않은 가장 빠른 회의가 회의실을 사용하도록 하면 된다. #include #include #define X first #define Y second using namespace std; pair meetings[100005]; int n, cnt, cur, mn; bo..

(C++) 백준 11047번 - 동전 0

문제 링크 : https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 문제 풀이 그리디 알고리즘을 활용한 문제이다. 가장 동전 수를 적게 이용하려면 금액이 큰 동전부터 빼가면서 계산해야 한다. 금액이 오름차순으로 입력되기 때문에 배열의 뒷부분부터 계산해 나가는 식으로 풀이하였다. #include using namespace std; int coins[12]; int n, k, cnt; i..