완전탐색(brute force)

모든 경우의 수를 탐색하는 유형이다. 순열 or 조합에 로직이 섞인 형태이며, 1억 시간복잡도 미만인 경우 시도해볼만 하다.

아래와 같은 형태의 로직을 기억해둘 필요가 있다. 배열 순회시 각 원소를 포함하는지-포함하지 않는지 여부에 따라 2^n 형태의 경우의 수를 계산하는 로직이다.

void go(int idx, int sum)
{
    if(idx == n){
        ret = max(ret, sum % 11);
        cnt++;
        return;
    }
    go(idx + 1, sum + v[idx]);
    go(idx + 1, sum);
}

원소 합을 가지고 로직을 꾸릴때, 1개씩 추가로 뽑아 그것을 더한 값과 더하지 않은 값 두 가지에 대한 재귀를 호출하면 기저사례에 따라 최종 경우의 수가 총 2^n개로 나타난다.

백트래킹

백트래킹은 완탐 과정에서 중간에 더 이상 탐색하지 않아도 되는 조건을 설정하여 탐색을 종료하는 방법이다.