알고리즘이란?
알고리즘 - 어떤 문제의 해결을 위하여, 입력된 자료를 토대로 하여 원하는 출력을 유도하여 내는 규칙의 집합. 여러 단계의 유한 집합으로 구성되는데, 각 단계는 하나 또는 그 이상의 연산을 필요로 한다. [표준국어대사전]
- 어떤 문제가 있을때, 그것을 해결하기 위한 여러 동작들의 모임
시간 복잡도 판단하기
- 시간 복잡도 - 입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계
- 최댓값 찾기 알고리즘의 시간 복잡도 판단해보기
- 첫 번째 방법
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]))이 해결 방법은 각 숫자마다 모든 다른 숫자와 비교해서 최대값인지 확인한다. 만약 다른 모든 값보다 크다면 반복문을 중단한다. 각 줄이 실행되는 걸 1번의 연산이 된다고 생각하고 계산하면
for num in array: # array 의 길이만큼 아래 연산이 실행
for compare_num in array: # array 의 길이만큼 아래 연산이 실행
if num < compare_num: # 비교 연산 1번 실행
break
else:
return numarray의 길이 X array의 길이 X 비교 연산 1번 만큼의 시간이 필요하다. 여기서 array(입력값)의 길이는 보통 N이라고 표현해 N * N, 즉, N^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]))이 해결 방법은 리스트를 하나씩 돌면서 num 과 max_num 값을 비교하는 함수이다. 시간복잡도를 분석하자면
max_num = array[0] # 연산 1번 실행 for num in array: # array 의 길이만큼 아래 연산이 실행
if num > max_num: # 비교 연산 1번 실행
max_num = num # 대입 연산 1번 실행위에서 연산된 것들을 더해보면
- max_num 대입 연산 1번
- array의 길이 X (비교 연산 1번 + 대입 연산 1번)
만큼의 시간이 필요하다. 첫 번째 방법에서 했던 것처럼 array 의 길이를 N이라고 하면 2N+1 만큼의 시간이 걸렸다고 표현 가능.
- 비교하기
* 매번 코드를 매 실행 단위로 이렇게 몇 번의 연산이 발생하는지 확인하는 건 불가능하다. 따라서 상수는 신경쓰지말고, 입력값에 비례해서 어느 정도로 증가하는지만 파악한다.
ex) 2N+1의 연산량이 나온 첫번째 풀이 방법은 N 만큼의 연산량이 필요하다
N^2 의 연산량이 나온 두번째 풀이 방법은 N^2 만큼의 연산량이 필요하다.
공간 복잡도 판단하기
공간 복잡도 - 입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계
최빈값 찾기 알고리즘의 공간 복잡도 판단해보기
- 첫 번째 방법
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"))- 이 해결방법은 각 알파벳마다 문자열을 돌면서 몇 글자 나왔는지 확인한다. 만약 그 숫자가 저장한 알파벳 빈도 수보다 크다면, 그 값을 저장하고 제일 큰 알파벳으로 저장한다. - 저장하는 데이터의 양이 1개의 공간을 사용한다고 계산
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만큼의 공간이 필요. 그러면 우리는 이제 이 함수는 29만큼의 공간이 사용되었다 라고 표현한다.
- 두 번째 방법
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 = index- 위에서 사용된 공간들을 더해보면, 30만큼의 공간이 필요.
- alphabet_array 의 길이 = 26
- arr_index, max_occurrence, max_alphabet_index, alphabet_occurrence 변수 = 4
** 공간을 더 적게 쓴 첫 번째 방법이 더 효율적인가?
29와 30 모두 상수라 큰 상관이 없다. 대부분의 문제에서는 알고리즘의 성능이 공간에 의해서 결정되지 않기 때문에 공간 복잡도보다는 시간 복잡도를 더 신경 쓰는게 좋다.
- 시간복잡도로 비교하기 - 첫 번째 방법
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번 실행- 위에서 연산된 것들을 더해보면, 26 * (1 + 2*N + 3) = 52N + 104
- alphabet_array 의 길이(26) X 대입 연산 1번
- alphabet_array 의 길이(26) X string의 길이 X (비교 연산 1번 + 대입 연산 1번) - string 의 길이는 보통 N으로 표현
- alphabet_array 의 길이(26) X (비교 연산 1번 + 대입 연산 2번)
- 상수시간의 연산은 무시하므로 N만큼의 시간이 걸렸다고 표현할 수 있다.
- 시간복잡도로 비교하기 - 두 번째 방법
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번 실행- 위에서 연산된 것들을 더해보면, N * (1 + 2) + 2 + 26 * (1 + 3) = 3N + 106
- string의 길이 X (비교 연산 1번 + 대입 연산 2번)
- 대입 연산 2번
- alphabet_array 의 길이 X (비교 연산 1번 + 대입 연산 3번)
- 같은 이유로 상수를 무시하면 N만큼의 시간이 걸렸다 표현 가능
- 비교하기
점근 표기법
점근 표기법 - 점근 표기법(asymptotic notation)은 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법이다. 점근 표기법의 종류에는 빅오(Big-O)표기법, 빅 오메가(Big-Ω) 표기법이 있다.
빅오(Big-O)표기법 - 빅오 표기법은 최악의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지 표기한다.
빅 오메가(Big-Ω) 표기법 - 빅오메가 표기법은 최선의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지에 대해 표기한다.
** 알고리즘에서는 거의 모든 알고리즘을 빅오 표기법으로 분석합니다. 왜냐면 대부분의 입력값이 최선의 경우일 가능성은 굉장히 적을 뿐더러, 우리는 최악의 경우를 대비해야 하기 때문입니다.