반응형 Programming/Algorithm35 네모네모 로직(nonogram) 풀기 - 3 네모네모로직을 사람이 하는 방법을 채택해서 풀어보면 어떨까요? 이미 무식한 방법(Brute force)으로 네모네모 로직을 풀어보았습니다. 이 방법을 이용하면, 모든 경우를 다 탐색하기 때문에 풀지 못 하는 로직은 없습니다. 시간은 많이 걸릴 수가 있습니다. 사람이 푸는 방식을 채택해서 풀어보면, 보다 합리적인 시간안에 문제를 풀 수 있고, 이것을 이용하면, 합리적인 네모네모로직 문제를 만들 수도 있습니다. (네모네모 로직 중 답이 여러개인 경우도 꽤 있고 여러 경우의 수를 생각해서 풀어야 하는 것들도 있습니다.) 새로운 방법을 기존의 NemoLogic 클래스에 적용해서 클래스 설계를 해보았습니다. [NemoLogic class] class NemoLogic { public: NemoLogic(); ~N.. 2014. 11. 26. 네모네모 로직(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 GetN.. 2014. 11. 17. 네모네모 로직(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. 네이버 개발자 센터에 알고리즘 프로젝트 개설 네이버 개발자 센터에 알고리즘 개발 프로젝트를 올렸습니다. http://dev.naver.com/projects/algc 위 링크고요. 소스에 접근하기 위해서는 저에게 쪽지나 기타 방법을 이용해서 알려주시면, 프로젝트 멤버로 등록해줄께요. 참고로 알고리즘 프로젝트는 VS2010, Windows Platform, C/C++ 입니다. 알고리즘 잘 안 되는 것들 있으면, 게시판에 적어주시거나 해서 같이 개발해봐요. 2014. 9. 19. 이전 1 2 3 4 5 6 다음 728x90
