Programming456 A* 알고리즘을 이용한 하노이 타워 풀기 A* 알고리즘을 이용해서 일반적으로는 길찾기를 많이 합니다. A* 알고리즘은 적절한 에너지 함수만 제공해준다면, 최적의 해를 적은 노드 탐방으로 찾을 수 있는 장점이 있습니다. 그러나 적절한 에너지 함수를 제공할 수 없는 경우에는, A* 알고리즘은 상당히 많은 시간을 소모할 수 있고, 또한 최적의 해를 찾을 수 없을 수도 있습니다. 1) 에너지 함수가 실제 소요되는 것보다 상대적으로 너무 적을 때에는 많은 노드를 탐방하게 됩니다. 2) 에너지 함수가 실제 소요되는 것보다 더 많을 가능성이 아주 조금이라도 있다면, 최적의 해를 찾는다는 보장을 할 수 없습니다. 제가 A* 알고리즘을 조금 더 관심있게 보고 있는 것은 바로 2)항 때문입니다. 게임 AI 로직에서 최적의 해를 꼭 찾아야한다고 볼 수 없습니다. .. 2014. 12. 11. PC 스크린 레코더 제가 주로 사용하는 PC 스크린 레코더는 LoiLo Game Recorder입니다. 이 프로그램은 일단 다음과 같은 장점들이 있습니다. 1. 가장 매력적인 부분은 무료로 제공되며, 어딘가에 붙어 있을만한 레코딩된 비디오에 어떤 광고글도 들어가있지 않습니다. 기간 제한도 없고요. 2. 가볍습니다. 3. 자동으로 인식해서 현재 동작중인 윈도우를 녹화할 수 있습니다. 4. 단축키로 녹화 시작과 종료를 할 수 있습니다. 일단 프로그램을 다운로드 받으셔야합니다. 다운로드할 수 있는 링크는 다음과 같습니다. http://http://loilo.tv/kr/product/game_recorder 해당 홈페이지의 내용입니다. 일단 게임레코더로 되어 있기 때문에 창 위주로 녹화를 진행합니다. 화면 전체로 녹화하기를 원하신.. 2014. 12. 9. A* 알고리즘을 위한 우선순위 큐 구현 알고리즘 그래프 이론을 들어가면, 가장 끝판왕은 역시나 A* 알고리즘이라고 생각합니다. A* 알고리즘은 게임 프로그래밍에서도 많이 쓰이는 기법이니, 알아두는 것이 좋지 않을까 하네요. A* 알고리즘을 적용할 때, 방문해야할 노드 수가 많을 때, 속도에 영향을 미치는 부분은 두가지가 있습니다. 첫번째는 가장 작은 에너지 함수값을 갖는 노드를 찾는 것입니다. 두번째는 방문한 셋에 포함되어 있는지 찾는 것입니다. 제 경우에는 작은 에너지 함수값을 갖는 노드를 찾는 것은 힙을 이용한 우선순위 큐를 사용합니다. 힙을 이용하게 되면, 삽입과 삭제의 경우 \(O(\log n)\)의 점근적 시간이 필요합니다. 선형으로 찾는 것보다 훨씬 빠르게 삽입 삭제를 할 수 있습니다. 방문한 셋에 포함되어있는지 검사하는 방법은 해.. 2014. 12. 8. 하노이 타워 알고리즘을 하다보면, 자기호출함수 부분을 배울 때, 하노이 타워에 관련되어서는 한번쯤 이야기가 됩니다. 하노이 타워는 대표적인 재귀적 관점이 들어가 있습니다. (사진출처 : 위키피디아) 하노이 타워가 재귀적 관점이 들어가는 가장 큰 이유는, 작은 디스크 위에 큰 디스크가 올라갈 수 없다는 이유때문입니다. 위 그림에서 첫번째 기둥에 있는 8개의 디스크를 가운데 기둥으로 모두 옮겨야 한다고 하면, 가장 큰 디스크는, 위에 있는 7개의 디스크를 맨 오른쪽 기둥으로 옮기고 나서야 옮길 수 있습니다. 가장 큰 디스크를 가운데 기둥으로 옮긴다음, 맨 오른쪽에 있는 7개의 디스크를 가운데 기둥으로 옮기면 됩니다. 그래서 n개의 디스크를 옮긴다면, 다음과 같이 재귀적 알고리즘을 적용할 수 있습니다. 1) n-1개의 디.. 2014. 12. 5. 마크로를 이용해서 문자열 찍기 C/C++ 언어에서 마크로를 사용하면 다양한 작업을 할 수 있습니다.그런데 의외로 이 마크로를 잘 이용하지 못 하는 사람들이 많습니다. 몇가지 마크로와 관련한 팁을 알려드릴께요. 1) 마크로를 이용한 디버그 메세지 찍기. 디버그 메세지를 찍고 싶다면, 다음과 같이 이용해보세요. #include #define OUTDEBUG(fmt, args...) { char s[128]; sprintf(s, fmt " : %s(%d)", ##args, __FILE__, __LINE__); puts(s); } int main() { char filename[] = "a.txt"; OUTDEBUG("%s file open error.", filename); } 윈도즈에서는 아래 형식밖에 안 되네요. #include #de.. 2014. 12. 2. [C/C++] 네모네모 로직(nonogram) 풀기 - 3 네모네모로직을 사람이 하는 방법을 채택해서 풀어보면 어떨까요? 이미 백트래킹 방법(back tracking)으로 네모네모 로직을 풀어보았습니다. 이 방법을 이용하면, 모든 경우를 다 탐색하기 때문에 풀지 못 하는 로직은 없습니다. 시간은 많이 걸릴 수가 있습니다. 사람이 푸는 방식을 채택해서 풀어보면, 보다 합리적인 시간안에 문제를 풀 수 있고, 이것을 이용하면, 합리적인 네모네모로직 문제를 만들 수도 있습니다. (네모네모 로직 중 답이 여러개인 경우도 꽤 있고 여러 경우의 수를 생각해서 풀어야 하는 것들도 있습니다.) 새로운 방법을 기존의 NemoLogic 클래스에 적용해서 클래스 설계를 해보았습니다. [NemoLogic class]class NemoLogic{public: NemoLogic().. 2014. 11. 26. 이전 1 ··· 67 68 69 70 71 72 73 ··· 76 다음 728x90
