Programming/Algorithm35 하노이 타워 알고리즘을 하다보면, 자기호출함수 부분을 배울 때, 하노이 타워에 관련되어서는 한번쯤 이야기가 됩니다. 하노이 타워는 대표적인 재귀적 관점이 들어가 있습니다. (사진출처 : 위키피디아) 하노이 타워가 재귀적 관점이 들어가는 가장 큰 이유는, 작은 디스크 위에 큰 디스크가 올라갈 수 없다는 이유때문입니다. 위 그림에서 첫번째 기둥에 있는 8개의 디스크를 가운데 기둥으로 모두 옮겨야 한다고 하면, 가장 큰 디스크는, 위에 있는 7개의 디스크를 맨 오른쪽 기둥으로 옮기고 나서야 옮길 수 있습니다. 가장 큰 디스크를 가운데 기둥으로 옮긴다음, 맨 오른쪽에 있는 7개의 디스크를 가운데 기둥으로 옮기면 됩니다. 그래서 n개의 디스크를 옮긴다면, 다음과 같이 재귀적 알고리즘을 적용할 수 있습니다. 1) n-1개의 디.. 2014. 12. 5. [C/C++] 네모네모 로직(nonogram) 풀기 - 3 네모네모로직을 사람이 하는 방법을 채택해서 풀어보면 어떨까요? 이미 백트래킹 방법(back tracking)으로 네모네모 로직을 풀어보았습니다. 이 방법을 이용하면, 모든 경우를 다 탐색하기 때문에 풀지 못 하는 로직은 없습니다. 시간은 많이 걸릴 수가 있습니다. 사람이 푸는 방식을 채택해서 풀어보면, 보다 합리적인 시간안에 문제를 풀 수 있고, 이것을 이용하면, 합리적인 네모네모로직 문제를 만들 수도 있습니다. (네모네모 로직 중 답이 여러개인 경우도 꽤 있고 여러 경우의 수를 생각해서 풀어야 하는 것들도 있습니다.) 새로운 방법을 기존의 NemoLogic 클래스에 적용해서 클래스 설계를 해보았습니다. [NemoLogic class]class NemoLogic{public: NemoLogic().. 2014. 11. 26. [C/C++] 네모네모 로직(nonogram) 풀기 - 2 네모네모로직을 풀기 위한 프로그램입니다. 기초적인 것은 앞의 글을 참고하세요. 첫번째, 로직프로그램을 담기 위한 클래스를 설계해봐야겠죠. [NemoLogic 클래스 뼈대]class NemoLogic{public: NemoLogic(); ~NemoLogic(); bool Load(const char *filename); void InitSolve(); bool Solve(); void PrintResult(); void Print(int row); int GetColNum() const { return colnum; } int GetRowNum() const { return rownum; } char *GetResult() const { return board; }protected: int GetNumb.. 2014. 11. 17. [C/C++] 네모네모 로직(nonogram) 풀기 - 1 머리를 말랑말랑하게 만들어주는 퍼즐 게임들은 여러가지가 있습니다. 대표적인 것은 스도쿠, 네모네모로직 등이 아닐까 합니다. 오늘 하려는 것은 네모네모로직을 풀어보는 것입니다. 그런데 사람이 풀자고 하는 것은 아니고, 컴퓨터가 네모네모 로직을 푸는 것이죠. 네모네모로직은 영어로는 nonogram이라고 불리며, 위 그림처럼, 모눈종이처럼 칸이 쳐져 있는 곳에 색을 칠해가는 게임입니다.색을 아무렇게나 칠할 수는 없고, 왼쪽과 위족에 숫자가 있는데, 그 숫자는 연달아 색칠되는 모눈칸의 갯수를 나열한 것입니다. 예를 들어서 3 4 가 써져있다면, 3개를 연달아 색칠한 후에 한개 이상의 빈칸을 둔 이 후에 다시 연달아 4개의 칸을 색칠하는 것입니다.예를 들어서 10개의 칸이 있다면, 3 4 의 숫자는 .. 2014. 11. 17. 다익스트라 알고리즘 다익스트라 알고리즘은 시작점에서 다른 모든 경로로 가는 최단 거리에 대한 그래프(트리)를 만들어줍니다. 다익스트라 알고리즘을 사용하려면, 힙을 이용해서 최소의 엔티티를 찾는 것이 필요하겠지만, 일단은 간단하게 구성해보았습니다. (참조 : http://sdev.tistory.com/72 , http://sdev.tistory.com/71) 이 소스는 애시당초 프림 알고리즘 소스를 만들었던 것을 고친지라, 코멘트가 프림에 맞추어져 있습니다. // Dijkstra.cpp : Defines the entry point for the console application. // #include "stdafx.h" #defineNIL(0) ///인접리스트를 위한 구조체 선언 struct vlist { int vert.. 2014. 10. 18. 소수 판별하기 우리가 컴퓨터에서 합당한 시간안에 결과를 찾을 수 있는 것은 과연 어느정도의 시간일까라는 생각을 많이 해봅니다. 암호학이라고 한다면, 적어도 100년? 아니면 그 이상일 수도 있겠다는 생각도 하죠. 주어진 수가 소수인지 아닌지, 판별하는 방법은 고전적인 방법에서부터 정수론에 기초한 방법까지 다양하게 있습니다. 소수판별법은 암호학에서 아주 중요합니다. 실제 소수판별을 쉽게 하는 방법이 있다면, 암호 해독도 더 쉬워집니다. 제일먼저 유클리드 호제법을 응용한 방법입니다. [유클리드 호제법을 이용한 소수 판별] bool isPrimeBF(_int64 n) { if( n%2 == 0 ) return false; for( unsigned __int64 r = 3 ; r*r >=1 ) ; for( int i = 0 .. 2014. 10. 7. 이전 1 2 3 4 5 6 다음 728x90
