원리는 귀찮아서 LTN 구현 다하면 한번에 적음


굳이 말하자면 비트 기반의 트리임




<목적>


요청역마다 고유번호가 있음.


요청 처리는 한번에 하나씩만 가능함. (기술적 한계임. 해결 불가능)


요청이 2개 이상이면 뭐부터 처리할지 회로 입장에서는 난감함.


역이 100개라면, 1부터 올라가면서 우선순위를 정해도 되긴 함.


근데 그러면 요청이 없는 최소 98개의 역을 쓸대없이 확인해서 시간낭비임.


그냥 비트단위로 분할해서 값을 찾기로 함.



원래대로면 n개 역 처리에 n틱의 시간이 소요되지만, 새로운 알고리즘으로는 2^n-1개의 역 처리르 2n틱의 시간만에 처리 가능함.


요청역의 고유번호 대소와 관련없이 무조건 2n틱의 시간임.


1023개의 역이 있을 때, 하나의 요청역 결정에 20틱이면 충분함.


이론적으로 21억개의 역도 1초면 된다.




0eNrNmc1um0AQx1+l2mOFI++ab6WRWvVYJVJi5VJFCMM6WQkDWharlsUtl75DD32GPlKv7UN016QuxgbvYmh8sYS9O8D/NzM7M16DWZTjlJKYAXcNQpwFlKSMJDFwwe2n6fWb38/ffv14BhogQRJnwP28Bhl5jP1IrGerFPOFhOEFXxH7C3El1jE/ZqMgWcxI7LOEgoLvj0P8Bbiw0I5aoD6JKluQxJb2m05OtqAXDxrAMSOM4FKFzcXKi/PFDFP+Xq2GNJAmGSl1XQMhw8S6MDSwAq7pXBj8PiGhOCgXIE3YYDSJvBl+8peEG+C75iRimDYgWBLKcv7N9inKFaMwYeItgiQXhGEFw8Pm6zgu75oJW1B8UBxW34/wqwlfSWiQE7a5FHsLoWhNAqQqgfNXAntICaanC6DvCoAaBJhsbx3igISYtr+/DtUc4MWox38LyfaZ54RmzJNWAy8xXbEnEj+WspSgNsrwh019unlYF7zjO5OcpbmC7Rel05W3kdub02ThkZjbAO7cjzJcyEsOK/o2INAAaths1B121xaEcg6td+O5583mgDynuxhRDeNlzxgZzVUoKlHT26lN2n9uCkpj+3o+JexpgRkJjnDU1eLyn93TUH4QumdY2PB2AjNJMedZHspvOwDlhovO2R7VdDb3Y6cZqSUXaGZnRvYrMlILqCrEy8vBKZrtFA0VimZ75NlykC11yOYZB+LVVQeGd0oMjcbs+UgxjuvL7XbkULKMsztzss+R0+j/h1o7JkuumHTUMdgv9bQ13sWgn2FOvK3nxPfXHzuQulciBceijTtIBeoqGfHQ6kMQ4VixJ9oy3A8mvcee6LbSEznjjl2RI6kBVPfkspK2oGQl3ZcnT4eqwKanVWCtrmhKYkBdi6x9DAPn9buhMKgdv0Kx1gPVUkoZ6EhTuk+9KVVN5E4QqDqPMNWirpf+9Wa3fx3X+teORVZf/Su0ZKFYasUXUvIVeV/Y8yok6Suqs45trYGkTqlefOWuS6FxX3rDiaOtmx5HW440XL3dqZzG/CNd4hz0BaPrINdCQw5ybypFy8gQnt2lapE+L81O0z9pCYaY/tWHuD+/fu/Z11Xzp3Fk9HokD0r2StDqXNugs6htRq9e3EClIlNutsDz2uY/NrfyL6MGIn+Go72/F5c8HZT621C3HGTpE1N3kF0UfwDC6cun


아래는 내가 혼자 회로 구상한거. 사용법은 나중에


T input
내부 Bit [ <<1 ]
전역 Bit [ -1 ]
전역 Search [ 래치 ]
전역 Search [ >>1 ]
유효 Value [ AND ]
전역 Output [ +1 ]
내부 Sum [ -Search ]
내부 Search [ +Sum ]




굳이 이런 서버를 구축한 이유 :


동시출발 방지, 요청역-공급역 1ㄷ1 최단거리 대응, 모든 요청역의 이름 통일, '요청량' 설정 가능, 다중하차 구현 목표


이론적으로는 다 되는데 다중하차는 좀 고민임.