프로그램을 배웠으나 알고리즘 시험을 봐야 한다면. #29

요즘 아이들과 포켓몬Go를 하는데

이 게임과 알고리즘 문제를 어떻게 합쳐볼까 고민하다가 아래와 같이 생각해 봤습니다.

 

1) 지도상(보통 2차원 격자, 1간 이동에 1분 소요)에 여러 포켓몬의 위치, 해당 포켓몬의 CP, 사라지는 시간을 알고 있을때,

    얻을 수 있는 포켓폰의 CP의 최대합은 얼마인가?

    (포켓몬 잡는 시간은 무시)

 

    일반적인 TSP 문제 ( https://en.wikipedia.org/wiki/Travelling_salesman_problem ) 와 유사하지만

    도달 할 때 이미 포켓몬이 없어지는 경우가 있으니 그것도 고려해야 합니다.

 

2) 지도 포켓스탑이 위치가 나와 있고 한번 돌리면 5분마다 다시 활성화가 된다고 할때

    지도상의 어느 경로로 돌아야 포켓스탑을 가장 효율적으로 사용할 수 있는가?

    (1시간 동안 포켓스탑 노가다를 한다고 가정)

 

이런 종류의 문제를 만들 수 있을 것 같습니다.

저도 실제 문제로 만들거나 풀어본 것은 아니지만 충분히 문제로 만들 수 있을 것 같습니다.

 

게임만 하지 마시고 이런 게임을 어떻게 만들 수 있을까? 아니면 어떤 알고리즘과 연결될 수 있을까?

를 생각해 보면 나중에 비슷한 문제를 만났을때 당황하지 않을 것 같습니다.

 

#삼성_소프트웨어_역량_테스트