선형 배열 (Linear Arrays), 재귀 함수(recursive functions)

배열

python의 list 사용
원소들을 순서대로 늘어놓은 것, 어떠한 type에 data라도 배열에 넣을 수 있다.
원소에는 각각의 번호가 붙어 있고 index라 불린다.

L = ['Bob', 'Cat', 'Spam', 'Programmer']

L[1] = 'Cat'
L[2] = 'Spam'

L.append('New') # ['Bob', 'Cat', 'Spam', 'Programmer', 'New']

# 끝에서 하나의 원소의 리스트를 꺼냄, 리스트에서 삭제
L.pop() # 'New'
# L = ['Bob', 'Cat', 'Spam', 'Programmer']
## O(1) 시간 복잡도

리스트 중간에 원소 삽입, 삭제

L = [20, 37, 58, 72, 91]

# index 3의 위치에, 원소 65를 삽입하라
L.insert(3, 65)
# index 위치에 데이터를 삽입하면서 뒤의 있던 데이터들의 인덱스 값은 1씩 증가

# 리스트 L의 index 2위치에 있는 데이터를 삭제
del(L[2])
# index 위치에 있는 데이터를 삭제하고, 그 뒤에 있던 데이터들의 index값은 1씩 감소

## O(n) 시간 복잡도

---

재귀함수 (recursive functions)

하나의 함수에서 자신을 다시 호출하여 작업을 수행하는것

1부터 n까지 모든 자연수의 합 구하기

def sum(n):
	if n <= 1: # 종결조건 설정
    	return n
    else:
		return n + sum(n - 1)

피보나치 수열 구하기

반복적인 방법과 재귀적인 방벙를 통한 피보나치 수열 구하기

# 재귀함수를 사용한 피보나치 수열 값 구하기
def fibo(x):
	if x == 0:
    	return 0
    elif x == 1:
    	return 1
    else:
    	retrun fibo(x-1) + fibo(x-2)
        
# 반복문을 사용한 피보나치 수열 값 구하기
def fibo(x):
	if x == 0:
    	return 0
    elif x == 1:
    	return 1
    else:
    	fibo1 = 0
        fibo2 = 1
        for i in range(2, x+1):
        	fibo = fib01 + fibo2
            fibo1, fibo2 = fib2, fib
        return fib0