티스토리로 블로그를 이전한 뒤, 기념비적인 첫 글이다. 요즈음도 알고리즘을 공부하다보면, 금새 잊곤 하기 때문에 이렇게 하나 하나 글을 써보려 한다. 오늘 공부한 알고리즘은, 바로 "게임 이론" 알고리즘 분류만 보면 상당히 귀엽고 재밌어 보이지만, 상당히 악랄하다. 우선 오늘의 문제를 소개해보겠다. 처음 문제를 보았을 때는, 상당히 간단해 보인다. 그냥 항상 최선의 경우를 고르면 되는거 아님? 아니다 바로 다음과 같은 상황이 야기될 수 있다. 전체 게임 결과를 보았을 때, 최선의 선택을 해야하고, 상대 또한 최선의 선택을 하기에 내가 처음에 2를 뽑으면, 상대에게 5를 내주기 때문에 점수가 더 낮아지게 된다. 따라서 이 경우에서의 "최선의 수"란 다음과 같다. 물론 우리가 보기에는 , 그렇게 어렵지 않다..