수학적 귀납법, 재귀

수학적 귀납법 - 모든 자연수 n에 대해 어떤 명제가 참임을 증명할 때 사용하는 것이다. 모순에 의한 증명과 더불어 가장 어려운 증명방법이다. 연역법의 한 종류이다. 재귀함수 설계에 도움을 줄 수 있다.

 

재귀 - 한 함수에서 자기 자신을 다시 호출해 작업을 수행하는 것이다. 동일한 문제를 조금 더 작은 단위로 해결함으로써 그 문제를 해결한다.

다중 분기 재귀 - 문제의 일부만 방문하는 것만으로 원하는 결과를 찾을 수 있다. 분할 정복 알고리즘의 영역이다.

분할 정복 - 문제의 영역을 여러 부분으로 나눈 뒤 한 부분씩 문제를 해결해 나가는 걸 반복한다.

시간 복잡도 - O(n)

 

이진 탐색 - 정렬되어 있는 데이터 집단에서 어떤 값을 찾을 때 유용한 알고리즘이다. 절반의 영역만 재귀적으로 탐색하면 답을 찾을 수 있다.

 

스레드(Thread) - CPU 수행의 기본 단위이다. 한 프로세스가 하나의 스레드를 사용해 한번에 한 작업만 하는 것을 싱글 스레드라고 한다.

멀티 스레딩 - 한 프로세스가 여러 스레드를 만들어 동시에 여러 작업을 수행하는 것이다. 여러 개의 스레드를 만들어 각 스레드가 어떤 코드를 병렬적, 독자적으로 실행하게 만든다. 스레드 간에 코드 실행을 공유하지 못한다.