두 개의 매개변수 (x, y)를 받는 함수 f가 있다고 가정해 보겠습니다. 이때 f(x, y) = z를 만족하는 모든 x, y 쌍을 반환해야 하며, z는 입력으로 주어지고 x, y는 양의 정수입니다.
여기서 중요한 조건은 함수 f가 단조 증가(monotonically increasing) 함수라는 점입니다. 즉, 다음 부등식이 항상 성립합니다.
f(x, y) < f(x + 1, y)
f(x, y) < f(x, y + 1)
x나 y가 커질수록 함수 값이 반드시 증가하기 때문에, 이 성질을 활용하면 탐색 범위를 줄이는 최적화도 가능합니다.
접근 방법
가장 직관적인 방법은 브루트 포스(완전 탐색)입니다. i를 1부터 1000까지, j를 1부터 1000까지 순회하면서 모든 조합에 대해 f(i, j)의 값을 확인하고, 그 값이 z와 같으면 해당 (i, j) 쌍을 결과에 추가하면 됩니다.
알고리즘 단계
- i를 1부터 1000까지 반복합니다.
- j를 1부터 1000까지 반복합니다.
- f(i, j) == z이면 (i, j)를 결과 리스트에 저장합니다.
- 모든 반복이 끝나면 결과 리스트를 반환합니다.
함수의 id 값은 미리 주어진다고 가정하며, id가 1이면 덧셈(x + y), 2이면 곱셈(x * y)을 수행합니다. z 값도 함께 전달됩니다.
C++ 구현 예시
아래 예제 코드를 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<int> > v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << "[";
for(int j = 0; j <v[i].size(); j++){
cout << v[i][j] << ", ";
}
cout << "],";
}
cout << "]"<<endl;
}
class CustomFunction {
int id;
public:
CustomFunction(int id){
this->id = id;
}
int f(int x, int y){
if(id == 1)
return y + x;
else if(id == 2)
return y * x;
return 0;
}
};
class Solution {
public:
vector<vector<int>> findSolution(CustomFunction& c, int z) {
vector < vector <int > > ans;
for(int i = 1; i <= 1000; i++ ){
for(int j = 1; j <= 1000; j++){
if(c.f(i,j) == z){
vector <int> t;
t.push_back(i);
t.push_back(j);
ans.push_back(t);
}
}
}
return ans;
}
};
main(){
Solution ob;
CustomFunction c(1);
print_vector(ob.findSolution(c, 7));
}입력
1 7
출력
[[1, 6],[2, 5],[3, 4],[4, 3],[5, 2],[6, 1]]
동작 원리 살펴보기
id가 1이므로 함수는 덧셈(x + y)을 수행하고, z는 7입니다. 따라서 두 양의 정수의 합이 7이 되는 모든 쌍인 (1, 6), (2, 5), (3, 4), (4, 3), (5, 2), (6, 1)이 순서대로 출력됩니다.
복잡도 분석과 개선 아이디어
위 브루트 포스 방식의 시간 복잡도는 O(1000 × 1000), 즉 최대 약 100만 번의 함수 호출이 발생할 수 있습니다. 하지만 함수가 단조 증가한다는 성질을 이용하면 투 포인터(two-pointer) 기법으로 개선할 수 있습니다.
x를 1부터 시작하고 y를 1000부터 시작한 뒤, f(x, y)가 z보다 작으면 x를 증가시키고, z보다 크면 y를 감소시키면 됩니다. 이렇게 하면 O(x + y), 즉 선형 시간 안에 모든 해를 찾을 수 있어 훨씬 효율적입니다.