728x90 🥇Baekjoon Solutions/그리디 알고리즘5 [C++] 백준 2812번: 크게 만들기 https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 중요풀이 이 문제는 그리디 알고리즘을 활요한 문제입니다. 앞에서부터 순차적으로 보았을 때 다음 자리 숫자보다 현재 자리 숫자가 작다면 현재 자리 숫자를 제거해주는 식으로 루프를 진행해주고 이 과정이 끝나고도 K자리를 다 빼지 않았다면 남은 K의 숫자만큼의 자리를 뒤에서부터 빼주는 과정을 반복합니다. 소스코드 #include #include using namespace std; int main() { int N, K, i = 0; string num; vectorv; cin .. 2021. 8. 27. [C++] 백준 8980번: 택배 https://www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 중요풀이 그리디 알고리즘과 배열을 통해 각각의 인덱스를 마을을 의미하는 것으로 몇개의 박스가 배달되고 있는지를 체크합니다. 첫 번째 잘못된 정렬로 구현한 풀이입니다...틀렸습니다...ㅠㅠ #include #include #include #include using namespace std; struct info { int start; int end; int num; }; bool.. 2021. 8. 23. [C++] 백준 11000번: 강의실 배정 https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109) www.acmicpc.net 중요풀이 그리디 알고리즘 활용에서 시간을 단축하기 위해 입력된 벡터를 O(N)의 시간복잡도만 확인하여 조건을 확인해보는 방법을 생각해봐야합니다. 우선적으로 받음 입력을 시작, 끝 시간 순으로 정렬을 시켜줍니다. 이후 벡터에서 꺼내 시간을 이동한다고 생각하여 중복되는 시간들의 수를 체크해줍니다. #include #include #include #include using namespace std; bool compare(pair a, pairb) .. 2021. 8. 22. [C++] 백준 1202번: 보석 도둑 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 문제를 풀면서 중요한 개념을 배웠습니다. 중요 포인트 set 라이브러리 활용 upper_bound, lower_bound 개념 그래야 시간복잡도를 최소한으로 구현할 수 있습니다. #include #include #include #include using namespace std; struct Jewelry { int M; int V; }.. 2021. 8. 22. [C++] 그리디 알고리즘 예시 코딩 문제 작업의 수 N(1~100,000), 제한시간 D(1~10,000,000) 작업을 다수의 컴퓨터로 수행할 시 작업을 최소의 컴퓨터로 수행하는 컴퓨터의 수를 구하시오. 예시 1 10 14 7 5 4 6 1 2 3 5 2 3 computer1 : 7 3 2 computer2 : 5 1 2 5 computer3 : 4 6 3 #include #include // 작업목록을 담을 work 벡터 #include // 가까운 시간대를 찾기위한 우선순위 큐 #include // 배열 초기화 memset사용 using namespace std; int main(void) { ios_base::sync_with_stdio(false); cout.tie(); cin.tie(); int TC, N, D, input; i.. 2021. 8. 21. 이전 1 다음 728x90
