2021/11
-
AVL Tree : Balancing 작업을 통해 최대 Height를 조절하는 BSTData Structure 2021. 11. 30. 00:10
AVL Tree AVL 트리는 아래의 성질을 만족하는 BST(Binary Search Tree)의 한 종류다 Tree 상의 모든 Node p에 대해 p의 left subtree와 right subtree의 height 차이가 최대 1을 넘을 수 없다 이러한 성질을 AVL 트리의 Balanced Property라고 하며, 일반적인 BST와 비교했을 때, Search 연산은 완전히 동일하지만 Insert/Delete 연산을 할 때 이 성질이 깨지지 않도록 추가적인 연산을 수행한다 위의 그림에서 12라는 노드를 추가했을 때, 해당 노드를 자손으로 가지는 노드들(4, 8, 15, 10, 12)의 height가 변한다 그리고 노드 15를 봤을 때 왼쪽 서브트리의 height가 2, 오른쪽 서브트리의 height가..
-
Binary Tree에서 Height를 조절하기 위한 Tree RotationAlgorithm 2021. 11. 29. 00:28
BST(Binary Search Tree)는 아래와 같은 편향 이진 트리(Skewed Binary Tree)일 경우, 성능이 악화된다 Complete Binary Tree일 때 탐색 시간복잡도는 O(log N)이지만, (최악의 경우) 연결리스트의 형태를 한 Skewed Binary Tree일 경우 시간 복잡도가 O(N)에 수렴한다 이러한 편향 현상은 BST에서 Insert, Delete 연산으로 인해 발생할 수 있어서, 이를 보완하기 위한 자료구조로 자가 균형 이진 탐색 트리(Self-Balanced Binary Search Tree)가 존재한다 그 대표적인 예시인 AVL Tree와 Red-Black Tree에서도 아래에서 소개할 Rotation 연산을 이용해서 스스로 Height 균형을 유지하기 때문에..
-
대칭 키/공개 키/단방향 암호화 알고리즘(정의와 예시)Algorithm 2021. 11. 12. 02:49
암호화 알고리즘은 암호화/복호화에 사용되는 키, 그리고 양방향 가능 유무를 기준으로 분류할 수 있다. Symmetric-Key Algorithm 대칭 키 알고리즘 대칭 키 암호는 암호화 알고리즘의 한 종류로, 암호화와 복호화에 같은 암호 키를 사용하는 알고리즘을 의미한다. 암호화를 하는 송신자가 평문을 암호화 하고, 해당 암호 키를 공유해서 복호화를 하는 수신자는 암호문을 복원한다. 공유되는 암호 키를 대칭 키라고 한다. 공개 키 암호화 방식과 비교해서 계산 속도가 빠르다는 장점이 있지만, 같은 키를 공유해야 하기 때문에 언젠가 한 번은 키를 전달해야 한다. 이 때, 키를 전송하는 과정에서 정보를 탈취당할 수 있다는 위험성이 있다. Public-Key Algorithm 공개 키(비대칭 키) 알고리즘 암호..
-
StackOverflowError가 뭘까? (사이트 아님)Programming/Java 2021. 11. 8. 22:22
https://stackoverflow.com/questions/3197708/what-causes-a-java-lang-stackoverflowerror/3197731 What causes a java.lang.StackOverflowError What can cause a java.lang.StackOverflowError? The stack printout that I get is not very deep at all (only 5 methods). stackoverflow.com When a function call is invoked by a Java Application, a stack frame is allocated on the call stack. The stack frame contai..
-
좋은 Pull Request를 만드는 방법과 PR Template 구성Project 2021. 11. 5. 19:55
https://docs.github.com/en/communities/using-templates-to-encourage-useful-issues-and-pull-requests/creating-a-pull-request-template-for-your-repository Creating a pull request template for your repository - GitHub Docs For more information, see "About issue and pull request templates." You can create a PULL_REQUEST_TEMPLATE/ subdirectory in any of the supported folders to contain multiple pull ..
-
JWT(Json Web Token) - 비대칭키 기반 토큰 인증 방식Web 2021. 11. 4. 21:21
JSON Web Token은 비대칭 암호화 알고리즘을 사용하는 토큰형 인증 방식의 하나로, Claim 기반의 토큰이다. 토큰 자체를 정보로 사용하는 Self-Contained 방식을 이용해서 정보를 안전하게 전달할 수 있다. 서명된 토큰은 해당 토큰에 포함된 클레임의 무결성을 확인할 수 있고, 암호화된 토큰은 다른 당사자의 클레임을 숨긴다. 공개키/개인키 쌍을 사용해서 토큰에 서명하면 개인 키를 보유한 사람만 토큰에 서명했음을 인증한다. JWT는 언제 사용할까 ❓ 인증/인가 JWT를 사용하는 가장 보편적인 방법이다. 사용자가 로그인하면 이후 모든 요청에 JWT 토큰을 헤더에 담아 인증할 수 있다. JWT를 이용하면 해당 토큰으로 허용되는 경로, 서비스, 리소스에 접근할 수 있다. 오버헤드가 적고 여러 도..
-
화상 미팅을 간단하게 구현할 수 있는 Kurento와 Openvidu 프레임워크Web 2021. 11. 4. 02:15
https://2jinishappy.tistory.com/248?category=948597 WebRTC - 웹 브라우저 간 실시간 미디어 통신 기술 WebRTC: Web Real-Time Communication 웹 브라우저 간에 플러그인의 도움 없이 서로 통신할 수 있도록 설계된 API 2020년 이후 COVID-19로 인한 비대면 수업, 화상 회의, 재택 근무가 증가하면서 스트리밍 서비 2jinishappy.tistory.com 이전에 미디어 통신 기술인 WebRTC에 대해 알아봤다. 이번에는 WebRTC를 기반으로 동작하는 프레임워크인 Kurento와 Openvidu를 왜 사용하고 어떤 장점이 있는지 소개할 것 이다. Kurento 쿠렌토는 WebRTC 미디어 서버이자 클라이언트 API 세트이면서..
-
NAT와 포트포워딩 - 패킷의 IP와 Port 번호 변환하기Computer Science/Network 2021. 11. 1. 22:23
NAT : Network Address Translation IP 패킷의 TCP/UDP Port Number와 출발지(Source), 목적지(Destination) IP 주소를 재기록 하면서 라우터를 통해 네트워크 트래픽을 주고 받는 기술 위의 그림처럼 Host - Router - Server를 거치는 과정에서 패킷은 많은 네트워크 단말을 거치게 되는데, 그 과정에서 출발지의 (IP, Port Num)과 도착지의 (IP, Port Num)과 같은 데이터는 계속해서 변할 수 있다. 패킷에 변화가 생기기 때문에 IP나 TCP/UDP의 체크섬도 다시 계산해서 재기록해야 한다. IPv4를 사용할 때 가능한 최대 IP 개수는 255^4 = 4,228,250,625(약 40억)로 한정되어 있기 때문에, 제한된 수의..