1. 문제 틱택토는 3x3 크기의 게임판에서 하는 3목 게임입니다. 두 명이 번갈아가며 o와 x를 게임판의 빈 칸에 쓰되, 먼저 같은 글자를 가로, 세로 혹은 대각선으로 3개 쓰이도록 하는 쪽이 이깁니다. 예를 들어, 다음 게임판은 x가 이긴 게임판입니다. xoo .x. ..x 게임은 항상 x부터 시작합니다. 틱택토 게임판의 현재 상태가 주어집니다. 두 사람 모두 최선을 다한다고 가정할 때, 어느쪽이 이길지 판단하는 프로그램을 작성하세요. 2. 풀이 /* - canWin(board) : 게임판이 현재 board일 때, 이번 차례인 사람이 이길 수 있다면 1, 비길 수 있다면 0, 질 수 밖에 없다면 -1을 반환한다. + board를 아홉 자리의 3진수로 본다. - 함수의 반환 값 중 -1이 있으므로, c..

1. 문제 계란 한 개에 _ _ _ _ _ _ _ _ _ _ _ _ _ 웨브바짐 달러! 계획 경제의 실패로 세계 최고의 인플레이션을 자랑하게 된 공산 국가 웨브바짐에서는 하루 중에도 물가가 계속 오르기 때문에 물건의 가격을 실시간으로 바꿔야 합니다. 웨브바짐에서 가장 큰 무가베 마트에서는 그래서 위와 같이 빈 칸만 쓰여 있는 광고판을 붙여놓고 계란 가격이 오름에 따라 (정확히는 웨브바짐 달러의 가치가 추락함에 따라) 실시간으로 숫자가 크게 적힌 플라스틱 판을 빈 칸에 갈아 끼웁니다. 예를 들어 계란 한 개에 35억 웨브바짐 달러라고 하면, 3이 쓰인 판 한 개, 5가 쓰인 판 한 개, 0이 쓰인 판 여덟 개를 빈칸에 순서대로 끼우는 것이죠. 무가베 마트에서 아르바이트를 하는 종욱이는 어느 날 곤란한 손님..

동적 계획법 중 메모이제이션을 적용하는 문제들이 참 많았는데, 무슨 소리인지 제대로 이해하지 못했다. 그래서 오늘 각잡고 조사해보았다. ^_^ 1. 동적 계획법이란? 동적 계획법 (dynamic programming): 처음 주어진 문제들을 분할하고, 이로부터 본 문제에 관한 답을 도출하는 접근 방법이다. 특히 부분 문제들의 수가 기하급수적으로 증가할 때 유용하다. 동적 계획법은 여러 문제 해결에 사용되는 부분 문제에 대한 결과를 여러번 계산하는 대신, 한 번만 계산하고 이를 재활용하여 속도를 향상시킨다는 점에서 분할 정복법과 차이가 있다. 이를 위하여 각 문제의 답을 메모리에 저장해야 하는데, 이미 계산된 값을 저장해두는 메모리의 장소를 캐시(cache)라고 하며, 두 번 이상 계산되는 부분 문제를 중..