문제 설명
정수 배열 arr이 주어졌을 때, 배열의 모든 요소를 삭제하는 데 필요한 최소 연산 횟수를 구하는 것이 과제입니다. 단, 요소를 삭제할 때 다음과 같은 제약 조건이 적용됩니다.
- 배열에서 임의의 요소 하나를 선택하면, 그 요소로 나누어 떨어지는 모든 요소를 한 번에 배열에서 제거할 수 있습니다.
예를 들어 arr[] = {2, 4, 15, 10, 8, 5, 3}인 경우, 모든 요소를 삭제하는 데 3번의 연산이 필요합니다.
- 2를 선택하면 {2, 4, 10, 8}이 삭제됩니다.
- 5를 선택하면 {5, 15}가 삭제됩니다.
- 3을 선택하면 {3}이 삭제됩니다.
알고리즘
이 문제는 그리디(Greedy) 방식으로 해결할 수 있습니다. 작은 수부터 선택하면 해당 수의 배수들이 함께 제거되므로, 전체 연산 횟수를 최소화할 수 있습니다.
- 배열을 오름차순으로 정렬하고, 각 요소의 등장 횟수를 카운트합니다.
- 배열의 앞부분부터 아직 삭제되지 않은(마킹되지 않은) 요소를 선택하고, 그 요소로 나누어 떨어지는 모든 요소를 마킹하여 제거 처리한 뒤, 결과 카운터를 1 증가시킵니다.
정렬된 상태에서 순회하기 때문에 어떤 요소가 먼저 선택되더라도, 그보다 작은 배수는 존재하지 않으므로 항상 최적의 선택이 보장됩니다.
구현 예제
#include <iostream>
#include <algorithm>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
#define MAX 100
using namespace std;
int getMinOperations(int *arr, int n){
int map[MAX] = {0};
sort(arr, arr + n);
for (int i = 0; i < n; ++i) {
map[arr[i]]++;
}
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (map[arr[i]]) {
for (int j = i; j < n; ++j) {
if (arr[j] % arr[i] == 0) {
map[arr[j]] = 0;
}
}
++cnt;
}
}
return cnt;
}
int main(){
int arr[] = {2, 4, 15, 10, 8, 5, 3};
cout << "Minimum required operations = " << getMinOperations(arr, SIZE(arr)) << endl;
return 0;
}출력 결과
위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.
Minimum required operations = 3
코드 설명
- map[MAX]: 각 값의 존재 여부(및 중복 횟수)를 저장하는 카운트 배열입니다.
- sort(): 배열을 오름차순으로 정렬하여 작은 값부터 처리하도록 합니다.
- getMinOperations(): 아직 삭제되지 않은 요소를 만나면, 이후 요소들 중 그 값으로 나누어 떨어지는 모든 값을 map에서 0으로 설정해 제거 처리하고, 연산 횟수를 증가시킵니다.
이 알고리즘의 시간 복잡도는 정렬에 O(n log n), 이중 반복문에 O(n²)이 소요되므로 전체적으로 O(n²)입니다. 배열의 크기가 크지 않은 경우에 효율적으로 동작합니다.