반응형 Programming/Algorithm35 숫자 야구 게임 만들기 Making baseball game. 숫자로 즐길 수 있는 숫자 야구게임은 어느정도 머리를 쓰면서 하는 게임이라 중고등학교를 다니면서 한두번씩은 접해본 적이 있는 게임일겁니다. 요즘은 컴퓨터 게임이 대세니 이런 장난스러운 게임도 안 할지도 모르겠네요. 서로 숫자를 생각하고 숫자맞추기를 하는 게임입니다. 한사람이 세자리 숫자를 생각합니다. 이 세자리 숫자의 각 자릿수는 서로 달라야 합니다. 맞추어야 하는 사람은 같은 규칙의 세자리 숫자를 제시합니다. 같은 자리의 숫자가 맞은 경우에는 스트라이크를, 다른 자리의 숫자가 맞은 경우에는 볼을 셉니다. 3 strike가 될 때까지 숫자를 제시해야 하며, 서로 더 적은 횟수만에 숫자를 맞추면 이기는 게임입니다. 예를 들어서 431 이라는 숫자를 생각했고, 제시한 .. 2011. 11. 20. Eight queens problem 체스판에서 8개의 퀸을 서로 죽이지 않도록 배치하는 문제는 알고리즘에서 많이 다루어집니다. 여기서는 알고리즘의 문제도 있지만, 어떻게 프로그램을 작성해야지 더 효율적일지를 생각해볼까 합니다. 체스에서 퀸은 전후좌우 그리고 대각선까지 장애물이 있지 않는 한 원하는 칸 수만큼 이동할 수 있습니다. 체스판에서 8개의 퀸을 어떻게 배치하면 서로 잡을 수 없는 위치에 놓일까 하는 것입니다. 이 조건을 간단하게 정리하면 다음과 같습니다. 각 열에는 오직 하나의 퀸만 존재해야 한다. 각 행에는 오직 하나의 퀸만 존재해야 한다. 각각의 퀸의 대각선에 다른 퀸이 존재해서는 안 된다. 여기서 첫번째 조건과 두번째 조건은 손쉽게 프로그램으로 작성할 수 있습니다. 만약 8개의 룩(Rook)을 가지고 이 문제를 냈다면, 수학적.. 2011. 11. 14. 자료구조의 보석 힙(Heap) 2010-02-19 19:27:20 오늘은 자료 구조의 보석인 힙(Heap)을 찾아서 가기로 해요.. 태고의 도시 야율론에 힙이라는 보물이 숨겨져 있다는 보물지도를 얻은 이비는 친구인 리시타와 피오나와 함께 야율론으로 떠나는 배를 탑니다. 이 보물지도는 고대 문자인 에리스문으로 되어 있는데, 이것을 해석하는 것은 아주 어렵다고 합니다. 특히 다중상속문이 존재하는 이 언어는, 고도의 지식을 요합니다. 더구나 템플릿을 이용하기도 하는데, 이 템플릿은 스택, 큐, 동적 배열을 한단어로 표현할 수 있을 정도로 강력한 마법 언어로 알려져 왔습니다. 다행히 이 보물지도에 있는 에리스문은 상속도 없고 템플릿도 없습니다. 리시타와 피오나 모두 준비가 되었다고 하는군요. 선장인 이비가 출발을 외칩니다..~ 뿌웅..~~~.. 2011. 9. 27. Prim algorithm with heap Prim algorithm with heap 제가 좋아하는 자료구조는 힙(Heap)이라는 것입니다. 힙은 이진트리 중에 특별한 형태를 사용하고 있습니다. 꽉 찬 이진트리를 사용함으로써 배열을 그대로 이진트리로 사용할 수 있습니다. 이중에서 최소힙과 최대힙이 있는데, 루트의 값이 가장 작은 경우를 최소힙, 가장 큰 경우를 최대힙으로 이해하면 됩니다. 힙의 조건은 다음과 같습니다. 힙의 제일 아래층을 제외하고 꽉 차있고, 제일 아래층은 왼쪽부터 꽉 차있다. 힙의 모든 노드는 하나의 값을 가지고 있다. 각 노드의 값은 자식의 값보다 항상 작다. (최소힙) 최대힙의 경우에는 3)항만 다릅니다. 꽉 찬 이진트리이기 때문에 배열로 바로 구현할 수 있습니다. 그렇지 않다면 자식들의 링크를 보관해야 하죠. 다음의 힙을.. 2011. 9. 27. Bitwise operation V 가장 오른쪽 비트의 위치를 알아내는 방법은 전에 소개한 방식이 있지만, 가장 빠른 계산을 할 수 있는 방법은 따로 있습니다. 기본적으로 가장 오른쪽 1인 비트만 남겨두고 나머지 비트들을 0으로 만드는 것은 똑같습니다. 우리가 연산을 할 때, 123x100을 생각해보면, 이 연산은 123이라는 숫자를 왼쪽으로 두자리 옮기는 효과가 있습니다. 마찬가지로 이진수에서도 이 방식은 그대로 통용됩니다. 예를 들어서 비트 7에만 1인 숫자가 있다면, 이 숫자를 다른 숫자와 곱하기를 하면, 결과는 7비트만큼 왼쪽으로 쉬프트 한 것과 같습니다. 즉 다음이 성립하는 것이죠. \[ x \times ( …0010^r )_2 = x \lt \lt r \] 위 식을 이용하면, 우리는 보다 쉽게 r 의 값을 구할 수 있습니다. 아.. 2011. 9. 27. Bitwise operation IV 가장 오른쪽의 1인 비트의 위치를 알기 위해서는 간단한 수식을 정의할 수 있습니다. 여기서는 \( \rho (x) \)란 함수를 정의해서 사용하고자 합니다. 이 함수는 x란 숫자가 입력되었을 때, 가장 오른쪽의 1인 비트의 위치를 0부터 시작해서 표시하는 함수입니다. 애석하게도 \( \rho (0) \)에 대해서는 정의를 내릴 수가 없습니다. \[ \rho(2x) = \rho(x) + 1 \] \[ \rho(2x+1) = 0 \] \[ \rho(x-y) = \rho(x \oplus y) \] 사실 여기서 어떤 힌트를 얻어서 알고리즘을 만드는 것은 아닙니다. 오히려 우리가 얻어야 하는 힌트는 다른 데에 있습니다. 옛날에 제가 어렸을 때, 숫자를 맞추는 마술카드를 본 적이 있습니다. 이 마술카드는 1부터 5.. 2011. 9. 26. 이전 1 2 3 4 5 6 다음 728x90
