코딩하는 공무원

수학적 귀납법과 재귀는 서로 비슷한 구석이 많은 놈들입니다. 원래의 문제를 해결하기 위해 자신의 부분 문제의 해를 이용한다는 점에서 매우 유사하지요... 그러나, 실제 문제가 해결되는 과정을 보면 개념적으로 많이 다릅니다. 수학적 귀납법은 너무나 자명한 기본 상태부터 시작합니다. 그리고 임의의 k에 대해서 증명하고자 하는 명제가 무조건 참임을 가정합니다. 그리고 기본 상태와 k에 대한 무조건적인 가정을 토대로 k+1에 대해 주어진 명제가 참임을 증명하지요.. 그것이 증명된다면 전체 문제에 대해 그 명제가 참임이 자연스럽게 증명되는 방식입니다. 재귀도 이와 비슷합니다. 그러나, 방향이 다릅니다. 수학적 귀납법은 작은 것에서 큰 것으로 나아가는 반면, 재귀는 큰 것에서 작은 것으로 나아가지요. 즉, 하향식 ..

http://en.wikipedia.org/wiki/Nassi-Shneiderman_diagram The Nassi-Shneiderman Diagram Editor Nessi : http://eii.ucv.cl/nessi/ Structorizer : http://structorizer.fisch.lu/ 정수 n이 주어질 때, 1~n까지의 합계를 구하는 알고리즘 정수 n이 주어질 때, 1~n까지 숫자 중에서 짝수의 합계를 구하는 알고리즘

코드 : 90rm3 퀵 정렬 알고리즘을 사용하여 주어진 수열을 오름차순 정렬하고자 한다. 다음은 퀵 정렬 알고리즘의 의사코드다. 현재 수열의 왼쪽 끝 항이 축이다; 다음을 반복한다. i = 현재 수열의 왼쪽 끝+1; j = 현재 수열의 오른쪽 끝; 오른쪽으로 검사, 축보다 크거나 같은 값이 있는 위치 i; 왼쪽으로 검사, 축보다 작거나 같은 값이 있는 위치 j; i>=j이면 반복을 중단한다; i항과 j항을 교환; 왼쪽 끝의 축과 j항을 교환; 왼쪽 부분 수열과 오른쪽 부분 수열에 대해서 위와 동일한 과정을 거친다. 단, 수열을 구성하는 데이터의 개수가 1보다 커야 한다. 위 알고리즘을 수행할 때, i항과 j항이 맞교환되는 경우 i와 j를 출력한다. 입력 INPUT.TXT의 첫 줄에는 수열을 구성하는 데이..

몬티홀 문제가 네이버 오늘의 과학에 나왔네요.. 정재승의 과학 콘서트에도 소개되었죠... 네이버에서는 조건부 확률로서 이를 자세히 증명하고 있습니다. http://navercast.naver.com/science/math/2426 이 몬티 홀 문제를 컴퓨터 시뮬레이션으로 확인해 볼 수 없을까요? 즉, 3개의 문 중에서 임의로 선택한 1개의 문 뒤에 고급 승용차를 놓습니다. 또한, 나머지 두 개의 문 뒤에는 "꽝"인 염소를 놓습니다. 참가자는 문 뒤에 무엇이 놓여 있는지 전혀 알 수 없는 상황에서, 이 3개의 문 중 아무 문이나 선택합니다. 이때, 참가자가 선택하지 않은 "꽝"인 문을 열어 보여주는데, 이때 참가자가 선택하지 않은 "꽝"인 문은 다음과 같은 2가지 경우가 있을 수 있습니다. 경우 1 : 참..

이산수학의 핵심적인 증명 방법인 "수학적 귀납법"이 네이버 “오늘의 과학”에 소개되었네요... http://navercast.naver.com/science/math/2354 수학적 귀납법으로 증명할 수 있는 대표적인 문제가 "하노이 탑"인데요... n개의 원반을 모두 이동하기 위한 원반의 이동 횟수가 2n-1임을 수학적 귀납법으로 증명할 수 있습니다. 언제 한번 관련 글을 포스트하지요... 위의 링크를 클릭해서 네이버의 “오늘의 과학”을 읽어보세요. 수학적 귀납법의 힘을 느낄 수 있습니다.

알고리즘 분야의 대표적인 난제 "P 대 NP 문제"가 네이버에 나왔네요... 우리가 심심풀이로 하던 지뢰 찾기가 바로 NP 문제입니다. 아래의 링크를 자세히 읽어 보시길… http://navercast.naver.com/science/math/2260 38초만에 지뢰찾기를 푸는 동영상도 감상하세요…