알고리즘(합 구하기, 최댓값 구하기, 하노이탑, 알고리즘 수행시간, 빅오 표기법, 재귀함수)

알고리즘이란

어떤 문제를 풀기 위한 절차나 방법으로 주어진 '입력'을 '출력'으로 만드는 과정이다. 각 단계는 구체적이고 명료해야한다.

Algorithm1.

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

// 방법 1
def sum_(n):
	s=0
    for i in range(1, n+1):
    	s = s+i
    return s
print(sum_n(10))
print(sum_n(100))

➡ 수행시간: O(n), n번의 계산량
입력 값 n이 커질수록 덧셈을 훨씬 더 많이 반복해야 함

// 방법 2
def sum_n(n):
	return(n*(n+1)) // 2           # 합 공식 이용
print(sum_n(10))
print(sum_n(100))   

➡ 수행시간: O(log n), 3번의 계산량
n값의 크기와 관계없이 덧셈, 곱셈, 나눗셈을 각각 한 번씩만 함

1. 합을 기록할 변수 s를 만들고 저장
2. 변수 i를 만들어 1부터 n까지의 숫자를 1씩 증가시키며 반복
3. [반복 블록] 기존의 s에 i를 더하여 얻은 값을 다시 s에 저장
4. 반복이 끝났을 때 s에 저장된 값이 결과값

• 알고리즘을 하나의 함수로 만들어 입력은 인자로 전달
• 출력은 함수의 결과값 (return 값)
• 알고리즘은 '입력->알고리즘->출력'을 수행하는 과정

+심화) 1~n까지의 수가 아니라 주어진 임의의 n개의 수의 합이라면?

ex. [4, 6, 1, 10, 4, 11, 7...] 원소의 개수가 n개 일 때, 원하는 만큼 프로세스를 사용할 수 있다면 계산복잡도는 어떻게 될까?

병렬 프로세스라면 병렬적 복잡도는 O(log2 n)의 복잡도를 가질 것이다.
2개씩 동시에 계산되기 때문!

ex. 3, 4, 7, 8, 1, 2, 5, 9
(3, 4) (7, 8) (1, 2) (5, 9) 2개씩 묶어서 합 연산 > 7, 15, 3, 14를 다시 두개 씩 묶어서 연산 > 22, 17을 묶어서 연산 > 39라는 최종 결과 획득

Algorithm2.

주어진 숫자 n개 중 가장 큰 숫자를 찾는 알고리즘

def find_max(a):
	n = len(a) 
    max_v = a[0]			# 리스트의 첫 번째 값을 최대로 기억
    
    for i in range(1, n):	# 리스트의 크기-1 만큼 돌면서
    if a[i] > max_v:		# 다음 원소와 최댓값 max_v와 비교해서 
    	max_v = a[i]		# 다음 원소값이 더 크면 최대값에 넣어줌
    return max_v
v= [17,92, 18, 33, 58, 7, 33, 42]
print(find_max(v))

Algorithm3.

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

팩토리얼 사용하기 <--- 재귀함수의 대표 예제

def fact(n):
	f = 1 						# 곱을 계산할 변수, 초기값은 1
	for i in range(1, n + 1): 	# 1부터 n까지 반복
		f = f * i 				# 곱셈 연산으로 수정
	return f
print(fact(0)) # 0! = 1
print(fact(5)) # 5! = 120
print(fact(10)) # 10! = 3628800

• 계산 복잡도 = n

def fact(n):
	if n<=1:					# 재귀종료조건
    	return 0;
    return n * fact(n-1)		# 재귀호출 더 작은 값으로 자기 자신을 호출함으로써, 하위 범주의 계산이 끝나야 상위 연산이 시작됨!
print(fact(10)) 				# =10!

Algorithm4.

하노이탑 퍼즐

원반이 N개 일때,
1. 1번 기둥에 있는 N개의 원반 중 N-1개를 2번 기둥으로 옮김
2. 1번 기둥에 남아 있는 가장 큰 원반을 3번 기둥으로 옮김
3. 2번 기둥에 있는 N-1개 원반을 다시 3번 기둥으로 옮김

Hanoi(N, start, to, via) = Hanoi(N-1, start, via, to) +move(N, start, to) + Hanoi(N-1, via, to ,start)

📌 결과(재귀가 호출되는 원리)
N = 1
1 번 기둥에 있는 원반을 3 번 기둥으로 옮긴다.
N = 2
1 번 기둥에 있는 원반을 2 번 기둥으로 옮긴다.
1 번 기둥에 있는 원반을 3 번 기둥으로 옮긴다.
2 번 기둥에 있는 원반을 3 번 기둥으로 옮긴다.
N = 3
1 번 기둥에 있는 원반을 3 번 기둥으로 옮긴다.
1 번 기둥에 있는 원반을 2 번 기둥으로 옮긴다.
3 번 기둥에 있는 원반을 2 번 기둥으로 옮긴다.
1 번 기둥에 있는 원반을 3 번 기둥으로 옮긴다.
2 번 기둥에 있는 원반을 1 번 기둥으로 옮긴다.
2 번 기둥에 있는 원반을 3 번 기둥으로 옮긴다.
1 번 기둥에 있는 원반을 3 번 기둥으로 옮긴다.

H(N)= H(N-1)+1+H(N-1) = 2H(N-1)+1

입력크기, 즉 탑의 층수가 높을수록 원반을 더 많이 움직여야 한다.
n층 짜리의 하노이 탑을 옮기려면 2^(n-1)번 옮겨야 함.

알고리즘 계산 복잡도 O(2^n)

Algorithm5.

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

def sum_n(n):
	if n == 0:
		return 0
	return sum_n(n - 1) + n
    
print(sum_n(10))
print(sum_n(100))

Algorithm6.

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

def find_max(a, n): 				# 리스트 a의 앞부분 n개 중 최댓값을 구하는 재귀 함수
	if n == 1:
		return a[0]
	max_n_1 = find_max(a, n - 1) 	# n-1개 중 최댓값을 구함
    
	if max_n_1 > a[n - 1]: 			# n-1개 중 최댓값과 n-1번 위치 값을 비교
		return max_n_1
	else:
		return a[n - 1]
        
v = [17, 92, 18, 33, 58, 7, 33, 42]
print(find_max(v, len(v)))

재귀 호출

어떤 함수 안에서 자기 자신을 호출하는 것으로 종료조건을 달아주지 않으면 재귀에러(RecursionError) 또는 스택오버플로우(StackOverflow)가 발생하게 된다.

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

알고리즘 수행시간 빅오 표기법

n에 관계해서 알고리즘의 수행 시간을 책정한다.
계산 복잡도: 어떤 알고리즘의 계산이 얼마나 복잡한지를 나타낸 정도

빅오 표기법

• 알고리즘에서 필요한 계산 획수를 정확한 숫자로 표현하는 것이 아니라 입력 크기와의 관계로 표현

• 입력 크기 n과 필요한 계산의 횟수가 무관하다면, 즉 입력 크기가 커져도 계산 시간이 더 늘어나지 않는 다면 O(1)로 표기