Notice: 이 글은 전체탐색법의 후행 내용으로서, 먼저 제 블로그의 전체탐색법을 보시고 이 포스트를 보시는 것을 추천드립니다!
탐색공간의 배제
전체탐색법은 대부분의 경우 해를 구할 수 있는 알고리즘이다. 하지만 실행시간이 너무 길어 제한 시간 내에 문제를 해결할 수 없는 경우가 많다. 탐색공간의 배제는 전체탐색 알고리즘을 구현하는 데 있어서 더 이상 탐색하지 않더라도 해를 구하는 데 문제가 없는 부분을 판단하여 이 부분에 대해서 탐색을 하지 않으므로 탐색의 효율을 높이고자 하는 방법이다.
탐색공간의 배제는 전체탐색에서 불필요한 탐색공간을 탐색하지 않음으로써 알고리즘의 효율을 향상시킨다. 이와 같이 탐색공간을 배제하는 방법은 다양하며 가장 기본 전략은 전체탐색설계와 같이 탐색으로 시작하여 모든 공간을 탐색하는 것이 아니라 일정한 조건을 두어 탐색영역을 배제하는 것이다.
배제되는 탐색공간의 크기에 따라 알고리즘의 성능의 향상 폭이 달라진다. 하지만 잘못 설계를 하여, 해가 있는 상태를 배제하면 해를 구할 수 없는 경우가 발생한다. 따라서 탐색 영역을 배제할 때는 엄밀한 수학적 접근이 필요하다. 이 설계방법은 탐색영역을 배제하는 방법에 따라서 수학적 배제, 경험적 배제, 구조적 배제로 나눌 수 있다.
각 방법에 대해서 자세히 알아보자.
수학적 배제를 이용한 설계
탐색 공간 중 배제할 영역을 수학적 증명으로 결정하는 방법으로는 이분탐색 알고리즘 이 있다. 이는 일종의 수학적 배제를 이용하여 탐색공간을 줄여나가는 알고리즘 설계방법 이라고 할 수 있다.
오름차순으로 정렬된 상태의 이분탐색에서 현재 탐색한 값이 목표하는 값보다 작다면, 현재 탐색 위치의 왼쪽 영역에는 해가 존재할 가능성이 없다. 이는 수학적으로 쉽게 증명 할 수 있다.
따라서 왼쪽 영역에 대해서는 탐색할 필요가 없음을 알 수 있다. 그러므로 다음 탐색영역은 이를 배제하고 오른쪽 영역만 탐색하는 방법이다. 이와 같이 수학적으로 탐색할 필요가 없음이 증명된 공간들을 배제해 나가며 탐색하는 것과 같은 접근법이 수학적 배제를 이 용한 방법이라고 할 수 있다.
수학적 배제로 알고리즘을 설계할 경우, 공간을 배제할 원리를 수학적으로 증명한 후, 이 방법을 반복적으로 해를 찾을 때까지 적용해 나가며 해를 찾는다. 탐색공간에서 선택 배제된 부분은 수학적으로 탐색할 필요가 없으므로, 일반적으로 탐색법이긴 하지만 백트랙 없이 선형으로 진행되는 경우가 많다.
수학적으로 공간을 배제해 나가는 이 방법은 일종의 탐욕법(greedy)이라고 할 수 있으며, 엄밀하게 수학적으로 증명을 하기 때문에 수학적 탐욕법(mathematical greedy)라고 할 수 있다.
하지만 수학적 증명 없이, 직관적으로 현재 상태만으로 잘못된 판단을 하게 되면 올바른 해를 구할 수 없는 가능성을 가지는 단순 탐욕법이 될 수 있으므로 주의해야 한다. 하지만 단순 탐욕법의 경우에도 다양한 응용법이 있으므로 다음에 다루도록 한다.
다음 예는 루트 정점에서 출발하여 각 정점의 값을 누적하며 마지막 정점까지의 합을 최대화하는 최적화문제이다. 이 문제의 목적은 값을 최대화 하는 것이므로 다음 [영역배제의 규칙]을 적용하여 탐색 영역을 배제해 나가보자.
영역배제의 규칙:
현재 상태에서 다음으로 탐색할 수 있는 정점들 중 더 높은 점수가 있는 정점으로 탐색한다.
(즉, 더 작은 점수가 있는 정점의 영역을 배제한다.)
이 규칙은 수학적으로 설득력이 있어 보인다. 왜냐하면 값을 최대화하기 위해서는 작은 값보다는 큰 값이 이득이 되기 때문이다. 하지만 엄밀한 수학적 증명은 하지 않았다. 이 방법으로 탐색을 진행하는 과정은 다음과 같다.
처음 출발점이 루트이므로 루트에 적힌 3점을 획득하여 현재 점수는 3점이다.
다음으로 이동할 수 있는 정점들은 왼쪽 아래로 연결된 8점이 기록된 정점과 오른쪽 아래로 연결된 2점이 기록된 정점의 2가지이다. 이 상태에서 [영역배제의 규칙]을 적용하여 값이 더 큰 8점이 기록된 정점을 선택하고 2점이 기록된 정점을 배제하고 진행한다.
이 규칙을 적용하여 마지막까지 탐색한 결과는 위 그림에서 구한 해는 3-8-4-5를 선택하게 되며 이 때 얻은 점수는 3+8+4+5 이 된다. 과연 20점 이상을 획득할 수 있는 경로는 존재하지 않을까? 다음 그림을 보자.
위 결과를 보면 알 수 있듯이 3+2+9+8=22의 경로가 존재하며 앞 에서 영역을 배제했던 규칙이 잘못됐음을 알 수 있다. 수학적 배제는 엄밀한 수학적 접근 없이, 단순히 직관적으로 배제의 규칙을 결정하면 최적해를 구할 수 있음을 보장할 수 없다. 하지만 구현이 간단하며, 일반적으로 최적해와의 차이가 크지 않은 해를 구할 수 있다는 장점을 이용하여 다른 설계법에 응용할 수 있으므로 나중에 다시 살펴보기로 하자.
주어진 문제들을 통하여 수학적 배제 방법으로 알고리즘을 설계해보자.
약수의 합
한 정수 n을 입력받아서 n의 모든 약수의 합을 구하는 프로그램을 작성하시오.
예를 들어 10의 약수는 1, 2, 5, 10이므로 이 값들의 합인 18이 10의 약수의 합이 된다.
입력
첫 번째 줄에 정수 n이 입력된다. (단, 1 <= n <= 10,000,000,000(100억))
출력
n의 약수의 합을 출력한다.
-------------------
입력 예
10
출력 예
18
이 문제는 전체탐색법 - 약수의 합과 동일한 문제이다. 차이점은 앞의 문제가 입력값의 정의역이 100,000이었던 것에 반해,이 문제에서는 입력값이 100억으로 커졌다는 것이다.
앞의 문제에서 작성했던 풀이는 다음과 같다.
#include <stdio.h>
int n;
int solve() {
int ans=0;
for(int i=1; i<=n; i++ )
if(n%i==0)
ans+=i;
return ans;
}
int main() {
scanf("%d", &n);
printf("%d\n", solve());
}
이 소스코드는 1부터 n까지의 모든 원소들을 탐색하여, 탐색 대상인 수 i가 n의 약수 라면 취하는 방식으로 진행된다.
따라서 계산량은 O(n)이다.
이번 문제는 n의 최댓값이 100억이므로 이 방법으로는 너무 많은 시간이 걸린다. 따라서 탐색영역을 배제해야 할 필요가 있다.
먼저 간단한 수학적인 원리들을 생각해보자. 먼저 다음 정리를 이용하자.
모든 자연수 n에 대하여 1과 n은 항상 n의 약수이다.
이 원리를 이용하면 위 소스코드의 8행의 탐색범위를 줄여서 다음과 같이 표현할 수 있다.
for(int i=2; i<n; i++)
if(n%i==0)
ans+=i;
원래 소스코드보다 탐색공간이 줄어들긴 했으나 효율을 높이기에는 너무 미미하기 때문에 효율향상을 느낄 수 없다. 하지만 위 아이디어를 조금 응용하면 탐색공간을 많이 줄일 수 있다.
위 아이디어를 응용하기 위해서 다음 원리를 적용할 수 있다.
모든 자연수 n에 대하여,
2이상 n미만의 자연수들중 가장 큰 n의 약수는 n/2를 넘지 않는다.
이 원리를 적용하면 다음과 같이 탐색영역을 줄일 수 있다.
for(int i=2; i<n/2; i++)
if(n%i==0)
ans+=i;
이 알고리즘은 탐색영역이 처음의 소스코드의 반이하로 줄어든 것이다. 따라서 실행시간 은 2배 이상 빨라질 것을 예상할 수 있다.
수학적인 아이디어로 탐색 영역을 반 정도 줄였지만 아직도 매우 큰 입력 값을 처리하기에는 시간이 너무 오래 걸린다. 탐색 공간을 더 배제할 수 있는 아이디어를 생각해보자.
임의의 자연수 n의 약수들 중 두 약수의 곱은 n되는 약수 a와 약수 b는 반드시 존재한 다. 단, n이 완전제곱수일 경우에는 약수 a와 약수 b가 같을 수 있다. 자연수 10의 약수를 통해서 알아보자. 자연수 10의 약수의 개수는 4개이며 다음과 같다.
{ 1, 2, 5, 10}
위 집합을 살펴보면 아래와 같은 관계를 찾을 수 있다.
|--|
{ 1, 2, 5, 10}
|_________|
10의 약수 관계
위 그림에서 알 수 있듯이 1과 10의 곱은 10이고 2와 5의 곱은 10이다. 약수의 개수를 $c$개라고 하고, $d_i$를 $n$의 약수 중 $i$번째 약수라 하면 다음과 같은 식이 성립한다.
Expression: $ n = d_k * d_{c-k+1}$
즉, $k$번째 원소와 $c-k+1$번째 원소의 곱은 항상 $n$이다. 이 원리를 적용하면 10의 약수 를 구할 때, 1과 2만 탐색하면 5와 10을 알 수 있으므로 모든 약수를 구할 수 있다.
단, $n$이 완전제곱수 일 경우에는 약수의 개수가 홀수이므로 $d_k$번째 원소와 $d_{c-k+1}$번째 원소가 같을 경우가 한 건 존재한다. 완전제곱수인 16의 약수를 살펴보자.
|-----|
{ 1, 2, 4, 8, 16}
|____________|
16의 약수 관계
위 그림에서 알 수 있듯이 완전제곱수인 경우에는 $\lceil{c\over2}\rceil$번째 원소는 짝이 없다.
따라서$d_{\lceil{c\over2}\rceil} * d_{\lceil{c\over2}\rceil} = n$이 된다. 즉 4와 4를 곱하여 16을 만들 수 있다.
이 원리를 적용하면 최악의 경우 2부터 $\sqrt{n}$까지만 탐색하면 모든 약수를 알 수 있다.
즉 100의 모든 약수를 구하려면 2부터 10까지만 조사해 보면 된다.
{2, 3, 4, 5, 6, 7, 8, 9, 10}
이 수들 중 10의 약수인 것만 찾아보면 다음과 같다.
{2, 4, 5, 10}
위 약수들을 이용하여 짝을 찾아서 정리하면 다음과 같다
{2, 4, 5, 10, 20, 25, 50}
여기에 1과 100은 당연히 100의 약수이므로 문제의 해는 다음과 같다.
1 + 2 + 4 + 5 + 10 + 20 + 25 + 50 + 100 = 217
탐색영역을 [2, $\sqrt{n}$]로 설정할 때 일반적으로 다음과 같이 프로그램을 작성한다.
// include <math.h>
for( i = 1 ; i <= sqrt(n) ; i++ )
// 또는
for(i=1;i*i<=n; i++)
이와 같이 간단한 수학적인 아이디어를 활용하면 효율적인 소스코드를 작성할 수 있으 므로 항상 이런 아이디어를 활용할 수 있도록 익혀두자.
이처럼 탐욕적인 방법을 이용하면 큰 범위의 수도 컴퓨터 없이 쉽게 계산할 수 있다. 그런데 이 방법을 프로그래밍으로 표현하기 위해서 주의할 점이 있다.
입력값 n이 100억 이기 때문에 자료형 int로는 이 값을 처리할 수 없다. 따라서 64bit형 정수인 long long int형을 활용해야 된다. 이 방법을 알고리즘으로 표현하면 다음과 같다.
#include <stdio.h>
long long int n;
long long int solve() {
long long int i, ans = 0;
for(i=1; i*i<n; i++)
if(n%i==0)
ans+=(i+n/i);
if(i*i==n)
ans += i;
return ans;
}
int main() {
scanf("%lld", &n);
printf("%lld\n", solve());
return 0;
}
소수 구하기
한 정수 n을 입력받는다.
n번째로 큰 소수를 구하여 출력한다.
예를 들어 n이 5라면
자연수들 중 소수는 2, 3, 5, 7, 11, 13, ...이므로
구하고자 하는 5번째 소수는 11 이 된다.
-----------------------------------
입력
첫 번째 줄에 정수 n이 입력된다.
( 단, 1 <= n <= 100,000 )
출력
n 이하의 소수들의 합을 구하여 출력한다.
입력 예 출력 예
5 11 77 389
일반적으로 소수를 구하는 방법은 약수가 2개라는 성질을 이용하는 경우가 많다. 이 성질을 이용하여 임의의 정수 $k$가 소수인지 판단하는 알고리즘을 다음과 같이 만들 수 있다.
bool isPrime(int k) {
int cnt=0;
for(int i=1; i<=k; i++)
if(k%i==0) cnt++;
return cnt==2;
}
이 방법은 계산량이 O($n$)이므로 효율이 좋지 않다. 결국 $k$번째 소수를 구하는 알고리즘은 O($nk$)정도의 계산량이 요구되므로 원하는 시간 내에 답을 구하지 못할 가능성이 크다.
효율을 높이기 위해서는 탐색공간의 배제가 필요하다. 어떤 아이디어로 탐색공간을 줄 일 수 있을까?
먼저 위 함수는 소수인지 판단하는 함수이며, 소수가 아니라면 약수가 몇 개이건 합성수인 것은 변함이 없으므로, 약수가 2개를 초과한다면 더 이상 탐색할 필요가 없다. 따라서 다음과 같이 isPrime 함수를 수정하여 탐색공간을 줄일 수 있다.
bool isPrime(int k) {
int cnt=0;
for(int i=1; i<=k; i++) {
if(k%i == 0) cnt++;
if(cnt>2) break;
}
return cnt==2;
}
이와 같이 처리하면 대부분의 합성수는 매우 빠른 시간 내에 소수가 아님을 판정할 수 있다. 그리고 위 알고리즘을 다음과 같이 표현해도 된다. 각자 코딩스타일에 맞추어 원하는 방법을 익힐 수 있도록 한다.
bool isPrime(int k) {
int cnt=0;
for(int i=1; i<=k && cnt<=2; i++) {
if(k%i == 0) cnt++;
}
return cnt==2;
}
이번에 소스코드는 3행의 반복문의 반복조건을 바꾸어 처리하고 있다. 이렇게 하여 합성수를 빠르게 검사할 수 있지만 결국은 $k$번째 소수를 찾는 것이 목적이므로 소수를 검사할 때는 여전히 많은 시간이 걸린다.
소수를 보다 빠르게 검사할 수 있는 방법은 무엇일까?
다음 명제를 생각해보자.
임의의 자연수 $n$이 소수라면 $n$의 약수는 1과 n만 존재한다.
위 명제를 조금 변경하면 다음과 같은 원리를 생각할 수 있다.
임의의 자연수 $n$이 소수라면 구간 [2, $n-1$]에서 약수는 존재하지 않는다.
따라서 소수 판정 알고리즘을 다음과 같이 줄일 수 있다.
bool isPrime(int k) {
int cnt=0;
for(int i=2; i<k; i++) {
if(k%i == 0) false;
}
return true;
}
이 방법도 합성수는 매우 빠르게 판정할 수 있지만 소수 판정은 시간이 많이 걸리는 단점이 있다.
하지만 이 방법으로부터 소수를 매우 빠르게 판정할 수 있는 방법을 만들 수 있다.
주어진 범위에서 약수가 없어야 하므로, 약수의 존재성만 파악하면 된다. 약수의 존재성을 파악하기 위해서 모든 범위를 검사할 필요는 없다. 앞서 약수 문제에서 다루었던 것과 같이 $n$의 약수를 구하기 위해서 탐색을 $\sqrt{n}$까지만 탐색하면 된다. 소수판정 에서도 이 원리를 그대로 적용할 수 있다. 이 원리를 적용하여 소수 판정 알고리즘을 완성 하면 다음과 같다.
bool isPrime(int k) {
int cnt=0;
for(int i=2; i*i<=k; i++)
if(k%i == 0) return false;
return true;
}
이 알고리즘은 매우 빠른 시간에 소수를 판정할 수 있다. O($\sqrt{n}$)으로 처리할 수 있다. 이 방법보다 더 빠른 방법이 있다. “에라토스테네스의 체”라는 방법을 이용하 면 더 빠른 시간에 $k$번째 소수를 구할 수 있다. “에라토스테네스의 체”는 다음과 같은 단계를 거쳐 소수를 구한다.
준비. 2부터 n까지 차례로 숫자를 쓰고, 2부터 탐색을 시작한다.
1단계. 현재 탐색 중인 수가 지워지지 않았으면 그 수는 소수이다.
2단계. 1단계에서 그 수가 소수이면 그 수의 배수를 모두 지운다.
3단계. 만약 아직 탐색이 끝나지 않았으면 다음 수를 탐색할 준비를 하고 1단계로 간다.
4단계. 지워지지 않은 모든 수는 소수, 지워진 수는 합성수이다.
이 “에라토스테네스의 체”를 이용해도 빠른 시간에 $k$번째 소수를 구할 수 있다.
다음 포스트를 참고하면 좋다. - 에라토스테네스의 체
경험적 배제를 이용한 설계
경험적 배제는 전체탐색법을 기본으로 한 알고리즘 설계 방법이다. 처음 시작은 전체탐색과 마찬가지로 해가 될 수 있는 모든 공간을 탐색해 나간다. 차이점은 특정 조건을 두고, 이 조건을 기준으로 다음 상태를 계속 탐색할지의 여부를 결정 한다.
여기서의 특정 조건이란, 더 이상 탐색하더라도 해를 구할 수 없음을 판단할 수 있는 조건을 말한다. 이 조건의 설정은 알고리즘이 시작될 때는 정할 수 없고, 탐색을 진행하는 중 에 조건을 설정하고, 탐색한 영역이 넓어질수록 상황에 따라 조건이 갱신된다. 따라서 탐색 한 정보, 즉 경험한 정보를 이용해서 배제할 조건을 정하기 때문에 경험적 배제라고 한다.
경험적 배제는 일반적으로 가지치기(branch & bound)라고 한다. 이는 마치 탐색구조를 나무로 비유하고, 탐색하지 않는 분기에 대해서 자르는 것이 마치 나무를 관리할 때 가치 를 쳐내는 것과 유사하여 붙여진 이름이다.
다음과 같은 탐색구조가 가지는 문제가 있다.
위 구조에서 각 번호는 탐색할 순서이다. 만약 2번에서 3번으로 진행하려고 할 때, 3번 정점이 알고리즘에서 설정한 조건을 만족한다면 3번 정점 이하의 모든 정점들을 더 이상 탐색할 필요가 없으며, 바로 9번으로 진행할 수 있다.
위 그림은 더 이상 필요 없음을 판단한 영역을 배제하고 탐색한 결과를 나타낸다. 이는 결과적으로 11회 탐색해야 할 문제를 6회의 탐색으로 동일한 결과를 얻을 수 있기 때문에 알고리즘의 효율을 향상시킬 수 있다.
일반적으로 더 이상 탐색할 정점이 없어서 되돌아오는 것을 백트랙 or 백트래킹(Backtracking)이라고 한다. 하지만 위의 예와 같이 3번 정점에서 되돌아 온 흐름은 백트랙과는 다르다.
이렇듯 어떤 조건에 의해서 더 탐색할 공간이 있음에도 불구하고 돌아오는 흐름을 바운딩(bounding) 혹은 커팅(cutting)라고 한다.
바운딩은 우리가 공을 벽에 던지면 튕겨 나오는 상태를 말한다. 마치 3번 정점이 벽과 같이서 흐름이 튕기는 것처럼 느껴지기 때문에 바운딩이라는 용어를 쓴다. 이 용어를 이해하면 branch & bound라는 이름의 의미를 알 수 있다.
경험적 배제 기법의 핵심은 더 이상 탐색할 필요가 없는 지점을 판단하는 기준을 정하는 것이다. 이 판단의 근거는 일반적으로 탐색 중에 얻을 수 있는 정보를 활용하는 경우가 대부분이다. 앞에서 다루었던 전체탐색법의 예제들 중 분기한정으로 효율을 향상시킬 수 있는 예제를 통하여 조건을 설정하는 방법을 익혀보자.
연구활동 가는 길
*위의 그래프를 참고하여 문제를 풀어보자*
정올이는 GSHS에서 연구활동 교수님을 뵈러 A대학교를 가려고 한다.
출발점과 도착점을 포함하여 경유하는 지역 n개, 한 지역에서 다른 지역으로 가는 방법이 총 m 개이며
GSHS는 지역 1이고 A대학교는 지역 n이라고 할 때 대학까지 최소 비용을 구하시오.
단, n은 10 이하, m은 30 이하, 그리고 한 지역에서 다른 지역으로
가는 데에 필요한 비용은 모두 200 이하 양의 정수이며
한 지역에서 다른 지역으로 가는 어떠한 방법이 존재하면
같은 방법과 비용을 통해 역방향으로 갈 수 있다.
위의 그래프는 예를 보여준다.
(단, 정점a->정점b로의 간선이 여러 개 있을 수 있으 며, 자기 자신으로 가는 정점을 가질 수도 있다.)
최소 비용이 드는 경로 : 1→3→5→7, 최소 비용 : 69+59+21=149
입력
첫 번째 줄에는 정점의 수 n과 간선의 수 m이 공백으로 구분되어 입력된다.
다음 줄부터 m개의 줄에 걸쳐서 두 정점의 번호와 가중치가 입력된다. (자기 간선, 멀티 간선이 있을 수 있다.)
출력
대학까지 가는 데 드는 최소 비용을 출력한다. 만약 갈 수 없다면 “-1”을 출력.
----------------------------
입력 예
7 11
1 2 47
1 3 69
2 4 57
2 5 124
3 4 37
3 5 59
3 6 86
4 6 27
4 7 94
5 7 21
6 7 40
출력 예
149
이 문제는 앞에서 전체탐색법으로 이미 해결했던 문제이다. 하지만 여기서 탐색을 배제 할 조건을 설정하여 탐색영역을 줄여보자. 먼저 탐색배제 조건을 설정해야 한다. 이 문제에서는 전체의 최소 이동거리를 구하는 것이므로 탐색 중 임의의 한 경로를 찾았을 때마다 새로운 거리를 구할 수 있으므로 탐색 중 다음과 같은 배제 조건을 설정할 수 있다.
현재 탐색한 거리 > 지금까지 구한최소 경로의 거리
위 조건을 만족할 경우, 더 이상 탐색하지 않더라도 해를 구하는 데 전혀 문제가 없음을 알 수 있다. 이 조건을 적용하여 탐색하는 과정의 일부를 살펴보자.
위와 같은 단계를 거치면서 진행하게 되면 해는 점점 더 좋아지고 커팅의 효율은 더 높아진다.
위의 방법으로 작성한 소스코드는 다음과 같다.
#include <stdio.h>
int n, m, G[11][11], sol=0x7fffffff, chk[11];
void solve(int V, int W) {
if(W>sol) return;
if(V==n) {
if(W<ol) sol=W;
return;
}
for(int i=1; i<=n; i++)
if(!chk[i] && G[V][i]) {
chk[i]=1;
solve(i, W+G[V][i]);
chk[i] = 0;
}
}
int main(void) {
scanf("%d %d", &n, &m);
for(int i=0; i<m; i++) {
int s,e,w;
scanf("%d %d %d", &s, &e, &w);
G[s][e]=G[e][s]=w;
}
solve(1, 0);
printf("%d\n", sol==0x7fffffff ? ‐1:sol);
return 0;
}
성능 검증을 하기 위하여 counter이라는 변수를 이용하여 해를 구하기까지 몇 개의 상태를 탐색하는지 카운팅하는 프로그램을 작성하고, 3번의 임의의 입력데이터를 이용하여 테스트를 해 보자.
검증하는 프로그램과 검증 데이터 셋은 다음과 같다.
#include <stdio.h>
int n, m, G[11][11], sol=0x7fffffff, chk[11];
int counter; // 추가
void solve(int V, int W) {
if(W>sol) return;
counter++; // 추가
if(V==n) {
if(W<ol) sol=W;
return;
}
for(int i=1; i<=n; i++)
if(!chk[i] && G[V][i]) {
chk[i]=1;
solve(i, W+G[V][i]);
chk[i] = 0;
}
}
int main(void) {
scanf("%d %d", &n, &m);
for(int i=0; i<m; i++) {
int s,e,w;
scanf("%d %d %d", &s, &e, &w);
G[s][e]=G[e][s]=w;
}
solve(1, 0);
printf("%d\n", sol==0x7fffffff ? ‐1:sol);
printf("[탐색한 정점 수 %d개]\n", counter);
return 0;
}
다음은 테스트 한 입력데이터 3개이다.
입력 1
5 7
1 2 2
1 3 10
1 4 7
2 5 4
2 3 6
4 5 3
3 5 4
입력 2
5 8
1 2 2
1 3 1
1 4 3
2 5 2
2 3 1
4 5 3
3 5 2
1 5 14
입력 3
7 11
1 2 47
1 3 69
2 4 57
2 5 124
3 4 37
3 5 59
3 6 86
4 6 27
4 7 94
5 7 21
6 7 40
위 3개의 데이터에 대한 결과이다.
다음은 배제된 공간의 비율을 보여준다.
위 표에서 알 수 있듯이 탐색한 정점의 수가 많이 줄어든 것을 알 수 있다. 대략적으로 원래 방법보다는 2배 이상 빨라졌음을 알 수 있다. 이는 데이터의 특성에 따라 달라질 수 있으니 참고하기 바란다.
이와 같은 알고리즘의 효율은 처음에 구한 해가 얼마나 질이 좋은 해인가에 따라 결정된다. 그렇다면 초반에 질이 좋은 해를 어떻게 구할 수 있을까? 앞에서 다룬 내용 중에 단순 탐욕법이라는 것이 있었다. 이는 현재 상태에서 수학적인 검증 없이 가장 유리한 상태만을 탐색하는 방법이다. 이 방법이 최적해를 구할 수는 없지만 비교적 질이 좋은 해를 구할 수 있다는 사실을 다루었다.
따라서 단순 탐욕법을 이용하여 처음에 하나의 해를 구한다. 일반적으로 이 해가 품질이 좋을 확률이 높으므로 이 해를 처음해로 탐색배제 조건의 기준이 된다. 그리고 위 알고리즘을 실행하면 평균적인 효율이 향상될 가능성이 크다.
단순 탐욕법으로 처음 해를 구하는 소스코드를 추가한 알고리즘은 다음과 같다.
#include <stdio.h>
int n, m, G[1001][1001], sol, chk[1001], greedy_chk[1001];
void greedy_ans(int V) {
int W=0, t;
greedy_chk[V]=1;
while(V!=n) {
int min=0x7fffffff;
for(int i=1; i<=n; i++)
if(!greedy_chk[i] && G[V][i] && G[V][i]<min) {
greedy_chk[i]=1;
min=G[V][i];
t=i;
}
sol+=G[V][t];
V=t;
}
}
void solve(int V, int W) {
if(W>sol) return; // bounding (cutting)
if(V==n) {
if(W<sol) sol=W;
return;
}
for(int i=1; i<=n; i++)
if(!chk[i] && G[V][i]) {
chk[i]=1;
solve(i, W+G[V][i]);
chk[i]=0;
}
}
int main(void) {
scanf("%d %d", &n, &m);
for(int i=0; i<m; i++) {
int s,e,w;
scanf("%d %d %d", &s, &e, &w);
G[s][e]=G[e][s]=w;
}
greedy_ans(1);
solve(1, 0);
printf("%d\n", sol==0x7fffffff ? ‐1:sol);
return 0;
}
위 알고리즘에서 greedy_ans 함수가 처음 해를 단순 탐욕법으로 구하고 있는 과정을 나타낸다. 단순 탐욕법으로 구한 해는 정답이 아닐 가능성이 크지만, 해의 품질이 좋기 때문에 커팅의 조건으로 적합하다. 단순 탐욕법은 이와 같이 다양한 응용이 가능하다.
마지막으로 전체의 효율을 비교한 결과는 다음과 같다.
다음은 배제된 공간의 비율을 보여준다.
이와 같이 원래 알고리즘 보다 4배 이상 효율이 향상되었음을 알 수 있다. 이와 같이 탐색을 배제하는 방법은 정해진 것이 없고, 여기에서 소개한 방법은 가장 기본적인 배제 방법이다.
여기서 소개한 방법 이외에도 다양한 조건을 설정할 수 있으므로 공간을 배제할 방법을 스스로 설정하여 조건을 추가하면 효율이 좋아질 수 있으므로, 항상 창의적인 사고력을 기를 수 있도록 연습하자.
References
- 문제해결을 위한 창의적 알고리즘
Leave a comment