Text 내에서 Key를 찾는 프로그램을 작성하시오... Quiz 1st 2007

 개학을 하고나서 머리 속에는 온통 수업에 관한 생각이 가득하다. 그중에서도 가장 많은 시간을 할애하게 되는 수업은 단연 알고리즘 수업이다. 이전에 10진수를 2진수로 변환하는 과제가 교수님께서 강의를 하시기 전에 학생들의 프로그래밍적인 능력을 보시기 위한 과제였는데, 이번에도 역시 Quiz를 내셔서 학생들의 능력을 보고 싶어하셨다.

 문제는 2가지로 하나는 주어진 Text 내에서 Key를 찾는 프로그램을 작성하는 것, 또 다른 하나는 Quick Sort를 개선할 수 있는 방법이 있다면 제시하는 것이였다. Quick Sort를 개선하는 방법의 경우는 너무나 자신이 없는 내용이라 Text내에서 Key를 찾는 프로그램을 작성하는 것만 포스팅 하려고 한다.
 우선 이 문제를 받고 제일 처음에 머리에 떠올랐던 생각은 Text와 Key를 배열로 구성해서, Key의 첫번째 단어로 검색하면서 Text내에서 Key[0]와 동일한 단어가 나오면 Key[1], Key[2] 와 비교하는 식으로 짜는 방법이 떠올라서 최초에 작성한 코드는 아래와 같다.
#include <stdio.h>

int main()
{
char key[] = "pen";
char text[] = "This is a pen. Pencil.";
int i = 0;

printf("%s\n", text);
while( text[i] != EOF ) {
if( key[0] == text[i] ) {
if( key[1] == text[i+1] ) {
if( key[2] == text[i+2] ) {
printf("Find \'%s\'. %d th char.\n", key, i+1);
return 0;
}
}
}
i++;
}
printf("Can\'t Find \'%s\'\n", key);

return 0;
}
  이 코드를 짤 때는 교수님께서 선착순이라고 했기에 바쁜 마음에 생각나는데로 두들겨서 결과가 나오는 것에만 신경을 썼다. 나중에 교수님께서 메일로 제출하라는 얘기를 하셔서 소스를 좀 가다듬어야 겠다는 생각을 하고, 나름대로 가다듬은 소스가 아래의 소스이다.
#include <stdio.h>
#include <string.h>

int search(char *text, char *key);

int main()
{
char key[] = "pen";
char text[] = "This is a pen. Pencil.";
int result, i = 1;

// 자리수 확인을 쉽게 하기 위한 숫자 가늠자 표시
printf("\n");
while( text[i] != (int) NULL ) {
printf("%d", i - (i/10)*10 );
i++;
}

// 검색 대상 문장 표시
printf("\n%s\n", text);
// 검색 결과 후 반환되는 자리 값을 result에 대입
result = search(text, key);
// result 가 0이 아니면 검색 성공
if ( result )
printf("\nFind \'%s\'. start word %d th char.\n", key, result);
else
printf("\nCan\'t Find \'pen\'.\n");

return 0;
}

int search(char *text, char *key)
{
int i = 0;
int n;
// strncmp를 사용하기 위한 검색어의 길이
n = strlen(key);

// 문장을 처음부터 검색해서 검색어의 첫 글자가 나오면 해당 단어를 비교
while( text[i] != EOF ) {
if ( key[0] == text[i] )
if ( strncmp(key, text+i, n) == 0 )
return i + 1;
i++;
}

return 0;
}
  사실 위의 가다듬은 소스의 경우, 100% 내 머리속에서 나온 것은 아니다. 참고 도서는 마지막에 적어 두었다. 하지만 위의 소스나 아래 소스나 그 효율은 거기서 거기이다. 문장의 처음부터 끝까지 비교해야 한다. (물론 text 길이 - key -1 길이만큼만큼만 검색해도 돼겠지만...) 하지만 교수님께서 원하셨던 것은 이렇게 한글자 한글자씩 검색하는 방법이 아닌 좀 더 효율적인 알고리즘을 원하신다고 하셨지만 순차적으로 검색하지 않으면 위의 소스에서 Key가 되는 pen의 경우 검색 대상에 pppen과 같은 단어가 나올 경우 어떻게 해야 효율적으로 검색을 할 수 있을까? 하는 생각이 들었다. 참고한 책에는 좀 더 나은 효율을 보인다는 보일러-무어(Boyer-More) 알고리즘도 나와 있었지만, 내 머리속에서는 나올 수 있는 알고리즘이 아니라는 생각이 들었다.

 알고리즘 수업이 힘들지만 이렇게 많은 시간을 할애하고, 이것 저것 해보는 이유는 진작에 배웠어야 하는 수업이기도 하고, 유명한 알고리즘을 접하는 재미도 솔솔하기 때문이다. 그리고 앞으로 프로그램을 짠다면 평생 함께 해야 할 것이 이런 알고리즘이 아닐까? 하고 생각을 하기도 하므로, 어려움을 즐겨보려는 중이다.

참고 도서
  C 언어로 배우는 알고리즘 입문 - 카사이 아사오 저 / 진명조 역 / 한빛미디어

by sakuragi | 2007/03/29 23:54 | :: R space :: 과제 | 트랙백 | 덧글(4)

트랙백 주소 : http://sakuragis.egloos.com/tb/3251358
☞ 내 이글루에 이 글과 관련된 글 쓰기 (트랙백 보내기) [도움말]
Commented by 환상경 at 2007/03/30 19:38
알고리즘 교수님이 진정으로 트레이닝 시켜주시는군요;;;;; 후.....
Commented by sakuragi at 2007/04/02 01:28
환상경, 그러게요 진정으로 트레이닝 시켜주시는군요. = _=);;;
Commented by dasomoli at 2007/04/04 17:39
저도 요즘 알고리즘을 수업을 듣고 있는데 꽤 힘드네요.
Quick sort를 개선하는 방법은 Pivot element를 적당히 선정할 수 있도록 만들어주면 될 것 같습니다.
Commented by sakuragi at 2007/04/05 18:19
dasomoli, 일단 적어 내기는 이러쿵 저러쿵 적었어요. 알고리즘 생각보다 힘드네요. T_T

:         :

:

비공개 덧글

◀ 이전 페이지          다음 페이지 ▶

:+: sakuragi's Steam :+: