11-07오늘배운 것
최대값구하기, 최빈값구하기
아스키코드 변환방법(ord, chr)
시간복잡도
java 자료형, 삼항연산자
코틀린 고랭과 같은 자바의 단점을 극복한 언어들이 있고
스칼라 코틀린은 JVM에서 돌아갈수 있는 언어들이다
알고리즘부터 듣기시작하게 되었다.
함수 이름을 만들 때 띄어쓰기가 필요한 경우 _(언더바)를 이용하여 띄어쓰기를 대신하는것이좋다
예시) name_one
1-4 알고리즘과 친해지기
input = [3, 5, 6, 1, 2, 4]
함수 하나를 선언후 비교하는 방식
def find_max_num(array):
#주의 for문안에 j =0 선언하게 된다면 j가 계속 0으로 선언되기 때문에
#항상 i가 j보다 크게 되니 for문 밖에서 선언해주어야 한다.
j=0
for i in array :
if i > j:
j = i
return j2개의 for문을 돌리면서 비교 후 전부 대조 후 조건을 충족 시키지 못한다면
함수를 빠져나와 값을 보내주는 방식
def find_max_num(array):
for i in array :
for j in array :
if i < j :
break;
else:
return I
파이참에 PEP규칙은 코드를 좀더 보기 좋게 하기위한 규칙이다
노란줄 알에 마우스를 대고 refrom시키면 재배치해준다.
아스키코드 확인하는 방법(아스키코드 문자를 숫자로변환 ord 반대는 chr)
ord(‘a’) 출력시 ->97, chr(97) 출력시-> a
배열에 순서대로 개수세서 넣는법
input = "hello my name is sparta"
def find_max_occurred_alphabet(string):
alphabet_occurrence_array = [0] * 26
for alphabet in string :
if not alphabet.isalpha():
continue
alphabet_occurrence_array[ord(alphabet)-ord("a")] += 1
return alphabet_occurrence_array
print(find_max_occurred_alphabet(input)
문자의 최빈값 찾는법
#문자를 하나하나 입력하여 문자열 리스트를 만들어주고 그 리스트를
#문자 변수와 최빈값을 넣어줄 변수하나 선언 후
#알파벳리스트의 길이 만큼 for문으로 돌려주면서 입력값인 input의 문자열내의 문자와 값다면
#for문안에서만 사용되도록 선언된 변수 occurrence에 +1을 해주고
#occurrence값이 max_occurrence보다 크다면 max_occurrence에 넣어주고
#max_alphabet은 현재 비교중인 alhabet을 넣어주고 다돌아가면 max_alphabet을 돌려보내줘소
#값을 출력해서 보여주는 방식이다.
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", "x", "y", "z"]
#순서대로 최빈값 변수, 문자변수
max_occurrence = 0
max_alphabet = alphabet_array[0]
#alphabet_array의 리스트 길이만큼 실행하는 반복문
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(input)
print(result)
최빈값 찾기 2
#26개의 숫자 0을 가지고 있는 리스트 하나를 만들고 입력값의 배열길이 만큼 for문을 돌리고
#문자가 아니라면 다음으로 넘어가고 맞다면 배열의 위치에 1을 더해줍니다.
#최대값과 위치를 저장하는 변수를 선언하고 range를 이용하여alphabet_occurrence_array의 길이만큼
#반복문을 돌리면서 alphabet_occurrence_array의 첫 번째 배열값을 처음으로하여 최대값보다
#크다면최대값에 집어 넣고 인덱스에는 현재 알파벳의 아스키 코드 숫자 변환 값을 넣어줍니다
#반복문이 끝났다면 chr를 이용하여 숫자를 다시 문자로 변환하여 돌려준뒤
#print를 이용하여 최빈값 문자를 출력하여 줍니다.
input = "hello my name is sparta"
def find_max_occurred_alphabet(string):
alphabet_occurrence_array = [0] * 26
for alphabet in string :
if not alphabet.isalpha():
continue
alphabet_occurrence_array[ord(alphabet)-ord("a")] += 1
max_occurrence =0
max_alphabet_index = 0
for index in range(len(alphabet_occurrence_array)):
alphabet_occurrence = alphabet_occurrence_array[index]
if alphabet_occurrence > max_occurrence:
max_alphabet_index = index
max_occurrence = alphabet_occurrence
return chr(max_alphabet_index +ord("a"))
result = find_max_occurred_alphabet(input)
print(result)
시간복잡도란?
입력값과 문제를 해결하는데 걸리는 시간과의 상관관계를 말한다.
입력값이 2배로 늘어났을 때 걸리는 시간이 몇배로 늘어나는지를 보는 것이다.
반복문 안에 if문이 2개라면 2N이 되는것이고 하나라면 N 3개라면 3N이 되며
반복문 안에 반복문이 있으면 이 되며 반복문 안에 if문이 각각 3개와 2개가 있다면 6이 되는것이며
반복문 앞에 조건문이 있다면 N+1이 시간복잡도이다. 허나 상수는 신경 쓰지말고 입력값에 비례해서
지수 N값이 얼마나 증가하는지를 신경쓰면된다.
공간 복잡도란
입력값이 늘어나도 공간이 적은 것이 좋은 것이다
최빈값의 공간 복잡도
1개의 저장하는 데이터양이 1개의 공간을 사용한다고 보면된다
첫 번째는 리스트 26개의 공간 변수 4개 해서 30개의 공간을 사용했다.
두 번째는 리스트의 길이 26 변수 3개 29개의 공간을 사용했다.
둘다 상수라서 별로 의미가 없다. 입력값이 커져도 변함이 없어 알고리즘의 성능에 차이를 비교할 수 없다
알고리즘의 성능은 공간보다 시간복잡도가 더 큰 영향을 끼진다
첫 번째는 3N +106이 나와서 N만큼의 시간복잡도가 나온다
두 번째는 52N +104의 시간복잡도가 나오지만 상수를 버리기로 했으니 N만큼의 시간복잡도이 나온다.
공간을 희생하더라고 시간복잡도를 최소한으로 만드는 것이 중요하다.
파이썬 1-8 점근표기법
점근표기법에는 빅오 표기법과 빅오메가 표기법이 있다
빅오는 최악의성능일때
빅오메가는 최선의 성능일때 어느정도의 연산량이 걸리는지에 대하여쓰는것으로
A라는 입력값은 10초이나 b라는 입력값은 300초일때
빅오는 300 빅오메가는 10입니다
입력값이 첫번째에 나왔을때는 빅오메가는 1이라는 연산량되고 가장 마지막에 나오게된다는 가정이면 빅오는(N)이라는 연산량을 가지게 됩니다
하지만 입력값에 최선은 거의 없기때문에 우리는 항상 최악의 연산령이 빅오를 기준으로 연산량을 잡게된다
