20.07.26 - 무어 기계(cont)

https://www.acmicpc.net/problem/3300

3300번: 무어 기계

이전에 짰던 코드가 입력되는 String에 반복적인 알파뱃이 존재 할 때
Shift 과정에서 오류가 발생한다는 점을 깨달았습니다.

더 큰 문제는 추가적인 복잡한 구조나 대량의 메모리가 없이는 개선을 할 수 없다는 점이었습니다.

 

그래서 구조를 다시 짜보고 있습니다.

처음에는 struct를 이용한 Graph를 이용해보려 했습니다.

runtime 상에서 메모리를 잡는 거은 큰 부하가 걸리므로 Stack Object들로 관리를 하였습니다.

하지만 Graph라고 해도 Directed Graph라서 흐름을 역행하는 케이스를 검색하는 것에 문제가 발생하였습니다.

 

현재는 여기까지 개발을 한 상태입니다.

그리고 일지를 적다가 Graph를 Array로 표현하는 방법을 떠올렸습니다.

입력된 Machine에서 모든 State를 Vector에 순차적을로 담고,
각 State가 어떤 State로 갈 수 있는지 index 값을 Vector로 담고 있는 방식입니다.

 

여기서 문제가 될 수 있는 부분은 두가지입니다.

하나는 하향식이든 상향식이든 일대 다 관계가 발생할 수 있다는 점.

다른 하나는 State가 많아질수록 기하급수적으로 Graph 정보가 많아진다는 점입니다.

 

우선은 이 구현하던 것을 지우고 Array 식으로 변경해서 새로 구현을 해보려 합니다.

아무래도 Vector보다는 부하가 적을 것 같아서입니다.