1-1. [구현] 반복

어디부터 어디까지 몇번 반복인지 체크하자

 

1. 합 구하기

 

# 반복... O(N)

def sum_i(a):
    rst = 0
    for i in range(len(a)):  # 0부터 (N-1)까지... N번 반복
        rst += a[i]

    return rst


# 재귀... O(N)

def sum_r(a):
    if len(a) == 0:
        return 0

    return a[0] + sum_r(a[1:])


print(sum_i([5, 3, 6, 2, 10]))
print(sum_r([5, 3, 6, 2, 10]))

 

2. 최대값 찾기

 

# 반복... O(N)

def max_i(a):
    rst = -int(1e9)
    for i in range(len(a)):
        if a[i] > rst:
            rst = a[i]
            
    return rst


# 재귀... O(N)

def max_r(a):
    if len(a) == 0:
        return -int(1e9)

    sub = max_r(a[1:])
    if a[0] > sub:
        return a[0]
    else:
        return sub


print(max_i([5, 3, 6, 2, 10]))
print(max_r([5, 3, 6, 2, 10]))

 

3. 피보나치

• 0 1 1 2 3 5 8

 

# 반복... O(N)

def fibo_i(n):
    a, b = (0, 1)
    for _ in range(n - 1):
        a, b = b, a + b

    return b


# 반복 (DP)... O(N)

dp = [-1] * 1000
dp[0] = 0
dp[1] = 1


def fibo_i_dp(n):
    for i in range(2, n + 1):
        dp[i] = dp[i - 2] + dp[i - 1]

    return dp[n]


# 재귀... O(2^N)

def fibo_r(n):
    if n <= 1:
        return n

    return fibo_r(n - 2) + fibo_r(n - 1)


# 재귀 (DP,메모이제이션)... O(N)

memo = [-1] * 1000
memo[0] = 0
memo[1] = 1


def fibo_r_dp(n):
    if memo[n] != -1:
        return memo[n]

    memo[n] = fibo_r(n - 2) + fibo_r(n - 1)
    return memo[n]


print(fibo_i(5))
print(fibo_i_dp(5))
print(fibo_r(5))
print(fibo_r_dp(5))