알고리즘이란?
: 계산을 통하여 해결할 수 있는 문제를 해결하는 방법
알고리즘 특징
- 유한성
- 명확성
- 입력
- 출력
- 효과성
재귀호출이란?
: 함수가 자기 자신을 호출
수학적 귀납법 = 재귀적 증명법
: 명제 P(n)을 다음과 같이 증명하는 방법
- N = 1일 때 성립함을 보인다.
- P(k)가 성립한다고 가정할 때, P(k+1)이 성립함을 보인다.
- 따라서 모든 자연수 n에 대하여 P(n)이 성립한다.
예시)
퀵정렬
: 재귀호출을 이용한 대표적인 정렬
예시) 4를 기준으로 작은수는 왼쪽 큰수는 오른쪽
재귀함수 디자인
재귀함수를디자인 하기 위한 세가지 단계
- 함수의 정의를 명확히 한다.
- 기저 조건에서 함수가 제대로 동작하게 작성한다.
- 함수가 작은 input에 대하여 제대로 동작한다고 가정하고 함수를 완성한다.
'자료구조' 카테고리의 다른 글
[알고리즘] 동적계획법 (0) | 2024.05.07 |
---|---|
[자료구조] 8일차 우선순위 큐의 방법과 힙 (0) | 2024.04.18 |
[자료구조] 7일차 트리의 표현 방법, 트리 순회하기 (0) | 2024.04.17 |
[자료구조] 7일차 트리의 활용 (0) | 2024.04.17 |
[자료구조] 6일차 비선형 구조와 트리 (0) | 2024.04.16 |