수학적 귀납법

수학적 귀납법(mathematical induction)

• 수학 증명 기법 중 하나
• 모든 자연수 n에 대해 어떤 명제 P(n)이 참임을 증명할 때 사용
  • n = { 0, 1, 2, ...}
  • P(0)도 참
  • P(1)도 참
  • 등..

 

수학적 귀납법의 증명 방법

 

1. 기본 가정 : 시작점 P(0)이 참임을 증명
2. 귀납 가정 : 임의의 자연수 k에 대해 P(k)가 참일 때 P(k + 1)도 참일 것이라는 일반적인 가설을 세움 : P(k) -> P(k + 1)
3. 귀납 단계 : 이 가설이 참임을 증명
4. 결론 : 그럼 P(0)이 참이니 P(1)도 참, P(1)이 참이니 P(2)도 참. 연쇄적으로 참이 일어나므로 모든 자연수 n에 대해 P(n)이 참임을 증명

 

예시 : 도미노 쓰러뜨리기

 

• 도미노를 전부 쓰러트리려면? 
• 간격을 정확히 잘 세워야 한다. => 그렇다면 잘 세운다는것을 증명한다면?
• 첫 번째 도미노 조각이 넘어질 때, 두 번째 도미노 조각과 함께 넘어져야 한다.(증명)
• 그렇다면 규칙에 맞게 세워둔 k번째 도미노 조각이 넘어지면 k + 1도 넘어진다라고 가정
• 실제로 그렇게 됨을 증명
• 연쇄 효과로 첫 번째 도미노부터 끝까지 넘어간다는것이 증명됨
• 즉, 근접한 두 도미노 조각 간에 적용되는 규칙을 연쇄적으로 적용하면 도미노 게임이 완성

 

수학적 귀납법과 재귀 함수의 연관성

 

재귀 함수의 동작 방법과 비슷하다. 

• 종료 조건이 만족하면 값을 그냥 반환
• 아닐 경우 현재 문제보다 하나 줄여서 자기 자신을 재귀적으로 호출
• 그 모든 과정을 합쳐주면 바로 답.
• 하지만 재귀함수와 수학적 귀납법은 비슷할 뿐 다른거다.

 

수학적 귀납법이 중요한 이유

 

1. 과학적 사고 방법을 훈련할 수 있게 해 줌
   • 패턴 분석 -> 가설 성립 -> 실제 증명
   • 연역적으로 확실히 증명할 수 있는 문제는 수학적 귀납법으로의 증명
   • 아닌 경우는 확률을 높여 객관성을 확보하는 과학적 사고 방법
   • 그러나 방법 자체는 동일
2. 재귀 함수 설계에 도움을 줌
   • 수학적 귀납법에서 문제를 반복 가능한 작은 부분으로 쪼개는 훈련이 재귀 함수를 설계하는데 도움
   • 그리고 수학적 귀납법에서의 기본 가정은 재귀 함수의 종료 조건과 같다.

 

분할정복

 

만약 어떤 배열에서 n을 찾는 코드를 짠다면?

//javascript
const arr = [0, 1, 2, 3, ...90];

for (let i = 0; i < arr.length; i++) {
	if (arr[i] === 85) {
    	return true;
    }
}

return false;

• 처음에 들어있는 경우 : 1번
• 끝에 들어있거나 안 들어 있는 경우 : n번
• 대충 평균 n / 2번
• 만약 arr의 수가 증가하면? 즉 10배가 많아지만, 10배 느려진다.
• 시간복잡도는 O(n)이다.
  • n에 어떤 상수를 곱하거나 나눠도 차이는 없음.
  • 그냥 정비례해서 선형적으로 증가한다는 뜻

 

오름차순으로 정렬된 배열에소 요소 찾기

 

반복횟수를 줄일 수 있는 경우라면?

//javascript
const arr = [0, 1, 2, 3, ...90];

for (let i = 0; i < arr.length; i++) {
	if (arr[i] === 85) {
    	return true;
    }
    
    if (arr[i] > 85) {
    	return false;
    }
}

return false;

• 그럼에도 시간 복잡도는 변하지 않는다. 조금이라도 빨리 발견할 수 있더라도 O(n)
• 요소 수가 증가하면, 탐색 시간도 비례해서 늘어남

 

이진탐색

• 정렬되어 있는 데이터 집단에서 어떤 값을 찾을 때 유용한 알고리즘
• 절반의 영역만 재귀적으로 탐색하면 답을 찾을 수 있음
• 재귀를 한 번 돌릴때마다 반씩 나눠가지는만큼 범위가 줄어드는 것
• 계속 2배씩 증가하면 2의n승인데, 그 반대니 이건 log₂n
• 이러한 시간 복잡도를 O(logn)이라 함

이진 탐색 방법

1. 탐색할 범위에서 가운데의 값을 가져와 찾으려는 값과 비교
2. 같으면 true를 반환
3. 다르면
   • 더 이상 절반으로 나눌 수 없다면 false를 반환
   • 가운데 값이 찾으려는 값보다 큰 경우, 왼쪽 절반으로 탐색 영역을 바꾼 뒤 1단계로 돌아가 반복
   • 가운데 값이 작은 경우, 오른쪽 절반으로 탐색 영역을 바꾼 뒤 1단계로 돌아가 반복

시간복잡도의 그래프

 

분할 정복 알고리즘 필요성, 멀티 스레딩

CPU의 코어를 모두 사용한다면?

• 멀티스레딩이란 기법을 이용하면 가능
• 여러 개의 스레드를 만들어서 각 스레드가 어떤 코드를 병렬적, 독자적으로 실행할 수 있게 만들 수 있음
• 각 코어가 스레드를 하나씩 맡아서 처리할 수 있음
• 이 때 스레드 간에 코드 실행을 공유하지는 못 함
• 그러나 그 결과는 공유하는 메모리에 저장 가능