희소 테이블(Sparse Table) 배열이 정적이어야 한다. 즉, 배열 내용이 수정되면 안 된다. 배열의 아이디어는 분할 정복과 비슷하지만 더 빠르다. 기본 원리 모든 정점의 간선이 1개인 유향 그래프가 존재할 때 어떤 정점에서 시작해 k번 이동을 하면 도착하는 점은 유일하다. 이때 k번을 일일이 매번 따라가며 도착점을 계산할 수도 있겠지만 k값이 커질수록 시간도 오래 걸릴 것이다. 만약 어떤 정점의 n번 이동했을 때 도착점, 또 그 도착점을 정점마다 다 기억하는 배열이 있다면 도착점을 매우 효율적으로 구할 수 있을 것이다. 그렇다면 이 배열은 어떻게 가져야 할까? 1칸, 2칸, 4칸, 8칸, 16칸,... 등 2진수를 이용해 2진수에 해당하는 이동 값을 모두 배열로 만든다. 그리고 이동 횟수 k를 2..

위상 정렬(Topological Sort) 위상 정렬은 순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위한 알고리즘이다. 여러 개의 답이 존재할 수 있다. DAG(Directed Acyclic Graph)에만 적용이 가능하다. 스택과 큐로 구현된다. 기본 원리 진입 차수가 0인 정점을 큐에 삽입한다. 큐에서 원소를 꺼내 연결된 모든 간선을 제거 후 진입 차수가 0이 된 정점을 큐에 삽입한다. 큐가 빌 때까지 2번 과정을 반복한다. 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재하는 것이고, 모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상 정렬의 결과이다. 문제 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ..

펜윅 트리(Fenwick Tree) 펜윅 트리는 바이너리 인덱스 트리(Binary Indexed Tree)라고도 부른다. 순서를 갖는 데이터가 주어졌을 때, 구간의 대표 값이나 연산 결과를 빠르게 얻을 수 있는 트리 형태의 자료구조이다. 기본 원리 https://www.acmicpc.net/blog/view/21 펜윅 트리 (바이너리 인덱스 트리) 블로그: 세그먼트 트리 (Segment Tree) 에서 풀어본 문제를 Fenwick Tree를 이용해서 풀어보겠습니다. Fenwick Tree는 Binary Indexed Tree라고도 하며, 줄여서 BIT라고 합니다. Fenwick Tree를 구현하려면, 어떤 수 X www.acmicpc.net 펜윅 트리를 구현하기 위해선 어떤 수를 이진수로 나타냈을 때 마..

옵저버 패턴(Observer Pattern) 만약 유저의 게임 머니가 업데이트되어 UI, 이벤트 등 다른 오브젝트의 변경이 필요하다면 어떻게 구현할 것인가? 매번 다른 오브젝트가 게임 머니 업데이트가 됐는지 확인할 순 없을 것이다. 이럴 때 필요한 것이 옵저버 패턴이다. Sudject(게임 머니)로부터 어떠한 변화가 생긴다면, Observer는 이 변화를 감지할 수 있다. 객체의 상태 변화를 관찰하는 관찰자(옵저버)가 있다. 관찰자를 객체가 갖고 있다가 상태 변화가 있을 때 메서드 등을 통해 객체가 각 옵저버에게 통지한다. 주로 분산 이벤트 핸들링 시스템을 구현하는 데 사용된다. 여기서 핵심은 객체의 상태 변화를 관찰하는 것인데, 과연 어떻게 관찰한다는 것일까? 1. 구현 1) Observer Concr..

AOP 2. AOP 적용 1) 적용 공통 관심 사항(cross-cutting concern)과 핵심 관심 사항(core concern)을 분리하는 것이다. 시간 측정 로직을 별도의 공통 로직으로 관리하고 원하는 곳에만 적용한다. 만약, 변경 사항이 있다면 이 로직만 변경하면 된다. package hello.hello.spring.aop; import org.aspectj.lang.ProceedingJoinPoint; import org.aspectj.lang.annotation.Around; import org.aspectj.lang.annotation.Aspect; import org.springframework.stereotype.Component; @Component // string been 등록..

AOP 처음부터 AOP 이론 및 용어를 학습하기엔 어려우니 간단한 예제를 통해 학습한 후 알아볼 것이다. 1. AOP가 필요한 상황 1) 예제 모든 메서드의 호출 시간을 측정하고 싶다면? 모든 메서드의 시작과 끝에 시간 측정 로직을 추가하였다. 만약, 갑자기 시간 단위를 변경해야 한다면 모든 메서드를 다시 수정해야 한다. package hello.hello.spring.service; import hello.hello.spring.domain.Member; import hello.hello.spring.repository.MemberRepository; import hello.hello.spring.repository.MemoryMemberRepository; import org.springframewo..