알고리즘 문제 풀이(최대값, 최소값, 재귀호출, 최대공약수, 피보나치)

# 1번
# 1부터 n까지 연속 숫자 합 (첫 번째 방법) -> O(n)
def sum_n(n):
    sum = 0
    
    for i in range(1, n+1):
        sum += i
        
    return sum
    
# 1부터 n까지 연속 숫자 합 (두 번째 방법) -> O(1)
def sum_n2(n):
    sum = (n * (n + 1))/2
    
    return sum

 

sum_n(3) # 1

sum_n2(3) # 2

 

# 1-1번
# 1부터 n까지 연속한 숫자의 제곱의 합을 구하는 프로그램(for 문) (첫 번째 방법)-> O(n)
def mul_sum_n(n):
    sum = 0
    
    for i in range(1, n+1):
        sum += i ** 2
        
    return sum

# 1부터 n까지 연속한 숫자의 제곱의 합을 구하는 프로그램 (두 번째 방법)-> O(1)
def mul_sum_n2(n):
    sum = (n * (n + 1) * (2 * n + 1)) / 6
    
    return sum

 

mul_sum_n(4)

mul_sum_n2(4)

---

# 2번
# 최댓값 찾기 -> O(n)
def find_max(list):
    max_value = 0
    
    for i in list:
        if i > max_value:
            max_value = i
    
    return max_value

# 최댓값 위치 번호 찾기 -> O(n)
def find_max_idx(list):
    max_value_idx = 0
    
    for i in range(1, len(list)):
        if list[i] > list[max_value_idx]:
            max_value_idx = i
    
    return max_value_idx

 

find_max([17, 98, 22, 33, 58, 92, 66, 101, 50])

find_max_idx([17, 98, 22, 33, 58, 92, 66, 101, 50])

 

# 2-1번
# 숫자 n개를 입력받아(list) 최솟값을 구하는 프로그램

def l_min_value():
    l = []
    while True:
        value = input('숫자를 입력하세요. q 입력시 종료')
        if value == 'q':
            break
        else:
            l.append(value)
        

    min_value = l[0]
    
    for i in range(1, len(l)):
        if l[i] < min_value:
            min_value = l[i]
    
    return min_value

 

l_min_value()

---

# 3번
# 두 번 이상 나온 이름 찾기 -> O(n^2)
def find_same_name(list):
    result_list = []
    for i in range(0, len(list)-1):
        for j in range(i+1, len(list)):
            if list[i] == list[j]:
                print(list[i])
                result_list.append(list[j])
                
    return result_list

 

find_same_name(["TOM", "JERRY", "TOM", "ASDFG", "JERRY"])

 

# 3-1번
# n명 중 두명을 뽑아 짝을 짓는다고 할 때, 짝을 지을 수 있는 모든 조합을 출력하는 알고리즘을 만들기
def a(list):
    for i in range(0, len(list)):
        for j in range(i+1, len(list)):
            print(list[i], list[j])

 

a(["tom", "jerry", "kim", "lee"])

---

# 4번
# 팩토리얼(factorial) 구하기 -> O(n)
def factorial(n):
    result = 1
    for i in range(1, n+1):
        result *= i 
    return result

 

factorial(5)

 

# 4번
# 팩토리얼(factorial) 구하기 (재귀호출(recursion) 알고리즘) -> O(n)
def fact_re(n):
    if n <= 1:
        return 1
    return n * fact_re(n-1)

 

fact_re(6)

 

# 4-1번
# 1부터 n까지 연속 숫자 합 (재귀호출)
def sum_re(n):
    sum = 0
    
    if n <= 0:
        return sum
    return n + sum_re(n-1)

 

sum_re(10)

 

# 4-2번
# 최댓값 찾기 (재귀호출)
def find_max_re(list, n):
    if n == 1:
        return list[0]
    else:
        return max(list[n-1], find_max_re(list, n-1))

 

find_max_re([1,2,3,5,8,6,11], 7)

---

# 5번 문제
# 최대공약수

def gcd(num1, num2):
    i = min(num1, num2)
    
    while True:
        if num1 % i == 0 and num2 % i == 0:
            return i
        i = i - 1

 

gcd(60, 24)

 

# 5번 문제
# 최대공약수 - 유클리드 방식
def gcd(num1, num2):
    print(num1,num2)
    if num2 == 0:
        return num1
    return gcd(num2, num1 % num2)

 

gcd(60,24)

 

# 5-1번 문제
# 피보나치 수열
def fibo(n):
    if n == 1:
        return 1
    if n == 2:
        return 1
    else:
        return fibo(n-1) + fibo(n-2)

 

fibo(7)