본문 바로가기

분류 전체보기

 (17)
[DB] DB Replication 💡 DB Replication 이란?원본 서버에서 발생하는 데이터 변경 사항을 복제 서버로 복제 시, 이 사이 데이터 일관성을 유지하는 메커니즘 - 데이터베이스의 고가용성과 데이터 안정성을 보장하기 위해 원본 데이터베이스의 복제 서버를 구축- 이 과정에서 데이터 신뢰성을 유지하기 위해 원본 서버와 복제 서버의 데이터 동기화가 필요 바이너리 로그(Binary log) 란?원본 서버에서 실행된 모든 데이터 변경 쿼리에 대한 기록 이 기록을 저장하는 방식은 Row, Statement, Mixed 세가지 방식이 있음 Row데이터베이스 행별로 변경된 내용을 정확히 기록하는 방식- 장점: 데이터 일관성 높음. 특정 행 수정 시 이전 상태와 변경 상태를 모두 기록하므로 복제 서버와 원본 서버가 정확히 일치함.- 단..
[알고리즘] 트라이(Trie) 알고리즘 💡트라이(Trie) 알고리즘이란?트라이(Trie)문자열을 저장하고, 빠르게 탐색하기 위한 트리 형태의 자료구조접두사를 기준으로 탐색문자열 배열에서 각 문자열 별 문자를 일일이 탐색하는 것보다 탐색 속도가 빠름각 노드에서 자식에 대한 포인터를 배열로 저장한다는 점에서 메모리를 더 사용 트라이 구조노드 구성class Node{ //노드의 자식 노드들을 저장 HashMap child; //이 노드가 단어의 끝인지 저장 boolean endOfWord;}메소드 구성삽입(insert)“TO” 삽입루트 노드에 T 자식 없으므로 생성T 노드에 O 자식 없으므로 생성O 노드 이후 문자 단위 탐색 끝났으므로 endOfWord = true 설정“TA” 삽입루트 노드에 T 자식 있으므로 T 자식으로 ..
[알고리즘] 프림(Prim) 알고리즘 💡프림(Prim) 알고리즘이란?프림(Prim) 알고리즘 특최소 신장 트리 알고리즘노드를 중심으로 간선 탐색배열로 구현할 경우 시간 복잡도 $O(n^2)$, 우선 순위 큐로 구현할 경우 시간 복잡도 $O(ElogN)$그리디 알고리즘알고리즘 과정임의의 노드를 선택해당 노드와 연결되어 있는 간선 중 가중치가 최소인 것을 MST에 추가MST에 포함된 모든 정점과 연결된 간선 중 가중치가 최소이고, 사이클을 형성하지 않는 것을 MST에 추가V-1개의 간선이 선택될 때까지 간선 선택을 반복과정 예시초기 상태2. 노드 1 선택노드 1과 연결된 세 개의 간선 우선 순위 큐 추가            우선 순위 큐 157   3. 큐에 포함된 간선 중 가장 작은 간선 선택 후 MST에 연결 노드 3 추가MST에 포함된 ..
[알고리즘] 최소 신장 트리(Minimum Spanning Tree) 💡최소 신장 트리란?신장 트리(Spanning Tree)그래프의 모든 정점을 포함하는 최소 연결 부분 그래프트리의 특징정점의 개수 n 개인 신장 트리의 간선 개수는 n-1 개모든 정점이 연결사이클 없음임의의 두 정점을 선택했을 때, 그 사이 경로는 유일함예시위 그래프에 대한 아래 신장 트리 예시들최소 신장 트리(MST, Minimum Spanning Tree)신장 트리 중 간선 가중치 합이 최소인 신장 트리예시위 그래프에 대해 최소 신장 트리💡최소 신장 트리 알고리즘1. 크루스칼(Kruskal) 알고리즘그리디를 이용하여 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 방법간선을 중심으로 하는 알고리즘greedy하게 간선을 선택하는 방법과정간선 가중치를 기준으로 오름차순 정렬간선 리스트 중 작은..
[알고리즘] 벨만-포드(Bellman-Ford) 알고리즘 💡 벨만-포드(Bellman-Ford) 알고리즘이란?벨만-포드한 노드에서 다른 모든 노드까지 최단 거리를 구하는 알고리즘매 단계마다 모든 간선을 전부 확인하면서 모든 노드 간의 최단 거리를 구함다익스트라는 방문하지 않은 노드 중 최단 거리가 가장 가까운 노드를 방문함간선 가중치가 음수일 때도 최단 거리를 구할 수 있음시간 복잡도: O($VE$)알고리즘 구현 방식아래 과정을 V-1 번 반복모든 간선 E개에 대해 각 간선을 거쳐 다른 노드로 가는 비용을 계산 후 최단 거리 테이블 갱신음수 사이클이 존재하는지 체크하고 싶다면 과정을 한번 더 수행→ 이 때 최단 거리 테이블이 변화가 있다면 음수 간선 순환 존재초기 상태 ABCDEINFINFINFINFINF     2. 모든 edge 탐색하여 노드 최솟값 업데..
[Algorithm] 최단 거리 알고리즘 - 다익스트라(dijkstra) 알고리즘 🔎 다익스트라(dijkstra) 알고리즘이란?다익스트라그래프의 한 정점에서 다른 모든 정점까지 최단 거리를 구하는 알고리즘이다.DP 문제: 최단 거리는 여러 개의 최단 거리로 이루어져 있기 때문에 작은 문제가 큰 문제의 부분 집합이다.한계: 음의 간선을 포함할 수 없다. (음의 간선을 포함하는 최단 경로 탐색 알고리즘으로 ‘벨만-포드’ 가 있다.)알고리즘 구현 방식아직 방문하지 않은 정점 중 출발지에서 가장 가까운 정점 방문 → by PriorityQueue해당 정점을 거쳐 갈 수 있는 정점의 거리가 이전 기록 값 보다 작으면 갱신1. 초기 상태ABCDEFINFINFINFINFINFINF   visit 배열ABCDEFfalsefalsefalsefalsefalsefalse   2. A 방문 후 주변 노드..
[java] 자바 객체 정렬하기 ( Comparable VS Comparator ) Comparable 을 이용한 정렬Comparable interface 상속compareTo 메소드를 오버라이드해야 함Comparable 클래스를 새로 정의할 때, 정렬 기준이 일정한 경우class Person implements Comparable { String name; int height, weight; Person(String name, int height, int weight) { this.name = name; this.height = height; this.weight = weight; } @Override public int compareTo (Person o) { //키 순으로 오름차순 정렬 //(내림차순은 받아온 객체와 자신의 객체 값을 반대로) retu..
엘라스틱서치 (ELK, RDB와 차이점, 관계형 모델링 방법) 데이터 플랫폼 - 엘라스틱 스택(Elastic Stack)Elastic search: 검색, 분석, 데이터 저장소 역할Beats: 데이터 수집Logstash : 정제, 전처리Kibana : 시각화, 관리장점빠른 속도, 확장성, 복원성정형, 비정형 데이터 모두 수용 가능→ 검색 뿐 아니라 빠른 데이터 확인이 필요한 분야에 활용 가능RDB 와 차이점RDB Elastic Search데이터 저장행을 기반단어를 기반(inverted index)장점데이터 수정, 삭제의 편의성다양한 조건의 데이터 검색 및 집계RDBElastic Search데이터 검색 및 집계Elastic Search는 도큐먼트를 행 기반으로 저장하고 특정 단어가 어디에 있는지 알기 때문에 한 번의 조회로 검색 가능RDB는 모든 행을 검색해야 함수정..

티스토리툴바