python 알고리즘 기본 문제 풀이

1부터 n까지 숫자 합

# range(10)은 0부터 10 미만의 숫자를 포함하는 range 객체를 생성한다는 의미이다.
# 시작 숫자와 끝 숫자를 지정하려면 range(시작, 끝) 형태를 사용하는데, 이때 끝 숫자는 포함되지 않는다.
# range(1, 11)은 숫자 1부터 10까지(1 이상 11 미만)의 숫자를 데이터로 갖는 객체이다. 
def sum(a, b):
    result = 0
    for i in range(a, b+1):
        result = result+i
    return result

# 가우스 1~n 까지 합 공식
def sumFormula(n):
    return n*(n+1)//2

def sumSquared(a, b):
    result = 0
    for i in range(a, b+1):
        result = result+squared(i)
    return result

def squared(n):
    return n*n

print(f'O(n) : {sum(1, 10)}');
print();
print(f'O(1) : {sumFormula(10)}');
print();
print(f'O(n) : {sumSquared(1, 10)}');

 

동일한 결과값을 반환하더라도, 알고리즘에 따라 성능차이가 크게 난다.   
위 예시의 sum() 과 sumFormula() 함수를 살펴보면, sum() 함수의 n 값이 클수록 반복해야하는 횟수는 n차시 만큼 증가한다.   
반면, sumFormula()는 n 값이 크더라도 곱셈, 덧셈, 나눗셈의 사칙연산만 수행하기 때문에 성능에서 큰 차이를 보인다.   
   
어떤 알고리즘에 대해 얼마나 복잡한지를 '계산 복잡도' 라고 하며, 대문자 O 로 표기하며, 빅오 표기법이라고 명명한다.   

- O(n) : 알고리즘을 통한 계산횟수가 입력된 n 값 만큼 증가한다.
- O(1) : 알고리즘을 통한 계산횟수가 입력된 n 값과 상관없이 일정하다.

최대값 / 최소값 구하기

def search(type):
    list = [8, 1, 7, 4, 5]

    idx = 0
    num = list[0];

    if type == 'Max':
        for i in range(0, len(list)):
            if (list[i])>num:
                num = (list[i])
        
        return num
    elif type == 'Min':
        for i in range(0, len(list)):
            if (list[i])<num:
                num = (list[i])
        
        return num
            

print(f'Find Max O(n) : {search("Max")}')
print()
print(f'Find Min O(n) : {search("Min")}')

 

 

동일한 문자열 찾기

def find(array):
    count = 0
    n = len(array)
    result = set()

    for i in range(0, n-1):
        text = array[i]
        for j in range(i+1, n):
            if text == array[j]:
                result.add(array[j])

    return result

array = ['나무', '기차', '기차', '나무', '자동차', '비행기', '나무']
print(f'Find Same Text : {find(array)}')