[종만북] 알고리즘 설계 패러다임 - 무식하게 풀기

Brute-force (=exhaustive search)

컴퓨터의 계산 능력을 이용해 가능한 경우의 수를 모두 나열하면서 답을 찾는 방법

 

1. 재귀 호출과 완전 탐색

◽ 재귀 호출

• 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 과정

• 재귀 호출에 사용되는 함수가 재귀 함수 ex) 1부터 n까지의 합

• Base case : 더 이상 나눌 수 없는 가장 작은 단위의 작업 ex) 1부터 n까지의 합에서 n이 1이면 return 1

• 존재하는 모든 입력이 base case의 답을 이용해 계산될 수 있도록 base case를 선택해야 함

 

🔑 Boggle game

 

① 문제의 분할

▫ 시작 위치 글자가 주어진 단어 첫 글자와 다르면 False

▫ word의 첫 글자를 제외한 word[1..]을 word와 인접한 상하좌우 대각선 여덟 칸에서 찾기

 

② 기저 사례의 선택

▫ 위치 (x, y)에 있는 글자가 주어진 단어의 첫 글자가 아닐 때

▫ 원하는 단어가 한 글자일 때(항상 성공하는 케이스)

 

cf. 입력이 잘못되거나 범위에서 벗어난 경우도 기저 사례로 선택해 맨 처음에 처리해준다면 코드가 간결해짐

 

③ 구현

▫ 완전 탐색의 시간 복잡도 분석

• 가능한 후보의 수가 시간 복잡도

▫ 완전 탐색 접근 방법

• 완전 탐색에 드는 시간은 가능한 답의 수에 정확히 비례하기 때문에 최대 크기의 입력 가정 후 답 개수를 계산해서 모두 제한 시간 안에 처리할 수 있을지 생각

• 가능한 모든 답의 후보를 만드는 과정을 여러 개의 선택으로 분할

• 하나를 선택해 답의 일부를 만들고, 나머지 답은 재귀 호출을 통해 완성

• 선택지가 하나 밖에 남지 않았거나 하나도 남지 않은 경우를 기저 사례로 선택

 

2. 최적화 문제

 

🔑 Traveling Sales-man Problem(TSP) 재귀 호출 알고리즘

int n;                        // 도시의 수

double distance[MAX][MAX];    // 두 도시 간 거리 저장 배열

/* 
path : 지금까지 만든 경로
visited : 각 도시의 방문 여부
currentLength : 지금까지 만든 경로의 길이
*/ 

double shortestPath(vector<int>& path, vector<bool>& visited, double currentLength) {
    if (path.size() == n) {
        return currentLength + distance[path[0]][path.back()]'

    double ret = INF;        // 매우 큰 값으로 초기화

    // 다음 방문할 도시 모두 확인
    for (int next = 0; next < n; ++next) {
        if (visited[next]) continue;

        int here = path.back();

        path.push_back(next);

        visited[next] = true;

        // 나머지 경로를 재귀 호출 통해 완성하고 최단 경로의 길이 얻기
        double cand = shortestPath(path, visited, currentLength + distance[here][next]);

        ret = min(ret, cand);

        visited[next] = false;

        path.pop_back();
     }

     return ret;
}   

 

3. 많이 등장하는 완전 탐색 유형

◽ 모든 순열/조합 만들기

◽ 2^n가지 경우의 수 만들기

 

관련 문제는 백준과 프로그래머스에서 풀어봐야겠다.