그리디

[백준 - 1946] 신입 사원 [C++]

1. 문제 https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 2. 풀이 그리디 문제이다. 일단 n이 10만이므로 O(n^2) 으로는 풀 수 없다. 그래서 우선 서류순으로 정렬하고, 1번째 지원자는 서류로 1등이니 반드시 뽑힌다. 2번째 지원자부터는 면접순위를 비교하면서 세줬다. 어떤 지원자가 서류점수는 낮더라도(정렬되어있으니 당연히 낮음) 현재까지의 최고 면접 순위보다 높은경우 그 지원자를 선발하고 key를 교체한다. 3. ..

[백준 - 1931] 회의실 배정 [C++]

1. 문제 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 2. 풀이 끝나는 시간이 빠른 회의를 우선적으로 선택함으로써 남은 시간을 최대한 활용할 수 있게 됩니다. 다시 말해, 어떤 회의가 빠르게 끝나면 그 후에 다른 회의들을 더 많이 배정할 수 있습니다. 예시) 회의 리스트: A: 1-4 B: 3-5 C: 0-6 D: 5-7 E: 3-8 F: 5-9 G: 6-10 H: 8-11 I: 8-12 J: 2-13 K: 12-14 1. 끝나는 시간을 기준으로 오름차순 정렬을 합니다: A: 1-4 B: 3-5 D: 5-7 F: 5-9 G: 6-10 C: 0-6 E: 3..

[프로그래머스] 체육복 [C++]

1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/42862 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이 그리디 문제이다. 체육복을 빌려줄 수 있으면 즉시 빌려준다. 그리고 여전히 체육복을 빌리지 못한 학생의 수를 세어서 전체 학생수에서 제외시켜준다. 3. 코드 #include #include #include #include using namespace std; int solution(int n, vector lost, vector reserve) { // 잃어버린 학생과 여벌을..

[백준 - 1541] 잃어버린 괄호 [C++]

1. 문제 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 2. 풀이 첫 번째 '-' 연산자가 나타날 때까지는 모든 숫자들을 더하고, 첫 번째 '-' 연산자가 나타난 이후의 모든 숫자들은 빼주면 된다. 3. 코드 #include #include #include using namespace std; string expression; string number; int answer; bool isNegative = false; // 1541 /..