DFA (Deterministic Finite Automata) 라는 개념에 대한 내용입니다.
간단히 말하면 그래프를 만드는데,
현재 상태가 i일 때
입력으로 0이 들어오면 i = next[i][0]으로,
아니면 i = next[i][1] 으로 이동하라는,
즉
위에 그림과 같은 형태의 방향그래프를 그려놓고
최종적으로 동그라미가 2개 쳐진 node에 도착을 하면 true
아니면 false 라고 판단하는 방식을 말합니다.
위의 그림의 예를 들어보면
문자열이 11, 111, 11000001 같은 경우는 true, 110000010 같은 경우는 false를 말하겠죠?
일단 이 문제같이, true인지 false인지 판단할 식이 하나로 정해져있으니
Contact 문자열이 들어오면 true, Contact 문자열이 아닌 애가 들어오면 false를 리턴하는
DFA 그래프를 "손으로"(!!!) 그려본 뒤
그 그래프를 따라서 시뮬레이션하면
Contact 문자열인지 아닌지 판단할 수 있게 되는겁니다..
자세한 내용은 이산수학 책의 'DFA' 부분을 정독하시거나
구글링 해보세요.ㅋ 이것저것 많이 나올겁니다...
dongilzzangzzang 9년 전
일단 단순한 케이스 분류 분석으로 맞긴 맞았는데..
제 기억으로는 정올 기출 문제여서 찾아보니 1996년도 고등부 문제였더라구요.
아무래도 정올에서 스트링을 단순히 분석하는 문제를 내진 않았을 것 같아서 (맞고 나서) 다른 솔루션을 찾아보니
첨부한 소스 코드와 같은 풀이가 가능하더라구요.
이거 어떤 원리로 동작하는 코드인지 알고 싶습니다.