최빈값 이해할 때까지 코드 공부하기 + a가 오늘 목표
.🚨아래의 코드로 최빈값 찾기
def find_alphabet_occurrence_array(string):
alphabet_occurrence_array = [0] * 26
# 이 부분을 채워보세요!
return alphabet_occurrence_array
print(find_alphabet_occurrence_array("hello my name is sparta"))
.👉 일단은 개념부터!
def find_alphabet_occurrence_array(string):
alphabet_occurrence_array = [0] * 26
for rmf in string:
if not rmf.isalpha():
continue #알파벳이 아니라면 넘어간다
arr_index = ord(rmf) - ord("a") #왜 문자에서 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]arr_index = ord(rmf) - ord('a')
여기서 왜 변수에서 a를 빼줄까 겁나 고민했다. 왤까? 대체 왜? 내 생각인데 그냥 맨 처음 글자에서 a를 빼준 값을 첫 변수로 잡고 싶었던 걸까? 알아보기 쉽게 a라고 설정하려고? 근데 첫 글자가 h 안데??? 대체 뭐지???라고 생각을 했었는데 생각해보면 나는 alphabet_occurrence_array에 0을 선언해줬기 때문에 a를 빼면 아스키코드값에 의해 -97이 나와서 여기에 a가 되나?라고 대충 이해를 했다. 아닐 시엔 어떡하지,,,?
👉 첫 번째 최빈값 찾기 코드
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
if occurrence > max_occurrence:
max_occurrence = occurrence
max_alphabet = alphabet
return max_alphabet
result = find_max_occurred_alphabet(input)
print(result)
이건 앞서서 했던 최댓값 찾기 첫 번째 방법처럼 배열을 일일이 대조해서 값을 세어 보는 코드이다. alphabet_array에 모든 알파벳들을 초기화해놓고, for문으로 일일이 대조해 보는 것이다. 그리고 최댓값 코드처럼 if문을 써주었다.
👉 두 번째 최빈값 찾기 코드
input = "hello my name is sparta"
def find_max_occurred_alphabet(string):
def find_alphabet_occurrence_array(string):
alphabet_occurrence_array = [0] * 26
for rmf in string:
if not rmf.isalpha():
continue
arr_index = ord(rmf) - 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
print(max_alphabet_index)
return chr(max_alphabet_index + ord("a"))
result = find_max_occurred_alphabet(input)
print(result)
와우 여기서 내가 맨 처음 개념에서 헷갈린 부분을 정리해 주셨다.
a를 0번째 index에 넣어주기 위해서 a를 0으로 바꿔주는 작업이었던 것이다.
a -> ord(a)로 변환시켜주면 값이 97이 나오니까 다시 ord(a)로 빼줘서 0으로 만들어 줘서 맨 첫 인덱스를 a값으로 시작하여 차례로 넣는 과정이었던 것!!
반대로 여기서는 앞서 숫자로 만들어줬던 문자를 다시 아스키코드를 이용하여 숫자를 문자로 바꿔주는 것이다.
0 -> a로 만들어줘야 하니까 0+ord(a) = 97 -> chr(97) = a 이렇게!!
근데 난 왜 또 값이 none만 나오지?? 어디서부터 들여 쓰기가 잘못된 거야,,,?
def find_max_occurred_alphabet(string):
def find_alphabet_occurrence_array(string):
alphabet_occurrence_array = [0] * 26
for rmf in string:
if not rmf.isalpha():
continue
arr_index = ord(rmf) - 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
print(max_alphabet_index)
return chr(max_alphabet_index + ord("a"))
result = find_max_occurred_alphabet
print(result("hello my name is sparta"))
시간 복잡도란?
입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계로 입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 시간은 몇 배로 늘어나는지를 보는 것이다. 입력값이 늘어나도 걸리는 시간이 덜 늘어나는 알고리즘이 좋은 알고리즘이다.
ex 1)
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("정답 = 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]))이 소스 코드로 봤을 때 시간 복잡도를 계산하는 법은 for문부터 시작하면 된다.
for num in array: # array 의 길이만큼 아래 연산이 실행
for compare_num in array: # array 의 길이만큼 아래 연산이 실행
if num < compare_num: # 비교 연산 1번 실행
break
else:
return num이렇게 이중 for문이 쓰였고, for문 하나마다 배열 길이만큼 2번이 연산되고, 비교 연산 if문이 1번 실행되고 break 되었으므로 이 만큼의 시간이 필요하다. 여기서 array(입력값)의 길이는 보통 N이라고 표현하고, 위의 시간을 다음과 같이 표현할 수 있다.
우리는 위의 소스코드를 N의 제곱만큼 시간(복잡도)이 걸렸다고 말할 수 있다.
ex 2)
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("정답 = 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]))이 소스코드는 입력받은 배열의 최댓값을 구하는 코드로, 배열 값이 달라지는 소스 코드이다. 이럴 때에는
max_num = array[0] # 연산 1번 실행
for num in array: # array 의 길이만큼 아래 연산이 실행
if num > max_num: # 비교 연산 1번 실행
max_num = num # 대입 연산 1번 실행max_num에서 배열 초기화 1번, for문에서 의 길이만큼 if문 속의 num = max_num비교 연산과, max_num = num이라는 대입 연산이 2번 이루어졌으므로
2N+1 만큼 시간(복잡도)이 걸렸다고 말할 수 있다.
공간 복잡도란?
입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계를 말한다. 입력 값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 공간은 몇 배로 늘어나는지를 보는 것이며, 시간 복잡도와 마찬가지로 입력값이 늘어나도 걸리는 공간이 덜 늘어나는 알고리즘이 좋은 알고리즘이다.
ex 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:
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"))공간 복잡도란 얼마나 공간을 많이 쓰느냐 인데
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개의 공간을 사용한다alphabet_array = 26개
max_occurrence = 1개
max_alphabet = 1개
occurrence = 1개
해서 이렇게 총 29개의 공간을 사용했음을 알 수 있다.
ex 2)
def find_max_occurred_alphabet(string):
alphabet_occurrence_list = [0] * 26
for char in string:
if not char.isalpha():
continue
arr_index = ord(char) - ord('a')
alphabet_occurrence_list[arr_index] += 1
max_occurrence = 0
max_alphabet_index = 0
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"))이 코드에서는
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(26):
alphabet_occurrence = alphabet_occurrence_list[index] # 1개의 공간을 사용한다
if alphabet_occurrence > max_occurrence:
max_occurrence = alphabet_occurrence
max_alphabet_index = indexalphabet_occurrence_list = 26개
arr_index = 1개
max_occurrence = 1개
max_alphabet_index = 1개
alphabet_occurrence = 1개
해서 이렇게 총 29개의 공간을 사용했음을 알 수 있다.
하지만 알고리즘에서는 공간 복잡도의 복잡성보다는 시간 복잡도의 복잡성이 훨씬 중요하기 때문에 효율성을 따지기 위해서는 시간 복잡도를 계산하는 것이 좋다.
다시 시간 계산도를 계산해보자면
ex 1-1)
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번 실행첫 번째 for문 안에 두 번째 for문과 if문이 둘 다 있으므로
이렇게 시간 복잡도를 계산할 수 있다.
ex 2-2)
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번 실행 첫 번째 for문 안에 if문이 있고, 빠져나와서 연산이 2번, 다시 for문 안에 if문이 들어 있으므로(엔터로 단락 나눠놓음)
이렇게 계산할 수 있다.
따라서 첫 번째 코드랑 두 번째 코드 중 시간 복잡도가 낮은 코드는 두 번째 코드이다.
점근 표기법
👉 점근 표기법(asymptotic notation)의 사전적 정의는 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법이다. 즉, 알고리즘의 성능을 수학적으로 표기하는 방법으로 "효율성"을 평가하는 방법이다. 시간 복잡도, 공간 복잡도를 구했던 것들이 전부 점근 표기법에 해당한다.
👉 점근 표기법의 종류
빅오(Big-O) 표기법, 빅 오메가(Big-Ω) 표기법 두 가지가 있다.
빅오 표기법은 최악의 성능이 나올 때 어느 정도의 연산량이 걸릴 것인지를 구하고 표기법으로 표시하면 O(N),
빅오메가 표기법은 최선의 성능이 나올 때 어느 정도의 연산량이 걸릴 것인지를 구하고 표기법으로 표시하면 Ω(1)이다.
Q) 배열에서 특정 요소 찾기
내가 쓴 코드는 잘 모르겠으니까 일단 접어두기
input = [3, 5, 6, 1, 2, 4]
def is_number_exist(number, array):
for num in array:
if num == number:
return True
else:
return False
result = is_number_exist(3, input)
print(result)여기서 시간 복잡도를 계산하면 ...?
for num in array: # array 길이만큼 아래 연산이 실행
if num == number: # 비교 연산 1번 실행
return True # N * 1만큼 실행
else:
return False # N * (1+1)만큼 실행이렇게 결과를 도출해 내는 게 맞는 건가,,,?
선생님이 쓴 코드
input = [3, 5, 6, 1, 2, 4]
def is_number_exist(number, array):
for num in array:
if num == number:
return True
return False
result = is_number_exist(3, input)
print(result)여기서 시간 복잡도를 계산하면
for num in array: # array 길이만큼 아래 연산이 실행
if num == number: # 비교 연산 1번 실행
return True # N * 1만큼 실행지금은 찾고자 하는 숫자 3이 배열의 첫 번째에 있어서 한 번만에 실행이 되지만,
만약 input = [5, 6, 1, 2, 4, 3] 이렇게 바뀐다면 N번만큼 즉, 배열을 한 바퀴 돌아서 6번 만에 실행이 되므로 입력값의 분포에 따라 성능이 달라지게 됨을 알 수 있다.
그래서 이걸 위에 빅오, 빅오 메가로 말했던 것을 아래의 사진처럼 정리할 수 있다.
그런데 시간 복잡도를 이야기할 때 왜 항상 빅오 표기법으로 하는가?
👉 왜냐면 대부분의 입력값이 최선의 경우일 가능성은 굉장히 적을뿐더러, 우리는 최악의 경우를 대비해야 하기 때문이다.
❣️🚨❣️ 이번 이론에서 꼭 기억해야 할 것들
1. 입력값에 비례해서 얼마나 늘어날지 파악해보자.1 ? N ? N^2 ?
2. 공간 복잡도보다는 시간 복잡도를 더 줄이기 위해 고민하자.
3. 최악의 경우에 시간이 얼마나 소요될지(빅오 표기법)에 대해 고민하자.