최대값 찾기, 최빈값 찾기

최대값 찾기

첫번째 방법

내용 (일일히 비교하는 방법)

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


def find_max_num(array):
    for num in array:              # 첫번째 반복문
        for compare_num in array:  # 두번째 반복문
            if num < compare_num:  # 두개의 반복문을 비교
                break              
        else:
            return num


result = find_max_num(input)
print(result)

 - 모든 경우의 수를 고려하는 방법이어서 비효율적이다. (중복체크)

 

시간복잡도

 - 반복문 : 리스트의 길이(N)만큼 연산이 실행

 - 반복문이 두번 실행 되었으므로 N * N

    * ex) num 반복문의 1 을 compare_num의 1, 2, 3과 비교, num 반복문의 2 를 compare_num의 1, 2, 3과 비교 ...

 - 비교 연산이 한번 실행 되었으므로 N * N에 1을 곱한다.

 - 따라서, 위 방법의 시간복잡도는 N^2이다.

 - Big O 표기법에 따르면 N^2이다.

---

두번째 방법

내용 (배열을 반복하면서 큰 수를 비교하여 변수에 담는 방법)

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


def find_max_num(array):
    max_num = array[0]   # 최대값을 저장할 변수
    for num in array:
        if num > max_num:  # 배열 내의 값이 저장된 최대값보다 크다면
            max_num = num  # 최대값에 저장

    return max_num


result = find_max_num(input)
print(result)

 

시간복잡도

 - 대입연산 1번 실행 되었으므로 1,

 - 반복문 : 리스트의 길이(N)만큼 연산이 실행

 - 반복문 내의 비교연산 1번, 대입연산 1번 실행 되었으므로 N*(1+1)

 - 따라서, 위 방법의 시간복잡도는 2N+1이다.

 - Big O 표기법에 따르면 N이다.

---

비교

 - 첫번째 방법의 시간복잡도는 O(N^2)

 - 두번째 방법의 시간복잡도는 O(N)

 - 따라서, 두번째 방법의 시간복잡도가 빠르다.

---

최빈값 찾기

첫번째 방법

내용 (모든 알파벳 나열 방법)

input = "hello my name is sparta"


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', 'w', 'x', 'y', 'z'] # 모든 알파벳을 나열.

    max_occurrence = 0               # [알파벳마다 최대 빈도수] 담을 변수.
    max_alphabet = alphabet_array[0] # [최빈값] 담을 변수.

    for alphabet in alphabet_array: # 알파벳을 나열한 배열의 반복문
        occurrence = 0              # [빈도수] 담을 변수
        for char in string:         # 입력값의 배열의 반복문
            if char == alphabet:    # 입력값과 나열한 알파벳이 동일하면
                occurrence += 1     # 빈도수에 1을 더한다.

        if occurrence > max_occurrence:  # [빈도수] 변수가 [알파벳마다 최대 빈도수] 변수보다 크면
            max_occurrence = occurrence  # [알파벳마다 최대 빈도수]에 담는다.
            max_alphabet = alphabet      # [최빈값] 변수에 입력값을 담는다.

    return max_alphabet




result = find_max_occurred_alphabet(input)
print(result)

 - 모든 알파벳을 나열하므로 나열해야 할 원소의 갯수가 늘어나면 늘어날수록 비효율적이다.

 

공간복잡도

 - alphabet_array = 26개

 - max_occurrence = 1개

 - max_alphabet = 1개

 - occurrence = 1개

 - 따라서, 위 방법의 공간복잡도는 29이다.

---

두번째 방법

내용 (아스키 코드를 이용하는 방법)

input = "hello my name is sparta"


def find_max_occurred_alphabet(string):
    alphabet_occurrence_array = [0] * 26  # 26개의 인덱스 저장 (0이 26개인 비트맵 자료구조

    for char in string:
        if not char.isalpha():            # char가 알파벳이 아니라면
            continue                      # for문으로 계속
        arr_index = ord(char) - ord('a')  # char의 아스키 코드에서 a의 아스키코드를 차감하여 인덱스화
        alphabet_occurrence_array[arr_index] += 1   # 해당 인덱스의 알파벳 빈도수를 카운팅

    max_occurrence = 0
    max_alphabet_index = 0
    for index in range(len(alphabet_occurrence_array)): # alphabet_occurrence_array의 길이만큼 반복
        alphabet_occurrence = alphabet_occurrence_array[arr_index]

        if alphabet_occurrence > max_occurrence:
            max_alphabet_index = index
            max_occurrence = alphabet_occurrence
    print(max_alphabet_index)
    return chr(max_alphabet_index + ord('a'))    # 인덱스와 a의 아스키코드를 더하여 해당 알파벳의 아스키코드를 구하고 char로 변환


result = find_max_occurred_alphabet(input)
print(result)

 

공간복잡도

 - alphabet_array = 26개

 - arr_index = 1개

 - max_occurrence = 1개

 - max_alphabet_index = 1개

 - alphabet_occurrence = 1개

 - 따라서, 위 방법의 공간복잡도는 30이다.

---

비교

 - 첫번째 방법과 두번째 방법의 공간복잡도는 모두 상수여서 차이가 미미하다.

 - 따라서, 시간복잡도로 비교하고 신경쓰면 된다.

---