[소프트웨어] 10개 도시를 최단거리로 여행하는 법

에게해 스터디원들과 함께하는 CS 간단 발표 및 독후감👶

[1일1로그 100일 완성 IT지식] 22번 '10개 도시를 최단거리로 여행하는 법'

 

 

내용이 모호하고 어렵다.. 그렇다고 또 그렇게 중요한것 같지도 않아서 짧게 정리하려고 한다! ㅎㅎ

 

알고리즘의 복잡도를 잠깐 언급하는데 크게 시간 복잡도와 공간 복잡도로 나뉜다.

 

1. 시간 복잡도  (어제자 그래프 느낌)

 -특정한 크기 입력(n) 에 알고리즘이 얼마나 오래 걸리는지.

 -알고리즘에 필요한 연산 횟수

2. 공간 복잡도

 -특정한 크기 입력(n)에 대해 알고리즘이 얼마나 많은 메모리를 차지하는지.

 -알고리즘에 필요한 메모리의 양

 

또 다항이다 비결정적 다항이다해서 P(합리적인 시간안에 푸는 문제) NP의 개념을 사용하시는데 이건 넘어가고 ㅎㅎ

 

---

오늘 Title인 여행하는 외판원 문제!

옛날에 한번씩 해본 모든 곳을 한번씩만 찍고와야되는데 최단거리로 찍고오는 문제다.

 

 

외판원 뿐만 아니라 통학 버스나 쓰레기차가 쓰레기를 수거 할 때도 최단거리를 한번씩 도는건 중요하니 요런게 생각보다

그들만의 세계에선 유명한 문제였다.

 

'휴리스틱' 이라는 내가 있는곳에서 가장 가까운 곳으로! 이동을 반복해서 처음 출발했던 곳으로 돌아오는 방법이 현실적으로 정답에 가까운 해결책이라고 한다.

 

방법이야 많지만 아직까진 결국 모든 경우의 수를 다~ 돌아봐야 최단거리를 구할 수 있다고한다.

(이런 류의 문제의 경우의 수 공식은 (n-1)!/2 로 저 외판원은 모든 경로 약 18만 개를 다 다녀봐야 가장 짧은 길을 구할 수 있다..) 

 

물론 현실적으로는 '휴리스틱' 방법처럼 대충~ 가겠지만 알고리즘에서는 컴퓨터의 모든 경우의 수를 생각해야되니까 똑똑한 사람들은 이것저것 고려를 하나보다.