알고리즘 입문 - 1부터 n까지 연속한 정수의 곱을 구하는 알고리즘 & 재귀호출

알고리즘의 수행시간

sample1(A[ ], n)
{
	k = ; // floor function
	return A[k];
}

• n에 관계없이 상수 시간이 소요된다.

---

sample2(A[ ], n)
{
	sum ← 0;
	for i ← 1 to n
	sum← sum+ A[i];
	return sum;
}

• n에 비례하는 시간이 소요된다. (n의 복잡도를 지닌다)

---

sample3(A[ ], n)
{
	sum ← 0;
	for i ← 1 to n
		for j ← 1 to n
			sum← sum+ A[i]*A[j];
	return sum;
}

• n제곱에 비례하는 시간이 소요된다. (복잡도를 지닌다.)

---

sample4(A[ ], n)
{
	sum ← 0;
	for i ← 1 to n
		for j ← 1 to n {
			k ← A[1 ... n] 중 최댓값;
			sum ← sum + k;
		}
	return sum;
} 

• n세제곱에 비례하는 시간이 소요된다. (복잡도를 지닌다.)

---

sample5(A[ ], n)
{
		sum ← 0;
		for i ← 1 to n-1
			for j ← i+1 to n
				sum← sum+ A[i]*A[j];
		return sum;
}

• n제곱에 비례하는 시간이 소요된다. (복잡도를 지닌다.)

---

1부터 n까지 연속한 정수의 곱을 구하는 알고리즘

• 1부터 n까지의 곱, 즉 팩토리얼(Factorial) 문제

1! = 1
3! = 1 × 2 × 3 = 6
5! = 1 × 2 × 3 × 4 × 5 = 120
n! = 1 × 2 × 3 × … × (n -1) × n
단, 0!은 1이라고 약속합니다.

# 연속한 숫자의 곱을 구하는 알고리즘
# 입력: n
# 출력: 1부터 n까지 연속한 숫자를 곱한 값


def fact(n):
    f = 1                      # 곱을 계산할 변수, 초깃값은 1
    for i in range(1, n + 1):  # 1부터 n까지 반복(n + 1은 제외)
        f = f * i              # 곱셈 연산으로 수정
    return f

 
print(fact(1))                 # 1! = 1
print(fact(5))                 # 5! = 120
print(fact(10))                # 10! = 3628800

• 알고리즘 분석

  for 반복문을 이용한 프로그램의 경우 n!을 구하려면 곱셈이 n번 필요

---

재귀 호출

• hello() 함수의 정의를 보면 “hello”라는 문장을 화면에 출력한 다음 자기 자신인 hello()를 다시 호출한다. 이것이 바로 재귀 호출이다.

def hello():
    print("hello")
    hello()    # hello( ) 함수 안에서 다시 hello( )를 호출

hello()        # hello( ) 함수를 호출

재귀 호출 프로그램이 정상적으로 작동하려면 ‘종료 조건’이 필요

팩토리얼을 재귀 호출로 표현

n! = n × (n -1)! ← 팩토리얼을 구하려고 다시 팩토리얼을 구함(재귀적 정의)

• 1부터 n까지의 합 구하기를 재귀 알고리즘으로 구현하는 방법

1. fact(4)는 4 * fact(3)이므로 fact(3)을 호출하고
2. fact(3)은 3 * fact(2)이므로 fact(2)를 호출하고
3. fact(2)는 2 * fact(1)이므로 fact(1)을 호출합니다.
4. fact(1)은 종료 조건이므로 fact() 함수를 더 이상 호출하지 않고 1을 돌려줍니다.
5. fact(2)는 fact(1)에서 돌려받은 결괏값 1에 2를 곱해 2를 돌려주고
6. fact(3)은 fact(2)에서 돌려받은 결괏값 2에 3을 곱해 6을 돌려주고
7. fact(4)는 fact(3)에서 돌려받은 결괏값 6에 4를 곱해 24를 돌려줍니다.(최종 결과)

4!
= 4×3!
= 4×3×2!
= 4×3×2×1!
= 4×3×2×1	#(1은 종료 조건이므로 재귀 호출을 멈춤)
= 4×3×2
= 4×6
= 24

# 연속한 숫자의 곱을 구하는 알고리즘
# 입력: n
# 출력: 1부터 n까지 연속한 숫자를 곱한 값

def fact(n):
    if n <= 1:
        return 1
    return n * fact(n - 1)  # fact( ) 함수를 호출

print(fact(1))  # 1! = 1
print(fact(5))  # 5! = 120
print(fact(10)) # 10! = 3628800

• 알고리즘 분석

fact(4)를 구하려면 fact(1)의 종료 조건으로 돌려받은 1을 2와 곱하여 돌려줍니다. 그리고 그 값에 다시 3을 곱하여 돌려주고, 다시 그 값에 4를 곱하여 돌려주므로 곱셈이 모두 세 번 필요하다. 마찬가지로 n!을 구하려면 곱셈이 모두 n-1번 필요하다는 것을 알 수 있다.

---

1. 1부터 n까지의 합 구하기를 재귀 알고리즘으로 구현

# 1부터 n까지 연속한 숫자의 합을 구하는 알고리즘 
# 입력: n
# 출력: 1부터 n까지의 숫자를 더한 값

def sum_n(n):
  if n < 2:
    return 1
  return n + sum_n(n-1)

print(sum_n(10))	# 실행결과: 55

2. 리스트에 있는 n개의 숫자 중에서 최댓값 찾기 알고리즘을 재귀 알고리즘으로 구현

# 최댓값 구하기
# 입력: 숫자가 n개 들어 있는 리스트
# 출력: 숫자 n개 중 최댓값

def find_max(v,n):
  if n == 1:
    return v[0]
    
  max_v = find_max(v, n-1)			# 재귀 호출 
  
  if (max_v > v[n-1]): 
    return max_v 
  
  else: 
    return v[n-1]

v = [17, 92, 18, 33, 58, 7, 33, 42]
print(find_max(v, len(v)))			# 실행결과: 92