[자료구조] - B-Tree

2022.06.10· 자료구조

Multiway Search Tree (다원 탐색 트리) / m-way Search Tree (m 분기 탐색 트리) 한 노드가 가질 수 있는 key의 값이 최대 m-1개이고 가질 수 있는 Child의 수가 m개인 트리를 Mulituway Search Tree라 합니다. 이진 트리 : 2-way search tree AVL 트리 : 2-way search tree 2-3 트리 : 3-way search tree 정의는 다음과 같습니다. m-way Search Tree는 다음을 만족하는 검색 트리입니다. 1. Leaf Node를 제외한 모든 노드는 m개 이하의 서브 트리를 가집니다. 2. k개의 자식 노드를 갖는 노드는, k-1개의 요소(key)를 가집니다. 3. 각 노드의 key는 오름차순으로 정렬되어 있..

[자료구조] - 2-3 Tree

2022.06.10· 자료구조

2-3 Tree 2-3트리는 검색 트리이지만 BST는 아닙니다. 차수가 3인 노드가 존재할 수 있으므로, Binary가 아니기 때문입니다. 2-3 Tree는 트리의 높이가 균형을 이루며 내부노드의 차수가 2 또는 3인 균형 탐색트리입니다. 2-3 Tree 조건 2-3 Tree에는 Internal Node와 External Node의 개념이 존재합니다. Internal Node(내부노드)는 Key가 들어있는 내부 노드이며, External Node(외부노드)는 데이터가 들어있지 않은 노드로써 Internal Node의 Leaf Node의 자식으로 존재하는 가상의 노드입니다. 2-3 Tree에서 각각의 내부 노드는 2-Node 이거나 3-Node 입니다. 중복된 Key는 허용하지 않습니다. 2-Node는 1..

[자료구조] - AVL 트리

2022.06.09· 자료구조

BST의 문제점 일반적인 BST(이진 검색 트리)는 데이터가 삽입되는 순서에 따라 한쪽으로 편향되는 형태로 트리가 형성될 수 있습니다. 예를 들어 입력열이 50 -> 30 -> 100 -> 20 -> 150 인 경우 다음과 같습니다. 그러나 입력열이 20 -> 30 -> 50 -> 100 -> 150 인 경우 다음과 같습니다. 이렇게 BST는 트리의 높이를 $log(n)$ 으로 보장받지 못할 가능성이 있습니다. 트리에서의 성능은 트리의 높이와 연관되어 있습니다. 즉 트리의 높이가 $log(n)$을 보장받지 못한다면, BST의 삽입과 삭제, 검색의 연산 역시 시간복잡도 $O(log(n))$을 보장받지 못합니다. AVL 트리 AVL 트리는 이진 검색 트리(BST)의 한가지 종류로써 스스로 높이의 균형을 잡는..

[자료구조] - Hash(해시)

2022.06.07· 자료구조

들어가기에 앞서 해시가 어디에 쓰이는지 알아보도록 하겠습니다. 유튜브를 예시로 생각해 보도록 하겠습니다. 제가 어떤 사람의 동영상을 그대로 제 채널에 올리려고 한다면, 그 순간 바로 유튜브에서 중복되는 동영상이라는 에러 메세지를 보내줍니다. 동영상은 크기도 매우 크고, 그 수도 매우 많습니다. 그렇게 많은 동영상 중에서 어떻게 중복되는 동영상인지를 빠르게 판단할 수 있을까요? 앞으로 살펴볼 자료구조인 해시테이블이 바로 이것을 가능하게 만들어줍니다. Hash Function (해시 함수) 해시 함수 (Hash Function) 또는 해시 알고리즘은 임의의 데이터를 배열의 인덱스로 매핑(변환)하는 함수입니다. 해시 테이블은 배열입니다. 따라서 인덱스를 통해 접근할 때에는 O(1)의 시간복잡도로 매우 빠르게 ..

[Spring] 쉬운 확장이 가능한 OAuth2.0 로그인 구현(카카오, 네이버, 구글 등) (Security 사용 X)

2023.07.27· 🏝️ Spring

(전 순정 백엔드 개발자기 때문에 React는 못합니다. React 코드는 Chat GPT 시켜서 구현하였고, 대신 백엔드에 온 진심을 담하서 구현하였으니, 프론트 코드는 정말 그냥 테스트용으로만 참고해 주시면 감사하겠습니다.) OAuth의 개념에 대해서는 이미 많은 블로그들에서 다루고 있으므로 저는 이에 대해서는 따로 다루지 않겠습니다. 이 글에서는 (적어도 제가 살펴보았던) 대부분의 블로그에서 애매하게 설명되어있는 프론트엔드와 백엔드의 역할과, 실제로 어떻게 구현하는지를 집중적으로 다뤄보도록 하겠습니다. 또한 이 과정에서 단순히 구현하고 끝내는 것이 아니라 새로운 타사 플랫폼을 추가하는 과정도 간단하게 처리할 수 있도록 유연하고 확장 가능한 구조를 가져가는 코드를 작성해보도록 하겠습니다. 소스 코드는..

[JPA] N+1 문제가 발생하는 여러 상황과 해결방법

2023.01.07· JPA

🧐 N + 1 문제N + 1 문제는 연관관계가 설정된 엔티티 사이에서 한 엔티티를 조회하였을 때,조회된 엔티티의 개수(N 개)만큼 연관된 엔티티를 조회하기 위해 추가적인 쿼리가 발생하는 문제를 의미합니다. 즉 N + 1에서, 1은 한 엔티티를 조회하기 위한 쿼리의 개수이며, N은 조회된 엔티티의 개수만큼 연관된 데이터를 조회하기 위한 추가적인 쿼리의 개수를 의미합니다. N + 1보다는, 1 + N이라 부르는 것이 더 이해하기 쉬우며, 정리하면 다음과 같습니다.엔티티 조회 쿼리(1 번) + 조회된 엔티티의 개수(N 개)만큼 연관된 엔티티를 조회하기 위한 추가 쿼리 (N 번) 🧐 발생하는 상황N + 1 문제가 발생하는 상황을 알아보기 위해 게시글과 댓글을 예시로 사용해 보도록 하겠습니다. 하..

[Spring] 동시성 문제 해결방법 (4) - Redis 사용(Lettuce, Redisson)

2023.11.13· 🏝️ Spring

🤔 서론 이번 글에서는 Redis를 사용하여 분산락을 구현해 보도록 하겠습니다. Java의 Redis 클라이언트로는 Jedis, Lettuce, Redisson 등이 있으며, 각각의 특징이 서로 다릅니다. 이중에서 Jedis는 제외하고 Lettuce와 Redisson을 사용해서 분산락을 구현해 보도록 하겠습니다. (Jedis와 Lettuce의 비교는 다음 글을 참고해주세요) 🤔 Redis 환경 설정 아래 명령어를 통해 redis를 다운받아줍니다. (반드시 도커를 사용할 필요는 없습니다.) docker pull redis 이후 레디스를 실행시켜줍니다. docker run --name redis -d -p 6379:6379 redis 프로젝트에서는 Redis 관련 의존성을 추가해주도록 하겠습니다. imple..

[Spring] 동시성 문제 해결방법 (3) - USER-LEVEL Lock(Named Lock) 사용

2023.11.06· 🏝️ Spring

🤔 서론이전 글에서는 비관적 락(Pessimistic Lock)과 낙관적 락(Optimistic Lock)을 통해 분산락을 구현하여 단일 서버는 물론 다중 서버에서도 동시성 문제를 해결하였습니다.이번 글에서는 비관적 락과 비슷한 MySQL의 USER-LEVEL Lock(Named Lock)을 통해서 동시성 문제를 해결해 보도록 하겠습니다.(앞으로는 user-level lock이라고 부르도록 하겠습니다.)       🤔 USER-LEVEL Lock (Named Lock)MySQL 공식 문서를 보면 다음과 같은 user level lock을 지원해주는 것을 알 수 있습니다.   🐳 GET_LOCK(str, timeout)주어진 이름(str)에 대한 Lock 획득을 시도합니다. 이때 문자열의 길이는 최대..

[Spring] 동시성 문제 해결방법 (2) - 낙관적 락(Optimistic Lock), 비관적 락(Pessimistic Lock)

2023.11.06· 🏝️ Spring

🤔 서론 이전 글에서 알아본 synchronized는 단일 서버 환경에서만 동시성 문제를 해결할 수 있었습니다. 이번 글에서는 다중 서버 환경에서 동시성 문제를 해결할 수 있는 방법에 대해 알아보도록 하겠습니다. 여러 대의 서버에서 동일 자원에 접근하는 경우, 동시에 한 개의 프로세스(혹은 쓰레드)만 접근 가능하도록 하기 위해 사용하는 Lock을 분산 락(Distributed Lock)이라 부릅니다. 이제부터 분산 락을 구현하는 여러 방법들에 대해 알아보도록 하겠습니다. 💡 분산 락에 대해서 분산 락에 대해서 이렇다 할 완전한 정의를 찾지는 못해서 다음 두 상황이 혼동될 수 있을 것 같습니다. 1. 웹 애플리케이션 서버가 여러대인 경우, 이들간의 동시성 문제를 해결하기 위해 사용되는 Lock 2. 스케일..

[Spring] 동시성 문제 해결방법 (1) - synchronized, Lock 사용

2023.11.06· 🏝️ Spring

🤔 서론 다중 사용자를 위한 웹 애플리케이션을 만들다 보면 한 번쯤은 동시성 문제에 접하게 됩니다. 동시성 문제는 하나의 자원에 대해서 여러 쓰레드가 동시에 접근하여 수정하는 경우에 발생하는 문제입니다. 동시성 문제가 발생하는 간단한 예시로는 특정 게시물의 조회 수가 올바르게 증가되지 않는 문제가 있을 수 있습니다. 특정 게시물에 100명의 사용자가 동시에 접근하는 경우 조회수는 100이 되어야 옳겠지만, 대부분의 경우 조회수는 100보다 작은 값으로 설정될 것입니다. 조회수 같은 경우에는 대체로 데이터의 정합성이 중요하지 않기 때문에 이러한 부분이 문제가 되지 않을 수 있지만, 상품의 재고 수량과 같은 경우에 이러한 동시성 문제가 발생한다면 치명적일 수 있습니다. 이러한 동시성 문제를 막기 위해서는 다..

[JPA] merge()시 연관관계가 있다면 어떻게 동작하는가

2023.08.28· JPA

(제 궁금증 풀 용도로 정리한거라 막 깔끔하게 정리하지는 않았습니다.) 🧐 ManyToOne, OneToOne 연관관계 일반적으로 merge 시 merge되는 특정 엔티티에 대해서만 조회합니다. 그러나 cascade 속성이 MERGE라면 merge 시 연관된 엔티티들도 left join으로 조회해옵니다. merge()가 되어 값이 변경되는 것도 일반적으로는 fk 값의 변경만이 반영되지만, cascade 속성이 merge라면 연관된 엔티티의 변경도 함께 반영됩니다. (DB 관점에서 생각하면 편합니다) @NoArgsConstructor @Accessors(fluent = true) @Getter @Entity public class Member { @Id @GeneratedValue(strategy = Ge..

[배포 및 인프라] 해보자 배포 [1] - AWS EC2 생성하고 접속하기

2023.05.27· 배포 시작하기 시리즈

🧐 어려운 배포 배포는 참 어렵습니다. 저는 지금 정말 너무 어려워서 울 것 같아요. 하지만, 배포를 처음 해보는 모두가 다 저와 같은 감정일 것이라 생각합니다. 그래서 배포를 처음하는 제가, 이 글을 써가면서 자동 배포까지 진행하는 과정을 세세히 정리함으로써, 누군가에게 도움을 줄 수 있지 않을까 하는 생각으로 이렇게 정리를 하게 되었습니다. (무엇보다, 다른 블로그들이 너무 불친절하달까... 정말 아무것도 모르는 사람이 이걸 따라할 수 있다고..? 하는 생각이 들어서 제가 그냥 저를 위해서 정리를 하고 있네요..😭) 예상하는 목차는 다음과 같습니다. AWS 계정 만들기 ~ EC2 인스턴스 만들고 접속하기 (이번 글) 간단한 스프링 프로젝트 생성하고 깃허브에 올리기 -> EC2에서 손수 clone받아 ..

[시스템 프로그래밍] Shall Lab

2022.11.24· 시스템 프로그래밍

🧐 Trace00 EOF(ctrl + d) 입력을 받으면 프로그램을 종료시켜야 합니다. 더보기 main문을 보면 다음과 같이 이미 구현되어 있는 것을 알 수 있습니다. while(1)을 통해 쉘을 계속 실행시키다가 ctrl + d가 입력되면 프로그램을 종료합니다. 🧐 Trace01 quit 명령어를 built-in command로 등록합니다. quit이 입력되면 프로그램이 종료되어야 합니다. 더보기 void eval(char *cmdline) { cahr * argv[MAXARGS]; parseline(cmdline, argv); builtin_cmd(argv); return; } int builtin_cmd(char **argv) { char * cmd = argv[0]; if (!strcmp(cmd,..

[그라파나] - [1] 그라파나(Grafana) 대시보드 생성

2023.06.10· 모니터링

🧐 그라파나 (Grafana) 이전 글에서 간단히 언급했지만 다시 한 번 하도록 하겠습니다. 프로메테우스가 DB라고 한다면, 이 DB에 있는 데이터를 불러서 사용자가 보기 편하게 보여주는 대시보드가 필요합니다. 그라파나는 데이터를 그래프로 보여주는 툴입니다. 수 많은 그래프를 제공하고, 프로메테우스를 포함한 다양한 데이터소스를 지원합니다. 🧐 그라파나 설치 그라파나 설치 사이트(https://grafana.com/grafana/download)로 이동합니다. 여기서는 맥 OS 기준으로 설치를 진행하겠습니다. 위의 명령어를 복사합니다. 이후 그라파나를 설치할 (임의의)폴더로 이동한 뒤, 위의 명령어를 그대로 입력합니다. (설치하는데 시간이 좀 걸릴 수 있습니다) 그라파나를 설치할 폴더의 bin 폴더로 이동..

[확률과 통계] - (19) 카이제곱 분포 (Chi-Square Distribution)

2022.05.23· 확률과 통계

카이제곱 분포카이제곱 분포를 배우기 전에 카이제곱 분포를 왜 배우는지, 어떨 때 사용하는지 알아보겠습니다.카이제곱 분포는 표본들의 평균과 분산을 통해,정규분포를 따르는 모집단의 분산, 즉 모분산을 추정할 때 사용합니다. 이전에도 말씀드렸다싶이, 저희의 목적은 표본들을 가지고 모수를 추정하거나, 모수에 대한 가설을 검정하는 것이었습니다.   그중 모집단의 분산을 추정하는 방법에 사용되는 것이 바로 카이제곱분포입니다.  맛보기로 어떻게 추정이 가능한지 살펴보겠습니다.(카이제곱 분포의 자유도라던가, 식이 도출되는 과정은 생략하고, 추정이 가능한 이유에 대해서만 살펴보겠습니다.)우선 다음은 자유도 n인 카이제곱 분포를 의미합니다. 각 자유도에 대한 카이제곱분포는 이미 구해져있으며, 대부분 표로 주어집니다.$$\..

[논리회로] (11) - 카운터(Counter)

2022.05.17· 논리회로

카운터(Counter) 고정된 상태열(예, 000, 001, 010, 011, ... , 111)을 가지고 순환하는 회로를 카운터라고 합니다. 간단하게는 레지스터의 출력을 입력에 피드백하여 설계할 수 있으며, 이렇게 설계한 반전된 피드백을 가진 쉬프트 레지스터를 존슨 카운터(Johnson counter) 혹은 트위스트 링 카운터(twisted ring counter)라고 부릅니다. 피드백이 반전되지 않았다면 그 쉬프트 레지스터 카운터를 링 카운터(ring counter)라고 합니다. 존슨 카운터(Johnson counter) 반전된 피드백을 가진 쉬프트 레지스터로써 다음과 같이 구성됩니다. 링 카운터(ring counter) 반전되지 않은 피드백을 가진 쉬프트 레지스터로써 다음과 같이 구성됩니다. 2진 ..