무한한 길을 가진 금광에서 금을 찾는 가장 효율적인 방법(경로)는?

A씨는 금을 찾기위해 금광으로 들어갔다. 그런데 들어간 금광은 N개의 길로 이루어져 있었다. 

A씨의 보폭을 S라고 했을때 금을 탐색하기 위한 가장 효율적인 방법을 제시하고 시간 복잡도를 구해라.

(단, 금을 구하기위한 단서는 아무것도 없으며 모든 길은 무한한 길이를 가지고 있음)

 

문제 설명을 돕기위한 그림

 

수업시간에 교수님께서 말씀하신 문제다. 옛날에 구글 면접보실때 면접보기전 맛보기 문제로 나왔다고 한다. 

 

 

생각해보면 쉽지만 그 답을 구체적으로 도출하기까지 시간이 조금 걸렷다.

 

먼저 경우를 따져보면 

 

1. 하나의 길을 끝까지 탐색
   1. 이 방법은 모든 길이 무한한 길이를 가지고 있기에 비효율 적임
2. 모든 경우의 수를 탐색
   1. 여기까지 생각하고 막혀버렸다. 접근은 맞지만 어떤식으로 경우의수를 찾을것인지가 문제였다.

따라서 모든 경우의 수를 찾을때는 조금씩 앞으로 가면서 탐색해야 한다.

 

이거처럼 주황색으로 점진적으로 탐색범위를 넓여서 1번길 조금 갔다가 나오고, 2번길 조금갔다가 나오고 .... 하는 식으로 진행해야한다. 따라서 보폭을 S라고 한다면, 

(S(S-1)^2 / 2 ) * 2 라는 수식이 나온다. ( 보폭의 수를 전부 더하고 여기에 가는거 1회 오는거 1회 이므로 *2 를 해준다.)

따라서 N개의 길을 탐색하는 가장 효율적인 알고리즘은 모든 경우의수를 해보는 것이므로 ( 금에대한 정보가 없기 때문에 알고리즘을 짤 수 없다.) 

(S(S-1)^2) * N 

따라서 시간복잡도는 O(S^2*N) 이 된다.