[TIL] 이분 탐색과 탐욕법 문제 풀이

프로그래머스 단속카메라

오늘은 탐욕법을 활용하는 프로그래머스 단속카메라 문제를 풀었습니다.

 

각 차량은 고속도로에 진입한 지점과 진출한 지점을 가지고 있으며, 모든 차량이 최소 한 번은 단속카메라를 만나도록 카메라를 설치해야 합니다. 목표는 필요한 카메라의 최소 개수를 구하는 것입니다.

 

처음에는 차량의 진입 지점을 기준으로 정렬하는 방법을 생각했습니다. 하지만 진입 지점을 기준으로 보면 현재 차량과 이후 차량이 어느 지점까지 겹치는지 계속 관리해야 해서 판단이 복잡해집니다.

 

반대로 차량을 진출 지점 기준으로 오름차순 정렬하면 선택 기준이 명확해집니다. 아직 카메라를 만나지 않은 차량이 나오면 해당 차량의 진출 지점에 카메라를 설치합니다.

 

진출 지점은 해당 차량을 단속할 수 있는 가장 오른쪽 위치입니다. 따라서 현재 차량을 놓치지 않으면서 뒤에 나오는 다른 차량까지 함께 단속할 가능성을 최대한 높일 수 있습니다.

 

카메라를 설치한 이후에는 다음 차량의 진입 지점이 현재 카메라 위치보다 오른쪽에 있는지만 확인하면 됩니다. 진입 지점이 카메라 위치보다 작거나 같다면 기존 카메라로 함께 단속할 수 있습니다.

 

처음에는 설치한 모든 카메라 위치를 저장한 뒤 차량마다 확인하려고 했습니다. 하지만 진출 지점 순서대로 처리하면 새 카메라는 항상 기존 카메라보다 오른쪽에 설치됩니다. 따라서 모든 카메라를 저장할 필요 없이 마지막으로 설치한 카메라의 위치 하나만 관리하면 됩니다.

 

이번 문제를 통해 탐욕법에서는 무엇을 기준으로 정렬하는지가 중요하다는 점을 다시 확인했습니다. 단순히 가장 빠른 값이나 가장 작은 값을 선택하는 것이 아니라, 현재 선택이 이후 선택의 가능성을 최대한 남겨야 합니다.

 

또한 정렬을 통해 입력에 규칙을 만들면 불필요한 상태를 제거하고 구현도 단순하게 만들 수 있다는 점을 학습했습니다.

---

프로그래머스 입국심사

이분 탐색을 활용하는 프로그래머스 입국심사 문제도 풀었습니다.

 

여러 심사관이 서로 다른 속도로 입국심사를 진행할 때, 모든 사람이 심사를 마치는 데 필요한 최소 시간을 구하는 문제입니다.

 

처음에는 각 심사대가 언제 비는지를 관리하면서 사람을 한 명씩 배치하는 방법을 생각할 수 있습니다. 하지만 대기 인원이 최대 10억 명이기 때문에 사람을 기준으로 직접 시뮬레이션하면 시간 안에 해결할 수 없습니다.

 

이 문제에서는 사람을 어떻게 배치할지를 직접 결정하는 대신, 특정 시간이 주어졌을 때 그 시간 안에 몇 명을 심사할 수 있는지를 계산했습니다.

 

어떤 심사관의 심사 시간이 time이고 주어진 시간이 T라면, 해당 심사관은 T / time명을 처리할 수 있습니다. 모든 심사관이 처리할 수 있는 인원을 합한 값이 대기 인원 n 이상이라면 T분 안에 모든 심사를 끝낼 수 있습니다.

 

시간이 짧을 때는 전체 인원을 처리할 수 없지만, 시간이 길어질수록 처리 가능한 인원은 계속 증가합니다. 따라서 판정 결과는 다음과 같이 한 방향으로만 변합니다.

불가능 불가능 불가능 가능 가능 가능

 

이러한 단조성을 이용해 모든 인원을 처리할 수 있는 최초의 시간을 이분 탐색으로 찾았습니다.

 

탐색 범위의 최솟값은 1로 두고, 최댓값은 가장 느린 심사관이 모든 사람을 혼자 처리하는 시간으로 설정할 수 있습니다.

long long right =
    static_cast<long long>(*max_element(times.begin(), times.end())) * n;

 

입력값과 정답의 범위가 크기 때문에 자료형 관리도 중요했습니다. n과 심사 시간은 각각 int 범위에 들어가더라도 두 값을 곱한 결과는 int 범위를 넘을 수 있습니다.

 

특히 결과를 long long 변수에 저장하는 것만으로는 충분하지 않습니다. 두 피연산자가 모두 int라면 곱셈이 먼저 int로 수행된 뒤 변환되므로, 연산 전에 하나를 long long으로 변환해야 합니다.

 

판정 과정에서도 모든 심사관의 처리 인원을 계속 더하면 합계가 매우 커질 수 있습니다. 따라서 합계가 n 이상이 되는 순간 반복을 종료하면 오버플로 위험과 불필요한 계산을 줄일 수 있습니다.

 

이번 문제를 통해 최솟값을 구하는 문제라도 정답을 직접 계산할 필요는 없다는 점을 학습했습니다. 정답 후보가 가능한지를 빠르게 판정할 수 있고, 그 판정에 단조성이 존재한다면 파라메트릭 서치를 적용할 수 있습니다.

 

앞으로 비슷한 문제를 보면 먼저 다음 내용을 확인해야겠습니다.

• 정답이 될 수 있는 값의 범위를 설정할 수 있는지
• 특정 값이 가능한지 빠르게 판정할 수 있는지
• 후보 값이 변할 때 판정 결과가 한 방향으로 변하는지
• 입력값뿐 아니라 중간 계산 결과에도 적절한 자료형을 사용했는지