반응형 Programming/Algorithm35 Induction I 2010.10.17. 논리를 증명하는데 있어서 자주 언급되는 것들로는 연역법과 귀납법이 있습니다. 위키피디아에 의하면 연역법(deductive reasoning)은 이미 알고 있는 사실로부터 새로운 사실을 추론하는 것이다라고 되어 있습니다. 그에 비해서 귀납법(Induction)은 경험적 근거를 바탕으로 한 사실을 말합니다. 연역법은 논리에 있어서 잘못된 추론이 있을 수 없지만, 귀납법은 잘못된 추론이 발생할 수 있습니다. 현대사회에서 귀납법을 이용하여 많은 사실을 이끌어내기는 하지만, 이것이 100% 올바른 답이라고 할 수 없습니다. 사회적 현상에서 특히 논란을 많이 발생시킵니다. 이 책에서는 일반적인 귀납법이 아닌 수학적 귀납법(Mathematical Induction)을 설명합니다. 수학적 귀납법은.. 2011. 9. 19. Euclid algorithm 유클리드의 소거법은 알고리즘을 설명하는데 자주 등장합니다. 그 이유 중 하나는 알고리즘(Algorithm)이란 말을 자주 사용하게 된 계기가 되었기 때문일겁니다. 유클리드의 소거법은 두 개의 숫자를 나눌 수 있는 최대 자연수를 찾는 과정을 기술하고 있습니다. E. 유클리드의 알고리즘 : m과 n이 주어졌을 때, 두 수를 나눌 수 있는 가장 큰 자연수를 찾는다. E1 : m과 n이 같다면 알고리즘을 종료한다. m이 원하는 답이다. E2 : m이 n보다 크다면 m ← m-n을 하고 그렇지 않다면 n ← n-m을 한다. E3 : E1 으로 돌아간다. 위의 알고리즘 E를 C 언어 함수로 만들면 아래와 같습니다. int foo(int m, int n) { while(m != n) { if( m > n ) m = .. 2011. 9. 19. The Art of Computer Programming 2010.10.10. 제가 개인적으로 읽고 있는 책입니다. 이 책은 Donald E. Knuth라고 하는 분이 쓰신 책인데요. 역작이라고 할 수 있습니다. 그러나 이 책을 읽기 위해서는 수학에 대해서 이해도가 높아야 하죠. 그렇지 않다면 조금 읽고서.. "이해 안 가"하면서 버릴만한 책이죠. 류광씨가 번역한 책이 한빛미디어를 통해서 판매되고 있으니 굳이 원서를 볼 이유는 없습니다. 오탈자가 좀 있는 것은 그런가 보다 이해하면 됩니다만.. 틈나는대로 이 책에 대해서 글을 올릴까 합니다. 물론 책 전체를 다 번역한다는 것은 아닙니다. 제가 이해하는 부분을 쓰기 때문에 혹시 책을 보면서 알고 싶으신 내용있으면 같이 풀어나갔으면 합니다. CHAPTER ONE 1.1 알고리즘(Algorithms) 알고리즘이란 것.. 2011. 9. 19. 이중 링크드 리스트 만들기 (Making double linked list) 링크드 리스트가 단일인 경우에는 포인터로 처리하는 것이 좋겠지만, 이중인 경우에는 그게 만만치 않아요. 포인터로 관리하려면, 포인터가 NULL인 경우 처리가 필요합니다. 새로운 노드를 추가하는 경우에는 포인터가 NULL인지 검사해야 하고, 기존 노드를 삭제하는 경우에는 노드의 갯수가 1개인지를 검사해야 합니다. 그래서 사용하는 방법은 바로 이것입니다. 클래스만 설계해보면, class CNode { public: CNode *m_pPrev; CNode *m_pNext; }; class CIntNode : public CNode { public: int data; }; class CDLinkedList { public: CDLinkedList() { m_kRoot.m_pPrev = &m_kRoot; m_kR.. 2011. 9. 16. 미로찾기 프로그램 미로의 크기는 10x10 으로, [0,0] 이 입구, [ 9,9]를 출구로 했습니다. 미로로 사용되는 데이터파일에는 다음과 같은 형식으로 미로가 지정되어 있습니다. 0 0 1 1 1 1 1 1 1 1 1 0 0 0 1 1 0 0 0 1 ... 1 1 1 1 1 0 1 1 1 0 즉 갈 수 있는 셀(cell)은 0으로 갈 수 없는 셀은 1로 설정되어 있죠. 사용한 알고리즘은 제일 간단한 방법을 사용했습니다. 더 좋은 방법이 당연히 있지만.. 2011. 9. 16. 이전 1 ··· 3 4 5 6 다음 728x90
