Programming/Algorithm34 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×(…0010r)2=x<<r 위 식을 이용하면, 우리는 보다 쉽게 r 의 값을 구할 수 있습니다. 아.. 2011. 9. 27. Bitwise operation IV 가장 오른쪽의 1인 비트의 위치를 알기 위해서는 간단한 수식을 정의할 수 있습니다. 여기서는 ρ(x)란 함수를 정의해서 사용하고자 합니다. 이 함수는 x란 숫자가 입력되었을 때, 가장 오른쪽의 1인 비트의 위치를 0부터 시작해서 표시하는 함수입니다. 애석하게도 ρ(0)에 대해서는 정의를 내릴 수가 없습니다. ρ(2x)=ρ(x)+1 ρ(2x+1)=0 ρ(x−y)=ρ(x⊕y) 사실 여기서 어떤 힌트를 얻어서 알고리즘을 만드는 것은 아닙니다. 오히려 우리가 얻어야 하는 힌트는 다른 데에 있습니다. 옛날에 제가 어렸을 때, 숫자를 맞추는 마술카드를 본 적이 있습니다. 이 마술카드는 1부터 5.. 2011. 9. 26. Bitwise operation III 비트단위 연산은 알고리즘에서도 많이 사용할 수 있는데, 이제까지 봤던 간단한 형태의 연산에서 이제는 알고리즘이라는 것을 적용해보고자 합니다. 일단 보수라는 것을 살펴보도록 할께요. 보수(Complement)라는 것은 반대되는 수를 말합니다. 우리는 알게모르게 보수라는 개념을 많이 사용하고 있습니다. 34-16 을 계산할 때에도 보수라는 개념을 사용할 수 있습니다. 14-6=8 이라는 개념보다는 보수를 사용하면 뺄셈을 덧셈으로 대치할 수 있으니까요. 14-6=10+4-6=(10-6)+4=4+4=8 이란 개념이죠. 여기서 4는 6에 대한 10의 보수입니다. 이진수에서도 보수를 많이 사용하는데 크게 두가지의 보수를 많이 사용합니다. 1의 보수와 2의 보수입니다. 엄밀하게 이야기한다면 -1의 보수와 0의 보수라.. 2011. 9. 23. 이전 1 2 3 4 5 6 다음 728x90
