1. 최댓값 설정
Q1. 배열 내에서 가장 큰 수를 반환
방법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
else:
return num
result = find_max_num(input)
print(result) => 6
#for in 중첩문
# 첫번째 for 문에 3이 돌아가는 동안 두번째 for 문에서 3,5,6,1,2,4가 돌아감
방법2
input = [3, 5, 6, 1, 2, 4]
#max_num지정변수에 가장 큰 숫자를 기록하도록
def find_max_num(array):
max_num = array[0]
#비교하면서 max_num이 조건을 만족할 때 num이 max_num라고 재정의 해줌
for num in array:
if num > max_num:
max_num = num
return max_num
result = find_max_num(input)
print(result) => 62. 최빈값 찾기
Q1. 어떤 알파벳이 가장 많이 포함되어 있는지 반환
방법1 [알파벳 별 빈도수 저장]
def find_alphabet_occurrence_array(string):
alphabet_occurrence_array = [0] * 26 #초기화된 배열을 만듦 /0이 26개인 배열(리스트)
for char in string: #char에 hello my name is sparta 문자들이 순서대로 담김; print줄에 string에 hello my name is sparta 문장을 넣어서
if not char.isalpha(): #char.isalpha()가 아니라면 알파벳이 아니라면 ;;str.isalpha() 해당 문자열이 알파벳인지 확인 ; 띄여쓰기 때문에 사용
continue # 다음 index로 넘어감
arr_index = ord(char) - ord("a") #배열의 index값이 됨/ char가 순서대로 진행되는 알파벳 순서대로 계산됨 char=[h,e,l,l,o, m,y, n,a,m,e, i,s, s,p,a,r,t,a]
#아스키코드 변환 함수 ord('a') = 97
# 내장 함수 ord() 이용해서 아스키 값 받기
# print(ord('a')) # 97
# print(ord('a') - ord('a')) # 97-97 -> 0 a는 0번째 index이다 라는걸 알려줄 수 있는 변환 코드
# print(ord('b') - ord('a')) # 98-97 -> 1
alphabet_occurrence_array[arr_index] += 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]Q2. 최빈값 찾기
방법1
input = "hello my name is sparta" #문자열을 순서대로 돌면서 몇글자 나오는지 확인하는 방법
def find_max_occurred_alphabet(string):
#각 alphabet의 배열이 필요/ 하나하나 꺼내면서 input과 비교 후
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"]
#나온 문자의 빈도수를 세어주면서 제일 높은 횟수를 저장하는 변수
max_occurrence = 0
#최고로 많이 나왔던 alphabet을 저장하기 위한 변수
max_alphabet = alphabet_array[0]
for alphabet in alphabet_array: #alphabet array에서 alphabet 변수에 하나하나 원소를 담아줌
occurrence = 0 #초기값 0
for char in string:
if char == alphabet:#문자열에 있는 문자와 동일하다면
occurrence += 1 #occurrence에 하나씩 추가해줌
if occurrence > max_occurrence: #만약에 occurrence가 max_occurrence보다 크면
max_occurrence = occurrence #max_occurrence에 occurrence를 넣고
max_alphabet = alphabet #max_alphabet에 alphabet을 넣어줌
return max_alphabet #마지막에 반환하는것, 출력하고자하는 값
result = find_max_occurred_alphabet(input)
print(result)방법2
input = "hello my name is sparta" # 문자열을 순서대로 돌면서 몇글자 나오는지 확인하는 방법
def find_max_occurred_alphabet(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
max_occurrence = 0 # 가장 많이 발생했던 빈도수를 저장
max_alphabet_index = 0 # 가장 많이 나왔던 alphabet의 index를 저장
for index in range(len(alphabet_occurrence_array)): # index를 알아야해서 index값을 하나하나 출력해보는 코드 작성
alphabet_occurrence = alphabet_occurrence_array[index]
# alphabet의 빈도수를 하나씩 꺼내보기; alphabet_occurrence_array에서 index번째의 값은 alphabet별 빈도수 이다
# index가 0이라면 -> alphabet_occurrencesms 3(0번째 index에 있는 alphabet은 a이고 a는 3번 나옴
if alphabet_occurrence > max_occurrence:
max_alphabet_index = index # 빈도수가 가장 많은 알파벳이라고 판단하고 max_alphabet_index에 넣음
max_occurrence = alphabet_occurrence # 가장 많은 빈도수를 max_occurrence에 저장
# 원하는 값은 index 값이 아니고 그 index값에 해당하는 alphabet이기 때문에 숫자를 alphabet으로 전환해줌
# index를 문자로 만드는 방법
print(max_alphabet_index) => 0 # =>이 함수를 실행시키면 0이 나옴 a가 가장 많이 나와서
# 원하는 값은 index 값이 아니고 그 index값에 해당하는 alphabet이기 때문에
# 숫자를 alphabet으로 전환해줌
return chr(max_alphabet_index + ord("a"))
# 아스키코드를 이용한 문자를 index로 만드는 방법, index를 문자로 만드는 방법
# a -> 0
# a -> ord(a) -> 97 - ord(a) = 0
#
# 0 -> a
# 0 -> 0 + ord(a) -> 97 -> chr(97) -> a
result = find_max_occurred_alphabet(input)
print(result) => a3. 시간 복잡도 판단하기
시간 복잡도란?
:입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계, 예를 들어 입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 시간은 몇 배로 늘어나는지를 보는 관계
Q1. 최댓값 찾기 함수가 시간이 얼마나 걸리는지 분석
방법1
for num in array: # array 의 길이만큼 아래 연산이 실행
for compare_num in array: # array 의 길이만큼 아래 연산이 실행
if num < compare_num: # 비교 연산 1번 실행
break
else:
return num- array의 길이 X array의 길이 X 비교 연산 1번: 여기서 array(입력값)의 길이는 보통 N이라고 표현
N x N = ( 만큼의 시간이 걸림)
*시간복잡도는 수식으로 표현해야함
*입력값: 함수에서 크기나 길이가 변경될 수 있는 값
ex) 길이가 변할 수 있는 배열이 입력값
방법2
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번)
1 + 2 x N =2N + 1
2N+1의 연산량이 나온 첫번째 풀이 방법은 N 만큼의 연산량이 필요하다
$$N^2$$의 연산량이 나온 두번째 풀이 방법은 N^2 만큼의 연산량이 필요하다.
만약 상수의 연산량이 필요하다면, 1 만큼의 연산량이 필요하다고 말하면 됨
*시간이 많이 걸릴 수록 비효율적인 것 Q2. 최빈값 찾기 함수가 시간이 얼마나 걸리는지 분석
방법1
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번 실행- alphabet_array 의 길이 X 대입 연산 1번
- alphabet_array 의 길이 X string의 길이 X (비교 연산 1번 + 대입 연산 1번)
- alphabet_array 의 길이 X (비교 연산 1번 + 대입 연산 2번)
26 (1 + 2 N + 3) = 52N + 104 (만큼 시간이 걸림)
방법2
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번 실행
- string의 길이 X (비교 연산 1번 + 대입 연산 2번)
- 대입 연산 2번
- alphabet_array 의 길이 X (비교 연산 1번 + 대입 연산 3번)
N (1 + 2) + 2 + 26 (1 + 3) = 3N + 106
2N+1의 연산량이 나온 첫번째 풀이 방법은 N 만큼의 연산량이 필요하다
N^2의 연산량이 나온 두번째 풀이 방법은 N^2 만큼의 연산량이 필요하다.
만약 상수의 연산량이 필요하다면, 1 만큼의 연산량이 필요하다고 말하면 됨
*시간이 많이 걸릴 수록 비효율적인 것 4. 공간 복잡도
공간 복잡도란?
:입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계, 입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 공간은 몇 배로 늘어나는지를 보는 것
(저장하는 데이터의 양이 1개의 공간을 사용)
Q1. 최빈값 찾기 알고리즘의 공간 복잡도 판단해보기
방법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
26 + 3 = 29
방법2
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, max_occurrence, max_alphabet_index, alphabet_occurrence 변수 = 4
26 + 4 = 30
5. 점근 표기법
점근 표기법이란?
: 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법(함수는 N 정도의 시간과 공간이 걸리겠구나 하면서 분석했던 게 점근 표기법의 일종)
- 빅오(Big-O)표기법:
최악의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지에 대한 표기 - 빅 오메가(Big-Ω)표기법:
- 최선의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지에 대한 표기
input = [3, 5, 6, 1, 2, 4]
def is_number_exist(number, array):
for i in array: # array 의 길이만큼 아래 연산이 실행
if array[i] == number: # 비교 연산 1번 실행
return True
result = is_number_exist(3, input)
print(result)- array 의 길이만큼 아래 연산이 실행 (N) 비교 연산 1번 실행 (1) = N 1 시간 복잡도
모든 경우 다 N 만큼의 시간이 걸리진 않음, 함수가 돌아가는 만큼 N은 늘어갈거기 때문에 첫번째 원소에서 결과값을 반환하게 되는 경우와 마지막 원소에서 결과값을 반환하게 되는 경우 시간 복잡도가 달라짐
| 입력값 | 소요되는 연산량 |
|---|---|
| 좋을 때 | 1 |
| 안 좋을 때 | N |
=> 표의 내용대로 빅오(Big-O), 빅 오메가(Big-Ω) 표기법을 사용한다면 O(N), Ω(1) 의 시간 복잡도를 가진 알고리즘
최악의 경우를 대비하기 위해 거의 모든 알고리즘을 빅오 표기법으로 분석함
https://github.com/jennaaaaaaaaa