문제
n개의 정수가 담긴 벡터에서 r개를 선택하여 다른 벡터에 담아야 한다.
계획
어떤 알고리즘을 선택할 것인가?
n개 중에 r개를 선택하는 과정은 주어진 벡터에서 1 개를 선택하는 과정을 반복하는 행위로 볼 수 있다.
어떤 문제를 동일한 소문제들로 쪼개서 해결하기에 적절한 방법은 재귀함수가 있다.
재귀함수로 문제를 해결하기 위해서는 어떤 정보들이 주어져야 할까?
어떤 정보를 함수로 전달해야할까를 결정하기 위해서는 함수가 해야할 일을 명확하게 정의할 필요가 있다.
이 재귀함수는 주어진 순차열에서 1개의 수를 고르고 나머지 choose는 재귀 호출로 해결하는 함수이다. 이때 첫 수는 from[0], from[1]...from[size - n]까지 될 수 있고 둘 째 수는 첫 수의 다음 수부터 from[size - n + 1]까지 될 수 있다.
고로 이 함수는 시작 index를 전달받아야 하고 함수의 호출 횟수를 결정하는 몇 개의 수를 더 골라야할지를 결정하는 변수도 전달받아야 한다.
void combination(const vector<int>& from, vector<int>& to, int start, int r)함수의 header는 이처럼 결정할 수 있다.
기저 사례에 대한 결정
만일 더 이상 골라야할 수가 없을 때 이 함수는 끝나야 한다.
if(r == 0)
{
f(to);
}재귀 호출부에 대한 결정
먼저 from[i]를 push하고 재귀함수를 호출한다.
이때 중요한 점은 호출이 끝나고 반드시 from[i]를 pop해야 한다는 것이다.
그래야 다음 case가 깔끔하게 들어가지기 때문이다.
for(int i = start; i < from.size(); i++)
{
to.push_back(from[i]);
combination(from, to, i + 1, r - 1);
to.pop_back();
}만약 i + 1이 벡터의 범위를 초과하더라도 호출된 재귀함수에서 반복문의 조건을 만족하지 못하기 때문에 기저 사례에 도달하지 못하고 반환되기 때문에 문제가 되지 않는다.
회고
안일한 마음으로 함수를 정확하게 정의하지 않고 막무가내로 구현했다가 계획 짜고 처음부터 다시 구현했다. 귀찮아서 제대로 안하면 더 귀찮아질 확률이 높다.
