모종닷컴

알고리즘 설계 패러다임이란 주어진 문제를 해결하기 위해 알고리즘이 채택한 전략이나 관점을 말한다. 무식하게 풀기'무식하게 푼다'라는 말은 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미한다. 이렇게 가능한 방법을 전부 만들어 보는 알고리즘들을 가리켜 흔히 "완전 탐색"이라고 한다. 재귀 호출과 완전 탐색재귀 호출(=재귀 함수)이란 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수를 말한다. 재귀 함수에는 '더 이상 쪼개지지 않는' 최소한의 작업에 도달했을 때 답을 곧장 반환하는 조건문(='거저 사례')을 포함해야 한다.ex) if(n==1) return 1; 재귀 호출은 기존에 ..

알고리즘이 존재가능한 모든 입력에 대해 정확하게 동작한다는 사실을 증명할 수 없다. 따라서 알고리즘의 정확한 증명은 각종 수학적인 기법을 기반으로 되야한다. 수학적 귀납법과 반복문 불변식 수학적 귀납법은 반복적인 구조를 갖는 명제들을 증명하는 데 유용하게 사용되는 증명 기법. 귀납법은 크게 3가지로 나뉜다.단계 나누기 = 증명하고 싶은 사실을 여러 단계로 나눈다. 첫 단계 증명 = 첫 단계에서 증명하고 싶은 내용이 성립함을 보인다. 귀납 증명 = 첫 단계에서 증명하고 싶은 내용이 성립하면, 다음 단계에서도 성립함을 보인다. 알고리즘은 어떠한 형태로든 반복적인 요소를 가지고 있기 때문에, 귀납법은 알고리즘의 정당성을 증명할 때 가장 유용하게 사용되는 기법. 반복문 불변식 = 반복문의 내용이 한 번 실행될 ..