수학적 귀납법1 수학적 귀납법, 재귀 수학적 귀납법 - 모든 자연수 n에 대해 어떤 명제가 참임을 증명할 때 사용하는 것이다. 모순에 의한 증명과 더불어 가장 어려운 증명방법이다. 연역법의 한 종류이다. 재귀함수 설계에 도움을 줄 수 있다. 재귀 - 한 함수에서 자기 자신을 다시 호출해 작업을 수행하는 것이다. 동일한 문제를 조금 더 작은 단위로 해결함으로써 그 문제를 해결한다. 다중 분기 재귀 - 문제의 일부만 방문하는 것만으로 원하는 결과를 찾을 수 있다. 분할 정복 알고리즘의 영역이다. 분할 정복 - 문제의 영역을 여러 부분으로 나눈 뒤 한 부분씩 문제를 해결해 나가는 걸 반복한다. 시간 복잡도 - O(n) 이진 탐색 - 정렬되어 있는 데이터 집단에서 어떤 값을 찾을 때 유용한 알고리즘이다. 절반의 영역만 재귀적으로 탐색하면 답을 찾을.. 2023. 1. 15. 이전 1 다음