[내일배움캠프] 2022-11-25 TIL

자료구조 & 알고리즘 특강 (강창민 튜터님)

스택

• LIFO(Last In First Out)의 성격을 가진 선형 자료구조
• 반복문에서 종료 조건을 지정하지 않거나 잘못된 종료조건을 지정하여 무한 루프가 발생하면 메모리의 스택영역이 쌓이고 쌓이다 터짐 → StackOverflow
• 역순의 성질을 사용해야될 때 유용한 구조
• 대표적인 기능: 픽(peek), 푸시(push), 팝(pop)

큐

• FIFO(First In First Out)의 성격을 가진 선형 자료구조
• 대표적인 기능: 픽(peek), 삽입(enqueue), 뽑기(dequeue)

버블 정렬

• 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, … 이런 식으로 (n-1)번째 자료와 n번째 자료를 비교하여 교환하면서 자료를 정렬
• 시간 복잡도는 O(N^2)

def bubble_sort(array):
    n = len(array)
    for i in range(n):
        for j in range(n - i - 1):
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]
    return array

*파이썬의 swap 기능 (a, b = b, a)은 매우 편리하니 잘 알아두자.

선택 정렬

• index 하나마다 위치할 원소를 결정하고 그 다음 index로 넘어가는 방식으로 정렬
• 시간 복잡도는 O(N^2)

def selection_sort(array):
    n = len(array)
    for i in range(n - 1):
        min_index = i
        for j in range(n - i):
            if array[i + j] < array[min_index]:
                min_index = i + j 
        array[i], array[min_index] = array[min_index], array[i]
    return array

삽입 정렬

• 전체에서 하나씩 올바른 위치에 "삽입" 하는 방식으로 정렬 → 필요할 때만 위치를 변경하므로 선택 정렬보다 효율적
• 시간 복잡도는 O(N^2), 최선의 경우엔 Ω(N)

def insertion_sort(array):
    n = len(array)
    for i in range(1, n):
        for j in range(i):
            if array[i - j - 1] > array[i - j]: 
                array[i - j - 1], array[i - j] = array[i - j], array[i - j - 1]
            else:
                break
    return array

더 공부할 것들

• 정렬: 머지 정렬/힙 정렬/퀵 정렬/셸 정렬/기수 정렬
• 자료구조: 트리/트라이/그래프/해시 테이블

재귀 함수

• 재귀함수에서 가장 중요한 것: 종료 조건(Terminal condition)
• 자료구조, 알고리즘 원격 강의 2주차 숙제  '더하거나 빼거나' 문제를 재귀함수가 아닌 반복문으로 풀어보기 ↓

numbers = [1, 1, 1, 1, 1]
target_number = 3
sums = []

def get_all_combinations(numbers):
    num_of_operator = 2 # +, -만 지원
    for i in range(num_of_operator ** len(numbers)):
        binary_value = '{:05b}'.format(i) # 0 ~ 31 => 00000 ~ 11111
        operators = [int(el) for el in list(binary_value)] # *list comprehension
        curr_sums = numbers[0] if operators[0] == 1 else -numbers[0]
        for j in range(1, len(operators)):
            if operators[j] == 1:
                curr_sums += numbers[j]
            else:
                curr_sums -= numbers[j]
        sums.append(curr_sums)

get_all_combinations(numbers)
print('sums:', sums)
print(len(sums))

*list comprehension을 잘 익히고 활용하기

*문제 푸는 법은 여러 가지가 있을 수 있음을 알기

 

HTTP/HTTPS 특강 (박민수 튜터님)

HTTP를 배우기 위한 기본 개념들

• IP 주소(Internet Protocol Address)
  • 인터넷에 연결되어 있는 모든 장치들을 식별할 수 있도록 각각의 장비에게 부여되는 고유 주소
  • 전세계적으로 보편화되어 사용되는 IP 버전은 4(IPv4)이며, 확장성과 용량 면에서 한계를 보이는 IPv4를 버전 6(IPv6) 로 대체될 것
• 도메인 네임 시스템(DNS, Domain Name System)
  • 도메인 네임은 IP 주소를 사람들이 이해하기 쉽게 문자로 표현한 것을 의미
  • 컴퓨터가 이해할 수 없는 도메인 네임을  IP 주소에 할당하고 이를 관리하는 시스템을 DNS라고 함
• 포트(port)
  • 운영 체제 통신에서의 종단점을 의미: 목적지 호스트까지 도달한 후 어떤 프로세스(Process)에서 데이터를 받을 것인지 를 알아야 하는데 쓰이는 것이 포트번호
• 회선 통신
  • 회선의 트래픽이나 이동 효율을 전혀 고려하지 않은 채 미리 정하는 회선 교환(Circuit Switching) 방식
  • 데이터를 전송하는 시점의 트래픽, 혼잡도 등의 요인에 따라 효율이 달라진다는 큰 단점을 가짐
• 패킷 통신
  • 미리 이동 경로를 정하지 않고, 데이터를 패킷 (Packet) 이라는 작은 단위로 나누어 전송하는 방식
  • 전송 당시 가장 효율적인 경로를 설정하여 최종 목적지까지 이동
• TCP/IP
  • IP: 패킷들을 가장 효율적인 방법으로 최종 목적지로 전송하기 위해 필요한 프로토콜, 패킷 전달 여부&순서 보장X
  • TCP: 패킷을 안전하게 전달해주는 전송 프로토콜
  • TCP/IP: IP + TCP = 인터넷 프로토콜 + 전송 제어 프로토콜
    • TCP를 기반으로 한(신뢰성 통신을 하는) HTTP,FTP,SMTP 등 수 많은 프로토콜들이 IP 위에서 동작하기에 묶어서 TCP/IP라고 함
    • 효율적으로 빠르게(IP) 보내면서 안전하게(TCP) 전달해주려는 목적

HTTP(HyperText Transfer Protocol)란?

• 클라이언트와 서버 간의 자원을 교환하기 위한 TCP/IP 기반 통신 프로토콜
• 단뱡향성: 서버가 먼저 응답을 보낼 수 없고 클라이언트가 요청을 보내야만 응답할 수 있음
• 비연결성: 클라이언트의 요청으로 서버와 연결된 후, 요청에 대한 응답의 데이터를 전송하면 연결을 종료
• 도청, 위장, 변조가 가능함 → HTTPS의 등장

HTTP 메소드 (Method)

주요 메소드

• GET: 보통 리소스를 조회할 때 사용하며, 서버에 전달하고 싶은 데이터는 query를 통해서 전달한다.
• POST: 주로 리소스를 새롭게 생성할 때 사용하며, 서버에 전달하고 싶은 데이터는 메시지 바디를 통해 전달한다.
• PUT: 리소스가 있으면 대체하고 리소스가 없으면 생성한다. 즉, 데이터를 덮어쓴다.
• PATCH : PUT과 마찬가지로 리소스를 수정할 때 사용하지만, PATCH는 리소스를 일부분만 변경할 때 사용한다.
• DELETE: 리소스를 제거할때 사용한다.

메소드 속성

• 안전(Safe Methods): 계속 호출해도 리소스를 변경하지 않는 특성
• 멱등(Idempotent Methods): 동일한 요청을 여러 번 보내도 한 번 보내는 것과 똑같은 결과를 갖는 것
• 캐시가능(Cacheable Methods): 응답 결과를 서버에 캐시 해서 사용해도 되는 메소드

HTTP 상태코드 (Status code)

• 1xx (Informational): 요청이 수신되어 처리중
• 2xx (Successful): 요청 정상 처리
• 3xx (Redirection): 요청을 완료하려면 추가 행동이 필요 (보통 리다이렉션처리)
• 4xx (Client Error): 클라이언트 오류, 잘못된 문법등으로 서버가 요청을 수행할 수 없음
• 5xx (Server Error): 서버 오류, 서버가 정상 요청을 처리하지 못함

**HTTP 통신흐름 (면접 단골 주제)

1. 웹 브라우저에 URL 주소 입력
2. 도메인 네임 부분이 DNS 서버에 검색되어 해당하는 IP주소를 찾아옴
3. HTTP 프로토콜을 사용하여 HTTP 요청 메세지를 생성하고, 생성된 메세지는 TCP 프로토콜을 사용하여 인터넷 망을 통해 해당 IP주소의 컴퓨터로 전송
4. HTTP 요청 메세지를 받은 컴퓨터(서버)는 웹 페이지 URL 정보 중 PATH와 HTTP Method에 맞는 액션을 취함
5. 생성된 응답 데이터는 또 다시 HTTP 프로토콜을 사용하여 HTTP 응답 메세지로 만들어지고 TCP 프로토콜을 사용하여 인터넷 망을 통해 요청했던 컴퓨터(클라이언트)로 전송
6. 도착한 HTTP 응답 메세지는 웹 브라우저에 의해 브라우저 렌더링 과정을 거쳐 화면에 출력되어 사용자가 볼 수 있게 됨

HTTPS란?

• 중요 개념 
  • 암호화: 평문 → 암호문    /     복호화: 암호문 → 평문
  • 대칭키 방식: 암호화와 복호화에 필요한 키가 동일하여 비용은 적게 들지만, 키를 전달하기가 쉽지 않다.
  • 비대칭키 방식: 공개 키로 암호화하면 개인 키로만 복호화가 가능하고, 개인 키로 암호화하면 공개 키로만 복호화 할 수 있다. 보안성이 매우 뛰어나지만, 구현하기 어렵고 속도가 느리다. ex) 전자서명
• HTTPS: HTTP(HyperText Transfer Protocol)의 보안(Secured)버전, SSL/TLS 프로토콜을 사용해 HTTP를 암호화하여 주고 받을 때 쓰는 통신 프로토콜
• SSL/TLS Handshake
  
  1. 서비스를 서빙하는 서버가 CA(certificate authority, 인증 기관)로부터 CA 인증서를 발급받는다. [인증서 기간 만료까지 1회성]
  2. 서비스를 서빙하는 서버는 CA에 자신의 도메인 정보와 서버 측 공개 키를 보낸다.
  3. 인증기관은 받은 두 데이터를 자신의 개인키로 암호화한 CA 인증서를 서버로 보낸다.
  4. 브라우저에서 도메인을 쳐서 요청을 보내 클라이언트(브라우저)와 서버가 TCP 연결을 맺는다.
  5. 서버는 브라우저가 보내준 Cipher Suite 중 하나를 고르고, 자신의 SSL/TLS 프로토콜 버전을 브라우저에게 알리면서, 서버 자신의 도메인에 대한 CA 인증서를 보낸다.
  6. 브라우저는 브라우저에 내장된 CA의 공개 키를 이용하여 CA 인증서를 복호화하여 인증서가 유효한지 검증한 후, 서버 측의 공개 키를 얻는다.
  7. 브라우저는 앞으로 서버와 통신하는데 있어 암호화를 위해 사용할 대칭 키를 만들고, 그 대칭 키를 사이트 공개 키로 암호화하여 서버로 보낸다.
  8. 서버는 자신의 개인 키를 사용하여 암호화된 것을 복호화하여 사용자 대칭 키를 얻어 낸다.
  9. 이렇게 얻은 대칭 키를 활용하여 서버와 클라이언트가 서로 데이터를 안전하게 암/복호화 하면서 통신할 수 있게 된다.