스파르타 코딩클럽의 '알고보면 알기쉬운 알고리즘 52기'를 수강하기 시작했다.
오늘이 1주차 강의를 들었다.
이렇게 모여서 오티를 듣고 1주차 방에 모여서 각자 공부를 시작했다.(온라인 모각코 느낌?)
내가 일등이다.. 키킥
사유는.. 내가 모여서 수업 듣는 건 줄 모르고, 먼저 들어버려서..
오늘 수업은 재밌었다.
튜터 분 목소리도 잠 오지 않고, 귀에 쏙쏙 들어온다.
그리고 코딩이론갓기인 나에게도 이해가 될 만큼 쉽게 설명해주신다.
휴식시간에 집에서 따뜻하게 잘 듣고 계시냐고 해서..😂
회사에 있는 나를 함께 슬퍼해주셨다..
이제.. 서론을 떨구고 오늘 공부한 내용을 주저리 해보도록 하겠다.
입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계
입력값이 N배로 늘어났을 때 문제를 해결하는 데 걸리는 시간은 몇 배로 늘어나는지를 보는 함수.
아래 코드는 입력한 array에서 최댓값을 반환하는 코드이다.
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)
입력값 input의 길이를 N이라고 했을 때, 비교 연산이 N * 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)
입력값 input의 길이를 N이라고 했을 때, 대입연산이 한번 비교연산이 N번 또 대입연산이 N번 실행된다.
고로 이 함수의 시간복잡도는 이다.
아래 표를 보면 입력값이 늘어날 수록 확연히 시간차이가 많이 난다는 것을 확인할 수 있다.
이 아닌 상수(1)는 거의 계산에 영향을 주지 않는다.
N의 길이 | ||
---|---|---|
1 | 1 | 3 |
100 | 10000 | 201 |
10000 | 100000000 | 20001 |
입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계
입력값이 N배로 늘어났을 때 문제를 해결하는 데 걸리는 공간은 몇 배로 늘어나는지를 보는 함수.
아래 코드는 입력한 입력한 string에서 가장 많이 포함된 alphabet을 구하는 코드이다.
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
만큼의 공간을 차지한다.
고로 공간 복잡도는 이다.
아래의 코드는 위와 같은 기능을 하는 코드이다.
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'))
하지만 공간 복잡도는 위의 코드가 더 효율적이다.
하지만 시간 복잡도로 본다면,
위의 코드는 아래와 같고,
아래 코드는 아래와 같다.
상수를 빼고 보면 이다.
위 같은 상황에서는 시간 복잡도만 생각하면 된다.