Python 기본 알고리즘

Jayce_97·2023년 5월 19일

python 순차탐색 알고리즘 절대값 최대값 팩토리얼 합계

Python 알고리즘

목록 보기

1/3

오늘부터는 절대값, 팩토리얼, 순차탐색등 알고리즘에대해 배워보도록 하겠습니다.

절대값(abs) 구현 및 사용

input

# abs함수 구현
def abs_sign(a):
    if a>=0:
        return a 
    else:
        return -a  # -(-7) => +7
abs_sign(-7)
# abs 함수 사용
print(abs(-7))

output

7
7

abs(절대값)을 구하는 함수를 abs_sign로 만들어 보았습니다.

합계(sum) 구현 및 사용

input

# sum함수 구현
def sum_sq(n):
    s=0
    for i in range(1,n+1): #연산횟수 n회 
        s=s+i
    return s 
sum_sq(100)
#sum 함수 사용
sum(range(1,101))

output

5050
5050

sum 함수가 어떤식으로 구동되는지 직접 구현해 보았습니다.

sum 구현 응용

input

def sum_n(n):
    return n*(n+1)//2 #연산횟수 3회 

sum_n(100)

output

5050

반복 횟수를 줄임으로써 시간 복잡도를 낮출 수 있습니다.

최대값(max)구현

input

#최대값 구하기
def find_max(a):
    n=len(a) #데이터 개수
    max_v=a[0] #첫번째 값을 초기 최대값으로 설정
    for i in range(1,n):
        if a[i]>max_v: #검사횟수 n-1회
            max_v=a[i] #최대값 변경
    return max_v 

#최대값 인덱스 구하기
def find_max_idx(a):
    n=len(a) #데이터 개수
    max_idx=0 #첫번째 값을 초기값으로 설정
    for i in range(1,n):
        if a[i]> a[max_idx]: #검사횟수 n-1회
            max_idx=i 
    return max_idx 

v=[13, 3, 33, 11, 17, 99, 38]
print(find_max(v))
print(find_max_idx(v))

output

99
5

max함수에는 주어진 값 중 최대값과 그 값의 인덱스를 찾아주는 함수가 있기에 함께 구현해 보았습니다. 순차적으로 탐색하기 때문에 n-1회 검사하며, 시간 복잡도가 높습니다.

최대값(max) 사용

input

import numpy as np 
v=[13, 3, 33, 11, 17, 99, 38]  
print(np.max(v)) #최대값
print(np.argmax(v)) #최대값의 인덱스

output

99
5

팩토리얼(factorial) 구현

input

#직접 구현
def fact(n):
    f=1
    for i in range(1,n+1):
        f=f*i 
    return f 
#재귀함수를 통해 구현
def fact_re(n):
    if n<=1:
        return 1 
    return n*fact_re(n-1) #재귀호출 

print(fact(10))
print(fact_re(10))

output

3628800
3628800

팩토리얼이란 !를 이용하여 표현하고 특정 숫자가 주어 졌을 때 n-1번 곱해 주는 것 입니다.

재귀함수는 만드려는 함수 안에 "나(함수)" 자신을 넣어 값이 만족 할때까지 반복해 주는 함수입니다. 백트레킹과 함께 자주 사용됩니다. 만들 때에는 탈출조건, 반복조건 순으로 작성되며 해당 코드에서는 n의 값이 1이 되면서 n-1번에 충족이 되어 값이 출력됨을 알 수 있습니다.