22년 11월 10일 알고리즘

알고리즘 강의를 수강했다.

그런데 이 알고리즘 강의가 너무 어려워서 일단 개념만 짚고 넘어갔다.

1. 시간 복잡도

시간 복잡도란 입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계를 말한다.

이렇게 복잡하게 쓰면 잘 모르겠고 쉽게 줄이면 코드가 값을 산출하는데 얼마나 시간이 걸리는지를 판별하는 것이다.

즉, 시간 복잡도가 더 크다 = 연산을 하는데 시간이 더 오래걸린다 이다.

그럼 시간 복잡도를 어떻게 판별하냐?

코드의 각 줄이 실행되는 걸 1번의 연산이 된다고 생각하고 계산하면 된다고 한다.

예를 들면 아래 코드에서, 

def find_max_num(array):
    for num in array:
        for num2 in array:
            if num < num2:
                break
        else:
            return num

array의 길이 X array의 길이 X 비교 연산 1번 이라고 계산을 한다

그럼 N(array) X N(array) X 1 = N^2이 된다.

이 코드는 N^2만큼의 시간 복잡도를 가진다.

보통 N에 상수가 붙어도, 상수는 신경쓰지 않고 N만으로 시간 복잡도를 판별한다고 한다.

2. 공간 복잡도

입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계를 말한다 라는데 그냥 공간을 얼마나 사용하냐를 말하는 것이다.

def find_max_occurred_alphabet(string):
    alphabet_array = [0] * 26

    for char in string:
        if not char.isalpha():
            continue
        array_index = ord(char) - ord('a')
        alphabet_array[array_index] += 1

    max_occ = 0 
    max_index = 0

    for index in range(len(alphabet_array)):
        alphabet_occurrence = alphabet_array[index]
        if alphabet_occurrence > max_occ:
            max_occ = alphabet_occurrence
            max_index = index 


    return chr(max_index + ord('a'))#아스키 코드를 알파벳으로 변환


result = find_max_occurred_alphabet
print("정답 = a 현재 풀이 값 =", result("Hello"))

위의 코드를 예로 들면

alphabet_array = [0] * 26 에서 26의 공간을 사용하고,

array_index = ord(char) - ord('a')에서 하나,

max_occ = 0 에서 하나,

max_index = 0에서 하나,

alphabet_occurrence = alphabet_array에서 하나

를 사용하여 총 30의 공간을 사용한다.

대부분의 문제에서 공간 복잡도보다는 시간 복잡도를 신경 써야 한다고 한다.

3.점근 표기법

알고리즘의 성능을 수학적으로 표기하는 방법이다.

앞서 썼던 시간 복잡도와 공간 복잡도가 점근 표기법이라고 할 수 있다.

점근 표기법의 종류에는 빅오(Big-O)표기법, 빅 오메가(Big-Ω) 표기법이 있다. 빅오 표기법은 최악의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지, 빅오메가 표기법은 최선의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지에 대해 표기한다. 

def is_number_exist(number, array):
    for element in array:
        if number == element:
            return True
    return False


result = is_number_exist

위의 코드를 예로 들자면 입력값이 운이 좋으면 1번 그렇지 않으면 N번 연산을 해야 하므로

빅오 표기법으로 표시하면 O(N), 빅 오메가 표기법으로 표시하면 Ω(1)의 시간 복잡도를 가진 알고리즘이다 라고 말할 수 있다고 한다.

 

앞서 썼던 코드들 중 알파벳 최빈값 찾기가 도저히 이해가 되지않아 늘 하던대로 순서도를 그려봤다.

순서도를 그리며 왜 내가 이 코드를 잘 이해하지 못하는가에 대해서 생각해봤는데,

첫번째는 파이썬 문법을 잘 모른다. 그냥 잘 모른다. 코드를 보면서 코드들이 어떠한 이유에서 들어가는지 잘 모르기 때문에 이해가 오래 걸렸다.

두번째는 코드의 흐름을 파악하지 못했다. 값이 어디서 어디로 가는지 변수 초기화가 어디서 되는지 전혀 이해하지 못하고 있다가 강의를 세네번 돌려보고 코드 흐름을 시각적으로 보여주는 사이트에서 돌려봐서 이해 할 수 있었는데, 사실 아직도 헷갈린다. 순서도를 제대로 그렸는지조차 확신하지 못하겠다.

 

알고리즘을 공부하며 내가 많이 부족하다는 생각이 들었다.