일단 단순한 케이스 분류 분석으로 맞긴 맞았는데..

제 기억으로는 정올 기출 문제여서 찾아보니 1996년도 고등부 문제였더라구요.

아무래도 정올에서 스트링을 단순히 분석하는 문제를 내진 않았을 것 같아서 (맞고 나서) 다른 솔루션을 찾아보니

첨부한 소스 코드와 같은 풀이가 가능하더라구요.

이거 어떤 원리로 동작하는 코드인지 알고 싶습니다.

pichulia   2년 전

DFA (Deterministic Finite Automata) 라는 개념에 대한 내용입니다.

간단히 말하면 그래프를 만드는데,

현재 상태가 i일 때

입력으로 0이 들어오면 i = next[i][0]으로,

아니면 i = next[i][1] 으로 이동하라는,

bf9ced095ac16f5ac97af0ecd58f7a10.jpg

위에 그림과 같은 형태의 방향그래프를 그려놓고

최종적으로 동그라미가 2개 쳐진 node에 도착을 하면 true

아니면 false 라고 판단하는 방식을 말합니다.

위의 그림의 예를 들어보면

문자열이 11, 111, 11000001 같은 경우는 true, 110000010 같은 경우는 false를 말하겠죠?

일단 이 문제같이, true인지 false인지 판단할 식이 하나로 정해져있으니

Contact 문자열이 들어오면 true, Contact 문자열이 아닌 애가 들어오면 false를 리턴하는

DFA 그래프를 "손으로"(!!!) 그려본 뒤

그 그래프를 따라서 시뮬레이션하면

Contact 문자열인지 아닌지 판단할 수 있게 되는겁니다..

자세한 내용은 이산수학 책의 'DFA' 부분을 정독하시거나

구글링 해보세요.ㅋ 이것저것 많이 나올겁니다...

와.. 굉장하네요

마침 이번 학기에 이산수학을 수강 중인데

바로 다음 수업 진도가 이 부분이 될 것 같습니다

좋은 예습이었던 것 같아요

친절한 답변 감사드립니다~

Hibbah   2년 전

갓츄리엘.......

adream   2년 전

God 츄리엘

따라갈수가없엉

댓글을 작성하려면 로그인해야 합니다.