:: 게시판
:: 이전 게시판
|
이전 질문 게시판은 새 글 쓰기를 막았습니다. [질문 게시판]을 이용바랍니다.
통합규정 1.3 이용안내 인용"Pgr은 '명문화된 삭제규정'이 반드시 필요하지 않은 분을 환영합니다.법 없이도 사는 사람, 남에게 상처를 주지 않으면서 같이 이야기 나눌 수 있는 분이면 좋겠습니다."
10/04/16 04:39
여기는 늦은 시간이 아니라서 답을 달아 봅니다. 우선 데드라인이 언제인가요? 저는 학부 때 한 과목을 재수강 한 적 있습니다. 초수강 땐 바쁘다는 핑계로 책 한 번 정독하지 않고 프로젝트부터 덤볐다가 3일 밤 새고 1/7도 못 끝내고 포기했습니다. 컴퓨터 과목이었고, 이미 당시에 나름 컴퓨터 좀 한다고 생각했었는데 좌절했었습니다. 재수강 때 차분히 며칠 들여서 텍스트 정독하고, 초수강 시절 숙제보다 업그레이드 된 것을 처리하는 데, 전체 다 해서 이틀 반이 걸렸습니다.
억지로 "숙제부터" 어떻게든 한다고 실력이 크게 늘지 않는다고 생각합니다. 누군지 기억은 나지 않는데, 어느 유명한 한국인 프로그래머가 컴퓨터가 늘려면 컴퓨터를 멀리 하(고 책상을 가까이 하)라고 쓴 적이 있습니다. 이 문제는 아주 단순하고 교과서적인 오토마타 문제입니다. 따라서 오토마타 책이나 컴파일러 책에서 NFA, NFA to DFA를 조금만 정독하셔도 어떻게 프로그램을 하셔야 하는지 알 수 있습니다. FSM을 논리회로 시간에, 오토마타를 오토마타 시간에 배우지 않나요? 혹시 둘다 모르신다면 덧글로 메모를 남겨주세요.
10/04/16 08:31
어렵게 풀면 어렵고 쉽게 풀면 쉬운 문제입니다.
순차적으로 접근을 하자면 '?' '*"를 제외한 상태에서 표현식에 부합하는지 검사하는 함수를 작성해 보겠습니다. int check(char *word, char *exp) if( strlen(word)==0&& strlen(exp)==0 )return 1; if(word[0]==exp[0]) return check(word+1,exp+1); return 0; 그냥 두단어가 일치하는지 검사하는 역할을 합니다. check("starcraft","starcraft")는 1을 반환합니다. 여기에 '?'를 구현하고 싶다면 if(exp[0]=='?') return check(word,exp+1)||check(word+1,exp+1); 이렇게 추가하면 됩니다. '?'의 정의 대로 0개의 임의의 문자라면 check(word,exp+1)에서, 1개의 임의의 문자라면 check(word+1,exp+1)에서 1을 반환합니다. 여기까지 추가하면 check("starcraft","st???cra??") 같은 표현식을 검사할수 있습니다. '*'를 구현하는 것도 '?'와 비슷합니다. 0~n의 임의의 문자라는 정의에 부합하게 하려면 if(exp[0]=='*') if(strlen(word)!=0)return check(word,exp+1)||check(word+1,exp); else return check(word,exp+1); 이런식으로 작성하면 됩니다. check(word+1,exp)는 '*'가 n개의 문자로 확장되는 경우를 검사하며 check(word,exp+1)는 '*'가 더이상 확장되지않는 경우를 검사합니다. 지난번에 '*'만 구현해 드렸는데 결과가 제대로 나와서 지나갔는데 다시 보니 word이후의 위치를 참조할 가능성이 있으니 이부분은 이번 코드를 사용하세요. 정리하자면 int check(char *word, char *exp) if( strlen(word)==0&& strlen(exp)==0 )return 1; if(word[0]==exp[0]) return check(word+1,exp+1); if(exp[0]=='?') return check(word,exp+1)||check(word+1,exp+1); if(exp[0]=='*') { if(strlen(word)!=0)return check(word,exp+1)||check(word+1,exp); else return check(word,exp+1); return 0; } 이 함수를 check("starcraft","s*r*a??"); 이런 식으로 사용하면 됩니다. 작성하신 코드에서check(str,word)호출하면 검사후 1이나 0을 반환할 겁니다.
|