알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/1213

문제 링크입니다. https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 까다로운 그리디 문제였습니다. 보석을 어떤 순으로 담아야 되는지 생각했어야 했습니다. N과 K의 범위가 300,000 이기에 가방 한개마다 모든 보석을 확인하기에는 문제가 있습니다. 따라서 우선순위 큐를 사용했습니다. 우선순위 큐를 사용하면 조건에 따라 가장 작은 or 가장 큰 값이 루트에 있기에 이를 가져오기만 하면 ..

문제 링크입니다. https://www.acmicpc.net/problem/27112 27112번: 시간 외 근무 멈춰! 오늘도 여러 체계의 개발 임무를 열심히 수행 중인 준민이에게 갑자기 새로운 개발 프로젝트가 들어왔다. 해당 개발 프로젝트는 총 $N$개의 작업으로 이루어져 있으며, 각 작업은 $t_i$의 근무일 www.acmicpc.net 정렬을 이용한 문제입니다. 일의 마감시한과 걸리는 시간이 주어졌을 때, 이를 끝낼 수 있는지를 구하는 문제입니다. 일을 끝내긴 위해선 먼저 마감기한이 빠른 일부터 끝내야합니다. 따라서 정렬을 해야하는데, 데이터 값이 2개가 있습니다. 마감기한과 걸리는 시간입니다. 마감기한이 우선이기에 마감기한 -> 걸리는 시간 순으로 우선순위를 정해서 정렬을 해주면 됩니다. 정렬을..

문제 링크입니다. https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 정렬을 이용한 그리디 문제입니다. 최소 강의실을 구해야하는 문제입니다. 강의를 최대로 이어서 할 수 있도록 만들어야합니다. 따라서 한 강의를 시작으로 최대한 다른 강의로 이어봅니다. 다른 강의를 시작할 수 없는 때가 온다면 강의실을 하나 추가하고 해당 강의를 시작합니다. 이러한 과정을 반복하면 강의실의 갯수를 구할 수 있습니다. 이를 우선순위 큐를 통해서 풀면 됩니다. 자세한 것은 코드를 참고해주세요 #define _CRT_S..

문제 링크입니다. 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 그리디의 대표적인 문제입니다. 필요한 동전의 최솟값을 구하는 방법은 값이 높은 동전을 최대한 이용하는 방법입니다. 따라서 큰 가치의 동전부터 사용하면서 내려가면 되는 문제입니다. 자세한 것은 코드를 참고해주세요 #define _CRT_SECURE_NO_WARNINGS #include #include #include ..

문제 링크입니다. https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 정렬을 이용해 푸는 문제입니다. A의 배열은 오름차순으로, B의 배열은 내림차순으로 정렬해 서로 곱해주면 되는 문제입니다. 자세한 것은 코드를 참고해주세요 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include using namespace std; int N;..

문제 링크입니다. https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 그리디 알고리즘 문제입니다. X개의 로프를 사용해 최대 중량을 구하는 문제입니다. 예를 들어 7, 10, 20를 버틸 수 있는 로프가 각각 있다고 가정하겠습니다. 이때 7을 이용해 만들 수 있는 중량은 7 * 3 = 21 입니다. 7을 10, 20 로프가 버틸 수 있기 때문입니다. 20을 이용한다면 20 * 1 = 20 입니다. 20은 7과 10 로프가 버틸 수 없기 때..

문제 링크입니다. https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 그리디 알고리즘을 이용해 정렬로 푸는 문제입니다. 최대로 많은 회의를 찾는 문제입니다. 찾는 방법은 A라는 회의가 끝났을 때, A 회의 끝나는 시간에 가장 빨리 시작하는 회의면서 가장 빨리 끝나는 회의여야합니다. 따라서 먼저 끝나는 시간을 기준으로 오름차순으로 정렬합니다. 이때 끝나는 시간이 같다면 -> 일찍 시작하는 것을 선택해야합니다. 따라서 시작 시간을 기준으로 오름차순 정렬합니다. 가장 먼저 시작하는 회의는 첫번째에 있는 회의입니다. 따라서 해당 회의의 끝나는 시간을 시작으로 다음 회의를..

문제 링크입니다. https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 문자열과 그리디 알고리즘을 사용하여 푸는 문제였습니다. 크게 2가지의 과정을 통해 문제를 풀면 됩니다. 1. 문자열을 숫자와 수식으로 변경해 저장하기 2. 숫자를 뺄 경우 뺄 수 있는 최댓값을 구하기 1. 문자열을 숫자와 수식으로 변경하기 void get_number() { string now_number; for (int i = 0; i < formula.size(); i..