그리디

코딩테스트 연습 → 탐욕법(Greedy) → Lv.3 단속카메라알고리즘 문제를 많이 풀어본 사람은 문제 유형만 봐도 그리디(Greedy) 알고리즘을 사용한다는 것을 바로 판단해야 한다. 필자 또한 비슷한 유형의 문제들을 풀어본 경험으로 인해 그리디를 사용한 문제라는 것을 알았지만, 왜 그리디를 사용하는 것인가? 라는 주입식 교육의 폐해인 의문이 들어 풀이 방법을 함께 살펴보고자 한다.풀이 방법 공식 예시와 함께 문제를 살펴보자. 먼저, 첫 번째 차량은 -20의 위치에서 진입하여 -15의 위치까지 달린다. 현재까지의 단속카메라 위치는 -20 ~ -15 사이의 어디든 설치해도 1개의 카메라만 설치하면 될 것이다.  두 번째 차량은 [-14, -5]의 위치까지 달린다. 그림으로 봤을 때 첫 번째 차량과 겹치는..

코딩테스트 연습 → 연습문제 → Lv. 3 최고의 집합 풀이 방법결론부터 말하자면 그리디(Greedy) 기법을 사용해야 한다. 집합 내 필요한 원소의 개수 n개가 있을 때, 각각의 원소에 s 값이 골고루 분배 되어야 한다. 즉, 차이가 가장 덜 나는 원소들로 집합을 이루어야 한다는 것이다. 말로 설명하자면 어려우니 예시와 함께 이해해보자. n = 2, s = 9일 때를 보자. 현재 집합에 아무 숫자도 넣지 않았기 때문에 필요한 원소의 개수는 2개이다. 이는 [1, 8], [2, 7], [3, 6], [4, 5]와 같이 분배가 될 수 있는데 각 원소의 차이가 가장 적은 원소 집합은 [4, 5]이다. 그러므로 정답이 [4, 5]가 되는 것이다. 위의 예시만으로는 감이 잡히지 않을 것이다. 다른 예시로 n =..

🔗 11000번 : 강의실 배정● Java 풀이● 시간 제한 1초● 메모리 제한 256 MB✅ 문제수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)수강신청 대충한 게 찔리면, 선생님을 도와드리자!✅ 테스트 케이스/** 출처 (https://steady-coding.tistory.com/253) **/// input61 32 57 89 107 114 12// answer3✅ 풀이import java.io.*;import java..