TIL - 22.11.10(파이썬 알고리즘)

배운거

알고리즘-2-최빈값 찾기

문자열에서 어떤 알파벳이 가장 많이 포함되었는지 반환하기

배열에 있는 알파벳의 빈도수를 index로 저장

def find_alphabet_occurrence_array(string):
    alphabet_occurrence_array = [0] * 26

    for char in string:
        if not char.isalpha():
            continue
        arr_index = ord(char) - ord("a")  ##배열의 인덱스 값을 나타내기
        alphabet_occurrence_array[arr_index] += 1

    return alphabet_occurrence_array


print(find_alphabet_occurrence_array("hello my name is sparta"))

: [3, 0, 0, 0, 2, 0, 0, 1, 1, 0, 0, 2, 2, 1, 1, 1, 0, 1, 2, 1, 0, 0, 0, 0, 1, 0]

최빈값 찾기

input = "hello my name is sparta"


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

    for char in string:
        if not char.isalpha():
            continue
        arr_index = ord(char) - ord("a")  ##배열의 인덱스 값
        alphabet_occurrence_array[arr_index] += 1

    max_occurrence = 0
    max_alphabet_index = 0
    for index in range(len(alphabet_occurrence_array)):
        alphabet_occurrence = alphabet_occurrence_array[index]

        if alphabet_occurrence > max_occurrence:
            max_alphabet_index = index
            max_occurrence = alphabet_occurrence

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

    return alphabet_occurrence_array


result = find_max_occurred_alphabet(input)
print(result)

: a

시간복잡도

: 입력값과 문제를 해결하는 데 걸리는 시간의 상관관계
입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 시간은 몇 배로 늘어나는지 보는 것

: array 입력값의 길이를 보통 N이라고 표현한다.
array : 함수에 전달되는 인자의 값 또는 길이가 변하는 것

1-4강의에서 사용한
첫번째 방법은 for문을 두번 돌리므로 array가 두번 나와서
'N^2'만큼의 시간이 걸렸다고 할 수 있다.
두번째 방법은 num과 max_num을 비교하는 함수이므로
'2N+1'만큼의 시간이 걸렸다고 할 수 있다.

N에 붙는 상수는 큰 의미가 없고, 지수에 따라 차이가 크게 생기므로 지수를 먼저 비교하는 것이 우선!

공간복잡도

: 입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계
입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 공간은 몇 배로 늘어나는지 보는 것

'저장하는 데이터의 양이 1개의 공간을 사용한다' 라고 할 수 있다

1-5강의에서 사용한
-. 첫번째 방법은 알파벳마다 문자열을 돌면서 확인

    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개의 공간을 사용합니다

: 총 29개의 공간을 사용

-. 두번째 방법은 각 알파벳의 빈도수를 저장한 후, 빈도수 중 가장 많은 알파벳의 인덱스 값을 반환

    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개의 공간을 사용합니다

: 총 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번 실행

: 26(1+2N+3) = 52N+104
간단하게 N만큼의 시간이 걸린다고 할 수 있다.

-. 두번째 방법 - 시간 복잡도

    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번 실행 

: N (1 + 2) + 2 + 26 (1 + 3) = 3N + 106
이 또한 마찬가지로 N만큼의 시간이 걸린다고 할 수 있다.

비슷하다면, 공간 복잡도 보다 시간 복잡도를 더 신경 써야 한다!

점근 표기법

: 알고리즘의 성능을 수학적으로 표기하여 효율성을 평가할 수 있는 방법.
위에서 해본 '이 함수는 N 정도의 시간과 공간이 걸리는구나' 분석 방법이 점근 표기법의 일종이다.

빅오(Big-O) 표기법, 빅오메가(Big-Ω) 표기법
빅오 표기법 : 최악의 성능이 나올 때 어느 정도의 연산량이 걸리지
빅오메가 표기법 : 최선의 성능이 나올 때 어느 정도의 연산량이 걸릴지

-. 예제를 통해 알아보자!
다음 숫자 배열에서 특정 숫자가 존재한다면 True, 존재하지 않다면 False를 반환하시오.

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


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

    return False


result = is_number_exist(3, input)
print(result)

: True

이 함수의 시간 복잡도는?

    for element in array: # array의 길이만큼 아래 연산이 실행
        if number == element: # 비교 연산 1번 실행
            return True   # 총 N*1 = N 만큼의 시간 복잡도가 걸렸다.

: 이 경우에 '3'이라는 값이 맨 앞에 있어서 N만큼 걸림

만약

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


def is_number_exist(number, array):
    for element in array: # array의 길이만큼 아래 연산이 실행
        if number == element: # 비교 연산 1번 실행
            return True   # 총 N*1 = N 만큼의 시간 복잡도가 걸렸다.

    return False


result = is_number_exist(3, input)
print(result)

이렇게 '3'이라는 값이 배열의 맨 뒤로 오게된다면 입력값의 분포에 따라 성능이 변할 수 있다.

위 경우에
빅오 표기법으로 표시하면 O(N)
빅오메가 표기으로 표시하면 Ω(1)
의 시간 복잡도를 가진 알고리즘이다.

대부분의 입력 값은 최선일 경우가 없기 때문에
알고리즘에서는 거의 모든 알고리즘을 빅오 표기법으로 분석한다.
최악의 경우를 대비해야한다.

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

알고리즘 예제-1

# 배열에 있는 각 수를 '더하기'또는 '곱하기'로 가장 큰 수를 만들어라.
# 단, 사칙연산 순서와 상관없이 앞에서부터 차례대로 진행
input = [0, 3, 5, 6, 1, 2, 4]


def find_max_plus_or_multiply(array):
    # 이 부분을 채워보세요!
    return 1


result = find_max_plus_or_multiply(input)
print(result)

: 방향성 잡기
계산해야 하는 숫자에 1보다 작거나 같으면 더하기,
1보다 크면 곱하기를 사용한다.

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


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


result = find_max_plus_or_multiply(input)
print(result)

: 728

알고리즘 예제-2

# 다음과 같이 영어로 되어 있는 문자열이 있을 때, 
# 이 문자열에서 반복되지 않는 첫번째 문자를 반환하시오. 
# 만약 그런 문자가 없다면 _ 를 반환하시오.
input = "abadabac"

def find_not_repeating_character(string):
    # 이 부분을 채워보세요!
    return "_"


result = find_not_repeating_character(input)
print(result)

: 방향성 잡기
반복되지 않다 -> 몇번 나왔는지 카운트 후 1이라면 출력
앞에서 배운 알파벳 빈도수 찾기 참고

input = "abadabac"


def find_not_repeating_first_character(string):
    alphabet_occurrence_array = [0] * 26

    for char in string:
        if not char.isalpha():
            continue
        arr_index = ord(char) - ord("a")
        alphabet_occurrence_array[arr_index] += 1

    not_repeating_character_array = []
    for index in range(len(alphabet_occurrence_array)):
        alphabet_occurrence = alphabet_occurrence_array[index]

        if alphabet_occurrence == 1:
            not_repeating_character_array.append(chr(index + ord("a")))

    for char in string:
        if char in not_repeating_character_array:
            return char

    return "_"


result = find_not_repeating_first_character
print(result(input))

알고리즘 문제 방향성 잡기

1. 바로 코드를 작성하는 것이 아닌, 문제의 예시를 떠올리며 규칙성 찾기
2. 배웠던 자료구조를 활용 가능한지 생각해보기
3. 문제의 특징들을 하나씩 글로 써보기