1. 최댓값 찾기
- 숫자로 이루어진 배열이 있을 때, 이 배열 내에서 가장 큰 수 반환하기
방법 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 # (2)
else:
return num # (1)
print(num)
result = find_max_num(input)
print(result)
# 결과
3 # (1) num: 3 > compare_num: 3 => {False} return 3
5 # (1) num: 3 > compare_num: 5 => {False} return 5
6 # (2) num: 5 < compare_num: 6 => {True} break방법 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
print(max_num)
return max_num
result = find_max_num(input)
print(result)
# 결과
5 # max_num: 3 > num: 5 => {False} return 5
6 # max_num: 5 > num: 6 => {False} return 6
6 # max_num: 6 > num: 1 => {True} return 62. 최빈값 찾기 (알파벳)
- 문자열을 입력 받았을 때, 어떤 알파벳이 가장 많이 포함되어 있는지 반환하기
Tip 1 - 문자인지 확인 방법. 내장함수 ".isalpha()"사용
print("a".isalpha()) # True
print("1".isalpha()) # False
s = "abcdefg"
print(s[0].isalpha()) # True
Tip 2 - 알바벳별로 빈도수를 리스트에 저장하기
1) 알파벳 길이만큼 '0 배열' 리스트 생성
alphabet_occurrence_array = [0] * 26 # a~z = 26
2) ASCII 코드를 통해 문자를 숫자로 변환 "ord()"
print(ord('a')) # 97
print(ord('a') - ord('a')) # 97 - 97 = 0
print(ord('b') - ord('a')) # 98 - 97 = 1방법 1
def find_alphabet_occurrence_array(string): # string <= hello my name is sparta
alphabet_occurrence_array = [0] * 26
for char in string:
if not char.isalpha():
continue # 알파벳이 아니면 코드를 수행하지 않고 넘어감
arr_index = ord(char) - ord("a") # ASCII 코드를 통해 문자 -> 숫자 변환하여 숫자 뻄
alphabet_occurrence_array[arr_index] += 1 # 문장안에 알파벳이 있을 때마다 숫자 +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]방법 2
input = "hello my name is sparta"
def find_max_occurred_alphabet(string): # 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"]
# a~z 까지의 26개의 배열 생성 (0 ~ 25)
max_occurrence = 0 # 문자열 안의 단어 최대 갯수 지정 초기값 0
max_alphabet = alphabet_array[0] # 초기값 알파벳을 배열 0번째인 'a'로 지정
for alphabet in alphabet_array: # 알파벳 배열 안에서 반복문 시작
occurrence = 0 # 문자열 안의 단어 갯수를 세기 위해 초기 값 0으로 지정
for char in string: # 주머진 문자 에서 반복문 시작. 주어진 문자열 : "hello my name is sparta"
if char == alphabet: # 주어진 문자열의 단어 중 알파벳 배열(a~z)에 있는 단어가 존재할 경우 True
occurrence += 1 # 해당 단어의 갯수 카운트 +1
if occurrence > max_occurrence: # 해당 단어의 갯수가 문자열 안의 최대 갯수보다 많으면
max_occurrence = occurrence # 해당 단어의 카운트한 수 만큼 최대 갯수로 바뀜
max_alphabet = alphabet # 해당 알파벳의 카운터 수 만큼 최대 갯수를 가지고 있는 알파벳으로 바꿈
return max_alphabet # 최대 갯수를 가지고 있는 알파벳을 반환
result = find_max_occurred_alphabet(input)
print(result)
# 결과
a방법 3
input = "hello my name is sparta"
def find_max_occurred_alphabet(string):
alphabet_occurrence_array = [0] * 26 # 0 배열 26개 생성
for char in string: # 입력 문자열 안에서 반복 시작. char 변수에 저장
if not char.isalpha(): # char 변수 안에 '.isalpha()'를 사용하여 문자인지 판별. 만약 문자가 아닐 경우
continue # 아래 내용을 수행하지 않고 그냥 넘어감
arr_index = ord(char) - ord("a") # 'ord()를 사용해 문자를 ASCII코드로 변경 후 arr_index에 저장
alphabet_occurrence_array[arr_index] += 1 # 공백을 제외한 단어 개수 만큼 h부터 시작해서 카운트 후 마지막 a까지 배열 반복 (총 19번)
max_occurrence = 0 # 초기 알파벳 최고 갯수
max_alphabet_index = 0 # 초기 알파벳 최고 갯수의 인덱스
for index in range(len(alphabet_occurrence_array)): # 0 배열의 길이만큼 숫자 반복(0 ~ 25) 총 26개
alphabet_occurrence = alphabet_occurrence_array[index] # 바로 위에서 만든 index의 위치에 맞게 카운트 된 단어의 갯수가 들어감
if alphabet_occurrence > max_occurrence: # 만약 카운트 된 알파벳 갯수가 기존 알파벳 최고 갯수보다 많다면
max_occurrence = alphabet_occurrence # 더 많이 카운트 된 알파벳 갯수로 바꿈
max_alphabet_index = index # 더 많이 카운트 된 알파벳 갯수의 인덱스로 바꿈
return chr(max_alphabet_index + ord("a")) # chr()을 통해 ASCII 코드 값을 "실제 문자"로 변경
result = find_max_occurred_alphabet(input)
print(result)3. 시간 복잡도
- 입력값과 문제를 해결하는데 걸리는 시간과의 상관관계
- 입력값이 2배로 늘어났을 때 문제를 해결하는데 걸리는 시간이 몇 배로 늘어나는지 보는 것
- 입력값이 늘어나도 걸리는 시간이 덜 늘어나는 알고리즘이 좋은 알고리즘
# 최댓값 찾기 알고리즘 - 방법 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
result = find_max_num(input)
# 시간 복잡도 해설
array의 길이 * array의 길이 * 비교 연산 1번 만큼의 시간이 걸림
여기서 array(입력값)의 길이는 보통 "N"이라고 표현함
방법 1의 시간은 N * N * 1 = N^2이라고 표현# 최댓값 찾기 알고리즘 - 방법 2
input = [3, 5, 6, 1, 2, 4]
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)
# 시간 복잡도 해설
1. max_num 대입 연산 1번
2. array의 길이 * (비교 연산 1번 + 대입 연산 1번)
방법 2의 시간은 1 + 2 * N = 2N + 1 만큼의 시간이 걸림- 결론 : 두 번째 방법이 더 효율적이다.
-
비교하기
N의길이 N^2 2N + 1 1 1 3 10 100 21 100 10000 201 1000 1000000 2001 10000 100000000 20001 -
N의 지수를 먼저 비교하면 된다. -
매번 코드를 매 실행 단위로 이렇게 몇 번의 연산이 발생하는지 확인하는 건
불가능 -
상수는 신경쓰지말고, 입력밧에 비례해서 어느 정도로 증가하는지만 파악 -
만약 산수의 연산량이 필요하다면,
1만큼의 연산량이 필요하다고 이야기 할 것
-
4. 공간 복잡도
- 입력값과 문제를 해결하는데 걸리는 공간과의 상관관계
- 입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 공간은 몇배로 늘어나는지 보는 것
- 입력값이 늘어나도 걸리는 공간이 덜 늘어나는 알고리즘이 좋은 것
# 최빈값 찾기 알고리즘 - 방법 1
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"] # 26개의 공간을 사용 (공간)
max_occurrence = 0 # 1개의 공간을 사용 (공간)
max_alphabet = alphabet_array[0] # 1개의 공간을 사용 (공간)
for alphabet in alphabet_array: # alphabet_array의 길이(26)만큼 아래 연산이 실행 (시간)
occurrence = 0 # 1개의 공간을 사용 (공간) // 대입 연산 1번 실행 (시간)
for char in string: # string 의 길이만큼 아래 연산이 실행 (시간)
if char == alphabet: # 비교 연산 1번 실행 (시간)
occurrence += 1 # 대입 연산 1번 실행 (시간)
if occurrence > max_occurrence: # 비교 연산 1번 실행 (시간)
max_alphabet = alphabet # 대입 연산 1번 실행 (시간)
max_occurrence = occurrence # 대입 연산 1번 실행 (시간)
return max_alphabet
result = find_max_occurred_alphabet
# 공간 복잡도 해설
1. alphabet_array 의 길이 = 26
2. max_occurrence, max_alphabet, occurrence 변수 = 3
총 29만큼의 공간 필요. 즉, 29만큼의 공간이 사용됨
# 시간 복잡도 해설
1. alphabet_array 의 길이 * 대입 연산 1번
2. alphabet_array 의 길이 * string의 길이 * (비교 연산 1번 + 대입 연산 1번)
3. alphabet_ array 의 길이 * (비교 연산 1번 + 대입 연산 2번)
만큼의 시간이 필요. 여기서 string의 길이는 보통 "N"이라고 표현
26 * (1 + 2 * N + 3) = 52N + 104
만큼의 시간이 걸림# 최빈값 찾기 알고리즘 - 방법 2
input = "hello my name is sparta"
def find_max_occurred_alphabet(string):
alphabet_occurrence_array = [0] * 26 # 26 개의 공간을 사용 (공간)
for char in string: # string의 길이만큼 아래 연산이 실행 (시간)
if not char.isalpha(): # 비교 연산 1번 실행 (시간)
continue
arr_index = ord(char) - ord("a") # 1개의 공간을 사용 (공간) // 대입 연산 1번 실행 (시간)
alphabet_occurrence_array[arr_index] += 1
max_occurrence = 0 # 1개의 공간을 사용 (공간) // 대입 연산 1번 실행 (시간)
max_alphabet_index = 0 # 1개의 공간을 사용 (공간) // 대입 연산 1번 실행 (시간)
for index in range(len(alphabet_occurrence_array)): # alphabet_array 의 길이(26)만큼 아래 연산이 실행 (시간)
alphabet_occurrence = alphabet_occurrence_array[index] # 1개의 공간을 사용 (공간) // 대입 연산 1번 실행 (시간)
if alphabet_occurrence > max_occurrence: # 비교 연산 1번 실행 (시간)
max_alphabet_index = index # 대입 연산 1번 실행 (시간)
max_occurrence = alphabet_occurrence # 대입 연산 1번 실행 (시간)
return chr(max_alphabet_index + ord("a"))
result = find_max_occurred_alphabet(input)
print(result)
# 공간 복잡도 해설
1. alphabet_array의 길이 = 26
2. arr_index, max_occurrence, max_alphabet_index, alphabet_occurrence 변수 = 4
총 30만큼 공간이 필요. 즉, 30만큼의 공간이 사용됨
# 시간 복잡도 해설
1. string의 길이 * (비교 연산 1번 + 대입 연산 3번)
2. 대입 연산 2번
3. alphabet_array 의 길이 * (비교 연산 1번 + 대입 연산 3번)
만큼의 시간이 필요. 여기서 string의 길이는 보통 "N"이라고 표현
N * (1 + 2) + 2 + 26 * (1 + 3) = 3N + 106
만큼의 시간이 걸림.5. 점근 표기법 (Asymptotic notation)
- 알고리즘 성능을 수학적으로 표기하는 방법. 알고리즘의 "효율성"을 평가
- 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법
- 시간 복잡도와, 공간 복잡도는 점근 표기법의 일종
- 점근 표기법의 종류 : 빅오(Big-O)표기법, 빅 오메가(Big-Ω)표기법
- 빅오 표기법 : 최악의 성능이 나올 때 어느 정도의 연산량이 걸릴 것인지 표기
- 빅 오메가 표기법 : 최선의 성능이 나올 때 어느 정도의 연산량이 걸릴 것인지에 대해 표기
- 표시 방법 : 빅오 표기법 O(N), 빅 오메가 표기법 Ω(1)의 시간 복잡도를 가진 알고리즘이라 표현
- 문제
다음과 같은 숫자로 이루어진 배열이 있을 때, 이 배열 내의 특정 숫자가 존재한다면 True, 존재하지 않다면 False 반환
input = [3, 5, 6, 1, 2, 4]
def is_number_exist(number, array):
for element in array: # array(배열)안의 요소를 element 라고 정의함 // array의 길이만큼 아래 연산이 실행 (시간)
if number == element: # 만약 입력한 숫자가 배열 안에 있는 요소가 존재하면 // 비교 연산 1번 실행 (시간)
return True # True 반환
return False # 없으면 False 반환
result = is_number_exist(3, input)
print(result)
# 결과
True
# 시간 복잡도 해설
N * 1 = N
만큼의 시간이 걸림.# 시간 복잡도 추가 해설
위에서 연산된 것들을 더해보면, 이렇게 총 N * 1의 시간 복잡도를 가진다는 걸 볼 수 있습니다.
그런데 여기서, 모든 경우에 N 만큼의 시간이 걸릴까요?
input = [3, 5, 6, 1, 2, 4] 이라는 입력값에 대해서 3을 찾으면,
첫 번째 원소를 비교하는 순간!! 바로 결괏값을 반환하게 됩니다.
즉, 운이 좋으면 1번의 연산 이후에 답을 찾을 수 있다는 의미입니다.
그러나, input = [4, 5, 6, 1, 2, 3] 이라는 입력값에 대해서 3을 찾으면 어떻게 될까요?
마지막 원소 끝까지 찾다가 겨우 마지막에 3을 찾아 결괏값을 반환하게 됩니다.
즉, 운이 좋지 않으면 input의 길이(N) 만큼 연산 이후에 답을 찾을 수 있습니다.
이처럼, 알고리즘의 성능은 항상 동일한 게 아니라 입력값에 따라서 달라질 수 있습니다.
어떤 값을 가지고 있는지, 어떤 패턴을 이루는 데이터인지에 따라서 뭐가 좋은 알고리즘인지 달라질 수 있다는 의미입니다.- 표
| 입력 값이 | 소요되는 연산량 |
|---|---|
| 좋을 때 | 1 |
| 안 좋을 때 | N |
- 표기 방법
| 빅오 표기법 | 빅 오메가 표기법 |
|---|---|
| O(N) | Ω(1) |
- 알고리즘에서는 거의 모든 알고리즘을
빅오 표기법으로 분석- 이유 : 대부분의 입력값이 최선의 경우일 가능성은 극히 적을 뿐더러, 최악의 경우를 대비해야 함.
- 이유 : 대부분의 입력값이 최선의 경우일 가능성은 극히 적을 뿐더러, 최악의 경우를 대비해야 함.
6. 곱하기 or 더하기
- 0 혹은 양의 정수로만 이루어진 배열이 있을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하여 숫자 사이에
+또는*연산자를 넣어 결과적으로 가장 큰 수를 구하여라
input = [0, 3, 5, 6, 1, 2, 4]
def find_max_plus_or_multiply(array):
multiply_sum = 0 # 초기 합산 값
for number in array: # 배열 안에 있는 요소를 number 안으로 정의함
if number <= 1 or multiply_sum <= 1: # number가 1보다 작거나 합산 값이 1보다 작으면
multiply_sum += number # 넘버를 더하여 합산 값으로 넣는다
else: # number가 1보다 크거나 합산 값이 1보다 크면
multiply_sum *= number # 넘버를 곱하여 합산 값으로 넣는다
return multiply_sum # 합산 값을 반환한다.
result = find_max_plus_or_multiply(input)
print(result)
# 결과
728
# 시간 복잡도
array의 길이만큼 반복 = O(N) 남은 계수는 버림7. 반복되지 않는 문자
- 영어로 되어 있는 문자열이 있을 때, 이 문자열에서 반복되지 않는
첫번째 문자를 반환하시오. 만약 그런 문자가 없다면 _ 를 반환하시오.
input = "abadabac"
def find_not_repeating_first_character(string):
alphabet_occurrence_array = [0] * 26 # 0~25 까지의 0 배열 생성
for char in string: # 입력 문자열을 char요소로 정의하여 반복
if not char.isalpha(): # 만약 char의 요소 중 문자가 아니라면
continue # 함수를 실행하지 않고 그냥 넘어간다
arr_index = ord(char) - ord('a') # char을 ASCII코드로 변환후 'a'의 값을 빼서 arr_index로 정의
alphabet_occurrence_array[arr_index] += 1 # (1) 결과
not_repeating_character_array = [] # 배열 생성
for index in range(len(alphabet_occurrence_array)): # alphabet_occurrence_array 길이만큼 인덱스 생성 0~25
alphabet_occurrence = alphabet_occurrence_array[index] # 인덱스에 맞춰 input의 단어 갯수 넣음 ex) a=4, b=2, ... z=0
if alphabet_occurrence == 1: # input의 단어 갯수 중 1개가 있는 경우
not_repeating_character_array.append(chr(index + ord("a"))) # index + a의 ASCII코드 수 더하여 배열 요소 추가 // (2) 결과
for char in string: # 입력 문자열을 char요소로 정의하여 반복
if char in not_repeating_character_array: # 반복되지 않는 첫번째 문자가 발견될 경우
return char # char로 반환한다
return "_" # 반복 안하는게 없는 경우 '_' 반환
result = find_not_repeating_first_character(input)
print(result)
# 결과
d
# (1) 결과
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[2, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[3, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[3, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[4, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[4, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
# (2) 결과
['c']
['c', 'd']
항상 처음 세웠던 목표 처럼