알고리즘with python_1-4

‘모두의 알고리즘 with 파이썬’  공부중   …. ​

1.
계산 복잡도 O (대문자 O 표기법)
알고리즘의 대략적인 성능을 표시한다

-필요한 계산 횟수가 입력크기 n과 정비례할때 O(n)으로 표기
-n과 무관할 때 O(1)로 표기

연습문제 1-1. 1~n까지 연속한 숫자의 제곱의 합 구하기
import math
def sqr_sum(n):
s=0
for i in range (1,n+1):
s+=i*i
return s
print (sqr_sum(2))
print (sqr_sum(3))
print (sqr_sum(10))

2. 최댓값찾기

Python 개념

list_ ruby의 array와 거의 유사.
a[-1]은 리스트의 끝에서 첫번째값(마지막 값)을 의미.
자주 쓰는 functions:
len(a)
append(x)
insert(i, x)
pop(i)
clear()
x in a

연습문제 2-1. 최소값 알고리즘
def find_min(a):
n= len(a)
min=a[0]
for i in range(1, n):
if a[i]< min:
min = a[i]
return min
v= [17, 92, 18, 33, 45]
print(find_min(v))

3.

집합 기능

s= set() #빈집합만들기
s.add(1) #집합에 자료 추가 !

연습문제 3-1 nC2 조합

“””including itself “””

def two_com(a):
n= len(a)
result= set()
for i in range(0, n-1):
for j in range(i-1, n):
result.add(a[i]+"--"+a[j])
return result


p= ["A", "B", "C"]
print(two_com(p))
# {'B--A', 'A--A', 'A--B', 'B--C', 'B--B', 'A--C'}

“””not to include itself”””

def two_com(a):
n= len(a)
result= set()
for i in range(0, n-1):
for j in range(i-1, n):
if i<j:
result.add(a[i]+"--"+a[j])
return result

p= ["A", "B", "C"]
print(two_com(p))
# {'B--C', 'A--B', 'A--C'}

4.재귀호출(recursion)
-어떤 함수 안에서 자기 자신을 부르는 것.
-종료조건을 반드시 걸어줘야함.

"""1부터n까지의 합 구하기 """

def sum(n):
if n<=1:
return 1
return n+sum(n-1)


print(sum(3))
print(sum(4))
print(sum(5))

“””숫자 n개중에서 최댓값찾기”””

def max_func(a):
n=len(a)
max=a[n-1]
if n<=0:
return 0
if a[n-2]<a[n-1]:
return a[n-1]
list=[3,6,8,12,4]
print(max(list))