10개의 도시를 최단거리로 여행하는 법

우리가 어딘가 목적지를 항할 땐 네비게이션을 사용한다. 그래서 네비게이션을 보고 우리는 최단 경로를 통해 목적지에 도작한다. 그렇다면 네비게이션을 수 많은 길중에 최단경로를 알려줄 수 있을까? 라는 생각을 해봤다. 이번 주제에서는 그 방법을 알려주는 알고리즘을 설명하였다.

우리가 알고리즘을 통해 최선의 값을 갖기 위해선 2가지를 고려해야한다. 그것이 알고리즘의 시간 복잡도와 공간 복잡도이다. 먼저 시간 복잡도는 '입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가? '를 뜻한다.

네비게이션으로 대입해서 이해했을 때, 아무리 짧은 거리라도 차가 밀려서 차의 속도가 느리다면 도착하는 시간은 늦어질 수 밖에 없다. 그렇기 때문에 네비게이션은 목적지의 거리뿐만 아니라 차가 어디가 밀리는지도 계산하여 경로를 추천해준다. 시간 복잡도는 Big-O 표기법이라는 것을 사용한다. Big-O 표기법은 다음과 같이 표기한다.

• Big-O(빅-오) ⇒ 상한 점근
• Big-Ω(빅-오메가) ⇒ 하한 점근
• Big-θ(빅-세타) ⇒ 그 둘의 평균
• 위 세 가지 표기법은 시간 복잡도를 각각 최악, 최선, 중간(평균)의 경우에 대하여 나타내는 방법이다.

Big-O 표기법을 사용하는 이유는 최악의 경우를 고려하므로, 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려 할 수 있기 때문이다. 우리는 무언가를 계획할 때 최악을 생각해야 미리 대비 할 수 있기때문에 중요한 부분인 것 같다.

공간 복잡도는 공간 복잡도(Space Complexity)란, 프로그램을 실행시킨 후 완료하는 데 필요로 하는 자원 공간의 양을 말합니다. 공간 복잡도는 '종이에 우리가 계속을 적을 때 계획이 너무 많으면 종이가 많아야 한다' 로 생각해 봤고, 여기서 자원 공간이 종이가 된다.