1. 알고리즘이란?
알고리즘이란 문제를 해결하는 방법입니다.
예를 들어 전구가 작동하지 않는다면, 전구를 작동하도록 만드는 순서도를 구현하여 풀어본다면 아래와 같이 보일 것 입니다.
여기서 우리가 배우는 알고리즘이란, 계산을 통하여 해결할 수 있는 문제를 해결하는 방법입니다.
알고리즘에는 5가지 성질이 있습니다.
- 유한성 | 유한한 횟수를 거친 후 종료. 종료되지 않는 무한 루프는 알고리즘이 아닙니다.
- 명확성 | 각 단계가 명확하게 정의되어야 합니다.
- 입력 | 입력은 0개 이상
- 출력 | 출력은 1개 이상
- 효과성 | 시간적, 공간적인 효율과 유의미 해야합니다.
[실습 1] k번째 숫자 찾기
문제를 해결하는 방법
1. 숫자 하나를 입력받는다.
2. 지금까지 받은 숫자들을 정렬한다.
3. k번째로 작은 숫자를 출력한다.
2. 재귀호출
함수가 자기 자신을 호출합니다.
왜?
재귀호출의 대표격인 팩토리얼을 정리해보겠습니다.
팩토리얼의 재귀적 정의
팩토리얼의 정의상 0! = 1 입니다. 그리고 n! 팩토리얼의 값은 n x (n-1)!입니다.
만약 팩토리얼 5를 구한다고 가정한다면, 팩토리얼 5는 4를, 4는 3을 호출하는 식으로 하여 팩토리얼 0까지 호출하게 됩니다.
그런데 팩토리얼 0에서는 1을 팩토리얼 1로 반환을 하기 때문에, 다시 팩토리얼 1이 계산값을 팩토리얼 2로 리턴,
팩토리얼 2는 팩토리얼 3에 넘겨주는 식으로 팩토리얼 5의 최종값은 120이 됩니다.
3. 수학적 귀납법
재귀호출의 의미에 대해서 조금 더 깊이 알아보기 위해서는 재귀호출과 비슷한 수학적 귀납법에 대해서 공부해봅니다.
재귀호출과 수학적 귀납법은 매우 밀접한 관계가 있으며, 거의 근본적으로 같다고 해도 과언이 아닙니다.
수학적 귀납법 = 재귀적 증명법
명제 P(n)을 다음과 같이 증명하는 방법
1. N = 1 일 때 성립함을 보인다.
2. P(k)가 성립한다고 가정할 때, P(k+1)이 성립함을 보인다.
3. 따라서 모든 자연수 n에 대하여 P(n)이 성립한다.
1번의 경우, P(n) = 모든 자연수 n에 대하여 n! ≤ n^n임을 증명하시오. 란 결국 1! ≤ 1^1임으로 성립함을 알 수 있습니다.
2번의 경우, k! * (k+1) ≤ k^k * (k+1)가 성립한다. 그런데 k! * (k+1)의 경우는 (k+1)! 이기 때문에, (k+1)! ≤ k^k * (k+1)가 성립.
그렇다면 P(k+1)의 경우는 (k+1)! ≤ (k+1)^k+1 여기서 (k+1)^k+1 는 (k+1)^k * (k+1)과 같은 값을 나타냅니다.
그리고 k^k * (k+1) ≤ (k+1)^k * (k+1)이기 때문에, 2번이 성립하게 됩니다.
따라서,
하지만 P(k)가 실제로 성립하는지는 아직 모릅니다.
우선 모든 자연수 n에 대하여 n! ≤ n^n임을 증명합니다. → 수학적 귀납법의 세단계를 따라가면 모든 자연수 n에 대하여 위의 명제가 성립합니다.
따라서 수학적 귀납법이란 명제를 재귀적으로 증명하는 방법입니다.
재귀적 계산 방법
Factorial(n) : n!을 반환하는 함수
Factorial(n) = Factorial(n-1) * n
n=1 일때는 Factorial(n)이 정상 작동합니다.
4. 퀵정렬(Quick Sort)
재귀호출을 이용한 대표적인 정렬입니다. 수학적 귀납법이 n = 1일 때, 성립함을 보였던 것처럼 퀵 정렬에서는 원소가 1이거나 0일 때가 기저조건입니다.
5. 재귀함수 디자인
올바른 괄호인지 판단하기
재귀함수를 디자인 하기 위한 세가지 단계
1. 함수의 정의를 명확히 한다.
2. 기저 조건(Base condition)에서 함수가 제대로 동작하게 작성한다.
3. 함수가 작은 input에 대하여 제대로 동작한다고 가정하고 함수를 완성한다.
isRightParenthesis(p)
p가 올바른 괄호이면
"YES", 아니면 "NO"를 반환하는 함수
↓
인접한 괄호쌍을 지워나가면서 재귀호출을 하면서 빈 문자열이 나온다면 올바른 괄호입니다.
'Algorithm' 카테고리의 다른 글
| /*elice*/ 문제 해결 절차, 완전 탐색, 시간복잡도 (0) | 2022.07.31 |
|---|---|
| [Python] k번째 수 찾기 (0) | 2022.07.28 |
| 프론트엔드 개발자라면 알아야할 다섯가지 알고리즘 (0) | 2022.06.12 |
| [알고리즘] 알고리즘의 기초 정리자료-2 (0) | 2021.06.20 |
| [알고리즘] 알고리즘의 기초 정리자료-1 (0) | 2021.06.20 |
