그래프는 정점과 간선의 집합으로 이루어진 자료구조이다. 정점(vertex)는 노드(node)라고도 부른다. 간선(edge)는 정점의 쌍으로 표현되는데, 간선을 통해서 정점 사이를 이동할 수 있다. 이때 간선에 방향이 존재하면 directed edge, 존재하지 않으면 undirected edge라고 하는데, 모든 간선이 directed edge인 그래프를 directed graph, 모든 간선이 undirected edge인 그래프를 undirected graph라고 한다. 용어 directed edge: 방향이 존재하는 간선. undirected edge: 방향이 존재하지 않는 간선. directed graph: 모든 간선이 directed edge인 그래프. undirected graph: 모든 간선..
카카오 소셜 로그인을 백엔드 서버와 프론트엔드(앱, 웹) 둘을 사용하는 서비스에서 구현하다보면, 카카오 로그인을 어떻게 구현하고 이들을 어떻게 서버와 잘 교환할지 고민이 생길 수 있다. 카카오 로그인 카카오 소셜 로그인은 타 OAuth와 같은 방식으로 이루어진다. REST API를 기준으로는 적절히 client_id와 redirect_uri를 포함하여 링크로 요청을 하고, 사용자가 여기서 로그인을 하면 code를 포함하여 redirect_uri로 리다이렉트 된다. 이때 이 code를 적절히 개발자가 받아서 카카오 소셜 서버와의 적절한 통신을 하고 최종적으로 access_token을 받는 방식이다. 앱의 SDK등의 기준으로는 그냥 위의 과정이 SDK에서 적당히 자동으로 처리되고 바로 access token..
해시 테이블(Hash table) 해시 테이블은 해시 함수를 이용하는 자료구조로 dictionary의 기능을 한다. 기본적인 원리는 적당한 크기의 공간(배열)을 할당해 두고, 특정 키 x로 접근할 시에 해당 키를 해싱하여 나온 값 h(x)를 배열의 인덱스로 이용하여 배열을 즉시 탐색하는 방식이다. 이진 탐색 트리와의 비교 해시 테이블은 맵 자료구조를 만들 때 유용한데, 이전에 소개한 이진 탐색 트리가 O(h)에 접근이 가능한 것과 달리 O(1)에 접근이 가능하다. 그러나 이진 탐색 트리는 범위를 두고 쿼리가 가능한 반면, 해시 테이블은 정확한 키값을 지정해 줘야 탐색이 가능하다. 공간 면에서도 이진 탐색 트리는 당장 필요한 만큼의 공간을 사용하지만, 해시 테이블은 사용할 공간을 에측해서 미리 할당해 두어..
요 며칠간 소셜 로그인을 구현하는 방식에 대해 찾아보고 고민해 본 결과를 정리합니다.소셜 로그인소셜 로그인이란 저희가 서비스에 가입할 때 흔히 보는 애플 로그인, 네이버 로그인, 카카오 로그인등을 의미합니다. 이러한 소셜 로그인들은 많은 수는 OAuth2.0이라 하는 프로토콜에 따라서 로그인을 방식을 제공하고 있습니다. 대략적인 OAuth 과정은, 유저가 소셜 서비스 제공 사이트에서 로그인을 하고 하면 유저의 소셜 서비스에서의 정보를 가져올 수 있게 되고, 이를 통해 자체적으로 로그인/유저 서비스를 만들고 제공하는 느낌입니다.여기서 말할 점은 결국 소셜 서비스에서 모든 것을 제공해주지 않고, 실제 유저 기능은 자체적으로 구현을 해야 한다는 점입니다. 이를 도와주는 많은 라이브러리도 제공되고 있어 이러한 ..
이전 시간에 살펴보았던 이진탐색트리는 O(h)의 시간 복잡도를 가지기에, 높이의 균형을 유지하여야 O(log n)의 효율을 유지할 수 있었다. 이렇게 밸런스를 유지하는 방법으로는 height-balanced와 weight-balanced의 방식이 있는데 그중 height-balanced 트리는 대표적으로 AVL 트리와 레드-블랙 트리가 존재한다. 이번 글에서는 이 중 AVL 트리에 대해서 다루어 보려 한다. AVL 트리 AVL 트리의 정의는 모든 노드 v에 대하여 v 양옆의 자식들의 높이(height) 차이가 1 이하인 이진탐색트리를 의미한다. AVL트리의 효율 증명 이러한 방식으로 AVL트리를 제작했을 때 이 효율이 O(log n)인 것의 증명을 서술...나중에 한다. ADT search(key) in..
dj-rest-auth는 업데이트가 중단된 django-rest-auth를 잇는 프로젝트입니다. 기능으로는 DRF를 베이스로 인증과 관련된 기능들을 간단하게 제공해 주고, django-allauth와 함께 사용하여 소셜 로그인(OAuth) 로그인과 이메일 인증등의 기능도 탑재되어 있습니다. 또한 djangorestframework-simplejwt등과 함께 사용하여 JWT기능도 지원하고 있습니다. dj-rest-auth의 기능 REST API 인증/유저 기능 dj-rest-auth가 기본적으로 제공하는 기능은 DRF에 맞춰 REST API로 인증기능을 지원하는 것입니다. DRF는 기본적으로 따로 편리하게 제공되는 유저 인증기능은 따로 없어서 일일이 제작해야 했습니다. dj-rest-auth는 우선 기본적..
MVC 패턴 장고의 뷰는 MVC패턴의 컨트롤러에 대응하는 부분이다. 뷰(View) 뷰는 클래스로 만드는 class-based-view 나 함수로 만드는 방식이 존재한다. 이번 글에서는 기초적인 함수형 뷰에 대해 소개하겠다. 뷰는 기본적으로 첫 번째 인자에 HttpRequest형의 객체를 일반적으로 request라는 이름으로 전달받는다. 이때 뷰의 이름은 임의로 정할 수 있다(임의로 정한 이름을 URL에 맵핑하기만 해 주면 되기 때문에). # books/urls.py from django.urls import path from books import views urlpatterns = [ path("/", views.index), ] # books/views.py def index(request: Http..
이진 탐색 트리는 이진트리로서, 중위순회(In-order traversal) 시 정렬된 형태라는 특징을 가지고 있다. ADT lookup(key): key값을 가지는 노드를 리턴하고, 없다면(NULL일시) NULL의 부모를 리턴한다 put(key): key값을 가지는 노드에 삽입한다. delete(key): key값을 가지는 노드를 삭제한다. 구현 이진탐색트리 구현의 핵심은 계속 중위순회순으로 정렬된 상태를 유지하는 것이다. 탐색 루트에서 시작해서 노드의 값이 탐색값보다 크면 left child로 탐색, 작으면 right child로 탐색을 반복하면 된다. 삽입 삽입은 탐색을 한 후 값을 변경하거나 추가만 해주니 단순하다. 경우를 나누어 보자면, 탐색하여 노드를 발견했다면 그대로 값을 수정하면 되고, 값..
맵 & 딕셔너리(Map & Dictionary) 맵과 딕셔너리는 매우 유사한 자료구조다. 이에 맵에 대해서 먼저 설명하고, 맵과 딕셔너리의 차이점을 알아보겠다. 우선 맵은 키-값(key-value) 쌍으로 이루어진 집합이다. 키를 통해서 값을 추가, 탐색하고 이를 수정, 삭제할 수 있다. 이때 맵의 특징은 같은 키를 가지는 여러 값이 존재할 수 없다는 것이다. 그렇다면 딕셔너리는 무엇일까? 딕셔너리는 기본적으로 맵과 동일하지만, 중복된 키값이 존재할 수 있다는 특징이 있다. 다만 실제로 맵과 딕셔너리의 차이를 엄밀하게 다들 지키는 것은 아니고, 반대의 의미로 쓰이거나 하여 사실상 같은 의미를 가진다고 볼 수 있다. 예를 들어 파이썬의 딕셔너리는 기본적으로 키 중복을 허용하지 않지만 딕셔너리(dict)라는..
