반응형 알고리즘63 숫자 야구 게임 만들기 Making baseball game. 숫자로 즐길 수 있는 숫자 야구게임은 어느정도 머리를 쓰면서 하는 게임이라 중고등학교를 다니면서 한두번씩은 접해본 적이 있는 게임일겁니다. 요즘은 컴퓨터 게임이 대세니 이런 장난스러운 게임도 안 할지도 모르겠네요. 서로 숫자를 생각하고 숫자맞추기를 하는 게임입니다. 한사람이 세자리 숫자를 생각합니다. 이 세자리 숫자의 각 자릿수는 서로 달라야 합니다. 맞추어야 하는 사람은 같은 규칙의 세자리 숫자를 제시합니다. 같은 자리의 숫자가 맞은 경우에는 스트라이크를, 다른 자리의 숫자가 맞은 경우에는 볼을 셉니다. 3 strike가 될 때까지 숫자를 제시해야 하며, 서로 더 적은 횟수만에 숫자를 맞추면 이기는 게임입니다. 예를 들어서 431 이라는 숫자를 생각했고, 제시한 .. 2011. 11. 20. Eight queens problem 체스판에서 8개의 퀸을 서로 죽이지 않도록 배치하는 문제는 알고리즘에서 많이 다루어집니다. 여기서는 알고리즘의 문제도 있지만, 어떻게 프로그램을 작성해야지 더 효율적일지를 생각해볼까 합니다. 체스에서 퀸은 전후좌우 그리고 대각선까지 장애물이 있지 않는 한 원하는 칸 수만큼 이동할 수 있습니다. 체스판에서 8개의 퀸을 어떻게 배치하면 서로 잡을 수 없는 위치에 놓일까 하는 것입니다. 이 조건을 간단하게 정리하면 다음과 같습니다. 각 열에는 오직 하나의 퀸만 존재해야 한다. 각 행에는 오직 하나의 퀸만 존재해야 한다. 각각의 퀸의 대각선에 다른 퀸이 존재해서는 안 된다. 여기서 첫번째 조건과 두번째 조건은 손쉽게 프로그램으로 작성할 수 있습니다. 만약 8개의 룩(Rook)을 가지고 이 문제를 냈다면, 수학적.. 2011. 11. 14. Prim algorithm with heap Prim algorithm with heap 제가 좋아하는 자료구조는 힙(Heap)이라는 것입니다. 힙은 이진트리 중에 특별한 형태를 사용하고 있습니다. 꽉 찬 이진트리를 사용함으로써 배열을 그대로 이진트리로 사용할 수 있습니다. 이중에서 최소힙과 최대힙이 있는데, 루트의 값이 가장 작은 경우를 최소힙, 가장 큰 경우를 최대힙으로 이해하면 됩니다. 힙의 조건은 다음과 같습니다. 힙의 제일 아래층을 제외하고 꽉 차있고, 제일 아래층은 왼쪽부터 꽉 차있다. 힙의 모든 노드는 하나의 값을 가지고 있다. 각 노드의 값은 자식의 값보다 항상 작다. (최소힙) 최대힙의 경우에는 3)항만 다릅니다. 꽉 찬 이진트리이기 때문에 배열로 바로 구현할 수 있습니다. 그렇지 않다면 자식들의 링크를 보관해야 하죠. 다음의 힙을.. 2011. 9. 27. 이전 1 ··· 8 9 10 11 다음 728x90
