[알고리즘] 세그먼트 트리 (Segment Tree)

개요옛날부터 세그트리에 대한 궁금증이 있었는데, 코테의 당락을 결정하지는 않을 알고리즘이라 취업과는 상관없다는 생각에 미뤄두었던 기억이 나서 이번에 알아두려고 한다. 세그먼트 트리는 '여러 개의 데이터가 연속적으로 존재할 때, 특정 범위의 데이터의 합/곱/최대값/최소값 등을 구하는 방법'중 하나이다. 수열을 저장하는 배열 A가 존재한다고 가정했을 때, 다음과 같은 케이스를 생각해보자. (A) 구간 l, r (l 이 경우 시간복잡도는 O(N)이다. 누적합, 구간합을 구해놓은 후 특정 구간의 합은 O(1)에 도출할 수 있기 때문이다. (B) 구간 l, r (l 이전 케이스와 다르게, 한번 구해놓은 누적합을 재사용할 수 없다. 따라서 구간합을 사용하게 되면 O(NM)의 시간이 걸린다. S[0] = A[..

• format_list_bulleted [ CS기초 ]/알고리즘
• · 2024. 10. 16.
• textsms

[DB] 인덱스(Index)로 조회 성능 개선하기

개요 그동안 데이터베이스 조회 성능 향상을 위해서 인덱스를 종종 사용했었는데, 따로 포스팅으로 정리한 적은 없어서 정리해보고자 한다.인덱스를 한 마디로 표현하면 "별도의 메모리를 추가로 할당하여 데이터베이스 조회 성능을 향상시킬 수 있는 방법"이라고 할 수 있다.  인덱스인덱스에 대해서 이야기하기 전에, 데이터베이스에서 어떻게 데이터를 조회하는지 서술하도록 하겠다. 우리가 흔히 말하는 Oracle이나 Mysql을 '데이터베이스 시스템' 이라고 부르는데, 데이터베이스 시스템은 데이터가 저장되는 '데이터베이스'와 데이터베이스를 관리하는 소프트웨어인 'DBMS(DataBase Management System)'으로 구성된다. DBMS에서 데이터베이스에 있는 데이터를 조회하기 위해서는 DBMS 내의 '질의 처리..

• format_list_bulleted [ CS기초 ]/데이터베이스
• · 2024. 9. 26.
• textsms

[Spring] @Valid와 @Validated를 이용한 순차 검증

개요 Spring에서 유효성 검증을 위해서 사용되는 어노테이션에는 흔히 @Valid와 @Validated가 있다. 필자는 평소에는 @Valid 위주로 사용했는데, 얼마 전 진행했던 프로젝트에서 @Validated를 사용한 좋은 검증 예시를 보아서 정리해보고자 한다.  @Valid 먼저 @Valid는 jakarta.validation(이전에는 javax.validation), 즉 Java 라이브러리 안에 속해있는 어노테이션이다.  @Valid 어노테이션은 Bean Validation API와의 통합을 통해서 데이터 무결성을 유지하는 데에 필요한 유효성 검사를 수행할 수 있다. Bean Validation API란?@NotBlank, @Min, @Email과 같이 도메인 모델의 필드에 유효성 제약을 위한 어..

• format_list_bulleted [ Backend ]/Spring
• · 2024. 9. 21.
• textsms

[Spring] 서블릿 분석 - Spring은 어떻게 multipart/form-data를 처리할까

부제) 필터에서 multipart/form-data 읽기 개요 갑자기 뜬금없는 주제로 글을 쓰게 됐는데, 최근에 진행했던 프로젝트에서 겪었던 문제를 해결하는 과정에서 알게 된 내용이라 까먹기 전에 정리해두려고 한다. 첫 번째 문제 - request body (사실 피할 수 있던 문제였기는 했지만 내가 해보고싶어서 시작해버림) 시작은 Spring AOP를 사용한 로깅 시스템의 도입이었다. 프로젝트에 타 동아리에서 봤던 Admin페이지에 요청 정보를 로깅하는 시스템을 그대로 도입해보려고 했는데, 나는 요청을 인터셉터하는 위치를 필터로 정했다. 이를 위해서 Filter에서 HttpServletRequest를 인터셉트하여 정보를 Mdc에 저장할 계획이었다. OncePerRequestFilter를 통해서 매..

• format_list_bulleted [ Backend ]/Spring
• · 2024. 8. 30.
• textsms

[Java] Collection

개요  자바에는 데이터의 그룹(자료구조)을 나타내기 위한 Collection 인터페이스가 존재한다. Collection 인터페이스에는 List, Set, Queue가 존재하며, 해당 인터페이스들을 구현하는 다양한 구현체들이 존재한다.  + Collections라는 클래스도 존재하는데, 여기에는 Collection과 그 하위 클래스들을 조작하기 위한 static 메서드들이 존재한다. 다양한 컬렉션 인터페이스들(+Map)을 살펴보고, 각 인터페이스를 구현하는 구현체의 특징과 자료구조, 시간복잡도 등에 대해서 정리해보겠다. 1. List List는 순서를 보장하는 컬렉션 인터페이스이며, 중복을 허용한다.  1-1. ArrayList - [배열 기반의 리스트]public class ArrayList extend..

• format_list_bulleted [ Languages ]/Java
• · 2024. 8. 10.
• textsms

[Spring] 자바 비동기와 스프링 @Async

자바의 비동기 자바에서 비동기 처리를 위해서는 쓰레드를 생성한 후 작업을 할당하는 방식을 주로 사용한다. 첫번째로 Thread 클래스를 상속받고, 상속받은 클래스에서 run()메서드를 오버라이딩해주는 방법이 있고, 두번째로는 Runnable 인터페이스를 구현하는 클래스를 정의하고 해당 클래스를 Thread의 생성자 파라미터로 전달하는 방법이 있다. 방법 1 - Thread 상속하기static class MyThread extends Thread { @Override public void run() { System.out.println("Thread: " + Thread.currentThread().getName()); }}void threadStart() { Thread..

• format_list_bulleted [ Backend ]/Spring
• · 2024. 7. 5.
• textsms

[OS] 멀티쓰레드와 멀티프로세스, 멀티코어

개요다들 알고 있을 기본적인 OS 내용이지만, 오랜만에 생각해보니 헷갈리는 부분도 있어서 기억을 되살릴 겸 정리해보고자 한다. 프로그램과 프로세스, 스레드 프로그램은 정적인 실행 파일을 말한다. 이러한 프로그램이 CPU에 올라와서 실행되면 그것을 프로세스라고 한다. 프로그램은 Long-Term Scheduler에 의해서 CPU에 올라오고(Ready), 메모리를 할당받아 프로세스가 된다. 스레드는 프로세스가 할당받은 자원을 이용하는 작업의 단위를 의미한다.  멀티프로세스와 멀티스레드CPU는 한번에 하나의 프로세스만 실행할 수 있다. 따라서 CPU를 점유(Run)하고 대기(Wait)하는 과정, 즉 Context Switching을 통해서 여러개의 프로세스를 번갈아서 실행시켜 사용자에게는 동시에 실행중인 것처..

• format_list_bulleted [ CS기초 ]/운영체제
• · 2024. 6. 30.
• textsms

'클린 아키텍처' 프로젝트 설계하기

개요 작년에 로버트 마틴의 '클린 아키텍처'를 읽은 적이 있다. SOLID부터 시작해서 여러 디자인 패턴이나 방법론에 대한 소개를 통해 객체지향적인 사고를 할 수 있도록 도왔고, OOP에 대한 새로운 시각을 제시해 주기도 했던 책이었다. 하지만 그 책을 읽고 나서도, 프로젝트를 진행하면서 책에 존재하는 수많은 선택지들 중에 '그렇다면 내가 앞으로 어떤 방법을 택해야 하는가?'라는 질문에 대한 확답을 내리지는 못했다. 예를 들어 추상화를 통해 클래스간의 결합도를 줄이고 외부 인터페이스에 의존하지 않는 코드를 만들고자 했던 목표를 두고 작성한 코드가, 간단한 프로젝트임에도 기존의 몇 배에 달하는 클래스들이 복잡한 연관관계를 가지고 있어 가독성이 떨어지고 간단한 유지보수조차 어렵게 하는 trade-off를 ..

• format_list_bulleted [ 아키텍쳐, 방법론, 디자인패턴 등 ]
• · 2024. 5. 19.
• textsms

[Spring DB] 트랜잭션 매니저 커스텀하기

개요 JPA는 내부에 하나의 EntityManagerFactory가 존재하고, EntityManagerFactory가 여러개의 EntityManager들을 생성할 수 있으며, 이렇게 생성된 EntityManager는 영속성 컨텍스트를 생성해 엔티티의 영속성을 관리한다. EntityManager는 트랜잭션 범위 내에서 작동하는 것이 일반적이기 때문에 트랜잭션을 시작할 때 마다 새로운 EntityManger 인스턴스가 필요하며, 이는 트랜잭션 종료 시 폐기된다.스프링 컨테이너에 등록된 트랜잭션 매니저는 데이터베이스 커넥션을 획득하고, 반납하는 역할을 한다. 스프링에는 데이터베이스 커넥션 풀이라는 것이 존재하는데, 스프링은 빈으로 등록된 Datasource 객체를 통해 커넥션 풀을 관리한다. 이 커넥션 풀에 ..

• format_list_bulleted [ Backend ]/Spring DB, JPA
• · 2024. 4. 25.
• textsms