내배캠 TIL 2022.11.10 (웹개발 보충수업, 알고리즘 1주차)
최원장 튜터님 보충수업
대충 - Google Slides (설명 PPT)
웹서비스는 어떻게 작동하는가?
식당에서 우리가 요청을 하면 서버분들이 응답해준다.
-웹서버란?
웹이라는 서비스를 제공해주는 곳 (서버는 컴퓨터)
AWS는 서버용 컴퓨터를 빌리는 것
-어떻게 서버에 요청을 보내나요?
서비스는 브라우저를 통해서 요청한다.
나와 브라우저를 묶어서 클라이언트라고 한다.
요청은 url로 하는 것이다. (get 방식, post 방식)
app.py에서 응답해주는 것 중 하나인 def home: 을 살펴보자
응답은 여러 종류가 있지만 여기에서는 render을 해주었다.
예시) 네이트에 로그인 시도했을 때
아이디와 패스트워드와 같은 내용을 url에 담아서(그릇같은 역할) 서버에 보내준다
응답은 내 아이디와 패스워드를 받아주고 그에 맞는 다음 페이지를 render 해주는 것이 될 것이다.
우리는 코아가 새로운걸 만들기 보다는 다른 사람들이 만들어놓은 것을 보면서 이해하면 된다.
B반 7조꺼 보자
우리는 서버 컴퓨터가 따로 없으니까 로컬 호스트 이용한다.
로컬호스트 localhost 127.0.0.1 은 내컴퓨터
app.py를 돌린다는 것를 인터넷에 연결하고 어떠한 요청이 오길 기다리고 있다는 것
프레임워크는 도와주는 것, 이미 다른 사람이 만들어둔 틀
app.route는 이리로 가세요 한다.
port 5000이란?
서버는 인터넷에 연결되어 있다.
컴퓨터에는 방화벽이 있다
방화벽은 다 열어놓고 들어오는것을 선별해서 막아주기 보다
일단 다 막아놓고 어떤 요청들만 열어주는게 더 간단하다.
열어둘 항구의 이름이 5000이다.
항구의 이름을 구분하기 위해 숫자를 붙여줬을 뿐
열어준 항구로만 들어올 수 있다.
코드 마지막 줄에 보면 우리가 설정해준 것을 볼 수 있다.
def home은 / url로 요청 받는다.
render template이라는 기능은 flask에서 import한 것이다.
react 할 때는 axios 라는 것을 ajax 대신에 쓸거다
method가 안 정해져있으면 get이 디폴트값이다.
ajax는 우리가 직접 치는거 대신 해주는 거?
경로와 메소드가 맞아야 서버에 정확하게 요청할 수 있다.
get 과 post의 차이점
get:파라미터 노출 o
post: 파라미터 노출 x
매개변수로 값을 주고 받는다
post는 주소뒤에 붙는 ?뒤의 내용을 노출 하지 않고
get은 노출하기 때문에 아주 단순한 불러오기에서 쓴다.
비동기 호출이란?
동기는 순차적으로 , 비동기는 한번에..?
비동기는 요청이 오래 걸리는 일이더라도 내가 보고 있는 페이지는 여전히 따로 작동하고 있는거- skeleton ui (작동하는 척하는 빈 페이지)
보통 비동기로 많이 짠다.
용어 정리
render: 제공하다
파라미터: 매개변수 = parameter =값을 담는 그릇
UX: user experience 사용자 경험
동기: 같은 시기. 또는 같은 기간.synchronism
venv virtual environment : 가상 환경, 코딩하면서 필요한 라이브러리 (도구)를 넣어놓는 도구함
log: 일지 (일어났던 모든 일들을 적어준다)
port: 항구
route: 길 - ~로 가세요 한다. 한 곳에서 어딘가로 연결하는 길
import: 들여오다
터미널 명령어
clear: 터미널 깨끗하게 지우기
pwd: print working directory 현재 경로확인
ls: 현재 경로 내용 확인 list directory contents
cd: change directory
파이썬 파일 실행: python3 app.py 파일 실행
우리는 튜터님 스펙임. 우리가 잘되면 튜터님도 잘되는 것
06. 시간 복잡도 판단하기
시간복잡도란?
입력값과 문제를 해결하는데 걸리는 시간의 상관관계
입렵값이 늘어나도 시간이 많이 안 걸리는 알고리즘이 좋은 알고리즘
최댓값 찾기 알고리즘의 시간 복잡도 판단해보기
첫번째 방법
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 입력값을 보통 N이라고 한다.
연산된 것을 계산해보면
N * N * 1 = N²
입력값은 크기가 변경될 수 있는 값이다.
답을 36 이렇게 말하면 되는게 아니라 상관관계를 수식으로 표현하는 것을 시간복잡도라고 한다.
#지수 키보드로 치는 법
ㅊ + 한자
두번째 방법
def find_max_num(array):
max_num = array[0] #대입 연산 1번
for a in array: #입력값 만큼 연산
if a > max_num: #비교 연산 1번
max_num = a #대입 연산 1번
return max_num #return은 연산에 해당 안된다?
# 2N + 11. N과 N²은 N이 커질 수록 더 큰 차이가 난다.
2. N의 지수를 먼저 비교하면 된다.
하지만 모든 코드를 매 실행단계로 몇번의 연산을 하는지 확인하는 것은 불가능
따라서 상수는 무시하고 N에 관련해서만 파악하면 된다
ex)
2N + 1 연산량은 N
5N² +128은 N²
07. 공간 복잡도 판단하기
시간 복잡도랑 거의 유사한데
입력값과 문제해결하는데 걸리는 공간과의 상관관계이다.
입력값 늘어날 때 공간은 얼마나 늘어나는지?
최빈값 찾는 코드
저장하는 데이터의 양이 1개의 공간을 사용한다
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"]
#26개 공간 사용
max_occurrence = 0 # 1개 공간 사용
max_alphabet = alphabet_array[0] #1개 공간 사용
for alphabet in alphabet_array: #반복문 돌리면서 alphabet 새로 만들어 준거 아닌가?
occurrence = 0 # 1개 공간
for char in string:
if char == alphabet: #이미 있던 변수에 다른 값을 저장해주는 것이기 때문에 공간 차지는 않하는 듯
occurrence += 1
if occurrence > max_occurrence:
max_alphabet = alphabet
max_occurrence = occurrence
return max_alphabet1. alphabet array 길이 26
2. max_occurence, max_alphabet, occurence 변수 = 3
29만큼의 공간을 사용
두번째 방법
def find_max_occurred_alphabet(string):
alphabet_occurrence_list = [0] * 26 # 배열의 개수만큼 공간 사용 26
for char in string:
if not char.isalpha():
continue
arr_index = ord(char) - ord('a') #arr_index
# 입력값 만큼 공간 사용하는게 아니라 arr_index라는 상자는 하나이므로 1
alphabet_occurrence_list[arr_index] += 1
max_occurrence = 0 # 공간사용 1
max_alphabet_index = 0 # 공간 사용 1
for index in range(len(alphabet_occurrence_list)):
alphabet_occurrence = alphabet_occurrence_list[index] #공간 사용 1
if alphabet_occurrence > max_occurrence:
max_occurrence = alphabet_occurrence
max_alphabet_index = index
return chr(max_alphabet_index + ord('a'))1. alphabet array 배열 = 26
2. arr_id, max_occurrecne, max_alphabet_index, alphabet_occurence 변수 = 4
총 30만큼 공간 사용함
둘 다 상수랑 차이없는거나 마찬가지
알고리즘 성능에 아무런 영향을 안 미친다
시간복잡도에 신경쓰는게 더 중요하다.
혼자 시간복잡도 이해해보쟈...
첫번재 방법 시간복잡도
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: #배열 연산 26번
occurrence = 0 #대입 연산 1번
for char in string: #배열 연산 입력값 만큼 N번
if char == alphabet: #대입연산 1이 아니고 비교연산 같은지 다른지 비교!
occurrence += 1 #대입 연산 1
if occurrence > max_occurrence: #비교연산 1
max_alphabet = alphabet #대입연산 1
max_occurrence = occurrence # 대입연산 1
return max_alphabet1. alphabet array 길이 X 대입연산 1번
2. alphabet array 길이 X 입력값 길이 X (비교연산 1 + 대입연산 1)
3. alphabet array 길이 (비교연산1 +대입연산 1+ 대입연산 1)
26(1+ 2N + 3) = 52N + 104
어디가 곱하기고 어디가 더하기지? for문안에 들어가서 같이 반복해주면 곱하기 사용
아래의 최대 알파벳 구하는 비교문은 안의 for문에서 occurence를 구해서 나와준 다음에 시작되는 거고,
알파벳 당 빈도수를 비교해주는 것이기 때문에 26만 곱해주면된다.
두번째 방식 시간 복잡도
alphabet_occurrence_list = [0] * 26 #대입 연산 26번?
def find_max_occurred_alphabet(string):
for char in string: #입력값 만큼 연산 N
if not char.isalpha(): #비교 연산 1
continue
arr_index = ord(char) - ord('a') #arr_index #대입 연산 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)): #알파벳 배열 인덱스 수 26번 연산
alphabet_occurrence = alphabet_occurrence_list[index] #대입 연산 1
if alphabet_occurrence > max_occurrence: #비교 연산 1
max_occurrence = alphabet_occurrence #대입 연산 1
max_alphabet_index = index # 대입 연산 1
return chr(max_alphabet_index + ord('a')) #대입 연산 11. alphabet_occurence_list array 길이 (답보니까 이거는 포함이 안 되어 있다. 왜 그렇지? 기본적으로 함수의 시간복잡도를 구하는 것이니까 함수에 포함되지 않는 것은 계산하지 않는다.
2. string 길이 연산 N X (비교1 + 대입 1 + 대입 1)
3. 대입 1+ 대입 1
3. alphabet_occurence_list array 길이 X (대입 1 + 비교1 + 대입 1+ 대입 1+ 대입 1)
26 + (N * 2) + 2+ (26 *5) = 3N + 182
답이랑 좀 다르네 여튼 어떤 식인지는 알겠다.
52N +104 든 3N + 182든 N²에 비하면 아무것도 아니다.
공간복잡도보다는 시간 복잡도를 더 신경써야한다.
08. 점근 표기법
점근표기법이란?
알고리즘 성능을 수학적으로 표기하는 방법
알고리즘의 효율성을 평가하는 방법
시간 복잡도, 공간복잡도를 분석했던게 점근표기법의 일종이다.
Big - O 빅오 표기법 Big- Ω 표기법
(연산량에 대한 표기니까 시간복잡도를 표현할 때 쓸 수 있다)
빅오 표기법: 최악의 성능이 나올 때 어느 정도 연산량이 걸릴 것인지
빅오메가 표기법: 최선의 성능이 나올 때 어느정도 연산량이 걸릴 것인지
ex) Ο(N), Ω(1) 의 시간복잡도를 가진 알고리즘이다
오메가 키보드로 치는 법
ㅎ + 한자
Q. 다음과 같은 숫자로 이루어진 배열이 있을 때, 이 배열 내에 특정 숫자가 존재한다면 True, 존재하지 않다면 False 를 반환하시오.
def is_number_exist(number, array):
for arr in array:
if number == arr:
return True
return False # 반복문 끝까지 돌 때까지 True가 아닐 경우 return false 해준다.
result = is_number_exist
print("정답 = True 현재 풀이 값 =", result(3,[3,5,6,1,2,4]))
print("정답 = Flase 현재 풀이 값 =", result(7,[6,6,6]))
print("정답 = True 현재 풀이 값 =", result(2,[6,9,2,7,1888]))위의 코드는 True가 나오지 않으면 다음 값이 나오도록 반복문을 돌려주고 True가 나오지 않고 반복문이 끝나면 조건문 밖으로 나가서 False를 return 해준다.
아래 것은 내가 쓴 답인데
def is_number_exist(number, array):
for arr in array:
if number == arr:
return True
else:
return False코드 실행 순서 설명해주는 페이지에 가서 보니까
반복문이 돌지를 않고 배열의 첫번째 값만 넣어주고 return 해버려서 틀린 답이 나왔다.
여윽시 코아가 이것도 틀리는데 저 위의 코드는 혼자 우째짤꼬
시간복잡도
def is_number_exist(number, array):
for arr in array: #배열 길이만큼 연산
if number == arr: #비교 연산 1
return True
return False # 반복문 끝까지 돌 때까지 True가 아닐 경우 return false 해준다.시간 복잡도 N *1이다.
그러나 모든 상황에서 N번 연산하는 것이 아니다!
print("정답 = True 현재 풀이 값 =", result(3,[3,5,6,1,2,4]))
비교할 값이 3인데 리스트의 첫번째 값부터 3이 나와서 바로 True로 끝난다 .비교 연산 1번 한다
print("정답 = Flase 현재 풀이 값 =", result(7,[6,6,6]))비교할 값이 7인데 리스트에 해당하는 값이 없어서 3번째까지 반복문 돌려서 비교 연산 3번 한다
print("정답 = True 현재 풀이 값 =", result(2,[6,9,2,7,1888]))비교할 값이 2인데 3번째에 해당하는 값이 있어서 True로 return하고 끝난다. 비교 연산 3번 한다.
즉 운이 좋으면 1번만 연산하고도 끝나지만 운이 좋지 않으면 리스트의 길이 N만큼 다 연산을 해야한다.
운이 안 좋을 때 빅오 표기법 O(N)
운이 좋을 때 빅오메가 표기법 Ω(1)
알고리즘은 성능이 항상 동일한게 아니라 입력값에 따라서 성능이 변화할 수 있다.
그런데 왜! 우리는 최악의 경우인 빅오표기법만 계산해서 썼을까?
알고리즘에서는 거의 빅오 표기법 분석한다.
왜?
최선의 경우는 별로 없고, 최악을 경우도 대비해야하기 때문이다.
오늘 기억해야할 것
1. 입력값에 비례해서 얼마나 늘어날지 파악해보자 1? N? N²?
2. 공간 복잡도보다는 시간 복잡도 줄이기 위해 고민하자
3. 최악의 경우에 시간이 얼마나 소요될지 (빅오 표기법에)대해 고민하자
09. 알고리즘 더 풀어보기 (1)
곱하기 or 더하기
Q.
다음과 같이 0 혹은 양의 정수로만 이루어진 배열이 있을 때,
왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 '✕' 혹은 '+' 연산자를 넣어
결과적으로 가장 큰 수를 구하는 프로그램을 작성하시오.
단, '+' 보다 '✕' 를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서 순서대로 이루어진다.
def find_max_plus_or_multiply(array):
total = 0
for element in array:
if element <= 1 or total <= 1:
total += element
else:
total *= element
return total
result = find_max_plus_or_multiply
print("정답 = 728 현재 풀이 값 =", result([0,3,5,6,1,2,4]))
print("정답 = 8820 현재 풀이 값 =", result([3,2,1,5,9,7,4]))
print("정답 = 270 현재 풀이 값 =", result([1,1,1,3,3,2,5]))약간씩 힌트를 얻어서 풀긴했으나 total이 0,1 인 경우에도 더해줘야한다는 조건문을 빼먹은거 말고는 거의 비슷하게 썼다.
이 함수의 시간 복잡도 구해보자
1. 대입연산 1
2. array 길이 연산 N X ( 비교 연산 2번? +대입 연산 1번) (둘 중 하나만 선택해서 실행하니까)
정답 3N + 1
오잉 이렇게 구할 필요 없이 중요한 N의 지수만 확인하기 위해 반복문만 확인해준다
빅오 표기는 O(N)
10. 알고리즘 더 풀어보기 (2)
반복되지 않는 문자
Q. 다음과 같이 영어로 되어 있는 문자열이 있을 때, 이 문자열에서 반복되지 않는 첫번째 문자를 반환하시오. 만약 그런 문자가 없다면 _ 를 반환하시오.
1. 반복문으로 리스트에 있는 문자열들을 뽑아준다...
2. 그 담에 자기 빼고 다른 배열들과 비교했을 때 같은게 나오면 다음 값으로 넘어가고 계속 다르고 마지막 까지 다르면 결과로 뽑아준다.
자기빼고 다른 배열을 어떻게 비교해? 나눈 그런거 몰루
input = "abadabac"
def find_not_repeating_first_character(string):
alphabet_occurrence_array = [0] * 26
for char in string:
if char.isalpha():
arr_index = ord(char) - ord('a')
alphabet_occurrence_array[arr_index] += 1
only_alphabet_array = []
for index in range(len(alphabet_occurrence_array)):
alphabet_occurence = alphabet_occurrence_array[index]
if alphabet_occurence == 1:
only_alphabet = chr(97 + index)
only_alphabet_array.append(only_alphabet)
for char in string:
if char in only_alphabet_array:
return char
return "_"
result = find_not_repeating_first_character
print("정답 = d 현재 풀이 값 =", result("abadabac"))
print("정답 = c 현재 풀이 값 =", result("aabbcddd"))
print("정답 =_ 현재 풀이 값 =", result("aaaaaaaa"))1.저번에 알파벳 개수만큼 배열의 숫자 증가 시켜주는 코드 써준다.
- 알파벳 갯수 리스트 다 0으로 설정
- 들어온 텍스트를 반복문 돌려서 뽑아주고 ord('a') - ord('문자하나') 써서 index에 해당하는 숫자를 뽑아준다.
-해당 배열에 인덱스를 이용해서 1씩 더해준다
2. 유일한 글자가 들어갈 배열 만드는 코드 쓴다
- 유일한 글자가 들어갈 빈 리스트 만든다
- 알파벳 개수가 들어간 배열을 len()과 range() 이용해서 인덱스를 뽑아준다
- 인덱스를 이용해 알파벳 개수를 가져 온다.
- 알파벳 개수가 1인 것을 찾아서 아스키 코드를 이용해 다시 문자로 바꾸고 리스트에 넣는다.
3. 유일한 알파벳 리스트를 다시 내가 넣은 텍스트랑 비교해서 첫번째 유일한 알파벳을 뽑는다.
들어온 텍스트의 문자들을 다시 한번 뽑아주고 만약 그 문자가 유일한 알파뱃 리스트에 포함되어 있다면
해당 문자를 return 한다. 해당 사항이 없으면 '_'으로 return 한다.
강창민 튜터님 알고리즘 실시간 강의
어려운 점
1. 어떤 식으로 코드를 짜야하는 지 잘 모르겠다.
2. 다 짜고 나서 들여쓰기를 어떻게 해서 포함관계를 어떻게 만들어야하는지 모르겠다.
결론- 다 모르겠다.