Kruskal AlgorithmKruskal 알고리즘은 최소신장트리 MST(Minimum Spanning Tree)를 구하는 알고리즘이다. Greedy하게 N개의 정점을 N-1개의 간선을 이용해 최소 비용으로 연결한다. Kruskal 알고리즘의 기본 개념은 Greedy이기 때문에 간선 정보를 가중치 기준으로 오름차순 정렬한다. 다음으로, Union-Find 알고리즘을 이용해 모든 N개의 정점을 N-1개의 간선을 통해 최소 비용으로 연결할 수 있다. 따라서, Kruskal 알고리즘은 Greedy + Union-Find 알고리즘의 개념을 합쳐놓은 알고리즘으로 최소신장트리를 구하는데 이용된다. [Data Structure] Minimum Spanning Tree - 최소 신장 트리노드의 갯수가 n개일때, 간..
Spanning Tree - 신장 트리 노드의 갯수가 N개일때 모든 노드가 연결되어 있고 간선의 갯수가 N-1개인 트리를 Spanning Tree라고 한다. N개의 모든 노드가 연결되어있고 최소 갯수의 간선(N-1)을 가지기 때문에 Spanning Tree는 트리내에 사이클이 존재하지 않는다. MST (Minimum Spanning Tree) - 최소 신장 트리 MST는 Spanning Tree에서 사용된 간선의 가중치 합이 가장 작은 트리를 의미한다. 모든 노드를 최소한의 간선과 최소한의 비용으로 연결하는것을 말한다. 참고자료 [알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree)란 - Heee's Development Blog Step by step goes a long way..
이전 글 보러가기 [최종프로젝트] WebSocket 실시간 채팅 서비스 개발개요스포츠 경기 일정 및 결과를 제공하는 서비스인 최종프로젝트에서 스포츠 게임별로 사용자들이 실시간으로 소통할 수 있는 채팅 기능을 제공하고자 하였다. 네이버 스포츠, 아프리카TV 등zzzzseong.tistory.com 개요기존 프로젝트에서 스포츠 게임별로 사용자들이 실시간 소통을 할 수 있는 채팅 기능을 개발했다. 개발 기간이 짧아 러닝커브를 고려해 채팅 데이터를 전달하는 브로커를 STOMP에서 기본적으로 제공하는 인메모리 브로커를 사용했다. 인메모리 브로커를 사용했기 때문에 서버의 스케일아웃에 대비할 수 없었다. 프로젝트 마무리 후 개인적으로 채팅 데이터 저장과 스케일아웃이 가능한 서버 아키텍처로 개선해보고자 했다. 해..
Install MongoDB Community Edition on macOS — MongoDB Manual Docs Home → MongoDB Manual MongoDB AtlasMongoDB Atlas is a hosted MongoDB service option in the cloud which requires no installation overhead and offers a free tier to get started.Use this tutorial to install MongoDB 7.0 Community Edition on macOS using www.mongodb.com Getting Started :: Spring Data MongoDB First, you need to set up a r..
Union-Find Union-Find 알고리즘은 서로소인 부분집합(그래프)을 표현하기 위한 알고리즘이다. union(x, y), find(x) 연산으로 이루어져 있으며 union(x, y)는 노드 x와 노드 y를 루트노드로 가지는 각 집합을 합하는 연산을 의미하고 find(x)는 x가 속한 집합의 루트노드를 확인하는 연산을 의미한다. Union-Find 알고리즘을 구현하기 위해서 필요한 자료구조는 각 노드의 부모노드를 저장하기 위한 배열이 필요하다. Union-Find 코드 public class Main { private static int[] parent; public static void main(String[] args) { parent = new int[N+1]; //union-find에 사용..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 기존코드 class Solution { //시작 좌표 private int sx, sy; //이동 변화값 배열 private int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; //노드 방문 기록 배열 private boolean[][] vis; //최소 시간 기록 변수 private int answer = Integer.MAX_VALUE; public void init(String[] maps) { for(int i=0; i
개요프로젝트 통합테스트로 상품 구매에 대한 테스트를 진행하던 중 멀티스레드 환경에서 상품 구매 기능에 접근할 시 레이스 컨디션이 발생하는 문제를 확인할 수 있었다. 이러한 이유로 상품 구매 기능에 동시성 제어가 필요할 것이라고 판단했고 동시성 제어에 필요한 기술의 의사결정, 기술 적용, 테스트 코드 작성 및 회고를 진행하고자 한다. 동시성 처리가 필요한 이유동시성 처리가 필요한 이유는 레이스 컨디션 발생에 있다. 레이스 컨디션이란 공유 자원에 대해 스레드가 동시에 접근해 값을 조작할때, 조작 순서가 보장되지 않아 잘못된 값이 저장되는 문제를 말한다. 레이스 컨디션의 가장 많이 알려진 예는 아래 코드라고 생각한다. 두 스레드가 동시에 count의 값을 증가시키려고 접근할때 count는 thread-sa..
성능 개전 전 부하테스트 리포트성능 개선 전 10명의 사용자가 30분간 지속적으로 요청을 보내는 환경에서 TPS가 1.2, MTT가 8000ms로 매우 비정상적인 매트릭을 보여주었다. 개발 단계에서는 데이터량이 많지 않았기 때문에 성능에 문제가 있다는것을 파악할 수 없었지만 데이터가 많아지면서 아래와 같은 비정상적인 매트릭을 측정할 수 있었다. 성능 개선 후 부하테스트 리포트상품 검색 기능에 대한 성능 개선을 완료하고 다시 한 번 부하테스트를 진행했다. 테스트를 진행한 서버의 스펙은 모두 t3.medium으로 동일하며 2vCPU와 4GiB 메모리를 가지는 EC2 환경에서 진행했다. 테스트는 30분 동안 N명의 사용자가 계속해서 요청을 보내는 환경으로 진행했고 사용자수를 10명, 100명, 1000명으..
