‘모두의 알고리즘 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))