-
websocket, socket.io를 이용한 양방향 통신
웹 브라우저에서 양방향 통신을 가능하게 해주는 websocket, socket.io에 대해 공부한 내용에 대하여 정리했습니다. 웹 브라우저 에서의 양방향 통신 기존 웹페이지에서 사용하는 http 프로토콜은 요청/응답 패러다임이기에 클라이언트에서 요청을 보내야만 그에 대한 응답을 받습니다. 옛날 홈페이지의 경우에는 동적인 홈페이지가 거의 없어서 큰 문제가 없었으나 동적인 기능이 많이 요구가 됩니다. 그러다 보니 요청을 보내지 않아도 서버에서 클라이언트쪽으로 데이터를 보내야 하는 경우도 종종 생기고는 합니다. 하지만 http 프로토콜로 통신하는 경우 특성상 연결이 유지되지 않아서 서버에서 먼저 요청을 보내는 것이...
-
Graph Neural Network
Graph Neural Network GNN (Graph Neural Network)는 그래프 구조에서 사용하는 인공 신경망을 말합니다. 우리가 흔히 알고 있는 인공 신경망에는 가장 기본적인 Fully-connected network 그리고 CNN (Convolutional Neural network)나 RNN (Recurrent Neural network)가 있습니다. 이러한 인공 신경망들은 보통 벡터나 행렬 형태로 input이 주어지는데 반해서 GNN의 경우에는 input이 그래프 구조라는 특징이 있습니다. 이 글에서는 GNN의 기본 원리와 GNN의 대표적인 예시들에 대해서 다루도록 하겠습니다. Neighborhoods Aggregation GNN은 입력으로 그래프 구조와 각 노드별 feature 정보를 받습니다. 입력으로 받은 feature...
-
Python의 큰 정수 표현법 3 - 기타 연산
이전 글 Python의 큰 정수 표현법 1 Python의 큰 정수 표현법 2 개요 지난 글들에서는 Python의 int가 큰 정수를 표현하기 위해 어떤 구조를 사용하고, 그 값을 C의 기본 자료형이나 문자열로 변환하는 방법이 무엇인지, 오브젝트끼리의 비교를 어떻게 하는지, 사칙연산은 어떻게 적용시키는지 등에 대해 알아보았습니다. 이번 글에서는 한 걸음 더 나아가, 지금까지 다루지 않은 몇 가지 연산들과 기타 기능들에 대해 알아보겠습니다. 단항 연산자 본격적으로 어렵고 복잡한 연산자들에 들어가기 전에, 간단한 단항 연산자들을 몇 가지 살펴봅시다.. 부호 변경...
-
빠른 격자점 세기
서론 우리는 어떤 그래프 내부의 격자점을 세어야 할 일이 있는 경우가 있다. 예를 들면, 원 안의 격자점의 갯수를 세는 것은 $\pi$ 의 값과 피타고라스 쌍과 관련이 있으며, 약수의 갯수의 합을 구하려 $f(x) = \frac{N}{x}$ 내부의 격자점의 수를 세기도 한다. 여기서는 이 전략을 구체화 시켜서 convex hull 위의 점의 갯수로 문제를 푸는 방법에 대해 알아보고, 또한 약수의 갯수를 $\tilde{O}(n^{\frac{1}{3}})$ 에 세는 방법을 알아본다. 약수 두 자연수 $A$, $B$에 대해서 $B$로 $A$를 나눴을 때 나누어 떨어지면, 우리는...
-
Treap
목차 1. 개요 2. 개념 3. 구현 4. 응용 5. 문제풀이 6. 마무리 7. 참고자료 개요 이 포스트를 쓰며 언제 한번, Treap의 활용성에 대해서 적고 싶었다. 물론 여기서 내가 여러분에게 소개하고자 하는 것은 Treap을 BST로서 다루는 것이 아닌, 배열을 자유롭게 붙이고 떼고 뒤집는 것에 설명하기 위함이다. Treap은 기본적으로 BST로서 사용할 수 있지만, Splay Tree 처럼 배열을 다루는 데 사용할 수 있다. Splay Tree 처럼 여러가지의 method 들을 활용하여 amortized 시간을 내는것은 아니고, 확률에 의존하는 경향이...