위상 정렬(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..

스프링 DB 접근 기술 6. 스프링 데이터 JPA 스프링 부트와 JPA만 사용해도 개발 생산성이 크게 증가하고 개발해야 할 코드도 확연히 줄어들었다. 여기에 스프링 데이터 JPA라는 프레임워크를 사용하면, 기존의 한계를 넘어 리포지토리에 구현 클래스 없이 인터페이스 만으로 개발을 완료할 수 있고 반복 개발해온 기본 CRUD 기능도 제공한다. 스프링 데이터 JPA는 JPA를 편리하게 사용하도록 도와주는 기술이다. JPA와 동일한 환경 설정을 가진다. 이 기술을 사용하면 개발자가 핵심 비즈니스 로직을 개발하는데 집중할 수 있다. 실무에서 관계형 데이터베이스를 사용한다면 스프링 데이터 JPA는 이제 선택이 아니라 필수이다. 더보기 실무에서는 JPA와 스프링 데이터 JPA를 기본으로 사용하고, 복잡한 동적 쿼리..