완전탐색과 백트래킹

1. 완전 탐색

완전 탐색이란 모든 경우의 수를 탐색하는 방법이다.

1) Brute-Force

단순히 조건문/반복문 등을 사용해 모든 경우의 수(case)마다 계산하여 답을 구하는 방법으로, N이 커지는 경우에는 사용이 불가하다.

• 대부분의 경우 사용될 일이 거의 없다고 보면 된다.

2) DFS/BFS

완전 탐색의 경우 DFS/BFS 알고리즘과 함께 활용되는 경우가 많다. 가령 길찾기/최단 거리 탐색/가능한 조합 중 최적의 조합 찾기 등의 경우에 활용될 수 있다.

완전탐색의 경우 입력 데이터(N)이 매우 작거나, 임의의 답을 하나 선택했을 떄, 역추적이 가능한 경우에 주로 사용된다.

2. DP vs DFS

그러나 DP와 DFS의 개념은 차이가 존재한다.

DFS는 그래프(주로 2D)를 탐색하는 데 사용되는 알고리즘으로 경로 탐색에 사용되며, 재귀 함수 or 스택을 사용해 구현된다.

1) DFS 구현 예시

void DFS(int x, int y, int dis)
{
    int cur_x = x;
    int cur_y = y;
    // 도달한 경우
    if (cur_x == h - 1 && cur_y == w - 1 && dis+1 < min_dis)
        min_dis = dis+1;
    // 도달하지 않은 경우, 상하좌우로 탐색
    for (int i = 0;i < 4;i++)
    {
        int nx = cur_x + dx[i];
        int ny = cur_y + dy[i];
        if (nx < 0 || ny < 0 || nx >= h || ny >= w||visited[nx][ny]==true)
            continue;
        else if (visited[nx][ny] == false && map[nx][ny] != 0)
        {
            visited[nx][ny] = true;
            DFS(nx, ny, ++dis);
        }
        else
            continue;
    }
}

반면 DP의 경우, 큰 문제를 하위문제 여러개로 나누어 해결하는 것이 핵심이다. 이를 통해 하위 문제의 결과를 재사용하도록 한다. 가령 DFS/BFS가 적합해 보이나 N이 너무 큰 경우 DP를 고려해보도록 한다.

2) DP 예시

• DP의 경우 프로그래머스-예제를 활용해 구현해보도록 한다.

① 문제 개요

숫자(N)와 사칙연산만으로 number을 표현할 수 있는 방법 중 숫자(N) 사용 횟수의 최솟값을 반환

② 입출력
입력 : N, number
출력 : 최소 N 사용 횟수

③ 풀이

#include <string>
#include <vector>
#include <unordered_set>

using namespace std;

// N을 idx번 사용해서 만들 수 있는 숫자
// getN(5,2) => 55 
int getN(int N, int idx)
{
    int result = N;
    for (int i = 1;i <= idx;i++)
        result = result * 10 + N;
    return result;
}

int solution(int N, int number) 
{
    int answer = 0;
    // N과 사칙연산으로 number 만들기
    if (N == number)
        return 1;
    // DP[I] : i개의 N으로 만들 수 있는 숫자들
    // DP[0] : 1개의 N으로 만들 수 있는 수들의 집합
    // DP[1] : 2개의 N으로 만들 수 있는 수들의 집합 == 2개의 조합 + 1개간 사직연산
    // DP[2] : 3개의 N으로 만들 수 있는 수들의 집합 = 3개의 조합 + 2개와 1개간 사칙연상
    vector<unordered_set<int>> DP(8);
    // 8개 초과 사용 시 -1 반환
    DP[0].insert(N);
    for (int k = 1;k < 8;k++)
    {
        DP[k].insert(getN(N, k));
        for (int i = 0;i < k;i++)
        {
            for (int j = 0;j < k;j++)
            {
                if (i + j + 1 != k)
                    continue;
                for (int a : DP[i])
                {
                    for (int b : DP[j])
                    {
                        // +
                        DP[k].insert(a + b);
                        // -
                        if (a - b > 0)
                            DP[k].insert(a - b);
                        // *
                        DP[k].insert(a * b);
                        // /
                        if (a / b > 0)
                            DP[k].insert(a / b);
                    }
                }
            }
        }
        if (DP[k].find(number) != DP[k].end())
            return k + 1;
    }

    return -1;
}

위 예시를 보면 DP[N+1]을 만들 때 DP[N]을 사용하는 것을 볼 수 있다. 따라서 DP[N+1]을 계산할 때 DP[N]을 활용해 계산 효율성을 향상시킬 수 있다.

그렇다면 여기서, 백트래킹이란 무엇이며 DP와 어떤 연관이 있는가?

3. DP and BackTracking

둘 다 최적화 문제 해결을 위한 기법이나, 차이가 존재한다.

DP의 경우 "부분 문제의 중복"을 피하기 위해 계산 결과를 저장하는 반면, 백트래킹은 DFS or BFS를 시도하다가 실패할 경우 "이전 상태로 돌아가서 다른 가능성을 시도"하는 것이다.

• DP는 부분 문제의 해결책을 저장하고 활용하는 반면, 백트래킹은 재귀적으로 가능성을 탐색하며 되돌아가므로 메모리 사용 측면에서 차이가 존재

4. DP 활용 ①

프로그래머스 예제-2를 활용해 DP를 자세히 알아보도록 한다.

① 문제 개요

수포자
유형1. 1,2,3,4,5,1,2,3,4,5,,
유형2. 2,1,2,3,2,4,2,5,2,1,,,
유형3. 3,3,1,1,2,2,4,4,5,5,3,3,1,1,2,2,,,,

• 주어진 정담을 토대로 최다 정답률이 누구인지 찾아내시오 (최다 동점자 발생 시 오름차순 정렬)

② 입출력
입력 : vector<int> answers
출력 : 최다 정답자

③ 풀이

#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

int ans1[5] = { 1,2,3,4,5 };
int ans2[8] = { 2,1,2,3,2,4,2,5 };
int ans3[10] = { 3,3,1,1,2,2,4,4,5,5};
bool cmp(pair<int, int> a, pair<int, int> b)
{
    if (a.second == b.second)
        return a.first < b.first;
    else if (a.second > b.second)
        return true;
    else
        return false;
}
vector<int> solution(vector < int > answers)
{
    vector<int> answer;
    // 유형(사람)/정답수
    map<int, int>score;
    score[1] = 0;
    score[2] = 0;
    score[3] = 0;
    for (int i = 0;i < answers.size();i++)
    {
        int ans = answers[i];
        if (ans1[i % 5] == ans)
            score[1]++;
        if (ans2[i % 8] == ans)
            score[2]++;
        if (ans3[i % 10] == ans)
            score[3]++;
    }
    vector<pair<int, int>> vec(score.begin(), score.end());
    sort(vec.begin(), vec.end(), cmp);
    if (vec[0].second == vec[1].second)
    {
        if (vec[1].second == vec[2].second)
        {
            answer.push_back(vec[0].first);
            answer.push_back(vec[1].first);
            answer.push_back(vec[2].first);
        }
        else
        {
            answer.push_back(vec[0].first);
            answer.push_back(vec[1].first);
        }
    }
    else
        answer.push_back(vec[0].first);

    return answer;
}

int main()
{
    solution({ 5,5,5,5,5,5,5,5 });
    return 0;
}