알고리즘이란?
문제 해결을 위하여 여러 동작들, 방법들의 집합이다.
최빈값 찾기 문제 - ASCII 코드를 활용하여 문제를푼다.
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
char에서 아스키 코드 변환 방법
ord('alphabet')을 넣으면 아스키 번호가 나오고 해당 아스키 번호에 97을 빼면 알파벳의 인덱스가 나온다.
ord('a') -97 = 0 (index number)
변환하는 방법은 반대로 하면된다.
chr(alphabet_index + ord('a'))
시간복잡도 판단하기
시간 복잡도란? 입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계
ex) 입력값이 2배로 늘어났을 때 문제를 해결하는데는 몇배로 늘어날지?
for num in array:
for compare_num in array: #array의 길이만큼 아래 연산이 실행
if num < compare_num: #array의 길이만큼 아래 연산이 실행
if num < compare_num: #비교 연산 1번 실행
break
입력값이란? 함수에서 크기가 변경될 수 있는 값이라고 보면 된다.
공간 복잡도 판단하기
공간 복잡도란? 입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계
ex) 입력값이 2배로 늘어났을 때 공간은 몇배로 늘어날지?
어떻게 공간복잡도를 판단할 수 있을까?저장하는 데이터의 양이 1개의 공간을 사용한다!
상수 값들은 큰 상관이 없다. N^2 와 N 과 같이 시간복잡도처럼 차이가 나지 않는다.
<명심해야할 것>
공간 복잡도보다는 시간 복잡도를 더 신경써야한다!!
점근표기법
알고리즘의 성능을 수학적으로 표기하는 방법. (알고리즘의 '효율성'을 평가하는 방법)
점근 표기법의 종류:
빅오(Big-O)표기법, 빅 오메가 표기법이 있다.
빅오 표기법: 최악의 성능이 나올 때 어느정도의 연산량이 걸릴지
빅오메가 표기법: 최선의 성능이 나올때 어느정도 걸릴지
보통 알고리즘은 빅오표기법으로 함. 최선의 경우가 나오는 경우는 많지 않다. (빅오메가)
