TIL 10일차: 큐 Queue, 해쉬 Hash, 트리 Tree, 힙 Heap, 그래프 Graph, DFS&BFS, Dynamic Programming, HTTP/HTTPS

오늘은 아침에 일찍 일어나서 스택 복습하고 큐와 해쉬 개념을 익혔다. 그리고는 알고리즘 마지막 강의를 들었다.

스택(push, pop, peek)과 큐(enqueueu, dequeue, peek)에 대해 배웠다.

정렬을 다룰 땐 집중하기 힘들어서 그냥 알고리즘 3주차 숙제를 풀었다.

쓱 최대로 할인적용하기는 각 정렬의 데이터를 내림차순으로 정렬한 후 값을 뽑아 새로운 배열에 더하면서 저장하는 문제였다.

괄호 짝짓기에서는 직전에 열린 괄호를 체크하는, 즉 가장 마지막 노드를 탐색하는 스택을 구현했다.

멜론 베스트 앨범 뽑기는 여러 단계를 거쳐가야 해서 굉장히 어려웠다.

해쉬에서 배운 key와 value를 배열 형태로 추가해주고, 각 장르별 1,2순위 곡들을 다른 배열에 추가해서 정렬 후에 인덱스 값으로 반환해야 했다.

이번 3주차에서 배운 모든 지식을 종합한 문제였다.

1. 큐 Queue

큐는 한쪽 끝으로 자료를 넣고, 반대쪽에서는 자료를 뺄 수 있는 선형 구조이다.

FIFO (First In First Out)

기능에는 enqueue(맨 뒤에 데이터 추가), dequeue(맨 앞의 데이터 뽑아 없앰), peek(head 조회)이 있다.

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


class Queue:
    def __init__(self):
        self.head = None
        self.tail = None

    def enqueue(self, value):
        new_node = Node(value)

        if self.is_empty():
            self.head = new_node
            self.tail = new_node
            return

        self.tail.next = new_node
        self.tail = new_node
        return

    def dequeue(self): #delete_head에 임시저장
        if self.is_empty():
            return None
        delete_head = self.head
        self.head = self.head.next
        return delete_head.data

    def peek(self):
        if self.is_empty():
            return None
        return self.head.data

    def is_empty(self):
        return self.head is None

queue = Queue()
queue.enqueue(3)
print(queue)
print(queue.peek())
queue.enqueue(4)
print(queue.peek())
queue.enqueue(5)
print(queue.peek())
print(queue.dequeue())
print(queue.peek())
print(queue.dequeue())
print(queue.is_empty())
print(queue.dequeue())
print(queue.is_empty())

2. 해쉬 Hash

해쉬 함수와 해쉬 테이블에 간단히 복습을 하자면,

해쉬 테이블은 key와 value를 저장함으로써 즉각적으로 데이터를 받고 업데이트 하고 싶을 때 사용하는 자료구조이다.

해쉬 테이블의 내부 구현은, 해쉬 함수를 통해 key를 임의의 값으로 변경한 뒤,

배열의 인덱스로 변환하여 해당하는 값에 데이터를 저장하는 것이다.

해쉬함수를 쓸 때 배열의 길이로 나눈 나머지값을 써준다는 특징이 있다.

해쉬에서 충돌이 일어날 땐 체이닝을 쓰는데, 링크드리스트를 사용해 연결지어 해결하는 방법이다.

 

class LinkedTuple:
    def __init__(self):
        self.items = list()


    def add(self, key, value):
        self.items.append((key, value))

    def get(self, key):
        for key, value in self.items:
            if key == k:
                return value


class LinkedDict:
    def __init__(self):
        self.items = [] # LinkedTuple(), LinkedTuple(), LinkedTuple(), ...
        for i in range(ß):
            self.items.append(LinkedTuple())

    def put(self, key, value):
        index = hash(key) % len(self.items)
        self.items[index].add(key, value) #LinkedTuple()에서 미리 만들어놓은 메소드

    def get(self, key):
        index = hash(key) % len(self.items)
        return self.items[index].get(key)

 

그리곤 곧바로 4주차에 들어갔다. 이번 4주차에는 트리, 힙, 그래프, DFS, BFS, Dynamic Programming에 대해 배웠다.

어차피 4주차 정리하면서 쓸 거라 간단히 한 두 줄로만 개념을 설명하자면,

3. 트리 Tree

비선형 자료구조로, 표현에 중점을 둔다.

4. 이진 트리 Binary Tree, 완전 이진 트리 Complete Binary Tree

이진 트리에서 각 노드는 최대 두 개의 자식을 갖고,  완전 이진 트리에서는 노드가 최하단 노드부터 차례대로 삽입된다.

완전 이진 트리를 배열로 표현하면, None값이 0번째 인덱스에 넣어지고 나머지 값은 다음과 같이 구한다.

Index * 2 = 왼쪽 자식 인덱스

Index * 2 + 1 = 오른쪽 자식 인덱스

Index // 2 = 부모 인덱스

5. 힙 Heap

최댓값과 최솟값을 빠르게 찾기 위한 완전 이진 트리.

부모 노드가 자식 노드보다 항상 크다.

맥스 힙과 민 힙 중에 맥스 힙에 초점을 맞추어 배웠다.

 

<맥스 힙에 원소를 추가하려면>

1) 원소를 맨 마지막에 넣기

2) 부모 노드와 비교. 더 크다면 자리 바꾼다

3) 부모 노드보다 작거나 가장 위에 도달하지 않을 때까지 반복한다.

 

<맥스 힙의 원소를 삭제하려면>

1) 루트 노드와 맨 끝에 있는 원소를 교체한다

2) 맨 뒤에 있는 원소(원래 루트 노드)를 삭제한다

3) 변경된 노드와 자식 노드들을 비교한다. 두 자식 중 더 큰 자식과 비교해서 자식이 더 크면 자리를 바꾼다

4) 자식 노드 둘보다 부모 노드가 크거나, 가장 바닥에 도달하지 않을 때까지 반복한다

5) 2)에서 제거한 원래 루트 노드를 반환한다.

6. 그래프 Graph

그래프란 연결되어 있는 정점과 정점자의 관계를 표현할 수 있는 자료구조이다. 연결관계에 초점을 맞춘다.

노드=정점, 간선, 인접노드

표현 방법에는 두 가지가 있는데, 인접 행렬과 인접 리스트이다.

7. DFS Depth First Search

우선 DFS와 BFS는 자료의 검색, 트리나 그래프를 탐색하는 방법으로,

모든 경우의 수를 탐색해야 할 때 쓰인다.

한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색하고, 끝까지 탐색하면 다시 위로 와서 탐색을 계속한다.

DFS와 BFS의 차이는 탐색하는 순서에 있다.

DFS는 갈 수 있는 만큼 계속 탐색하다가, 갈 수 없게 되면 다른 방향으로 다시 탐색한다(이것이 곧 탈출 조건)

따라서 재귀함수를 이용해서 코드를 짤 수 있다.

즉, DFS node = node + DFS node와 인접하지만 방문하지 않은 다른 node로 반복.

방문하지 않을 조건을 알기 위해 visited라는 배열에 방문한 노드를 기록할 필요가 있다.

알고리즘 순서를 보면,

1) 루트 노드부터 시작

2) 현재 방문한 노드를 visited에 추가

3) 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드에 방문한다.

4) 2)부터 반복

 

하지만 재귀함수를 사용할 땐 충돌 문제가 발생할 수 있으니, 이를 해결 하기 위해 스택Stack을 활용한다.

스택으로 가장 마지막 노드만 꺼내서 탐색할 수 있다.

이 알고리즘 순서를 보면,

1. 뤁 노드를 스택에 넣는다.

2) 현재 스택의 노드를 빼서 visited에 추가한다.

3) 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 스택에 추가한다.

4) 2)부터 반복

5) 스택이 비면 탐색을 종료한다.

8. BFS Breadth First Search

BFS에서는 현재 인접한 노드 먼저 방문한다.

즉 인접한 녿 중 방문하지 않은 모든 노드들을 저장하고, 가장 처음에 넣은 노드를 꺼내서 탐색한다.

따라서 큐 Queue를 활용할 수 있다.

이 알고리즘은 앞서 살핀 stack과 유사하며, stack자리에 queue가 들어갔을 뿐이다.

1) 루트 노드를 큐에 넣는다.

2) 현재 큐의 노드를 빼서 visited에 추가한다.

3) 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 추가한다.

4) 2)부터 반복

5) 큐가 비면 탐색을 종료한다.

9. Dynamic Programming

다이나믹 프로그래밍, 같은 말로 동적 계획법은

여러 개의 하위 문제를 풀고, 그 결과를 기록하고 이용하여,

문제를 쪼개서 정의할 수 있을 때 사용한다.

이 때 결과를 기록하는 것을 메모이제이션 Memoization이라 하며,

쪼갤 수 있는 문제를 겹치는 부분 문제 Overlapping Subproblem이라고 한다.

동적 계획법으로 해결할 수 있는 대표적인 수학 문제는 피보나치 수열이다.

이 알고리즘을 살펴보면,

1) 메모용 데이터 fibo_memo를 만든다.

처음 값인 Fibo(1), Fibo(2)에 각각 1씩 넣어 저장한다.

2) FIbo(n)을 구할 때 만약 메모에 그 값이 있다면 바로 반환한다.

3) Fibo(n)을 처음 구했다면 메모에 그 값을 기록한다.

 

10. HTTP, HTTPS 특강

저녁 7시부터 HTTP 특강을 들었다. 평소에 궁금하던 부분이었는데 굉장히 유용했다.

이건 따로 글을 쓰는 걸로... 키웓만 나열하자면 다음과 같다.

IP 주소, DNS 도메인 메인 시스템, TCP/IP, HTTP, 메소드,

HTTP의 통신 흐름(웹 브라우저에 www.naver.com을 을 입력했을 때 클라이언트와 서버에서 어떤 일이 일어나는지), 

HTTPS의 대칭키 방식과 비대칭키 방식(암호화, 복호화), SSL/TLS handshake

 

후아 오늘 많이 공부했다. 머리가 터질 것만 같아서 밤에 못쓰고 다음날이 되어 쓰는 Today I learnt 끝.