이제 스프링 Boot에서 JWT를 사용해서 토큰을 생성하는 방법에 대해서 알아보자. 프로젝트 구성 의존성JWT를 자바에서 사용하기 위해서는 여러가지 라이브러리가 있는데 여기서는 jjwt라는 녀석을 사용해보자. 이를 위해 다음의 의존성을 추가한다. 이 녀석의 역할은 토큰은 base64로 인코딩 하거나 signature를 만들고 검증하는 역할등을 수행한다. io.jsonwebtoken jjwt-api 0.12.6 io.jsonwebtoken jjwt-impl 0.12.6 runtime io.jsonwebtoken jjwt-jackson 0.12.6 runtime application.ymlapplication.properties에는 사용자 정의 속..

이번에 살펴볼 투 포인터나 다음에 살펴볼 슬라이딩 윈도우는 모두 1차원 배열 상에서 O(N*M)의 시간 복잡도로 해결해야 할 일들을 O(N)에 해결하게 도와주는 알고리즘이다.  특별하게 코드가 복잡하지도 않고 쉽게 이해할 수 있는데 왕왕 써먹을데가 많은 알고리즘 중 하나이다. 투 포인터(Two Pointer) 알고리즘  문제 살펴보기먼저 Tow Pointer를 이용해서 풀어볼 수 있는 간단한 문제를 살펴보자.https://www.acmicpc.net/problem/2018 2018번: 수들의 합 5어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어..

이번 포스트에서는 JWT의 개념과 기본 동작에 대해 살펴보자.  Session Cookie와 JWT를 통한 인증의 차이 Session Cookie 활용session cookie는 전통적인 server의 인증 방식이다.클라이언트가 id/pass를 가지고 서버로 로그인 요청을 한다. 서버는 db server를 이용해 해당 사용자가 valid한지 점검하고 결과를 반환한다.로그인 성공 시 서버는 session store에 세션 공간을 할당하고 이 공간에 접근할 수 있도록 session cookie를 response로 내려보낸다.작업을 요청할 때 client는 session cookie를 request에 포함시켜 서버로 전송한다.서버는 이 cookie 값으로 로그인한 적이 있는지 session store에 확인..

이번 포스트에서는 위상정렬 알고리즘에 대해 살펴보자.위상정렬 알고리즘 문제제시https://www.acmicpc.net/problem/14567  위상정렬 알고리즘이란?위상정렬(位相整列:  Topological Sorting)이란 노드 간의 위치(선-후관계)에 따라 모든 정점들을 배열하는 작업을 말한다. 주로 업무의 일정을 일이 진행되어야 할 순서에 따라 배치하기 위해 사용되는 알고리즘이다. 대표적으로 과목들간의 선수관계에 따른 수강 계획을 작성한다든가 게임에서 어떤 빌딩을 생성하기 위한 테크트리를 떠올리면 쉽다.대부분의 위상 정렬 문제들은 선-후 관계에 위배되지 않는 경우 중 하나를 출력하는 문제들이다.그래프 요소들이 정렬되기 위해서는 당연히 명확한 순서가 있어야 한다. 따라서 위상 정렬은 DAG(di..

이번에는 최단 경로의 마지막 알고리즘인 플로이드 워셜 알고리즘에 대해서 살펴보자. 플로이드 워셜 알고리즘 플로이드 워셜의 특징이제까지 다익스트라와 벨만포드 알고리즘을 이용한 최단 경로를 구해봤다. 한 점에서 모든 점까지의 최단 거리를 구할 수 있었고 여차하면 음의 간선까지 처리할 수 있었는데 또 필요한 최단 거리 알고리즘이 있을까?있으니까 여기서 글을 쓰고 있다. ㅎ이번에 알아볼 알고리즘은 플로이드 워셜 알고리즘이다. 플로이드는 이전까지의 알고리즘과 달리 모든 정점에서 모든 정점까지의 최단거리를 구하기 위한 알고리즘이다.물론 다익스트라, 벨만포드의 모든 정점을 출발점으로 해서 N번 돌리면 모든 정점에서의 최단거리를 구할 수 있다. 하지만 플로이드 워셜은 대체로 다익스트라, 벨만포드를 N번 돌릴 때보다 빠..

이번 포스트에서는 음의 가중치를 갖는 간선에서 최단 거리를 구할 수 있는 벨만포드 알고리즘에 대해 살펴보자. 벨만포드(Bellman-Ford) 알고리즘 다익스트라의 한계이전 글에서 다룬 다익스트라 알고리즘은 검증된 그리디한 알고리즘으로 매번 최선의 선택을 하기 때문에 상당히 빠른 시간에 최단 경로를 구할 수 있다. 하지만 나중에 발견된 경로에서 음의 가중치가 발견되면 이전의 선택이 최선이 아니기 때문에 사용할 수 없다. 벨만포드 알고리즘벨만포드는 다익스트라 처럼 가중치 그래프에서 출발점에서 다른 모든 정점까지의 최단 거리를 찾는 알고리즘이다. 단 다익스트라와 달리 음의 가중치를 처리할 수 있으며 간선 중심의 알고리즘이다.벨만포드는 최단 거리의 정점만을 찾아다니지 않고 시작 정점에서 각 정점까지의 최단 거..

이번 포스트에서는 발음이 정말 생소한 다익스트라 알고리즘에 대해서 살펴보자. 이 알고리즘은 에츠허르 다익스트라라는 네델란드 개발자분이 고안한 알고리즘이라고 한다. 튜링상을 받은 어마어마한 분이다.! 다익스트라 알고리즘이란?다익스트라 알고리즘은 특정 시작 정점에서 거리가 최소인 정점을 계속해서 선택해 나가다보면 결국 각 정점까지의 최단거리를 구할 수 있다는 생각에서 출발한 알고리즘이다.다익스트라 알고리즘은 현재 상태에서 가장 최선이라고 생각되는 정점들을 쭉~탐색해 나가는 그리디 알고리즘이다. 검증이야 이미 다익스트라 아저씨가 잘 해놓은 상태이다. ㅎ아래와 같은 그래프를 생각해보자. 출발점 S에서 목적지 D로 가는 경로는 총 3가지가 가능하다.S->D로 한방에 갈 수도 있지만(W_SD = 50) 이 길은 시..

이번 포스트에서는 알고리즘 문제에 자주 나오는 "최단 경로"문제를 해결하기 위한 알고리즘들에 대해서 살펴보자. 최단 경로란? 최단 경로란 그래프를 탐색하면서 임의의 두 정점 사이에 다양한 간선의 조합 중 간선의 가중치의 합이 최단인 경로를 의미한다. 이 최단거리를 구할 때는 크게 간선의 가중치가 없는 경우와 있는 경우 두 가지 경우로 나눌 수 있다. 가중치가 없는 그래프가중치가 없는 경우 즉 모든 정점간의 이동 비용이 동일한 경우는 BFS 탐색이 가장 간단하다. 이때 BFS의 depth가 총 비용이 된다. 예를 들어 아래와 같은 그래프를 살펴보자.만약 서울에서 출발해서 부산에 도착하는데 각 도시 간 이동 비용이 동일하다면 서울에서 원주, 대구를 찍고 부산에 도착하는게 depth(==비용) 3으로 가장 짧..