코딩테스트 연습 → 탐욕법(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 =..