본문 바로가기

전체 글181

(25.01.28) DFS 알고리즘의 시간 부족 Time Limit Exceeded 해결 : 자료구조의 활용 DFS의 다중 탐색을 여러번 사용하는 경우, 반복문 단위에서 DFS 횟수를 줄여서 Time Limit을 벗어날 수 있었다.(이분탐색) 하지만 어떤 조건에 맞춱가면서 하나의 DFS를 찾아가는 알고리즘에서 발생하는 것은 탐색해야하는 데이터에 비해, 리소스가 (메모리 등)이 한정적일 때 발생할 수도 있다.즉, 하나의 깊이 탐색 자체가 너무 많은 리로스를 사용하기 때문인데,이 때, List 나 Set 처럼 백트래킹이 있는 알고리즘에서 불필요한 사용이 있을 수 있다. 이 때,  백트래킹을 진행하지 않고 조건에 만족하는 방향만 찾아게 하면서 탐색 속도를 줄이려면 어떻게 해야할까.Questionare given a list of airline tickets where tickets[i] = [fromi, toi] r.. 2025. 1. 28.
(25.01.25) DFS 알고리즘의 시간 부족 Time Limit Exceeded 해결 DFS를 통한 깊이 전체 탐색을 진행하는 알고리즘일 경우엔, 조건에 부합하는 경로가 나올때까지, DFS를 계속해서 진행하는 로직이 구현될 수 있다.이런 상황에서 탐색해야하는 구간이 커질 수록 Time Limit 이 발생할 수 있다. 이 때 활용할 수 있는 간단한 방법을 정리하고자한다.QuestionThere is a 1-based binary matrix where 0 represents land and 1 represents water. You are given integers row and col representing the number of rows and columns in the matrix, respectively.Initially on day 0, the entire matrix is la.. 2025. 1. 25.
(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.

티스토리툴바