칠레처럼 아주 길쭉한 국가가 있다고 치자. 이 국가에는 지형을 따라 거대한 간선 철도가 놓여 있고 n개의 역이 있으며, n개의 역에 모두 정차하는 완행 열차가 일정 간격으로 다닌다.
이 설정을 좀 극단적으로 확장하여 역 수가 수백, 수천, 수만-_-개에 달한다고 가정하자. 그렇다면 급행 열차를 운행할 필요가 응당 생긴다. 2000개역쯤 떨어진 지역에 가려고 하는데 전역정차 열차를 탈 수는 없는 노릇 아닌가. 그렇게 여행 거리가 길어지면, 급행 열차가 서는 곳까지 가서 환승하는 불편 정도는 급행의 빠른 속도가 충분히 보상하고도 남게 된다.
자, 이를 일반화하면.. 급행도 등급이 필요해서 특급, 쾌특 등 n차원의 급행을 생각할 수 있게 된다. 등급이 올라갈수록, 서는 역 수가 무척 적어서 타기 힘든 대신에 일단 타기만 하면 엄청난 이동성이 보장된다. 급행과 완행은 배차 간격은 모두 동일하다고 치자.
여기서 문제가 생긴다.
각 등급의 급행 열차들은 정차역 수를 얼마로 설정하는 게 좋을까?
또한, 철도역 수 n에 대해서, 최대 몇 등급의 급행이 존재하는 게 적당할까?
n개의 역이 모두 똑같이 중요하고 이용객 수가 균일하다고 가정할 때,
어떻게 급행을 운영하는 게 승객의 평균 표정속도를 최대화하고 반대로 평균 환승 대기 시간을 최소화할 수 있을까?
선로 수는 충분하기 때문에, 완급 결합으로 인한 대피 대기 오버헤드라든가 선로 용량 걱정은 할 필요 없다고 가정하겠다. ^^
역 수가 10개 남짓이라면 급행이 있을 필요가 없겠지만, 역 수가 100개쯤 된다면 3~4개역을 건너뛰는 1차 급행에 이어서 한 10~12개쯤 역을 쉬엄쉬엄 건너뛰는 2차 급행이 있어도 좋을 것 같다.
전산학을 전공한 친구라면, 이런 부류의 문제를 생각하면서 비슷한 형태의 아주 유명한 알고리즘을 하나 떠올리게 될 것이다.
바로 '쉘 정렬'이다!
쉘 정렬은 삽입 정렬을 원소별로 띄엄띄엄 적용하되 나중에 그 간격을 촘촘히 좁히는 방식이다.
삽입 정렬은 시간 복잡도가 O(n^2)이지만, n의 크기가 작아서 띄엄띄엄일 때는 오버헤드가 크지 않으며, 또 편차가 커서 리스트가 상당수 정렬되어 있을 때는 매우 빠르게 수행되기 때문에 그 특성을 이용한 것이다.
쉘 정렬은 알고리즘의 특성상 실제로 코딩해 보면 루프가 3중, 4중으로 들어가기 때문에 무거울 것 같지만 돌려 보면 성능이 매우 좋다. 프로그래밍 언어라고는 아직 어셈블리밖에 없던 1950년대에 고안된 알고리즘이다.
여타 정렬 알고리즘들이 O(n^2), O(n log n) 아니면 심지어 O(n) 같은 식으로 시간 복잡도가 딱 파악되는 반면, 이 쉘 정렬은 비록 O(n^2)보다야 훨씬 빠르긴 하지만 시간 복잡도가 제대로 분석되어 있지 않다.
삽입 간격을 설정해서 좁히는 방식을 어떻게 설정하냐에 따라서 성능이 크게 달라지기 때문이다.
완행 다음으로 급행을 겨우 1역 균일 통과, 특급을 2역 균일 통과처럼 정말 무식하기 짝이 없게 운행하지는 않는다. 급행 등급이 하나 올라갈 때마다 급행은 최소한 기하급수적으로 통과역 수가 늘어야 이치에 맞다.
쉘 정렬도 그와 마찬가지이다. 23, 10, 4, 1 같은 급으로 큼직하게 수가 바뀌고, 이 수들이 가능한 한 서로소가 되게 하는 게 정렬 효율에 좋다고 알려져 있다. 16, 8, 4, 2, 1처럼 정확하게 컴퓨터스럽게 배수· 약수 관계로 포개지는 간격은 매우 비효율적이며, 그런 나쁜 수열을 쓰면 쉘 정렬의 시간 복잡도가 최악의 경우 도로 O(n^2)로 치솟는다고 한다.
우리나라의 급행 전철이 정차역 수가 여전히 너무 많다는 지적이 있긴 하지만, 이것은 환승을 싫어하는 국민 정서 내지 환승이 불편한 구조, 급행도 어차피 최대 속도는 동일하고 완행보다 그렇게 많이 빠르지 않은 것, 역마다 weight가 현실적으로 차이가 나는 것, 급행의 소극적인 운행(긴 배차 간격) 같은 다른 환경적인 요인 때문에 그런 것이다. (현실에서는 환승역이냐 그렇지 않느냐의 여부 하나만으로도 역별 weight가 크게 벌어질 수밖에 없다)
이상, 철도와 전산학을 융합한 뻘글이었다.
쉘 정렬의 수열 설정 방식이 철도 운영에서도 이론상 효율적이라 말할 수 있을까? ^^;; (급행은 4역씩 건너뛰고 특급은 10개역, 쾌특은 23개역.. ㄲㄲ)
참고로 쉘 정렬은 수열을 제일 잘 설정했을 때 시간 복잡도가 O(n (log n)^2) 까지는 떨어진다고 한다.
* 덧붙이는 말:
어제는 KTX 열차가 개통 사상 처음으로 탈선 사고를 일으켰다고 한다.
여기에 대해 철도 덕후 사무엘 님의 공식 입장을 말하자면, 이건 두말 할 나위도 없이 선로 시설 문제이지 차량 문제가 아니라는 것이다.
차량이 떼제베가 아닌 산천이었다고 하는데, 지금까지 늘 말썽을 일으켜 온 것처럼 차량이 고장을 일으킨 거라면, 그대로 차가 멈춰서는 걸로 끝나지 지가 무슨 능력으로 탈선까지 하겠는가?
더구나 이 차는 보기 드문 광명 시종착 KTX였다. 광명이 단순 경유역이 아닌 종착역이기 때문에 여타 열차와는 다른 선로로 건너가야만 했다. 그래서 선로 분기기가 열차를 새 선로로 유도하고 있었는데, 열차가 다 건너기 전에 선로 분기기가 전산 착오 내지 추위로 인해 오작동한 것 같다. 그래서 뒷부분 객차의 진로를 막았고, 이것 때문에 찌이이이익 소음+타는 냄새+탈선이 야기된 것으로 추정된다.
열차가 고속으로 쌩쌩 달리다가 교량이 붕괴했다거나 차량이 자폭이라도 한 것과는 전혀 다른 부류의 사고이다. 오히려 열차는 종착역 진입을 앞두고 위와 같은 이유로 인해서 아주 천천히 달리면서 신호를 기다리고 있는 상태였을 것이다. 그리고 그 사고도 그런 특수한 상황에서나 발생한 사고이다. 이 사고가 KTX 차량 시스템 전반에 대한 불신풍조로 이어지기는 않기를 본인은 바란다.
이 사고로 인해 이 열차를 바로 뒤따라오던 상행 KTX는 평택쯤에서 다시 천안아산-_- 역으로 역주행하여 돌아가야만 했고, 대전-서울 구간의 고속선이 폐쇄되는 바람에 다른 KTX들은 아예 경부선 기존선으로 우회해서 다녀야 했다. 주말 임시 열차는 아예 선로 용량 부족으로 인해 운행 중단. 코레일의 입장에서는 손해가 그야말로 막심했을 것이다. 이로 인해 수원-천안 구간에서 KTX 산천이 보이는 진풍경이 연출되기도 했다.
Posted by 사무엘
