[jaewooklee]

2012년 게시판에 당시의 조교님이 올린 글을 참고해보면
https://ropas.snu.ac.kr/phpbb/viewtopic.php?t=3650

프로젝트의 1번 문제에 주어진 hint는,

두 로봇의 경로가 겹칠 때마다, 두 로봇의 대피소를 바꾸어주면,
로봇의 이동거리 합이 항상 줄어들고,
로봇과 대피소를 짝짓는 방법은 총 n!개로 유한하기 때문에,
최악의 경우에도 n!의 경우의 수를 모두 순회하고 나면
프로그램이 종료된다는 점을 보일 수 있다는 의미인 것 같습니다.

그런데 만일 위의 hint대로 프로그램을 구현한다면,
worst case time complexity가 O(n!)이 되어버리는 것이 아닌가요?

예를 들어, 로봇 1,로봇 2,로봇 3,..., 로봇 99에 대해 문제를 풀어서,
99개의 로봇의 경로는 모두 겹치지 않는 상태에 도달하였다고 하더라도,
로봇 100의 경로가 나머지 로봇들의 경로를 모두 통과하는 바람에,
로봇 1~99의 로봇과 로봇 100의 대피소를 바꾸게 되고,
그래서 결국 거의 처음부터 문제를 다시 풀어야 하는 상황이 나올 수도 있지 않나 궁금합니다.
물론 그럴지라도 프로그램이 언젠가 종료된다는 것은 확실하지만요.

만일 프로그램의 운이 매우 나쁘다면
(1,2,3)->(1,3,2)->(3,1,2)->(3,2,1)->(2,3,1)->(2,1,3)
과 같이 3!의 상태를 모두 거치는 것이 원리적으로 불가능하지는 않은 것 같습니다.

그럼에도 불구하고 위의 프로그램을 실제로 사용한다면 대부분의 경우,
즉 average case에서는 나쁘지 않은 성능이 나올 것 같기는 합니다.
예컨데 로봇 5개의 문제를 푸는 경우, 위와 같이 5!=120의 경우를 모두 순회하는
120번째로 짧은 상태->119번째로 짧은 상태->118번째로 짧은 상태->..->가장 짧은 상태
프로그램 수행이 이루어질 확률은 매우 작고,
실제로는 n번째로 짧은 상태에서 임의의 두 로봇 경로의 중첩을 해소시켰을 때 이행할 수 있는 상태는,
1번째로 짧은 상태~(n-1)번째로 짧은 상태일 것이므로,
그 중 기대값을 따지면 평균적으로는 n/2번째로 짧은 상태로 이동하게 될 것입니다.
그래서 실제로 프로그램을 수행할 경우 상태변화는
120번째로 짧은 상태->60번째로 짧은 상태->30번째로 짧은 상태->...->가장 짧은 상태
가 될 것이고, average case에는 O(log n!)=O(nlog n)라는 무척 짧은 시간에 올바른 상태에 도달할 수 있을 것으로 보입니다.
(실제로는 매 상태마다 경로가 중첩되는 로봇 쌍을 발견해야 하므로 n^2번씩의 계산이 더 필요하겠지만요)

그럼에도 불구하고, worst case가 O(n!)이라면 그것이 올바른 풀이라고 할 수 있는지 잘 모르겠습니다.
프로젝트 채점에서 "매우" 작은 확률로 시간이 "매우" 오래 걸릴 수도 있는 여지는 무시하는 것인가요?
아니면 제가 위의 worst case 분석에서 놓치고 있는 부분이 있나요?

[김윤승]

저 글이 지워지지 않고 남아있었군요... 큰일입니다.

어쨌든, 이 수업은 컴퓨터공학부의 기초 수업이기 때문에 시간복잡도를 고려한 적은 없습니다.

특정한 알고리즘에 대해서, 구현을 지저분하게 해서 비효율적이 되는 경우를 피하는 정도가 이 과목에서 배우는 정도라고 생각합니다.

이 문제에서는 힌트대로 푸시면 됩니다.