|
:: 게시판
:: 이전 게시판
|
이전 질문 게시판은 새 글 쓰기를 막았습니다. [질문 게시판]을 이용바랍니다.
통합규정 1.3 이용안내 인용"Pgr은 '명문화된 삭제규정'이 반드시 필요하지 않은 분을 환영합니다.법 없이도 사는 사람, 남에게 상처를 주지 않으면서 같이 이야기 나눌 수 있는 분이면 좋겠습니다."
10/04/14 20:49
문제에서 *s*s* 꼴로 입력하면 essential, describes, successive 가 출력이 되면 안되는거 아닙니까? systems 도 *s*s* 형태가 아니라 s*s 형태 아닌가요? 잘 이해가 안되는데요...
10/04/14 20:51
정규식에 대해서 이해를 하셔야 하는데 왠지 쓰신 걸 보니 정규식을 모르시는 거 같네요.
정규식 프로그래밍은 http://www.joinc.co.kr/modules/moniwiki/wiki.php/article/regex를 보세요.
10/04/14 20:59
꼭 C로 짜야 하는 건가요, 아니면, 저런 기능이 있는 프로그램이 있으면 되는 건가요?
만일 후자라면, C보다는 정규 표현(regular expression)에 대한 라이브러리가 지원되는 언어를 쓰시는 게 낫습니다. 예를 들어, Perl 이나 Python 같은 언어가 있겠죠. PS) 하긴, 위의 언어들을 쓰면 숙제가 너무 쉬워지겠네요.
10/04/14 21:00
유준범 교수님 프로그래밍 프로젝트군요;; 소프트웨어 검증시간에 들어오셔서 저걸 과제로 내려고 생각중인데 4학년들이
극구 말렸는데 진짜 내셨군요... 개인적으론 파일 입출력함수랑 문자열함수랑 알면 어느정도 모양새가 나올꺼 같긴한데 솔직히 말하면 저거 짜라 그러면 저도 막막합니다... 일단 행운을 빌구요;;; 그리고 교수님이 치팅 프로그램으로 소스 전부다 검사 한다그러니까 어지간하게 카피하면 거의다 카피로 나올껍니다;;;
10/04/14 22:35
*만 구현한 함수에요 어떻게 작동하는지 보고 ?도 추가로 구현하면 됩니다.
word에 단어를 넣고 exp에 표현식 넣으면 됩니다. 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+1,exp)||check(word,exp+1); return 0;
10/04/14 22:38
그런 거 몰라도 구현 가능합니다. 힌트를 드리겠습니다.
*와 ?를 기준으로 단어들을 분리합니다. a?b 라면 a와 b가 되겠죠. a?b*b라면 a와 b와 b로 나뉘겠죠. 자, 이 패턴을 가지고 어떤 문자열이 패턴에 적용되는지를 검사하고 싶습니다. 어떻게 하느냐.. 나뉘어진 각 단어들을 가지고 그 단어들이 어느 위치에 있는지를 모두 찾아내어 검사합니다. e*s*se??al라는 패턴이 있다고 가정할까요? essential 이라는 단어가 이 패턴에 들어맞는지를 검사하기 위해 다음과 같은 리스트가 만들어질 겁니다. 각 숫자는 해당 단어의 시작 위치를 나타내죠. e: 0 3 s: 1 2 se: 2 al : 8 그럼 뭐.. 이 위치들 가지고 잘 가지고 놀면 됩니다. e의 끝 위치와 s의 시작 위치는 최소한 1만큼 차이가 나야 할 것이고, 반면 se의 끝 위치(이건 시작 위치에 길이를 더하면 나오겠죠?)와 al의 시작 위치 사이의 거리는 물음표가 두개이므로 최소 3의 차이가 나야 할 겁니다. 이러한 관계를 가지고 저 정보들 사이에 그래프를 만들 수 있는데, 맨 처음 단어로부터 시작해 마지막 단어까지의 경로가 존재한다면(이건 알고리즘 책 보면 있을 겁니다.), 그리고 그게 검사하는 문자열의 범위를 완전히 커버한다면 패턴을 만족하는 것이죠.
10/04/15 02:29
제가 생각하는 방식으로는 가장 본질적인 접근이 낫다고 봅니다.
일단 입력 식을 받아들인 후에 Start state에서 시작하여 DFA(Deterministic Finite Automaton)를 만듭니다 A 다음에 ?가 있는 경우는 next state로 transition *가 있는 경우는 자기 자신으로 transition을 합니다. 입력식의 끝에서 End state를 넣어주면 DFA가 만들어집니다. 이 DFA는 linked list나 그 외에 적당한 자료구조로 만들어주면 됩니다. 그리고 테스트 할 문장을 이 DFA로 검사를 해줍니다. Accept state에서 멈춘다면 조건에 맞는 문장이 되는거겠죠-
10/04/15 08:07
저도 MoreThanAir님의 의견에 동의합니다. '추상적인' 얘기가 어려워 보여도 진입 장벽이 약간 있을 뿐 문제를 가장 쉽게 푸는 방법입니다.
처음부터 구현의 디테일까지 한꺼번에 생각하면 안 됩니다. 최대한 구현과 분리된, 추상 수준이 높은 문제부터 풀어야 합니다. 이 문제는, 주어진 정규표현식 패턴에, 문자열이 일치하는지 검증하는, 검증기를 생성하는 문제입니다. 프로그램을 한다고 생각하지 마시고, 그냥, 사람이 직접 같은 문제를 푼다고 상상해 보세요. 대신 ad hoc하게 푸는 게 아니라, 거기에 의지하면 항상 이 문제를 풀 수 있는, 기계적인 방법을 만들어낸다고 생각하시면 될 것 같습니다. 쉽지 않다는 걸 발견하시게 될 것 같고요. 일반적으로 automata를 만들어서, 그 automata의 입력으로 판별할 대상인 문자열을 주게 됩니다. 오토마타 책을 보시면 어떻게 정규표현식을 판별하는 오토마타를 만드는지 아마 잘 나와 있을 것 같습니다. 저의 경우엔 컴파일러 책 앞부분에서 봤습니다. 먼저 구현은 잊고 오토마타를 익히신 다음, 오토마타 생성기를 구현하고, 그 다음에 문자열을 그 오토마타로 판독하는 루틴을 만드시면 됩니다. 이 문제는 실생활에서 만나게 될 문제들에 비해 "아주 쉬운" 문제입니다. 이런 문제를 쉽게 풀 수 있는 방법론을 갖고 계시지 않으면 안 되는 것 같습니다.
|
||||||||||