프로그래밍 알고리즘

소개글

프로그래밍 알고리즘에 대한 보고서 자료입니다.

목차

- 알고리즘 개론 -

- 다이나믹 #1 -

- 다이나믹 #2 -

- 다이나믹 #3 -

- 그리디 #1 -

- 그리디 #2 -

- 백 트래킹 #1 -

- 백 트래킹 #2 -

본문내용

면, 이 경우는 더 이상 탐색해 나갈 필요가 없다. 벌써 저 위에서 조건이 빗나가 버렸는데 밑으로 내려가봐야 아무것도 안나온다. 이 경우는 밑으로 따라오는 경우를 모두 무시해 버리면 되는 것이다. 이것을 또 트리로 나타내보자.
이 허접한 그림을 보면 위에 있는 트리와 크게 다르지 않음을 느낄 것이다. 여기서 모든 트리를 모두 그리지는 않았다. 다만 유의할 것은 밑에 X자와 O자가 쳐진 맨 왼쪽 아래의 두 노드다. X가 쳐진 노드는 이미 지금까지 누적시킨 부분집합의 합이 m(21)를 넘어버린 경우를 의미한다. 이때는 저 노드 밑으로는 더 이상 탐색할 필요가 없다. 그럼 O가 쳐진 노드의 경우는? 6+5+10=21 즉 답이 튀어나온 귀여운 노드다. 이미 답이 나와버렸으므로, 경우의 수(답)을 하나 증가시키고 더 밑으로 내려갈 필요 없이 다시 돌아가면 된다. 하지만 X,O가 쳐지지 않은 나머지 모든 노드들은 아직 부분집합의 합이 m에 도달하려면 멀었으므로, 좀 더 트리를 내려가면서 계속 탐색해 볼 필요성이 있다. 자! 이제 설명은 끝났다. 소스를 보면서 스스로 공부해 보길 바란다.
#include
const int n=5;
const int m=21;
const int w[n]={5,6,10,11,16}; //보석의 값어치
int cnt; //부분집합의 합이 m이 되는
//경우의 수를 저장하는 변수
void recall(int num, int sum) //num번째 보석에 대해 생각해 본다
{
int i;
if(sum==m) { //조건에 맞으면
cnt++;
}
else {
if(num for(i=0;i<2;i++) {
//i=0이면 w[num]을 추가
//i=1이면 추가시키지 않음.
if(i==0 && sum+w[num]<=m)
recall(num+1, sum+w[num]); //추가시킬때
if(i==1)
recall(num+1, sum); //추가시키지 않을때
}
}
}
}
void main()
{
cnt=0;
recall(0,0); //재귀호출 시작
printf("부분집합의 합이 %d이 되는 경우의 수 : %d\n",m,cnt);
}
크게 어려운 내용은 없다. n-Queen문제보다도 오히려 쉬우므로... recall부분에서 i=0이면 보석을 추가, i=1이면 보석을 그냥 두고 지나치는 것이 포인트.
4. 추적
방금 풀어본 "부분집합의 합 구하기" 문제에서 무언가 부족한듯한 구석을 하나 꼽아보자. 그렇다. 출력은 오로지 경우의 수 뿐, 그 경우의 수가 각각 어떻게 구성된 건지 모른다. 우리가 손수 구했던 것처럼 10+11, 5+16, 5+6+10이란 답도 구해보자. 실제 대회에서도 그냥 달랑 해만 구하시오, 하는 문제는 별로 없다. 어떻게 그 답이 나왔는지 해의 구성요소도 출력해야 하는 경우가 대부분이다. 사실 답을 추적하는 부분은 프로그래밍 기교에 속하는 부분이라 알고리즘 강좌에서는 잘 다루지 않지만, 그래도 비슷한 부류의 문제를 풀어보다 보면 자주 접하게 되는 부분이라 생각되어 짧게나마 설명해 보겠다.
답을 추적하는 기술은 방금 언급했듯 프로그래밍 기교에 속하기 때문에, 사람들마다 개성적인 노하우가 있는 경우가 많다. 필자는 옛날에는 문자열을 사용하는 방법을 애용했지만, 주 언어를 C로 바꾸면서 이제 그 짓은 안한다-_-; C에서 문자열 처리는 정말로 극악하기 때문에...--; 아마 많은 사람들이 쓰고 있을거라 생각하는, 배열에 정답의 경로를 저장해 놓는 방법을 보기로 하자. 아래 소스는 부분집합의 합 구하기 문제의 답을 경로까지 소상히 출력하도록 풀어놓은 것이다. 위 소스와 비교해 보면서 어떤 것이 더해졌는지 잘 보자.
#include
const int n=5;
const int m=21;
const int w[n]={5,6,10,11,16};
int cnt;
int saved[n];
void recall(int num, int sum)
{
int i;
if(sum==m) {
cnt++;
for(i=0;i if(saved[i]==1) printf("%d ",w[i]);
printf("\n");
}
else {
if(num for(i=0;i<2;i++) {
if(i==0 && sum+w[num]<=m) {
//num번째 보석이 선택되면 saved[num]=1 이 된다.
saved[num]=1;
recall(num+1, sum+w[num]);
//재귀호출이 끝남으로서 num번째 보석은 선택이 풀린다.
saved[num]=0;
}
if(i==1) {
//아예 안 훔치기로 작정했으면 saved에 저장할 필요가 없다.
recall(num+1, sum);
}
}
}
}
}
void main()
{
cnt=0;
recall(0,0);
printf("부분집합의 합이 %d이 되는 경우의 수 : %d\n",m,cnt);
}
saved[i]=1이면 i번째 보석은 훔치기로 선택되었단 표시이다. 출력할 때 saved[i]=1이면 출력하는 이유도 거기에 있다.
5. 정리
지금까지 상당히 장황하게 백트래킹에 대한 설명을 늘어놓았다. 백트래킹 강좌를 마무리 지으면서 가장 당부하고 싶은 것은 백트래킹을 쓸 때에는 항상 속도를 염두에 두어야 한다는 것이다. 백트래킹의 특성상 그 속도는 다른 알고리즘들 보다 훨씬 느려질 수 밖에 없다. 예를들어 n이 30일 때 n!의 시간복잡도를 갖는 프로그램을 짰다면, 그 문제는 왠만하면 포기하라고 말하고 싶다. 컴퓨터가 답을 뱉어내는데 몇십시간은 족히 걸릴것이다. 하지만 백트래킹은 문제의 조건을 얼마나 잘 이용하고 필요없는 것들을 잘라내느냐에 따라 속도를 크게 향상시킬 수도 있다.(앞서 설명했던 문제들을 기억해보라) 얼마나 효율적으로 짜느냐도 백트래킹 사용에 큰 관건이다.
모든 알고리즘들이 그렇듯이 여러 가지 상황이나 문제에 많이 적용시켜보는 것이 실력을 늘리기에 가장 좋은 방법이다. 많은 연습으로 백트래킹도 능숙하게 쓸 수 있기를 바란다.
--------------------------------------------------------------------------

키워드

프로그래밍,   알고리즘,   프로그램