스파르타코딩클럽 내일배움캠프4기 -10-

알고리즘 두번째 시간
한번 가봅시다~

시간복잡도

입력값과 문제를 해결하는 시간과 상관관계를 말하는 것이다.
참고로 입력값이 늘어나도 걸리는 시간이 빠른 알고리즘이 좋은 알고리즘이다.
예시를 통해 알아보자!

input = [3, 5, 6, 1, 2, 4]


def find_max_num(array):
    for num in array:          # array 의 길이만큼 아래 연산이 실행
        for compare_num in array:  # array 의 길이만큼 아래 연산이 실행
            if num < compare_num:   # 비교 연산 1번 실행
                break
        else:
            return num


result = find_max_num(input)
print("정답 = 6 / 현재 풀이 값 = ", find_max_num([3, 5, 6, 1, 2, 4]))
print("정답 = 6 / 현재 풀이 값 = ", find_max_num([6, 6, 6]))
print("정답 = 1888 / 현재 풀이 값 = ", find_max_num([6, 9, 2, 7, 1888]))


설명
array의 길이 X array의 길이 X 비교 연산 1번
만큼의 시간이 필요하다. 여기서 array(입력값)의 길이는 보통 N이라고 표현하며
그러면 위의 시간을 다음과 같이 표현할 수 있다.
N * N

즉 $N^2$ 만큼의 시간이 걸렸다!

참고로 입력값은 크기가 변경될 수 있는 값이라고 보면 된다.
위에 예시에는 배열이 입력값이다. 또한 표현할떄는 제곱으로 표현을해야한다.
6이라고해서 6의 제곱인 36으로 표현하는게 아니고 6의제곱이라고 표현해야함.

두번째 방법.


def find_max_num(array):
    max_num = array[0]      # 연산 1번 실행
    for num in array:       # array 의 길이만큼 연산 실행
        if num > max_num:   # 비교 연산 1번 실행
            max_num = num   # 대입 연산 1번 실행
    return max_num

result = find_max_num(input)
print("정답 = 6 / 현재 풀이 값 = ", find_max_num([3, 5, 6, 1, 2, 4]))
print("정답 = 6 / 현재 풀이 값 = ", find_max_num([6, 6, 6]))
print("정답 = 1888 / 현재 풀이 값 = ", find_max_num([6, 9, 2, 7, 1888]))


설명
1. max_num 대입 연산 1번
2. array의 길이 X (비교 연산 1번 + 대입 연산 1번) 

만큼의 시간이 필요하다.
첫 번째 방법에서 했던 것처럼 array 의 길이를 N이라고 하면, 다음과 같이 표현할 수 있다.
1 + 2 * N
그러면 우리는 이제 이 함수는 2N+1 만큼의 시간이 걸렸다.

두 식들을 비교하면

이렇게 차이가 난다.

그러나, 매번 코드를 매 실행 단위로 이렇게 몇 번의 연산이 발생하는지 확인하는 건 불가능하다... 따라서 상수는 신경쓰지말고, 입력값에 비례해서 어느 정도로 증가하는지만 파악하면 됩니다.

즉 숫자인 상수는 무시하고 변수로 쓰는 n제곱이나 이런거 신경쓰라는 소리다.

공간복잡도

자꾸 뭐가 이렇게 복잡하대...?
이번에는 공간복잡도에 대해 알아보자.

공간복잡도란...?
입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계를 말한다.
입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 공간은 몇 배로 늘어나는지를 보는 것.
우리는 공간이 적게 걸리는 알고리즘을 좋아하,니 입력값이 늘어나도 걸리는 공간이 덜 늘어나는 알고리즘이 좋은 알고리즘이다.

def find_max_occurred_alphabet(string):
    alphabet_array = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "x", "y", "z"]  # 26개의 공간을 사용한다.
    max_occurrence = 0    # 1개의 공간을 사용한다.
    max_alphabet = alphabet_array[0]   # 1개의 공간을 사용한다.

    for alphabet in alphabet_array:
        occurrence = 0  # 1개의 공간을 사용한다.
        for char in string:
            if char == alphabet:
                occurrence += 1

        if occurrence > max_occurrence:
            max_alphabet = alphabet
            max_occurrence = occurrence

    return max_alphabet

result = find_max_occurred_alphabet
print("정답 = a 현재 풀이 값 =", result("Hello my name is sparta"))
print("정답 = a 현재 풀이 값 =", result("Sparta coding club"))
print("정답 = s 현재 풀이 값 =", result("best of best sparta"))


설명
1. alphabet_array 의 길이 = 26
2. max_occurrence, max_alphabet, occurrence 변수 = 3
총 29개의 공간을 사용한다.

---


def find_max_occurred_alphabet(string):
    alphabet_occurrence_list = [0] * 26   # 26개의 공간을 사용.

    for char in string:
        if not char.isalpha():
            continue
        arr_index = ord(char) - ord('a')   # 1개의 공간을 사용.
        alphabet_occurrence_list[arr_index] += 1

    max_occurrence = 0   # 1개의 공간을 사용.
    max_alphabet_index = 0   # 1개의 공간을 사용.
    for index in range(len(alphabet_occurrence_list)):
        alphabet_occurrence = alphabet_occurrence_list[index]
        if alphabet_occurrence > max_occurrence:
            max_occurrence = alphabet_occurrence
            max_alphabet_index = index

    return chr(max_alphabet_index + ord('a'))


result = find_max_occurred_alphabet
print("정답 = a 현재 풀이 값 =", result("Hello my name is sparta"))
print("정답 = a 현재 풀이 값 =", result("Sparta coding club"))
print("정답 = s 현재 풀이 값 =", result("best of best sparta"))

설명

1. alphabet_array 의 길이 = 26
2. arr_index, max_occurrence, max_alphabet_index, alphabet_occurrence 변수 = 4
총 30개의 공간을 사용.

여기서 잠깐!
공간을 더 적게 쓴게 효울적인가?
꼭 그렇지만은 않다.
29, 30 모두 상수라 큰 상관은 없다.
그럴때는 시간복잡도로 비굑를 해야한다.
사실 공간복잡도 보다는 시간 복잡도를 더 신경써야 된다.

		 for alphabet in alphabet_array:    # alphabet_array 의 길이(26)만큼 아래 연산이 실행
        occurrence = 0                  # 대입 연산 1번 실행
        for char in string:             # string 의 길이만큼 아래 연산이 실행
            if char == alphabet:        # 비교 연산 1번 실행
                occurrence += 1         # 대입 연산 1번 실행 

        if occurrence > max_occurrence: # 비교 연산 1번 실행
            max_alphabet = alphabet     # 대입 연산 1번 실행
            max_occurrence = number     # 대입 연산 1번 실행
            
            
            
 설명
 1. alphabet_array 의 길이 X 대입 연산 1번
2. alphabet_array 의 길이 X string의 길이 X (비교 연산 1번 + 대입 연산 1번)
3. alphabet_array 의 길이 X (비교 연산 1번 + 대입 연산 2번)

만큼의 시간이 필요합니다. 여기서 string 의 길이는 보통 N이라고 표현. 그러면 위의 시간을 다음과 같이 표현할 수 있다.

26*(1 + 2*N + 3) = 52N + 104
즉
52N + 104 
만큼의 시간이 걸림.


---


    for char in string:        # string 의 길이만큼 아래 연산이 실행
        if not char.isalpha(): # 비교 연산 1번 실행
            continue
        arr_index = ord(char) - ord('a')         # 대입 연산 1번 실행 
        alphabet_occurrence_list[arr_index] += 1 # 대입 연산 1번 실행 

    max_occurrence = 0        # 대입 연산 1번 실행 
    max_alphabet_index = 0    # 대입 연산 1번 실행 
    for index in range(len(alphabet_occurrence_list)):    # alphabet_array 의 길이(26)만큼 아래 연산이 실행
        alphabet_occurrence = alphabet_occurrence_list[index] # 대입 연산 1번 실행 
        if alphabet_occurrence > max_occurrence: # 비교 연산 1번 실행 
            max_occurrence = alphabet_occurrence # 대입 연산 1번 실행 
            max_alphabet_index = index           # 대입 연산 1번 실행 
            
            
            
설명
1. string의 길이 X  (비교 연산 1번 + 대입 연산 2번) 
2. 대입 연산 2번 
3. alphabet_array 의 길이 X (비교 연산 1번 + 대입 연산 3번)
   만큼의 시간이. 여기서 string 의 길이는 보통 N이라고 표현

N * (1 + 2) + 2 + 26 * (1 + 3) = 3N + 106

그러면 
3N+106 만큼의 시간이걸림.

그런데, 이제 다른 상수 시간의 연산은 이제 계산하지 않아도 됨.
마찬가지로 N 만큼의 시간이 필요함.

여튼 결론은 상수인 숫자 다빼고 보자
3N, 103N 이든 별차이없다...
만약 그게 N의 제곱이나 세제곱 등등 되면 그게 훨씬 복잡해지니까...

점근 표기법

알고리즘의 “효율성”을 평가하는 방법이며 점근 표기법(asymptotic notation)은 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법이다.
지금까지 이 함수는 N 정도의 시간과 공간이 걸리겠구나 하면서 분석했던 게 점근 표기법의 일종이라고 말할 수 있다.

점근 표기법의 종류에는
빅오(Big-O)표기법, 빅 오메가(Big-Ω) 표기법이 있다.

빅오 표기법은 최악의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지,
빅오메가 표기법은 최선의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지에 대해 표기.

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

예시 통해서 알아보쨩..

def is_number_exist(number, array):
    for element in array:   # array 의 길이만큼 아래 연산이 실행
        if number == element:  # 비교 연산 1번 실행
            return True
    return False


result = is_number_exist
print("정답 = True 현재 풀이 값 =", result(3,[3,5,6,1,2,4]))
print("정답 = Flase 현재 풀이 값 =", result(7,[6,6,6]))
print("정답 = True 현재 풀이 값 =", result(2,[6,9,2,7,1888]))

쉽게 설명하겠다.
공식으로 따지면 
N*1의 복잡도를 가진다.
만약에 우리가 찾는게 숫자가 앞에 있으면 그건 빨리 끝날것이고
맨 마지막에 있으면 늦게 끝날것이다.
그러면 운에 따라서 알고리즘 성능이 결정된다는 소리다.
그래서 요즘은 최악의 경우를 표기하는 빅오법으로 표현을 하는것이다.

왜냐하면 최선의 경우보다 최악의 경우를 대비해서 프로그램을 짜야되기 때문!

---

알고리즘 기초 정리
3가지만 기억하자.

1. 입력값에 비례해서 얼마나 늘어날지 파악해보자. $1$ ? $N$ ? $N^2$ ?
2. 공간복잡도 보다는 시간 복잡도를 더 줄이기 위해 고민하자.
3. 최악의 경우에 시간이 얼마나 소요될지(빅오 표기법)에 대해 고민하자

---

알고리즘 문제풀어보기

Q. 다음과 같이 0 혹은 양의 정수로만 이루어진 배열이 있을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 '✕' 혹은 '+' 연산자를 넣어 결과적으로 가장 큰 수를 구하는 프로그램을 작성하시오.

단, '+' 보다 '✕' 를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서 순서대로 이루어진다.

[0, 3, 5, 6, 1, 2, 4]

def find_max_plus_or_multiply(array):
    multiply_sum = 0
    for number in array:
        if number <= 1 or multiply_sum <= 1:
            multiply_sum += number
        else:
            multiply_sum *= number
    return multiply_sum


result = find_max_plus_or_multiply
print("정답 = 728 현재 풀이 값 =", result([0,3,5,6,1,2,4]))
print("정답 = 8820 현재 풀이 값 =", result([3,2,1,5,9,7,4]))
print("정답 = 270 현재 풀이 값 =", result([1,1,1,3,3,2,5]))

설명
0이라는 숫자 함정이 있다. 이 숫자를 곱하면 0이 나오니까
더해주는것으로하자...! 0, 1 두 숫자만 더하고 나머지는 다 곱하는것으로
그럼 위에 같은 식이 나온다.