나의 개발일지 TIL(Today I learned) - 알고리즘 자료구조 특강 및 복습 HTTP / HTTPS 특강

Today I learned

• 자료구조 알고리즘 특강
• 자료구조 알고리즘 복습
• HTTP / HTTPS 특강

 

자료구조 알고리즘 특강

스택과 큐 그리고 기본 정렬인 버블정렬 선택정렬 삽입정렬을 배웠다

 

스택이란 순서대로 차곡차곡 쌓아서 제일 위 부터 차곡차곡 빼는게 스택이다

LIFO(Last In First Out)의 성격을 가진 자료구조!

이것이 넘치면 StackOverflow가 된다

스택은 어디에 쓰일까? 모바일 앱을 사용하면 뒤로 가기 버튼을 꽤 많이 누른다 이때 사용하는 자료구조가

바로 스택이다

 

스택에는 push, pop, peek 또는 top이 있다

push는 스택에 원소를 Top에 삽입한다

pop은 스택의 Top의 원소를 가져오고 삭제한다

peek 또는 top은 스택의 Top의 데이터를 본다

 

큐란 FIFO(First In First Out)의 성격을 가진 자료구조이다

대기줄을 섰을때 먼저 대기한 사람이 먼저 빠저나가는 구조라고 생각하자

큐는 어디서 사용할까? 바로 티켓팅 대기열, 게임 접속 시간 대기열이다 로스트아크라는 게임을 하면

큰 업데이트가 있을 때는 항상 대기열이 걸리는데 이런 경우가 큐를 사용한 경우 였다!

그리고 윈도우에서도 자주 본 인쇄를 할때 인쇄 대기열도 큐의 자료구조이다

 

큐에는 peek, enqueue, dequeue가 있다

peek은 제일 앞에 대기하고 있는 데이터를 본다

enqueue는 대기줄 제일 끝에 원소를 삽입한다

dequeue는 대기줄 제일 앞의 원소를 가져오고 삭제한다

 

1. 버블 정렬

가장 쉽고 직관적인 버블 정렬

첫 번째 자료와 두 번째 자료를 두 번째 자료와 세 번째 자료를 하나하나 비교하면서 교환하는 정렬 방식이다

 

2. 선택 정렬

하나의 요소를 골라서 모든 수와 비교하고 바꾸고를 반복해 정렬하는 방법이다

 

3. 삽입 정렬

선택 정렬은 최솟값을 선택해 그릇에 담아두고 비교했지만 삽입 정렬은 하나씩 자기 위치에 삽입하는 방식

선택 정렬은 현재 데이터의 상태와 상관없이 항상 비교하고 위를 바꾸지만 삽입 정렬은 필요할 때만 위치를 변경한다

그래서 더 효율적인 방법이다

 

자료구조 알고리즘 복습

스택의 성질

1. 원소의 추가가 O(1)

2. 원소의 제거가 O(1)

3. 제일 상단의 원소 확인이 O(1)

4. 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능

 

파이썬으로 연결리스트를 이용해 구현해 보자

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class Stack:
    def __init__(self):
        self.head = None

    def push(self, data):
        if self.head is None:
            self.head = Node(data)
            return 1

        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
        return 1

    def peek(self):
        if self.head is None:
            return 0

        return self.head.data

    def pop(self):
        if self.head is None:
            return 0

        node = self.head
        self.head = self.head.next

        return node.data

list = Stack()
list.push(2)
list.push(3)
print(list.peek())
list.push(4)
print(list.pop())
print(list.peek())

스택은 push, pop, top 혹은 peek의 기능이 있다 push는 제일 위 요수를 추가하고 pop은 제일 위 요소를 제거 및 반환한다

top혹은 peek는 제일 위 요소를 반환해준다

 

스택을 이용한 알고리즘을 풀면서 복습해보자

10773번: 제로

array = []
answer = 0
input_cnt = int(input())
for _ in range(input_cnt):
    input_data = int(input())

    if input_data == 0:
        if len(array) == 0:
            break

        array.pop()

    else:
        array.append(input_data)


while array:
    answer += array.pop()

print(answer)

파이썬은 배열을 이용해 스택처럼 사용할 수 있다 이미 pop()메서드와 append()라는 메서드가 stack의 push와 pop의 기능과 유사하다 입력값이 0인지 확인하고 0이면 스택에서 pop하고 아니면 push를 반복하고 스택이 비었다면 break를 건다

 

다음 문제를 보자

1874번: 스택 수열

stack = []
answer = []
cnt = 0
input_cnt = int(input())
for _ in range(input_cnt):
    input_num = int(input())

    while cnt <= input_num:
        stack.append(cnt)
        answer.append("+")
        cnt += 1

    if input_num == stack[-1]:
        stack.pop()
        answer.append("-")

    else:
        print("NO")

for i in answer:
    print(i)

이 문제는 문제가 이해를 하기까지 오래걸렸지만 문제만 이해하면 생각보다 쉬웠다

이 문제는 입력한 숫자를 스택안에서 뽑아 수열을 만든다 스택안에는 오름차순 정렬로 1~입력한 숫자까지 있어야 입력한 숫자를 뽑을 수 있다 8을 뽑아 수열로 만들고 싶다면 스택 안에는 1~8까지 있어야 한다는 말이다

 

HTTP / HTTPS 특강

HTTP란 무엇인가? 클라이언트와 서버 간의 자원을 교환하기 위한 TCP/IP 기반 통신 프로토콜

TCP/IP란 무엇인가? IP + TCP 인터넷 프로토콜 + 전송 제어 프로토콜이다

효율적으로 빠르게 안전하게 통신을 할 수 있게 해주는 목적을 가진 프로토콜이다

 

HTTPS란 무언인가? SSL/TLS 프로토콜을 사용해 HTTP를 암호화하여 주고 받을 때 쓰는 통신 프로토콜

 

www.naver.com을  을 입력하면 어떤 일이 일어날까?

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