이 포스트를 만든 목적

  • 생각 절차, 푼 방법, 고민거리 등을 기록하기 위해서 만들었다.

이 포스트의 준비물

  • firefox4 b8
  • eclipse + vrapper
  • lua 5.1.4

참조 문헌

  • 스티븐 스키에나, 미구엘 레비야 저. Programming Challenges: 알고리즘 트레이닝 북. 서환수 역.
    Springer. 한빛미디어 초판 2쇄 2004.12.05. (문제 16 Yahtzee, page 82 ~ 83)

참고 링크

내용

이 문제의 목표는 야찌 게임에서 최고 점수를 찾는것이다.

야찌(Yahtzee) 게임은 어떻게 하는 것인가?

  1. 주사위 5개를 준비 한다.
  2. 5개의 주사위를 모두 던지고, 각 주사위의 눈을 기록한다. 이것을 13번 반복한다.
  3. 적어 놓은 13개의 기록을 카테고리와 대조하여 점수를 낸다.
  4. 한번 대조된 주사위 기록은 쓸수 없다.

  5. 이렇게 모두 모운 점수를 총점이라고 하고, 총점이 높은 사람이 이기는 게임이다.

점수 계산 카테고리들

  1. 카테고리 1 - 모든 1들의 합
  2. 카테고리 2 - 모든 2들의 합
  3. 카테고리 3 - 모든 3들의 합
  4. 카테고리 4 - 모든 4들의 합
  5. 카테고리 5 - 모든 5들의 합
  6. 카테고리 6 - 모든 6들의 합

  7. 카테고리 7 - 모든 숫자의 합
  8. 카테고리 8 - 같은 주사위가 적어도 3개 일 때, 모든 숫자의 합
  9. 카테고리 9 - 같은 주사위가 적어도 4개 일 때, 모든 숫자의 합

  10. 카테고리 10 - 같은 주사위가 적어도 5개 일 때, 50점
  11. 카테고리 11 - 4 개의 주사위가 연속된 숫자일 때, 25점
  12. 카테고리 12 - 5 개의 주사위가 연속된 숫자일 때, 35점

  13. 카테고리 13 - 3개가 같은 숫자이고, 나머지 2개가 같은 숫자일때, 40점
  14. 카테고리 14 - 카테고리 1 ~ 6까지의 합이 63점 이상일 경우, 35점
맛보기 문제 풀이




여담

  • 백트랙킹 알고리즘(backtracking:모든 경우의 수로 문제는 푸는 알고리즘) 이란 이름을 알았다.
    - 전부 백트랙킹으로 풀기엔 시간이 너무 많이 들어서, 카테고리 1 ~ 6 까지만 백트랙킹을 이용했다.

  • 휴리스틱 알고리즘(heuristic:경험이나 학습으로 문제를 푸는 알고리즘) 이란 이름을 알았다.
    - 카테고리 7 ~ 13 까지는 휴리스틱 알고리즘을 사용했는데, 썩 좋은 답을 내놓지 못했다.(최고점보다 2점이나 낮다...)

  • 메모라이즈(memorize) 기법 이란 이름을 알았다.
    - 계속 계산할 필요 없이, 한번 계산한 것을 기록해 두었다가 쓰는 기법인데, 여기선 모든 스코어를 기록해 두었다가 사용했다.

  • 1년 전에 이 문제를 접했다가 못풀어서, 쉬었었는데, 얼마전에 시작해서, 감잡고 다시 풀었다.

:wq

posted by 농사를 짓는 게임 프로그래머 최익필

댓글을 달아 주세요

  1. Favicon of https://www.ikpil.com 농사를 짓는 게임 프로그래머 최익필 2009.12.21 02:15 신고  Addr  Edit/Del  Reply

    두 가지 방법
    1. 카테고리를 분석해서 최고 높은 점수를 받을 수 있는 경우를 찾아서 코드로 구현을 하는 방법
    2. 모든 경우의 수를 조사하여, 최고 높은 점수를 받는 경우를 찾는 방법
    이렇게 이 두가지 방법이 있겠다.

    1번은 "어떻게 스타크래프트를 잘 할 수 있는지 생각하는 것" 이고,
    2번은 "이길때까지 스타크래프트를 하는 것" 이다.

  2. Favicon of https://www.ikpil.com 농사를 짓는 게임 프로그래머 최익필 2009.12.24 02:46 신고  Addr  Edit/Del  Reply

    모르는 것을 알았다.

    각 카테고리에 원하는 라운드를 고를 경우, 다른 카테고리에 얼마큼의 손실을 입힐 수 있는지 수식을 계산한줄 모른다는 것을 알았다.

  3. Favicon of https://www.ikpil.com 농사를 짓는 게임 프로그래머 최익필 2010.01.28 23:37 신고  Addr  Edit/Del  Reply

    계산해서 구현해 놔야 하는데, 생각을 구체화 못하겠다. 구체화 못하는 이유가 생각이 없어서 인지, 규칙을 못찾아서 인지. 흠!

  4. Favicon of https://www.ikpil.com 농사를 짓는 게임 프로그래머 최익필 2010.01.31 21:17 신고  Addr  Edit/Del  Reply

    풀어야 하는데 선뜻 못하겠음.

  5. Favicon of https://www.ikpil.com 농사를 짓는 게임 프로그래머 최익필 2010.12.18 21:48 신고  Addr  Edit/Del  Reply

    어렵지 않다. 다시 풀어야지.

  6. Favicon of https://www.ikpil.com 농사를 짓는 게임 프로그래머 최익필 2010.12.28 03:09 신고  Addr  Edit/Del  Reply

    풀었긴 풀었는데, .. 325 점이 최고 점수로 나온다. ... 327점이 최고 점수인데. .. 최고 점수 로직이 부실하다..