[일상] 알고리즘 잡스 수강 후기 -6 (손진호 대표님 특강4)

8/1 토요일 오늘 특강에서 풀 문제는 밀렵 꾼이라는 문제이다. 밀렵꾼이라는 문제는 지정된 맵 안에 다수의 멧돼지들이 움직이고 있고 손전등을 확인하여 눈앞에 있는 멧돼지들을 포획하고 여러 번 이 동작을 반복하였을 때 잡은 멧돼지들의 무게의 합을 구하는 문제이다. 코치님이 삼성 입사 문제로 나왔던 문제라고 하니 이 정도 문제만 쉽게 풀 수 있다면 알고리즘을 어느 정도 준비가 되었구나 하는 기준이 될 수 있다고 하셨다. 

 

입력값으로 멧돼지들의 위치와 움직이는 방향, 달리는 속력, 돼지의 무게가 주어지고 만약 같은 격자 안에 2마리 이상의 멧돼지가 있을 경우 가장 무게가 많이 나가는 멧돼지가 다른 멧돼지를 잡아먹는다는 옵션도 있다. 문제만 들어서는 그렇게 난이도가 있는 문제인것 같지는 않았지만 문제의 제한시간이 1초이기에 시간 복잡도도 감안해야 해서 막상 구현을 상당히 난도가 높은 어려운 문제였다.

 

밀렵꾼이라는 문제를 풀기 위해서는 위의 그림과 같은 알고리즘을 먼저 구현하여야 한다. 이번에도 알고리즘 잡스에서 위의 알고리즘을 풀 수 있는 미니 문제들을 준비해주셔서 미니문제들 부터 먼저 풀고 밀렵꾼이라는 문제를 풀었다. 손전등을 켜 무게를 합하는 조회 알고리즘은 크게 어렵지 않았는데 여러 마리의 멧돼지들이 맵 안을 이동하는 이동 알고리즘이 조금 어려웠다. 시간 복잡도를 감안해서 이동 알고리즘을 구현했어야 했기에 단순하게 여러 마리의 멧돼지들을 일일이 for문으로 움직이는 것이 아닌 수학 수식을 세워 이동시키는 알고리즘을 구현하였는데 그 수식은 설명을 들어서 알게 된 것이지 막상 시험장에 들어가면 저러한 수식을 생각해내기 힘들수도 있을것 같다.