[알고리즘 문제해결 전략]6장. 무식하게 풀기_①

Preview

---

 

1. 재귀 호출과 완전 탐색

2. 최적화 문제

3. 많이 등장하는 완전 탐색 알고리즘

1. 재귀 호출과 완전 탐색

---

재귀 함수:?자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고 나머지를 자신을 호출해 실행하는 함수

완전 탐색? 컴퓨터의 빠른 계산 능력을 이용하여 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법

**재귀 호출의 기저사례: 더 이상 쪼개지지 않는 가장 작은 작업

EX> 0부터 N까지의 숫자들 중 M개를 선택하는 방법에 대한 논의

for(int i = 0; i <= N; i++){
    for(int j = i + 1; j <= N; j++){
        for(int k = j + 1; k <= N; k++){
            //총 M개의 for문이 존재한다.
        }
    }
}

 [코드 1] for문을 이용한 문제 해결

[코드 1]을 보면 원하는 M의 수 만큼의 for문을 직접 적어 줘야하는 문제점이 존재한다. 

vector<int> pick(int N, vector<int>& picked, int picks){
    if(picks == M) return picked;
    
    int min = picked.empty()? 0 : picked.back()+1;
 
    for(int i = min; i <= N; i++){
        picked.push_back(i);
        pick(N, picked, picks + 1);
        picked.pop_back();    
    }
}

[코드 2] 재귀함수를 이용한 문제 해결

[코드 2]를 보면 원하는 M의 수가 어떤 것이든 pick함수의 호출을 통해 문제를 해결할 수 있다.

완전탐색 접근 지침

1. 완전 탐색은 존재하는 모든 답을 하나 씩 검사하는 방법이므로 걸리는 시간은 가능한 답의 수에 비례한다. 때문에 알고리즘의 실행시간은 최대 입력을 가정하여 계산한다. 만약, 제한 시간내에 문제 해결이 불가능할 경우 다른 방법을 모색해본다.

2. 가능한 모든 답의 후보를 만드는 과정을 여러개 선택으로 분할한다. 각 선택은 답의 후보를 만드는 과정의 한 조각을 나타낸다.

3. 그 중 하나의 조각을 선택하여 답의 후보를 만들고 나머지를 재귀호출을 통해 만들어라.

4. 하나가 남거나 없을 경우 답의 생성이 완료된 것이므로 해당 경우를 재귀 호출의 기저사례로 설정하라.

 

2. 최적화 문제

---

어떤 기준에 따라 가장 "좋은" 답을 찾아내는 문제이다.

**즉, 하나의 알고리즘만이 존재하는 문제는 최적화 문제가 될 수 없다. 예를 들어 5사람의 몸무게를 모두 더하는 문제의 경우 최적화 문제가 될 수 없다. 하지만 5사람 중 2사람을 선택하여 최대의 몸무게 합을 구하는 문제는 여러가지의 풀이법이 존재함으로 최적화문제가 될 수 있다.

여행하는 외판원 문제

 가장 유명한 최적화 문제들 중 하나이다.

<problem>

어떤 나라에 n(2 ≤ n ≤ 10)개의 큰 도시가 있다고 한다면 한 영업 사원이 한 도시에서 출발하여 다른 도시들을 전부 한번씩 방문한 다음 시작도시로 돌아오려고 한다. (문제를 간단히 생각하기 위해 모든 도시들이 연결 되어 있다고 하자. 단, 도시들을 연결한 다리의 길이는 동일하지 않다.) 이때 가능한 모든 경로들 중 가장 짧은 경로를 찾아 내라.

고민하기

모든 경우의 수를 고려하여 문제를 푼다고 할때 가능한 경우의 수는 최대 (10 - 1)! = 362880이다. 즉, 1초이내에 가볍게 계산할 수 있다. 

문제풀기

double map[N][N];
 
double TSL(vector<int>& path, vector<bool>& visited, double dist){
    if(path.size() == n){
        return dist + map[path[0]][path.back()];
    }
    
    double ret = 987654321;
    
    for(int i = 0; i < n; i++){
        if(visited[i]) continue;
        int now = path.back();
        path.push_back(i);
        visited[i] = true;
        ret = min(ret, TSL(path, visitied, dist + map[now][i]);
        visited[i] = false;
        path.pop_back();
    } 
    return ret;
}

[코드 3] 외판원 문제 (simple)

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

---

1. 모든 순열 만들기

2. 모든 조합 구하기

3. 2^n가지의 경우의 수 구하기

ex) yes or no에 대하여 판단하며 풀어나가는 문제

4. 출처

---

[코드 1]: 프로그래밍 대회에서 배우는 알고리즘 문제 해결전략 p.148

[코드 2]: 프로그래밍 대회에서 배우는 알고리즘 문제 해결전략 p.149(코드 6.2)

[코드 3]: 프로그래밍 대회에서 배우는 알고리즘 문제 해결전략 p.167(코드 6.7)