✏️ 알고리즘 1주차 기록하기
이번주에 할 것은...
-
알고리즘 공부가 필요한 이유를 이해하기
-
알고리즘 학습을 위한 기본 코드 구현력을 높이기
-
시간복잡도, 공간복잡도를 알아보기
Q1. 알고리즘이란?
어떤 문제를 해결하기 위한 방법들의 모임, 어떤 방법이 가장 효율적인 것에 대해 고민하는 것이다.
📍 시간복잡도
입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계를 말합니다! 입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 시간은 몇 배로 늘어나는지를 보는 것이죠.
우리는 시간이 적게 걸리는 알고리즘을 좋아하니 입력값이 늘어나도 걸리는 시간이 덜 늘어나는 알고리즘이 좋은 알고리즘이겠죠?
문제 01. 최대값 구하기
각 숫자마다 다른 숫자와 비교해서 최대값인 지 확인하여 반환한다.
두개의 풀이 중 더 효율적인 풀이 방법은?
# 1번 풀이
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
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]))
=> N * N 의 시간만큼 걸림
O(N^2)
#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
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 + 2*N : O(N)
N의 지수를 비교하면 된다!
📍 공간복잡도
입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계를 말합니다! 입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 공간은 몇 배로 늘어나는지를 보는 것이죠.
우리는 공간이 적게 걸리는 알고리즘을 좋아하니 입력값이 늘어나도 걸리는 공간이 덜 늘어나는 알고리즘이 좋은 알고리즘이겠죠?
문제 02. 알파벳 빈도수 세기
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, max_alphabet, occurrence 변수 = 3
총 29의 공간이 사용된다!
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 = index- alphabet_array 의 길이 = 26
- arr_index, m
ax_occurrence, max_alphabet_index, alphabet_occurrence 변수 = 4
총 30의 공간이 사용된다!
Q. 공간을 더 적게 쓴 첫 번째 방법이 더 효율적인가?
29와 30 모두 상수라 큰 상관이 없으므로.. => 시간 복잡도로 비교!
대부분의 문제에서는 알고리즘의 성능이 공간에 의해서 결정되지 않습니다. 따라서 공간 복잡도보다는 시간 복잡도를 더 신경 써야 합니다.
두가지의 시간 복잡도를 비교해본다!
