finding_target = 14
finding_numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
def is_existing_target_number_binary(target, array):
first_num = array[0]
for last in range(1, len(array)+1):
last_num = last
middle_num = (first_num + last_num) // 2
print(first_num, middle_num, last_num)
find_num = 0
while find_num is target:
if middle_num == target:
find_num = middle_num
print(find_num)
if middle_num > target:
last_num = middle_num
middle_num = (first_num + middle_num) // 2
find_num = middle_num
print(find_num)
if middle_num < target:
first_num = middle_num
middle_num = (last_num + middle_num) // 2
find_num = middle_num
print(find_num)
result = is_existing_target_number_binary(finding_target, finding_numbers)
print(result)
순차 탐색
1에서 16까지 오름차순으로 정렬되어 있는 배열이 있을 때, 14를 찾는 코드입니다!
finding_target = 14
finding_numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
def is_existing_target_number_binary(target, array):
find_count = 0
for num in array:
find_count += 1
if target == num:
print(find_count)
return True
result = is_existing_target_number_binary(finding_target, finding_numbers)
print(result)array 를 따라가면서 target 이 존재한다면 True 를 반환하고, 끝까지 없다면 False 를 반환하는 간단한 코드입니다!
이진 탐색
일정한 규칙으로 정렬되어 있는 데이터일때만 이진 탐색이 가능합니다.
업다운 게임 : 특정 숫자를 맞추는 게임, 정답인 숫자가 더 높다면 UP 낮다면 DOWN 을 부르는 게임
답을 맞춰볼 수 있는 기회를 7번 드리는데 숫자의 범위는 1~100 입니다! 7번 안에 맞춰야 된다면, 여러분은 어떻게 맞추실 건가요?
알고리즘 관점으로 가장 효율적인 방법은 바로 범위의 절반인 50을 시도해보는 것입니다! 대답이 UP 이라면 1~49 은 후보에서 없어지고 대답이 DOWN 이라면 51~100을 후보에서 없어지기 때문입니다. 이 방법을 이진 탐색이라고 합니다.
Q. 1에서 16까지 오름차순으로 정렬되어 있는 배열이 있다. 이 배열 내에 14가 존재한다면 True, 존재하지 않는다면 False 를 반환하시오.
Tip : 숫자 내림 하는 방법 // 연산자를 이용한다. 소수점 이하의 수를 모두 버리고 몫만 나타낼 수 있습니다!
>>> print((4 + 5) / 2)
4.5
>>> print((4 + 5) // 2)
4업다운 게임의 개념을 그대로 구현하면 됩니다. 숫자들의 중간, 8을 시도하는 것
만약 UP 이라면? 9 ~ 16을 시도하고, 만약 DOWN 이라면? 1 ~ 7을 시도하고,
만약 정답이라면? True 를 반환하면 됩니다. 이 구조를 반복하면 됩니다.
- 범위를 세울 때 쓰는 최솟값과 최댓값을 변수로 놓습니다. 현재 시도하는 인덱스 또한 변수로 잡습니다.
- 시도했을 때 target 보다 작다면 더 큰 값들을 뒤져야 하니까 최솟값에 시돗값 + 1 을 대입합니다.
- 시도했을 때 target 보다 크다면 더 작은 값들을 뒤져야 하니까 최댓값에 시돗값 - 1 을 대입하면 됩니다.
- 이를 최솟값 ≤ 최댓값 까지 반복해야 합니다! 왜 < 가 아니라 ≤ 냐면 최솟값 == 최댓값인 시점까지 확인을 해야 하기 때문입니다.
finding_target = 14
finding_numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
def is_existing_target_number_binary(target, array):
min_num = array[0] #배열의 첫번째 수(최소값)
max_num = len(array) - 1 #배열의 마지막 수(최대값)
mid_num = (min_num + max_num) // 2 #배열의 가운데 수(시도값)
find_count = 0 #시간복잡도 체크
while min_num <= max_num: #최솟값 ≤ 최댓값 까지 반복
find_count += 1 #count + 1
if array[mid_num] == target: #중간값이 타겟(14)라면
print(find_count)
return True #True 반환
elif array[mid_num] < target: #중간값이 타겟(14)보다 작다면
min_num = mid_num + 1 #배열의 첫번째 수(최소값)을 중간값+1로 변환
else:
max_num = mid_num - 1 #배열의 마지막 수(최대값)을 중간값-1로 변환
mid_num = (min_num + max_num) // 2 #시도값 재정의
return False
result = is_existing_target_number_binary(finding_target, finding_numbers)
print(result)이진 탐색과 순차 탐색의 시간 복잡도
이전에 한 순차 탐색 코드를 실행했을때 검색횟수가 14회로 나왔습니다. 찾는 숫자가 마지막 숫자인 16이었다면 16번 검색해야 하니 최악의 경우는 O(N) 걸린다고 할 수 있습니다.
이진 탐색의 경우는 몇 번을 시도할까요?
최소 인덱스가 0, 최대 인덱스가 15이니까 둘의 중간값을 가지고 찾아봅시다!
첫 번째 시도 : (0 + 15) / 2 = 7번째 인덱스의 값, 8 < 14 이므로 7 + 1, 8번째부터 15번째 사이를 찾아요!
두 번째 시도 : (8 + 15) / 2 = 11번째 인덱스의 값, 12 < 14 이므로 11 + 1, 12번째부터 15번째 사이를 찾아요!
세 번째 시도 : (12 + 15) / 2 = 13번째 인덱스의 값, 14 == 14 이므로 성공! 배열을 반씩 나눠가면서 찾다보니, 검색횟수가 총 3번이 걸렸습니다! 그러면, 배열의 길이가 N일 때 최악의 경우 시간 복잡도가 어떻게 될까요?
총 숫자가 1~N 까지라고 한다면,
1번 탐색하면 반절이 줄어드니 N/2 개가 남습니다.
2번 탐색하면 반절이 줄어드니 N/4 = N/2^2 개가 남습니다.
3번 탐색하면 반절이 줄어드니 N/8 = N/2^3 개가 남습니다.
k번 탐색하면 반절이 줄어드니 N/2^k 개가 남습니다.
이 때, 이분탐색을 열심히 시도해서 딱 1개만 남았다고 가정을 해보겠습니다. 이걸 수식으로 표현하면, N/2^k = 1 입니다. 즉, k = log_2{N} 횟수를 시도하면 정답을 찾을 수 있습니다!
결론적으로 이분탐색을 위해서는 시간 복잡도가 O(logN) 만큼 걸린다. 라고 말할 수 있습니다.
Q. 여기서 왜 log_2N 이 아니라 logN 인가요?
A. 상수는 무시해도 되기 때문에 표기하기 쉽도록 logN 으로 부르기로 약속했습니다!
연산량이 반으로 나눠진다! 싶으면 O(log{n}) 이겠구나 생각하시면 됩니다.
재귀 함수
재귀(Recursion)은 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 뜻한다
재귀 함수 : 바로 자기 자신을 호출하는 함수
재귀 함수의 목적 : 문제의 범위를 점점 좁혀가는 것
Q. 60에서 0까지 숫자를 출력하시오.
def count_down(number):
print(number) # number를 출력하고
count_down(number - 1) # count_down 함수를 number - 1 인자를 주고 다시 호출한다!
count_down(60)
재귀함수는 반드시 빠져나가는 지점을 명확하게 정해줘야 합니다.
그렇지 않으면 무한 루프에 빠져서 에러가 날 것입니다!
def count_down(number):
if number < 0: # 만약 숫자가 0보다 작다면, 빠져나가자!
return
print(number) # number를 출력하고
count_down(number - 1) # count_down 함수를 number - 1 인자를 주고 다시 호출한다!
count_down(60)다음과 같이 탈출 조건을 만들어줌으로써 재귀 함수의 반복을 멈출 수 있었습니다!
팩토리얼
팩토리얼 : 1부터 어떤 양의 정수 n까지의 정수를 모두 곱한 것
예를 들면 아래와 같습니다
3! 은 3 * 2 * 1 = 6,
4! 는 4 * 3 * 2 * 1 = 4 * 3! = 24
즉, Factorial(n) = n * Factorial(n - 1) Factorial(n - 1) = (n - 1) * Factorial(n - 2) .... Factorial(1) = 1 의 구조입니다!
def factorial(n):
if n == 1:
return 1
return n * factorial(n - 1)
print(factorial(5))
회문 검사
회문은 똑바로 읽으나 거꾸로 읽으나 똑같은 단어나 문장을 의미합니다. (소주만병만주소)
소주만병만주소가 회문인지 알기 위해서는, 아래와 같은 검사들이 필요합니다.
↓ ↓
소주만병만주소 첫 번째 글자와 맨 뒤에서 첫번째 글자가 같아야 합니다.
↓ ↓
소주만병만주소 두 번째 글자와 맨 뒤에서 두번째 글자가 같아야 합니다.
↓ ↓
소주만병만주소 세 번째 글자와 맨 뒤에서 세번째 글자가 같아야 합니다.
↓
소주만병만주소 마지막 남은 가운데 글자는 뭐가 오든 상관 없습니다!
이 과정을 반복문으로 아래와 같이 쉽게 구현할 수 있습니다.Q. 다음과 같이 문자열이 입력되었을 때, 회문이라면 True 아니라면 False 를 반환하시오.
"abcba" # Trueinput = "abcba"
def is_palindrome(string):
first = string[0]
last = string[len(string) - 1]
for i in range(0, len(string)):
if first == last:
first = string[i]
last = string[len(string) - 1 - i]
print(first, last)
if first != last:
return False
else:
return True
input = "abcba"
def is_palindrome(string):
n = len(string)
for i in range(n):
if string[i] != string[n - i - 1]:
return False
return True
print(is_palindrome(input))
회문 검사 - 재귀 함수
Factorial 에서는 F(n) = n * F(n - 1) 로 줄여갔는데, 이번 is_palindrome 함수에서는 어떻게 줄일 수 있을까요?
맨 앞과 맨 뒤를 비교했다면 그 중간 값들만 비교하면 됩니다.
↓ ↓
소주만병만주소 즉, 맨 앞 문자와 맨 뒤를 비교 했다면 소주만병만주소 이제 "주만병만주" 만 확인하면 됩니다!
is_palindrome(문자열) → is_palindrome(문자열[1, -1]) 로 문제가 축소되는 것입니다.
input = "abcba"
def is_palindrome(string):
if len(string) <= 1:
return True
if string[0] != string[-1]:
return False
return is_palindrome(string[1:-1])
print(is_palindrome(input))문자열의 길이가 1보다 작거나 같을 때, (이 때는 무조건 회문이니까 참이겠죠?)
맨 첫번째 문자와 맨 뒤의 문자가 다를 때! (이 때는 회문이 아니므로 거짓입니다!)
탈출시키도록 하면 됩니다!
HTTP, HTTPS
오늘의 목표
- TCP/IP의 간단한 개요, HTTP/HTTPS 에 대한 기본적인 개념 잡기
- Over the basic concep, 활용될 수 있는 내용까지 학습하기
- 실제 어떻게 활용되고 있는지 이해하기
- 기술 면접 대비
학습 체크 리스트
- HTTP에 대해 설명할 수 있는가?
- HTTP의 통신 흐름을 설명할 수 있는가?
- HTTPS에 대해 설명할 수 있는가?
IP 주소(Internet Protocol Address)
IP(Internet Protocol) 주소란 인터넷에 연결되어 있는 모든 장치들(컴퓨터, 서버 장비, 스마트폰 등)을 식별할 수 있도록 각각의 장비에게 부여되는 고유 주소이다.
도메인 네임 시스템(DNS, Domain Name System)
도메인 네임은 IP 주소를 사람들이 이해하기 쉽게 문자료 표현한 것을 의미한다.
하지만, 컴퓨터는 IP주소로 서로의 위치를 확인하고 통신하고, 도메인 네임은 식별할 수 없기 때문에, IP 주소에 도메인 네임을 할당하고 이를 관리하는 시스템을 DNS라고 한다.
포트(port)
직역하면 '항구'라는 뜻으로, 컴퓨터 관련 분야에서의 의미로는 운영 체제 통신에서의 종단점을 뜻한다.
IP Address를 통해 목적지 호스트까지 도달한 후에는 어떤 프로세스(Process)에서 데이터를 받을 것인지 를 알아야 하는데 이 때 쓰이는 것이 포트번호(Port Number)다.
- 간단하게 살펴보는 TCP/IP
- IP 정의
- 패킷들을 가장 효율적인 방법으로 최종 목적지로 전송하기 위해 필요한 프로토콜
- 패킷 전달 여부를 보장하지 않고, 순서 역시 보장하지 않는다.
- TCP
- 정의
- 패킷을 안전하게 전달해주는 전송 프로토콜
- IP위에서 동작하고 데이터의 전달을 보장하고 순서도 보장한다.
- 흐름제어
- 송신측과 수신측의 데이터 처리 속도 차이를 해결하기 위한 기법
- 혼잡제어
- 송신측의 데이터 전달과 네트워크의 데이터 처리 속도 차이를 해결하기 위한 기법
- TCP handshake
- 3-way handshake
- 두 종단 간 정확한 데이터 전송을 보장하기 위해 연결을 설정하는 과정
- 4-way handshake
- 두 종단 간 데이터 전송을 끝낸 후 연결 설정을 해제하는 과정
- 3-way handshake
- 정의
- TCP/IP
- IP + TCP = 인터넷 프로토콜 + 전송 제어 프로토콜 이다.
- TCP를 기반으로 한(신뢰성 통신을 하는) HTTP,FTP,SMTP 등 수 많은 프로토콜들이 IP 위에서 동작하기에 묶어서 TCP/IP라고 한다.
- 결국에는 효율적으로 빠르게(IP) 보내면서 안전하게(TCP) 전달해주려는 목적
- IP 정의
HTTP(HyperText Transfer Protocol)란?
클라이언트와 서버 간의 자원을 교환하기 위한 TCP/IP 기반 통신 프로토콜(규약,약속)
- 특징
- 단방향성 : 서버가 먼저 응답을 보낼 수 없고 클라이언트가 요청을 보내야만 응답할 수 있다.
- 비연결성(connectionless) : 클라이언트의 요청으로 서버와 연결된 후, 요청에 대한 응답의 데이터를 전송하면 연결을 종료한다.
- 따라서, 실시간 통신을 할 수 없다.
- 문제점
- HTTP는 평문 통신이기 때문에 도청이 가능하다.
- 통신 상대가 검증된 상대인지 확인하지 않기 때문에 위장이 가능하다.
- 완전성을 증명할 수 없기 때문에 변조가 가능하다.
- 이러한 문제점을 해결하기 위해 HTTPS가 등장한다.
- HTTP 메소드(Method)와 상태코드(Status code)
- HTTP 메소드
- 정의
- HTTP 메소드는 클라이언트가 웹 서버에게 요청의 목적이나 종류를 알리는 수단 이다.
- 주요 메소드 5가지
- GET : 보통 리소스를 조회할 때 사용하며, 서버에 전달하고 싶은 데이터는 query를 통해서 전달한다. 메시지 바디를 사용해서 데이터를 전달할 수는 있지만, 지원하지 않는 곳이 많아서 권장하지 않는다.
- POST : 주로 리소스를 새롭게 생성할 때 사용하며, 서버에 전달하고 싶은 데이터는 메시지 바디를 통해 전달한다.
- PUT : 리소스가 있으면 대체하고 리소스가 없으면 생성한다. 즉, 데이터를 덮어쓴다.
- PATCH : PUT과 마찬가지로 리소스를 수정할 때 사용하지만, PATCH는 리소스를 일부분만 변경할 때 사용한다.
- DELETE : 리소스를 제거할때 사용한다.
- 메소드 속성
- 안전(Safe Methods) : 계속 호출해도 리소스를 변경하지 않는 특성
- 멱등(Idempotent Methods) : 동일한 요청을 여러 번 보내도 한 번 보내는 것과 똑같은 결과를 갖는 것 Get, PUT, DELETE는 멱등하다고 볼 수 있지만, POST나 PATCH는 멱등하다고 볼 수 없다.
- 캐시가능(Cacheable Methods) : 응답 결과를 서버에 캐시 해서 사용해도 되는 메소드 GET, HEAD, POST, PATCH가 캐시가 가능하지만 구현이 어려워 실제로는 GET과 HEAD만 주로 캐싱이 쓰인다고 한다.
- 정의
- HTTP 메소드
- HTTP 상태코드
- 정의
- 클라이언트가 보낸 요청의 처리 상태를 응답에서 알려주기 위한 정보
- 종류
- 1xx (Informational): 요청이 수신되어 처리중
- 2xx (Successful): 요청 정상 처리
- 200 OK : 요청 성공
- 201 Created : 요청 성공해서 새로운 리소스가 생성됨
- 202 Accepted : 요청이 접수되었으나 처리가 완료되지 않았음
- 204 No Content : 서버가 요청을 성공적으로 수행했지만, 응답 페이로드 본문에 보낼 데이터가 없음
- 3xx (Redirection): 요청을 완료하려면 추가 행동이 필요 (보통 리다이렉션처리)
- 301 Moved Permanently : 리다이렉트시 요청 메서드가 GET으로 변하고, 본문이 제거될 수 있음
- 302 Found : 리다이렉트시 요청 메서드가 GET으로 변하고, 본문이 제거될 수 있음
- 303 See Other : 리다이렉트시 요청 메서드가 GET으로 변경
- 304 Not Modified : 캐시를 목적으로 사용
- 307 Temporary Redirect : 리다이렉트시 요청 메서드와 본문 유지(요청 메서드를 변경하면 안된다.)
- 308 Permanent Redirect : 리다이렉트시 요청 메서드와 본문 유지(처음 POST를 보내면 리다이렉트도 POST 유지)
- 4xx (Client Error): 클라이언트 오류, 잘못된 문법등으로 서버가 요청을 수행할 수 없음
- 400 Bad Request : 클라이언트가 잘못된 요청을 해서 서버가 요청을 처리할 수 없음
- 401 Unauthorized : 클라이언트가 해당 리소스에 대한 인증이 필요함
- 403 Forbidden : 서버가 요청을 이해했지만 승인을 거부함
- 404 Not Found : 요청 리소스를 찾을 수 없음
- 5xx (Server Error): 서버 오류, 서버가 정상 요청을 처리하지 못함
- 정의
- HTTP 통신흐름
- 웹 브라우저에 www.naver.com 입력.
- 사용자가 입력한 URL 주소 중 도메인 네임 부분을 DNS 서버에 검색하고, DNS서버에서 해당 도메인 네임에 해당하는 IP주소를 찾아온다.
- HTTP 프로토콜을 사용하여 페이지 URL정보와 찾아온 IP주소를 포함하는 HTTP 요청 메세지를 생성하고, 생성된 HTTP 요청 메세지는 TCP 프로토콜을 사용하여 인터넷 망을 통해 해당 IP주소의 컴퓨터로 전송된다.
- HTTP 요청 메세지를 받은 컴퓨터(서버)는 웹 페이지 URL 정보 중 PATH와 HTTP Method에 맞는 액션을 취한다. (여기서는 naver 페이지를 띄우기 위해 필요한 html 등의 리소스를 찾을 것이다.)
- 생성된 응답 데이터는 또 다시 HTTP 프로토콜을 사용하여 HTTP 응답 메세지로 만들어지고 TCP 프로토콜을 사용하여 인터넷 망을 통해 요청했던 컴퓨터(클라이언트)로 전송된다.
- 도착한 HTTP 응답 메세지는 웹 브라우저에 의해 브라우저 렌더링 과정을 거쳐 화면에 출력되어 사용자가 볼 수 있게 된다.
- 브라우저 렌더링 과정
1~4 HTML 파일과 CSS 파일을 파싱해서 DOM Tree*, CSSOM Tree*를 만든다. (Parsing)
5. 두 Tree를 결합하여 Rendering Tree*를 만든다. (Style)
6. Rendering Tree에서 각 노드의 위치와 크기를 계산한다. (Layout)
7. 계산된 값을 이용해 각 노드를 화면상의 실제 픽셀로 변환하고, 레이어를 만든다. (Paint)
8. 레이어를 합성하여 실제 화면에 나타낸다. (Composite)
HTTPS란?
대칭키, 비대칭키 암호화 방식이란?
- 대칭키 방식
- 암호화 및 복호화에 드는 비용이 적지만, 키를 상대방과 함께 사용해야하기 때문에 전달하기가 쉽지 않다는 단점이 있다.
- 비대칭키 방식
- 수학적인 공식으로부터 만들어진 두 쌍의 키로 구성되며, 하나는 외부에 공개하여 공개 키로 사용하고 다른 하나는 공개하지 않고 개인 키사용한다.
- 공개 키로 데이터를 암호화하면 반드시 개인 키로만 복호화 가능하고, 개인 키로 데이터를 암호화하면 공개 키로만 복호화 할 수 있다. 보안성이 뛰어나다는 장점이 있지만, 구현하기가 어렵고 암호화 및 복호화 속도가 느리다는 단점이 있다.
- 주로 전자서명과 메세지 송신에 사용된다.
- 전사 서명
- 내 공개키로 암호화된 것을 나만 가지고 있는 개인키로 복호화함으로써 내가 맞다는 것을 증명할 수 있다.
- 메세지 송신
- 상대방의 공개키로 암호화하여 보내면 개인키를 갖고 있는 상대방만 복호화할 수 있기 때문에 안전하게 보낼 수 있다.
- 전사 서명
- 정의
- HTTP(HyperText Transfer Protocol)의 보안(Secured)버전
- SSL/TLS 프로토콜을 사용해 HTTP를 암호화하여 주고 받을 때 쓰는 통신 프로토콜
정리
- HTTP : 클라이언트와 서버 간의 자원을 교환하기 위한 TCP/IP 기반 통신 프로토콜
- HTTPS : SSL/TLS 프로토콜을 사용해 HTTP를 암호화하여 주고 받을 때 쓰는 통신 프로토콜
- 웹 브라우저에 www.naver.com 을 치면 어떤일이 일어나는가?
더보기- 웹 브라우저에 www.naver.com 입력.
- 사용자가 입력한 URL 주소 중 도메인 네임 부분을 DNS 서버에 검색하고, DNS서버에서 해당 도메인 네임에 해당하는 IP주소를 찾아온다.
- HTTP 프로토콜을 사용하여 페이지 URL정보와 찾아온 IP주소를 포함하는 HTTP 요청 메세지를 생성하고, 생성된 HTTP 요청 메세지는 TCP 프로토콜을 사용하여 인터넷 망을 통해 해당 IP주소의 컴퓨터로 전송된다.
- HTTP 요청 메세지를 받은 컴퓨터(서버)는 웹 페이지 URL 정보 중 PATH와 HTTP Method에 맞는 액션을 취한다. (여기서는 naver 페이지를 띄우기 위해 필요한 html 등의 리소스를 찾을 것이다.)
- 생성된 응답 데이터는 또 다시 HTTP 프로토콜을 사용하여 HTTP 응답 메세지로 만들어지고 TCP 프로토콜을 사용하여 인터넷 망을 통해 요청했던 컴퓨터(클라이언트)로 전송된다.
- 도착한 HTTP 응답 메세지는 웹 브라우저에 의해 브라우저 렌더링 과정을 거쳐 화면에 출력되어 사용자가 볼 수 있게 된다.
'내일배움캠프 노드 4기 > Today I Learned' 카테고리의 다른 글
| 22년 11월 29일 TIL (0) | 2022.11.29 |
|---|---|
| 22년 11월 28일 TIL - javascript 기초 문법 (0) | 2022.11.28 |
| 22년 11월 24일 TIL (0) | 2022.11.24 |
| 22년 11월 23일 TIL (0) | 2022.11.23 |
| 22년 11월 22일 TIL 알고리즘 (0) | 2022.11.22 |
