팩토리얼을 구하는 알고리즘 1
def fact(n):
f=1 #결과 저장 변수f
for i in range (1,n+1): #1부터 n+1 미만까지
f= f*i
print(n, f)
return f
print(fact(1))
print("")
print(fact(3))
print("")
print(fact(10))
각 단계마다 무슨 값을 가지는지 보기 쉽게 print함수를 몇개 추가했다. 결과는 아래와 같다.
1 1
1
3 1
3 2
3 6
6
10 1
10 2
10 6
10 24
10 120
10 720
10 5040
10 40320
10 362880
10 3628800
3628800
Process finished with exit code 0
입력n이 1일 때 1에 1을 곱하고 결과는 1.
입력n이 3일 때 1에 1을 곱하고, 2를 곱하고, 3을 곱해서 결과는 6.
입력n이 10일 때도 마찬가지로 1부터 10까지 차례대로 곱한 후 결과를 출력한다.
위의 코드는 재귀 호출 방식이 아니다. 재귀 호출 방식으로 팩토리얼을 구하는 알고리즘을 만들어보자.
팩토리얼을 구하는 알고리즘 2 - 재귀 호출 방식 사용
def fact(n):
if n <= 1:
print("x", 1)
return 1
print("x", n )
return n * fact(n-1)
print("결과:", fact(1))
print("")
print("결과:",fact(5))
print("")
print("결과:",fact(10))
이번에도 알고리즘이 돌아가는 과정을 알기 쉽게 print문 몇개를 삽입했다.
처음 봤을 땐 어떻게 구해지는거지? 하고 어리둥절 했다. 대충 어렴풋이 어떤식인지는 감을 잡았고 교재에 설명이 자세히 써져있어서 금방 이해됐다. 어떻게 이걸 만든건지 대단하다.
결과는 아래와 같다.
x 1
결과: 1
x 5
x 4
x 3
x 2
x 1
결과: 120
x 10
x 9
x 8
x 7
x 6
x 5
x 4
x 3
x 2
x 1
결과: 3628800
Process finished with exit code 0
위 결과의 'x 10', 'x 9' 등은 해당하는 숫자의 팩토리얼을 호출할 때 출력된다. fact(10)을 호출했을 때 'x 10' 출력, fact(10)은 fact(9)를 호출하여 fact(9)가 실행되고 'x 9'가 출력. 이런식으로 각 함수가 호출될 때마다 차례대로 출력된다.
이후 fact(1)까지 내려간 후에 fact(1)에서부터 값을 반환받아 fact(2)부터 fact(10)까지 차례대로 값을 반환하며 올라오고 fact(10)에서 '결과: n * fact(n - 1)'을 반환한다.
작동방식을 설명해보겠다.
1. 5를 입력했다고 해보자. fact(5) 호출.
2. fact(5) 즉 5!은 5 * 4!이다. 파이썬으로 표현하자면 [fact(5) == 5 * fact(4)]
3. fact(4) 값을 알아야 fact(5)를 구할 수 있으므로 fact(4) 호출.
4. fact(4)는 fact(3)을 알아야 구할 수 있으므로 fact(3)을 호출, fact(3)은 fact(2)를 호출, fact(2)는 fact(1)을 호출한다.
5. fact(2)가 호출한 fact(1)은 조건문에 걸려서 1을 반환한다.
6. 1을 반환받은 fact(2)는 값을 fact(3)에 반환한다. fact(3)도 3 * fact(2)인 상황에서 fact(2) 값을 반환받아서 3!을 계산하고 값을 fact(4) 에 반환한다. fact(4)도 4!값을 fact(5)에 반환한다.
7. fact(5)가 값을 반환한다.
for를 사용한 알고리즘, 재귀 호출을 사용한 알고리즘은 빅 오 표기법으로 어떻게 표현할 수 있을지 알아보자.
for 반복문을 이용한 알고리즘의 경우 n!을 구하려면 곱셈이 n번 필요하다. 1!은 1번, 10!은 10번.
재귀 호출을 이용한 알고리즘의 경우 fact(4)를 구하려면 fact(1)에서 1을 반환받은 후 fact(2)에서 반환, fact(3)에서 반환, fact(4)에서 반환, 총 3번의 곱셈이 필요하다. 즉, fact(n)을 구하기 위해서 n-1 번의 곱셈이 필요하다.
for 반복문, 재귀 호출 두 경우 모두 입력값의 크기와 알고리즘 시간이 비례한다. 따라서 알고리즘의 시간 복잡도는 O(n)이다.
끝으로, 교재에서 강조하는 중요한 점은 재귀호출을 사용할 때는 반드시 '종료 조건'이 필요하다는 것이다. 종료 조건이 없으면 재귀 에러나 스택 오버플로 등 프로그램 에러가 발생해 비정상적인 동작을 할 수도 있다.
'프로그래밍 > 알고리즘 공부' 카테고리의 다른 글
모두의 알고리즘 문제 03. 동명이인 찾기 1 연습문제 (0) | 2022.05.12 |
---|---|
모두의 알고리즘 문제 03. 동명이인 찾기 1 (0) | 2022.05.12 |
모두의 알고리즘 문제 02. 최댓값 찾기 연습문제 (0) | 2022.05.09 |
모두의 알고리즘 문제 02. 최댓값 찾기 (0) | 2022.05.09 |
시간 복잡도와 빅 오 표기법 공부 - O(n), O(1), O(n^2), O(log n)에 대하여 (0) | 2022.05.08 |