JWT란? JWT 사이트 주소 : https://jwt.io/ JWT는 Json Web Token으로 JSON 객체의 정보를 토큰 기반의 인증 시스템을 이용하여 안전하게 정보를 전송하는 방법이다. JWT는 Base64로 인코딩되는 구조를 갖고 있다. 정리에 앞서 Base64 인코딩에 대해서 다뤄보자. Base64 인코딩 Base64는 말 그대로 64진법으로, ASCII 문자들을 표시할 수 있는 가장 큰 진법이다. (참고로 ASCII 코드에서 화면에 표시되는 문자는 128개가 되지 않는다.) 즉, Binary 데이터를 Text로 변환하는 인코딩 기능 중 하나로, 공통 ASCII 영역의 문자로 이루어진 문자열로 변환해주는 기능이다. 인코딩된 문자열은 알파벳 대소문자와 숫자, 그리고 기호 64개로 이루어지며 ..

Hash Table Hash Table은 key와 value의 구조를 자료구조다. Hash Function을 통해 Hash 값을 구해서 인덱스로 사용하고, 이 인덱스가 key가 되며, key를 통해 value를 얻을 수 있다. 버킷에 있는 해시값을 인덱스로 접근하기 때문에 탐색 시간 복잡도는 O(1)이므로 탐색 시에 효율적인 알고리즘이다. 다만 해시 테이블은 해시 함수를 구하는 과정에서 중복이 발생할 수 있으며, 이를 해시 충돌(Hash Collision)이라 한다. 해시 테이블은 다음과 같이 해시 함수, 버킷, 엔트리를 통해서 값을 보관한다. 충돌 해결 방법 해시 충돌 해결 방법으로는 개방 주소법(open-addressing)과 체이닝(chaining) 기법이 있다. 개방 주소법(open-address..

Red-Black 트리 이진 트리에서 편향 이진 트리와 같은 최악의 시간복잡도를 같는 경우를 해결하기 위해 균형 트리인 AVL트리가 존재했었다. Red-Black 트리는 AVL과 동일하게 균형 트리이지만, AVL 트리보다는 덜 균형하다는 특징이 있다. 즉, 균형트리에서 삽입이나 삭제가 많은 경우 Red-Black 트리를 사용하는 것이 유리하며, 탐색이 많은 경우 AVL 트리가 유리하다. 평균과 최악의 상황에서 검색, 삽입, 삭제 등 모두 log(N)의 시간 복잡도를 갖는다. Red-Black 트리의 규칙 Red-Black 트리에는 5가지 규칙이 있다. 해당 규칙을 위배하는 순간 노드 재배치를 진행한다. 규칙은 다음과 같다. 모든 노드는 빨강 또는 검정이다. 루트 노드는 항상 검정이다. 모든 리프 노드는 ..

AVL 트리 AVL 트리는 이진 트리의 단점 (편향 이진 트리의 경우 O(N))을 보완하기 위해 스스로 균형을 잡는 트리를 의미한다. 이 때 트리의 균형을 맞추기 위해 (좌측 자식 노드의 깊이 - 우측 자식 노드의 깊이)의 절댓값이 1이하인 경우를 유지하며, 초과할 경우 회전을 통해 균형을 맞춘다. 노드의 균형도는 다음과 같이 좌측 균형도 - 우측 균형도를 통해 계산한다. 불균형 트리 다음과 같이 균형도의 절댓값이 2 이상이 된 경우를 불균형 트리라고 부르며, 균형도가 양수이면 좌측 비대 트리, 음수이면 우측 비대 트리라고 부른다. 불균형도의 양수와 음수를 판단하여 LL, RR, LR, RL 회전을 사용하여 불균형을 해결한다. LL 회전 LL 회전은 이름 그대로 Left, Left로 치우쳐서 불균형이 발..

이진트리 트리 트리란 정점과 간선을 갖는 그래프에서 부모와 자식의 계층 구조를 갖는 자료구조를 의미한다. 이진트리를 정리하기에 앞서 트리에 대해 간단하게 정리해보자. 트리는 다음과 같이 계층 구조를 갖고 있다. 위에 있는 노드(정점)가 아래에 있는 노드의 부모가 되며, 같은 높이에 있는 노드 간은 형제 노드라고 부른다. 최상위 노드는 루트노드, 최하위 노드는 리프노드라고 칭한다. 트리는 정점(V), 간선(E) 관계에서 E = V-1 속성을 갖는다. 트리에는 레벨, 높이, 깊이를 나누어서 비교한다. 레벨의 경우 루트 노드가 있는 곳은 Level 0로 시작하고, 트리의 높이는 (리프 노드의 레벨 - 루트 노드의 레벨)로 정해진다. 트리의 깊이는 지정한 노드로 부터의 깊이를 의미하며 예를 들어서 C 노드의 깊..

재귀 재귀란 자신을 정의할 때 자기 자신을 재참조하는 방식을 의미하며, 프로그래밍에 적용한 Recursive call의 형태로 많이 사용된다. 재귀는 계속적으로 순환하기 때문에 이를 중단하는 조건 (기저 조건)이 반드시 있어야 한다. 재귀는 점화식, 분할, 백트래킹 관점에서 바라볼 수 있다. 점화식 관점 점화식 관점은 하나의 반복문으로 해결 가능한 반복 순차 방식과 하나의 반복문으로 해결하기 어려워 스택 구조의 특성을 이용하는 분할 병합 방식으로 나뉜다. 피보나치 값을 구하는 예제를 통해 점화식 관점을 살펴보자. 반복 순차 방식 public static int fibonacci(int n, int a, int b) { if (n > 5) return b; int value = (n==1 || n==2) ..

스택 스택은 한 쪽 끝에서만 데이터를 넣거나 뺄 수 있는 선형 구조로 만들어져 있으며, 데이터를 넣는 경우 Push, 꺼내는 경우 Pop을 이용한다. 마지막에 들어간 데이터가 가장 먼저 나온다는 LIFO(Last In First Out)의 특징을 갖고 있다. 스택은 웹 브라우저의 뒤로가기, 뒤로가기 단축키 (ctrl + z), 후위 표기법, 재귀 알고리즘 등에서 사용된다. 스택 구현 스택은 배열과 리스트로 구현할 수 있다. 배열의 경우 간단하지만, 고정길이를 벗어나는 경우를 대비하기 어렵다. 따라서 스택의 경우 리스트로 구현하여 필요한 만큼 메모리를 사용하고, 가변길이에 대응하는 예제를 진행해보자. package ds; public class StackByList { private Node head; p..

연결 리스트 연결 리스트란 각 노드가 데이터와 참조값을 갖고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조라 한다. head: head는 연결 리스트의 시작으로 첫 번째 노드를 가리키는 노드를 의미 한다. Node : 데이터와 다음 노드로 접근할 수 있는 참조값을 가지고 있다. Pointer : 노드의 참조 값을 가리키는 변수를 의미한다. Array vs LinkedList 조회가 많은 경우 Array를 사용, 삽입 또는 삭제가 많은 경우 LinkedList를 사용하는 것이 적합하다. 단일 연결 리스트 장점 : 저장 될 데이터 수를 몰라도 사용할 수 있다. 또한 사용한 만큼 메모리 공간을 할당하기 때문에 효율적인 메모리 관리를 할 수 있다. 단점 : 하나의 연결만을 가지고 있기 때문에 순차적..