YoungQ

0. 시작하기

 - 언제 어디서나 인터넷만 되면, 접속이 가능한 Jupyter Server를 구축해보겠습니다.

 - 서버는 무료로 사용가능한 Oracle Cloud 프리티어, OS는 Ubuntu 18를 사용하였습니다.

 - 클라우드 보안 및 네트워킹 설정에 대한 부분은 다루지 않습니다.

 - 운영체제 및 개인네트워크 환경에 따라 정상적으로 설치가 안될 수 있습니다.

1. pip 및 Jupyter 설치

  1) PIP 설치

    최근에는 기본적으로 유닉스/리눅스 OS계열에서는 Python이 설치되어있기는 하지만, 적어주고 가겠습니다.

sudo apt-get update
sudo apt install python3-pip
sudo pip3 install --upgrade pip

  2) 개발 작업공간 및 인증서보관 폴더 생성

mkdir jupyter
mkdir jupyter/cert
mkdir jupyter/contents

    cert          : 인증서 보관용 폴더

    contents   : 실제 작업공간

  3) 인증서 생성

cd jupyter/cert
openssl req -x509 -nodes -days 365 -newkey rsa:2048 -keyout notebook.key -out notebook.pem

    cert 폴더로 이동하여 openssl을 이용한 사설인증서 생성(openssl 생성시 설정은 그냥 빈칸으로 넣고 Enter처도 무관합니다)

  4) Jupyter 설치

sudo pip3 install jupyter notebook

    주피터 설치 시, 기본설정은 로컬에서만 작동하도록 되어있습니다. 때문에 원격지에서 접속 할 수 있도록 설정을 해줘야합니다.

3. Jupyter 설정

  1) Jupyter Server 설정

    1.1) 접속 패스워드 설정 (파이썬에서 argon2 방식으로 암호화된 값을 구해 config 파일에 넣어주는 방식입니다.)

Python3
>> from notebook.auth import passwd
>> passwd()
Enter password : (입력)
Verify password : (입력)
'argon2:$argon2id$v=19$m=10240,t=10,p=8$vyRuJXe9zdvrHFqZMe4FMg$gPmyWbmPLWJz7E/m6AoAGg'
>> exit()

      위에 마지막줄 '~~~' 부분을 복사해서 config 파일에 넣어줘야합니다.

    1.2) config 파일 생성

jupyter notebook --generate-config

    jupyter notebook --generate-config  :  기본 설정파일 생성(jupyter_notebook_config.py)

    1.3) config 파일 설정

sudo vi ~/.jupyter/jupyter_notebook_config.py

파일내용 맨 아랫부분에 아래와 같은 내용을 추가해줍니다.

c = get_config()
c.NotebookApp.password = u'argon2:$argon~~~~~~~~~~~~~'                 # 위에서 복사한 암호값을 넣어줍니다.
c.NotebookApp.ip = '*'
c.NotebookApp.open_browser = False
c.NotebookApp.certfile = u'/home/ubuntu/jupyter/cert/notebook.pem'
c.NotebookApp.keyfile = u'/home/ubuntu/jupyter/cert/notebook.key'
c.NotebookApp.port = 8888                                                                     # 접속용 포트를 입력해주세요.
c.NotebookApp.notebook_dir = u'/home/ubuntu/jupyter/contents'

    sudo vi ~/.jupyter/jupyter_notebook_config.py  :  생성된 설정파일 수정 (vi가 아닌 편한 에디터를 이용해주세요)

    1.4) 외부접속 포트 허용

sudo iptables -I INPUT 5 -i ens3 -p tcp --dport 8888 -m state --state NEW,ESTABLISHED -j ACCEPT

  2) 접속 확인

브라우저에 서버의 공인IP와 위에서 설정한 포트IP를 입력 후 접속하여, 설정한 암호로 접속할 수 있습니다.
브라우저 : https://공인IP:8888

꼭 https 를 통해서 접속해야합니다. 접속시, 사설인증서를 사용하였기 때문에, 안전하지 않은 사이트라고 나오지만, 그냥 접속하면됩니다.

맥 OS에서 접속할 경우 해당인증서를 키체인에 등록 후 신뢰할 수 있는 인증서로 등록해주셔야합니다.

Fin

1. 트리(Tree)

아직까지도 많이 사용되고, 앞에서 다룬 자료형들보다 더욱 다양한 형태로 개발된 자료형입니다.

트리는 그래프와 유사한 형태이지만, A에서 B라는 노드로 갈 수 있는 한개의 길만 존재하는 자료구조입니다.

트리(Tree)는 아래와 같은 요소를 갖고있습니다.

 - Root(루트노드) : 최상의 노드 (위 그림에서 2)

 - parent(부모노드) : 특정 노드의 바로 상위에 연결된 노드 (2는 루트노드이며, 7과 5의 부모노드입니다.)

 - child(자식노드) : 특정노드의 바로 아래에 연결된 노드 (7과 5는 2의 자식노드입니다.)

 - sibling(형제노드) : 같은 부모노드를 갖고있는 노드입니다. (7과 5는 형제노드입니다)

 - leaf(단말노드) : 자식이 없는 최하단의 노드입니다. (2"중복", 5, 11, 4는 단말노드입니다.)

 - Level(레벨) : Root를 Level 1로 두고, 아래로 자식노드로 내려갈 수록 1씩 증가합니다. (6의 경우 Level3)

 - depth(깊이) : 트리의 최대 Level을 의미합니다. 위 트리의 depth는 4입니다.

 - degree(차수) : 특정 노드의 하위 트리의 개수를 의미합니다.

1.1. 이진트리 (Binary Tree)

가장 대표적인 트리의 형태로, 위 그림에서 다루었던 형태입니다.

하나의 노드는 최대 두 개의 자식노드만을 갖을 수 있는 형태입니다. 이진트리를 사용하는 이유는, 자식노드이 수가 최대 2개로 정해져있기 때문에 구현하기 쉽고, 이를 이용하여 다양한 알고리즘을 구현하는것이 가능하다는 장점이 있습니다.

 1) BST(Binary Search Tree)

가장 대표적인 탐색알고리즘입니다. BST를 이용하기 위해서는 아래와같은 전재가 필요합니다.

 - 이진트리로 구현되어있을 것

 - 특정 노드를 기준으로 좌측에는 항상 작은 값이, 우측에는 항상 큰 값이 존재해야합니다.

 - 모든 노드는 서로다른 값(키)을 갖고있어야 합니다.

class Node():
    def __init__(self, data, left=None, right=None, parent=None):
    	self.value = data
        self.left = left
        self.right = right
        self.parent = parent
    def __str__(self):
    	return str(self.value)
        
class BST:
    def __init__(self):
        self.root = None
    def search(self, target, tree):
        if tree == None: return None
        if tree.value == target: 
            return tree
        if tree.value < target:
            return self.search(target, tree.right)
        else:
            return self.search(target, tree.left)

위는 BST의 가장 기본적인 탐색 코드입니다. 각 노드는 부모와, 두 자식 노드를 객체로 갖고있으며, 탐색하기를 원하는 값을 현재의 값과 비교하며 탐색하게 됩니다.

BST의 경우, 찾고싶은 값이 최악의 경우에도 Leaf 이하에는 존재할 수 없기 때문에 평균 O(logn)으로 탐색이 가능하다는 장점이 있습니다.

BST에서 값을 추가하고, 제거하는 것 역시도 추가 역시도 O(depth)로 가능하다는 장점이 있습니다.

물론 BST도 정말 큰 단점이 있습니다.

바로 "Skewed" 라는 현생이 발생할 수 있다는 것입니다.

즉, 아래 그림과 같이 한쪽으로만 일방적으로 자식노드가 생길 경우 n개의 노드에 대해서 탐색에 n만큼의 탐색이 필요할 수 있습니다.

이러한 문제를 방지하기위해 Bad-Black Tree라는 개념이 등장했습니다.

만........ 정말 많은 이미지를 통한 설명이 필요한 부분이기에... 차후에 뒤에서 다루도록하겠습니다.(꾸벅)

0. 시작하기

 - 대표적인 알고리즘 몇개를 10개정도의 게시물로 나눠 살펴볼 예정입니다.

 - 초점이 알고리즘인 만큼, 다양한 포인터의 활용이나, 복잡한 문법의 사용이 적은 파이썬을 통해 풀어낼 예정입니다.

 - 복습 차원에서 진행하다보니 특정 자료형에서 많이 사용되는 알고리즘임에도 깜빡하고 넘어갈 수 있으며, 내용에 오류가 있을 수 있습니다. 이러한 부분이 있으실 경우 댓글 부탁드리곘습니다.

 - 시작은 간단한 자료형에 대한부분으로 시작하겠습니다.

1. 리스트(List)

배열과 비교되는 자료 형태로, 일반적으로 크기를 미리 정해두고 순차적으로 자료를 저장하여 관리하는 배열과 다르게, [데이터와 포인터]의 형태로 만들어져, 포인터를 통해 연결되어 크기를 미리 정하지 않고도 얼마든지 객체의 추가와 제거가 가능한 데이터 형태입니다.

배열과 다르게 무한히 새로운 데이터를 연결하여 만들어 줄 수 있다는 장점이 있지만, Index를 통해 특정 데이터를 한번에 호출 할 수 없다는 단점도 있습니다. 때문에, 최악의 경우 N개의 객체를 갖은 리스트에서 특정한 값을 찾기위해서는 N번 탐색을 해야할 수 있습니다.

또한 위와같은 단일연결리스트에서는 다음 객체에 대한 포인터만을 갖기 때문에 이미 지나간 값을 참조하기 위해서는 다시 처음부터 리스트를 탐색해야하는 문제가 있습니다. 때문에 아래와 같이 여러 목적을 위한 몇가지 형태가 생겼습니다.

 2. 스택(Stack)

대표적인 LIFO(Last In First Out)의 자료형입니다. 입력되는 데이터가 층층이 쌓이는 형태로 주로 아래 그림과 같이 표현되며, 운영체제, 메모리에 대한 개념을 다룰때 많이 다루는 자료형입니다.

3. 큐(Queue)

대표적인 FIFO(First In First Out) 형태의 자료형입니다. 네트워크에서 라우터, 스위치와 같이 데이터(패킷)를 수신하여 특정한 방향으로 다시 발송하는 형태(순차적인 처리)에서 많이 채용되어 사용중에 있습니다.

4. 정리

대표적인 자료형이고, 대부분의 언어에서 기본으로 제공하거나 대표적인 라이브러리로 제공되는 자료형이기 때문에 코드로 구현해보지는 않았습니다.

특히 스택이나 큐의 경우 단순한 배열에 포인터만 추가하면 되는 형태이기 때문에 더욱이 별도로 코드를 첨부하지는 않았습니다.

궁금한 부분은 댓글로 남겨주세요~