str.isalpha()

• 해당 문자열이 알파벳인지 판단

print("a".isalpha())    # True
print("1".isalpha())    # False

s = "abcdefg"
print(s[0].isalpha())   # True

ord()

• 문자를 ASCII 코드로 변경

# 내장 함수 ord() 이용해서 아스키 값 받기
print(ord('a'))               # 97
print(ord('a') - ord('a'))    # 97-97 -> 0
print(ord('b') - ord('a'))    # 98-97 -> 1

chr()

• ASCII코드를 문자로 변경

chr(97) == 'a'
chr(0 + ord('a')) == 'a'
chr(0 + 97) == 'a'
chr(1 + 97) == 'b'

최빈값 찾기

• 다음 문장에서 가장 많이 사용된 알파벳 반환

0. 각 알파벳 빈도수 찾기

def find_alphabet_occurrence_array(string):
    alphabet_occurrence_array = [0] * 26     # 26개의 초기화된 배열 만들기

    for char in string:					   # 'e'
        if not char.isalpha():  # 알파벳이 아니라면
            continue
        arr_index = ord(char) - ord("a")   # 101 - 97 = 4 
        alphabet_occurrence_array[arr_index] += 1   # [4] += 1

    return alphabet_occurrence_array

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

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

1. 각 알파벳마다 문자열을 돌려서 최빈값 찾기

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"]
    max_occurrence = 0
    max_alphabet = alphabet_array[0]

    for alphabet in alphabet_array:
        occurrence = 0
        for char in string:    		
            if char == alphabet:			# 'a' == "a"
                occurrence += 1

        if occurrence > max_occurrence:
            max_alphabet = alphabet			# 'a'
            max_occurrence = occurrence		# 3

    return max_alphabet    # 'a'


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

2. 알파벳 빈도수를 저장 후 가장 큰 값 찾기

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_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"))

시간 복잡도, 공간 복잡도, 점근 표기법

시간 복잡도

• 입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계를 말함
  입력값이 2배로 늘어났을 때 시간이 몇 배 걸리는지 알아보기위해!

첫번째 방법 - N^2

# 가장 큰 수 찾기
# for문이 다 끝날 때까지 한번도 break가 나오지 않았다면 else    

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번 -> N x N x 1
									  -> N^2 시간이 걸림

두번째 방법 - N

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번) ->  1 + (N x 2)
					    				  ->  시간 복잡도 N
                                  상수일 때 ->  시간 복잡도 1

공간 복잡도

• 입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계를 말함
  입력값이 2배로 늘어났을 때 공간이 몇 배 걸리는지 알아보기위해!

점근 표기법(symptotic notation)

• 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법
• 알고리즘의 성능을 수학적으로 표기하는 방법, 효율성을 평가하는 방법

빅오(Big-O)표기법
빅오 표기법은 최악의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지

빅 오메가(Big-Ω) 표기법
빅오메가 표기법은 최선의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지

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

Reference

https://stay-present.tistory.com/35 - 시간복잡도 log 표현
https://kangworld.tistory.com/74 - 병합 정렬 시간복잡도