본문 바로가기

그리디7

[C++] 백준 2812번: 크게 만들기(그리디) https://www.acmicpc.net/problem/2812문제 이해하기 문제의 요구사항은 다음과 같습니다.주어진 숫자에서 숫자 K개를 지웠을 때, 만들 수 있는 가장 큰 수를 구하여라.시간복잡도 어림하기브루트 포스 알고리즘 제외할 모든 수를 골라 수를 제거하여 만드는 방법을 생각해볼 수 있습니다. 제거할 수를 선택하는 경우의 수는 조합이므로 nCk로 계산됩니다. 하지만, 문제의 n과 k의 최댓값은 500,000 이므로 그 경우의 수가 너무 큽니다. 따라서 브루트 포스 알고리즘으로 문제를 해결할 수 없습니다.DP 알고리즘 DP 알고리즘을 사용하기 위해서는 이전 상태를 활용할 수 있어야 합니다. 만약 지금까지 idx에 문자를 덧붙이는 방식으로 진행한다면, 매 idx 마다 문자를 붙일지 붙이지 않을지 .. 2024. 8. 28.
[C++] 백준 1744번: 수 묶기 (그리디) https://www.acmicpc.net/problem/1744문제 이해하기 문제의 요구사항은 다음과 같습니다.주어진 집합의 수를 적절히 배치하고 묶었을 때, 식의 최댓값을 구하여라.시간복잡도 어림하기브루트 포스 알고리즘 n개의 수를 나열하는 경우의 수는 n!입니다. 문제에서 n의 최댓값은 50이므로 50개의 수를 나열하는 경우의 수는 50!입니다. 50!은 제한 시간 내에 문제를 해결할 수 없는 수치이므로 브루트포스 알고리즘을 사용할 수 없습니다. DP 알고리즘 이 문제는 주어진 수열의 순서가 정해지지 않은 상태로 수들을 적절히 배치하여 최대 합을 구하는 것입니다. DP 알고리즘을 사용한다고 해도 수열을 순서를 정해놓고 DP 알고리즘을 적용해야하므로 브루트 포스 알고리즘과 마찬가지로 최소 O(n!)의.. 2024. 7. 9.
[C++] 백준 1339번: 단어 수학 (그리디) https://www.acmicpc.net/problem/1339문제 이해하기 문제의 요구사항은 다음과 같습니다.N개의 단어가 주어지고, 단어를 구성하는 알파벳에 한 자리 수를 대응시킬 때, 단어들의 합의 최댓값을 구하여라.시간복잡도 어림하기브루트 포스 알고리즘 모든 단어에 포함되어 있는 알파벳은 최대 10개이고, 단어의 최대 길이는 8입니다. 따라서 알파벳에 한 자리 수를 대응시키는 경우의 수는 10^8 = 100,000,000으로 1억 가지의 경우의 수를 가집니다. 이는 한 단어에 대해 가지는 경우의 수 이므로 최대 10개의 단어가 들어오는 입력에 대해 모든 경우의 수를 구하기는 어렵습니다. 따라서 브루트 포스 알고리즘은 적절하지 않습니다. DP 알고리즘 현재 상태를 구하기 위해 이전 상태를 사용하는.. 2024. 7. 4.
[C++] 백준 11000번: 강의실 배정 (그리디) https://www.acmicpc.net/problem/11000문제 이해하기 문제의 요구사항은 다음과 같습니다.수업의 시작 시간과 종료 시간이 주어질 때, 사용가능한 최소의 강의실 수를 구하여라.시간복잡도 어림하기브루트 포스 알고리즘 모든 경우의 수 탐색은 강의실의 수가 1개일 때 부터 n개일 때 까지 탐색하면서 확인할 수 있습니다. 하지만 n개의 강의를 2개의 집합으로 나눈다고 할 때, 그 경우의 수는 2^(n - 1) - 1개 이고, n = 200,000이므로 전체 경우의 수는 아주 큰 수가 될 것입니다. 따라서 브루트 포스 알고리즘으로 문제를 해결할 수 없습니다. DP 알고리즘 dp를 사용한다면 dp에는 현재 시간까지 사용가능한 최소 강의실의 수를 담을 수 있습니다. 하지만, 강의 시간의 범위가.. 2024. 5. 17.
[C++] 백준 1946번: 신입 사원 (그리디) 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 문제 이해하기 문제의 요구 사항은 다음과 같습니다. 주어진 조건에 따라 신입 사원을 선발할 때, 선발 가능한 최대 신입 사원 수를 구하여라. 신입 사원 선발 조건은 서류 성적과 면적 성적 중 적어도 하나가 다른 지원자들보다 높은 지원자를 선발한다. 시간복잡도 어림하기 브루트 포스 알고리즘 모든 지원자들의 성적을 담은 배열에서 현재 지원자가 다른 모든 사람들보다 적어도 하나의 성적이 높다는 것을 찾기 위해서는 전체 N명의 지원자에 대해 N -.. 2024. 4. 23.
[C++] 백준 1931번: 회의실 배정 (그리디) 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 이해하기 문제의 요구사항은 다음과 같습니다. 각 회의를 겹치지 않게 진행할 때, 사용할 수 있는 회의의 최대 갯수를 구하여라. 시간복잡도 어림하기 브루트 포스 알고리즘 브루트 포스 알고리즘으로 이 문제를 해결한다면 시간 복잡도가 얼마나 될까요? 각 회의는 회의를 진행하는 경우와 진행하지 않는 두 경우로 나누어질 것입니다. 이때, 회의의 수가 100,000이므로 모든 경우의 수는 2^1000000으로 제한 시간내에 해결하기 불가능한 수치입니다. DP 알고리즘 DP 알고리즘은 어떨까요? DP에 i번 인덱스까지의 최대 회의 수를 담는다고 해봅시다. i번에서의 최대 회의 수를 계.. 2024. 4. 11.

티스토리툴바