Directed graph란 유방향 간선으로 이루어진 그래프를 의미합니다. 이에 대치되는 개념은 앞선 시간에서 살펴보았던 undireced graph, 즉 무방향 간선으로 이루어진 그래프입니다. Directed graph에서 간선 정리 Undirected graph에서 그래프 탐색을 할 때는 DFS의 경우 unvisited, discovery, back edge의 3가지 간선 종류가 있었고, BFS의 경우에는 unexplored, discovery, cross edge의 3가지 간선 종류가 있었습니다. Directed graph의 탐색된 간선은 4가지가 있는데, 이를 정리해 보도록 하겠습니다. 정점 v에서 시작하여 DFS와 BFS 등으로 탐색된 경로가 정점 v를 루트로 하는 트리와 같은 형식이라는 것을 ..
Breadth First Search(BFS)는 그래프 탐색 방식중 하나이다. BFS는 시작 정점을 기준으로 가까운 정점부터 차례대로 방문하는 방식이다. 이런 특성을 통하여 가중치가 없는 간선 그래프에서 가장 가까운 경로를 발견할때 사용할 수 있다. 구현 시작 정점 v에서 출발하고, 큐 Q에 시작 정점을 추가하고 VISITED 상태로 만든 후 다음 과정을 반복한다. 1. Q가 비었다면 종료한다. 정점이 있다면 해당 정점 v에 대하여 다음을 실행한다 2. v에 인접한 정점중 UNVISITED인 정점을 큐에 삽입하고, VISITED상태로 변경한다. 용어 unvisited vertex: 아직 방문하지 않은 정점 visited vertex: 방문한 정점 unexlored edge: 아직 방문하지 않은 간선 di..
Depth First Search(DFS)는 그래프 탐색 방식중 하나이다. DFS의 방식은 분기점이 생겼을시, 우선 무시하고 한 방향의 끝에 다다를때 까지 진행한 후, 하나의 경로를 완전히 탐색했으면, 분기점으로 돌아가 분기점을 탐색하는 방식이다. 구현 시작 정점 v에서 출발하여, 다음과 같은 과정을 거친다. 1. 현재 정점이 VISITED라면 재귀를 종료하고 다시 돌아가기 2. 현재 정점을 VISITED로 설정(중복 방문을 막기 위하여) 3. 연결되어 있는 다른 정점 탐색 4. 연결된 모든 다른 정점에 대하여 해당 알고리즘 반복 용어 unvisited vertex: 아직 방문하지 않은 정점 visited vertex: 방문한 정점 unvisited edge: 아직 방문하지 않은 간선 discovery ..
서비스 제작을 위한 앱 개발 수단을 찾아야 했다. 필요 사항은, 빠르게 개발 가능하고, 유지보수의 용이성을 위해 인력이 많은 개발 방식이 필요했다. 크로스플랫폼 고려 처음으로 고려한 것은 네이티브 대신 크로스플랫폼 프레임워크를 사용하는 것이었다. 가장 사용률이 높은 Flutter(플러터)와 React native(RN)를 중심적으로 봤었다. 플러터는 구글에서 관리하고, 자체 언어인 Dart언어를 이용한다. RN은 메타에서 관리하고, React와 비슷하게 자바스크립트를 이용한다. 크로스플랫폼으로 제작하면, 각 안드로이드 개발자와 IOS개발자로 앱 개발자를 두 분류로 나누어 구할 필요가 없어, 단순히 보았을 때 2배의 생산성을 보여준다. 또한 IOS개발 같은 경우에는 애플 기기가 필요한 등 접근 장벽이 높아..
템플릿(Template) 템플릿이란, 장고 뷰에서 웹사이트를 반환할 때, 웹사이트 정보를 하드코딩으로 생성하지 않고, 다르게 관리할 수 있게 해주는 장고의 기능이다. 사이트 생성을 도와주는 것이기에, 장고를 DRF 등의 프레임워크를 통해 REST API를 사용하는 API 서버용으로 사용한다면 이용할 일이 없는 기능이다. 이때 템플릿은 .html의 파일로 생성을 하며, 내부의 파일은 완전한 html은 아니고, 장고의 템플릿 태그(template tag)를 문법이 추가된 형태이다. 템플릿 파일 작성 위치 그렇다면 템플릿은 어느 위치에 정의할까? 이것에는 크게 2가지 방법이 보통 사용된다. 첫 번째는 각 앱의 templates/ 폴더를 정의해 각 앱별로 모아두거나, 프로젝트의 매인앱에 templates/ 폴더..
그래프는 정점과 간선의 집합으로 이루어진 자료구조이다. 정점(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..
