본문 바로가기

전체 글213

(25.01.15) BFS 알고리즘의 메모리 부족 Memory Limit 해결 BFS 알고리즘을 활용하면서 bigint 내지는 BigIntegerdml 10^19 정도 크기 그 이상의 과학적 계산의 영역의 큰 규모의 데이터를 다룰 떄는 전체 탐색이라는 알고리즘의 특성상 리소스가 초과적으로 발생할 수 있다. 이 때는 주어진 Resource를 최대한 활용하면서 두개의 BFS를 활용하면서 제한된 리소스에서 BFS를 통해 이상적인 답을 찾아나가는 알고리즘에 대해서 좀 더 찾아보고 공부하면서 기록을 했다. QuestionThere is a 1 million by 1 million grid on an XY-plane, and the coordinates of each grid square are (x, y).We start at the source = [sx, sy] square and wa.. 2025. 1. 15.
(24.12.18) MVCC 매커니즘 최근 몸살과 장염으로 컨디션이 안좋은 가운데에서도, 저번에 학습했던 DB 격리수준의 연장선으로 Read  Lock을 걸지 않고도 동시성 제어를 하는 매커니즘으로 MVCC에 대해서 한번 정리하면서DB의 CS 지식에 대해서 간단히 찾아보고 정리하고자 했다.MVCC, Multi-Version Concurrency Control데이터베이스에서 락을 최소화 하면서, 동시성 제어를 위한 메커니즘MySQL의 InnoDB 엔진에서 사용하는 주요 기법 (아래 다시 정리)읽기 작업 read 과 쓰기 작업 write 이 충돌하지 않도록 데이터를 변경할 때 데이터의 복사본(버전)을 생성하여 관리하는 방식레코드 단위로 여러 데이터 버전을 관리하며, 데이터 읽기 시 락을 최소화하여 동시성을 높이는 구조읽기 작업을 Lock을 거는.. 2024. 12. 18.
(24.12.12) 관계형 DB의 격리수준 채용 공고를 보거나 RDB를 충분히 다룰 수 있다는 있는 역량을 보는 것과 동시에,Spring Framework 에서의 JPA를 활용하면서, Transaction 전파 전략(Propagation)  설정하는 선에서 Transaction 을 다루고자 했다. 하지만, SQL을 활용해서 DB 내에서 Transaction간 격리수준을 설정하는 것만으로 Session 별 또는 Global로 Transaction간 읽기 쓰기에 대한 동시성 제어가 가능할 수 있기 때문에,  Spring 단이 아닌 DB 단에서 격리 수준을 다루기 위해 찾아보고 정리를 했다. 관계형 DB의 격리수준DB의 격리 수준트랜잭션 간 동시성 제어를 위한 독립성 보장하는 설정여러 트랜잭션이 동시에 실행될 때 서로의 작업에 간섭하지 않도록 조정데이.. 2024. 12. 12.
(24.11.25) DP(Dynamic Programming) 과 전체탐색(BFS, DFS)에 대한 정리 DP(Dynamic Programming)은 간단하게 부분합을 사용해서 전체 합을 구하는 알고리즘이라고 넘어갔지만, 계속해서 찾아보고 알고리즘 문제를 풀어보면서  BFS와 DFS와의 구분이 애매한 것 같아서 스스로 구분하고적절하게 알고리즘을 사용하기 위해서 정리했다. 예제는 GPT를 활용해서 가장 많이 사용하는 경우를 간단하게 정리했다.DP(Dynamic Programming) & 전체 탐색DP 알고리즘모든 경로에 대해서 계산을 통해서 **“최적의 값”**을 찾기위해서 진행하는 알고리즘아무리 그 경로가 복잡하더라도 그 순서나 관련된 내용은 체크할 필요가 없이 “최적의 값” 을 향해 나가는 방식에 사용메모이제이션(Memoization) & 타뷸레이션(Tabulation)재귀를 통한 값을 캐싱하면서, 표로 .. 2024. 11. 25.
(24.11.18) BFS를 활용한 도현의 외각선 탐색 도형의 외곽선 탐색하기 알고리즘도형의 외곽선을 탐색하면서 가장 짧은 거리를 반환하는 알고리즘내부로 진입 Ximport java.util.*;class Solution { // 방향키 public int[] dx = {-1,1,0,0}; public int[] dy = {0,0,-1,1}; public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) { // 영역 지정 2배 확장 int[][] map = new int[101][101]; // 주어진 사각형 외각선 1 내부 2 설정하기 for(in.. 2024. 11. 18.
(24.11.11) BFS를 활용한 미로 최단 거리 찾기 가중치가 없는 그래프일 경우 Map> 자료구조의 graph로 BFS를 노드 단위, 또는 neighbor 단위로 활용할 수 있다. 하지만, 미로에서는 가중치가 1인 그래프에 특정 조건(막혀있을 경우 해당 경로는 X)이 있기 떄문에복잡할 수 있는 BFS 내지는 아래 비교를 위한 DFS를 좀더 다듬어서 사용할 수 있었다. 이전 DFS BFS 알고리즘에선 그 알고리즘의 플로우에 집중해서 정리를 해서 코드의 양이 길고, 효율적이지 못했기 때문에이번에는 미로에서 BFS 를 이용한 최단 거리 알고리즘을 통해서효율적으로 그래프에서 최단거리를 확인하는 방식을 정리하려고 한다.최단경로 미로찾기“최단경로” 이기 때문에 BFS를 통해서 Queue 를 통해 같은 레벨의 node(neighbors)를 반복하면서 도착지점에 부합할.. 2024. 11. 11.
(24.11.08) ELK 스택에 관하여 (1) ELK 스택을 적극적으로 활용하는 회사도 많지만,실제로는 실무 경험 내지는 대용량 트래픽을 다루는 경험이 많지 않은 이상 ELK 스택을 전부 활용하자는 아키텍쳐 구성 아이디러를 활용할 기회가 없었다. 오픈 소스이기도 해서 부담은 없지만, 실제로는 ElasticSearch에 대해서만 알고 있었기 때문에,이번 기회에 ELK 스택 전부를 알아보고 실제 프로젝트의 파이프라인(AWS 인프라 활용, 컨테이너 활용) 환경에서 어떻게 적응할지에 대해서 고민하면서 찾아보고 공부하면서 스스로 정리했다.ELK 스택Elasticsearch, Logstash, Kibana 의 약자, 로그 및 데이터 분석을 위한 강력한 오픈소스 플랫폼 스택가격 부담없이 운용이 가능각 구성요소가 서로 보완적으로 작동 내지는 독립적으로대규모 데이터.. 2024. 11. 8.

티스토리툴바