캐싱 대상

• 읽기 비율이 압도적으로 높은 데이터

사용자 프로필: userId, 이름, 소속, 슬랙ID, 전화번호, 등급

상품 정보: 상품Id, 허브Id, 상품명

캐시 구조

1차 캐시 L1: Caffeine(in-memory)

2차 캐시 L2: Redis(공유 캐시)

조회 흐름

사용자 프로필: L1→ L2 → UserService API

상품 정보: L1→ L2 → HubService API

캐시 관리 전략

캐시 키 설계

• user:profile:{userId}
  • userId, 이름, 소속, 슬랙ID, 전화번호, 등급
• product:{productId}
  • 상품Id, 허브Id, 상품명, 업체명, 가격(X)

만료 전략

정상 캐시

L1: TTL 5분, TTI 2분30초

L2: TTL 20분

Negative Cache

L1: TTL 15초, TTI 7초 (정상 캐시의 5%)

L2: TTL 1분 (정상 캐시의 5%)

읽기 전략

• Cache Aside: 요청 시 캐시 조회, 없으면 DB 조회 후 캐시 저장

쓰기 전략

• Write Around: 사용자/상품 데이터 변경은 데이터 소유 서비스에서 처리, Order는 캐시만 관리
• 캐시에 저장 시 L1+L2 모두 저장
• 사용자, 상품 데이터 변경 시 이벤트 발행 → Order 서비스에서 구독 L1,L2 모두 캐시 삭제

1차 설계

• Redis pub/sub invalidation으로 L1 캐시 갱신(https://channel.io/ko/team/blog/articles/tech-distributed-cache-1-67a392c5)

  2차 설계

Redis Pub/Sub은 메시지 유실 가능성이 있어 kafka로 변경

장애/실패 시나리오

Redis 장애 시

• L1 miss → L2(REDIS) 실패 → 사용자/상품 서비스 API 바로 호출
• 캐시 기능은 비활성에 가깝지만 기능은 정상 동작

UserService / HubService 장애 시

• L1/L2 모두 miss → UserService/HubService 호출 실패
• 404 NotFound: null 반환 + 네거티브 캐시 저장
• 5xx / 타임아웃 / 네트워크 장애 등: ExternalApiException 예외 던짐

이벤트 누락 시

• TTL로 만료 기간을 둬서 안전 장치

캐시 스탬피드(Cache Stampede) 방지

• 캐시 스탬피드: key(캐시 항목)가 만료되는 순간 다수의 요청이 동시에 캐시를 갱신하려고 하면서 발생하는 문제 (https://jhzlo.tistory.com/69)
• 문제점: DB 부하가 급증하고 시스템 응답 시간이 느려지거나 장애가 발생
• 대응
  • TTL에 랜덤 지터(±10~20%) 적용해서 동시 만료 방지
  • L2 캐시에서 PER(Probabilistic Early Refresh) 알고리즘 적용 : TTL 만료되기 전에 확률적으로 데이터를 갱신하는 기법

    Stale Cache

L1 miss → L2 캐시 조회 하는 상황에서 만약 L2 캐시의 TTL이 만료 직전인 stale 데이터라면?

threshold 2분30초 ( L1 캐시의 TTL 시간의 50% )
L2의 데이터가 TTL <= threshold 이면 DB 조회해서 새로 갱신

Negative Caching

존재하지 않는 데이터(= null, empty)도 캐시에 넣어서, ‘없는 데이터’ 조회가 반복될 때 원본(DB, 외부 API)을 계속 호출하지 않도록 막는 기법

TTL 시간 정상 캐시의 10%

L1: 30초

L2: 2분

모니터링/ 알람

모니터링 지표

• L1,L2 캐시 히트율
• Redis 지표: 메모리 사용량, 명령어 QPS
• Redis pub/sub 이벤트 소비 상태 -> kafka 이벤트 소비 상태

알람

• L1/L2 hit ratio가 특정 값 이하로 떨어질 때

참고자료 : https://bcuts.tistory.com/185

필요 의존성

implementation 'net.javacrumbs.shedlock:shedlock-spring:6.10.0'
implementation 'net.javacrumbs.shedlock:shedlock-provider-redis-spring:6.10.0'

SchedulingConfig

@Configuration
@EnableScheduling
@EnableSchedulerLock(defaultLockAtLeastFor = "10s", defaultLockAtMostFor = "90s") //Lock 이 유지되는 최소,최대 시간
public class SchedulingConfig {

    @Value("${spring.profiles.active}")
    private String profile;

    @Value("${spring.application.name}")
    private String appName;

    @Bean
    public LockProvider lockProvider(RedisConnectionFactory redisConnectionFactory) {
        String prefix = appName + ":" + profile;
        return new RedisLockProvider(redisConnectionFactory, prefix);
    }
}

defaultLockAtLeastFor : Lock을 유지하는 최소 시간 기본 설정 defaultLockAtMostFor : Lock을 유지하는 최대 시간 기본 설정 해당 코드는 RedisLockProvider를 사용하고 있습니다.

Scheduler

@Component
@RequiredArgsConstructor
@Slf4j
public class HubRouteInfoScheduler {

    private final HubRepository hubRepository;
    private final HubRouteInfoRepository routeInfoRepository;
    private final HubService hubService;
    private final HubRouteInfoRepository hubRouteInfoRepository;

    //기본 설정 2시간마다
    @Scheduled(
        fixedRateString = "${scheduler.route-infos.fixed-rate}",
        initialDelayString = "${scheduler.route-infos.initial-delay}"
    )
    // 멀티 서버, 멀티 스레드 환경에서도 스케줄러를 하나만 실행 / lock 유지 최소, 최대 시간
    @SchedulerLock(
        name = "generateMissingHubRouteInfos",
        lockAtLeastFor = "${shedlock.route-infos.at-least}",
        lockAtMostFor  = "${shedlock.route-infos.at-most}"
    )
    public void generateMissingRoutes() {
        log.info("[{}] HubRouteInfoScheduler started at {}", LocalDateTime.now(), Thread.currentThread().getName());
        long start = System.currentTimeMillis();
        int createdCount = 0;

        List<UUID> hubIds = hubRepository.getActiveHubIds();
        if (hubIds.size() < 2) return;

        Set<RoutePairDto> existing = new HashSet<>(routeInfoRepository.findExistingParisIn(hubIds));

        // 전체 순서쌍(출발!=도착) 생성 → 차집합으로 미존재 목록 계산
        List<RoutePairDto> missing = new ArrayList<>();
        for (UUID dep : hubIds) {
            for (UUID arr : hubIds) {
                if (!dep.equals(arr)) {
                    RoutePairDto pair = new RoutePairDto(dep, arr);
                    if (!existing.contains(pair)) {
                        missing.add(pair);
                    }
                }
            }
        }
        log.debug("missing size : {}", missing.size());

        Map<UUID, Hub> hubCache=hubService.getHubByIds(hubIds).stream()
            .collect(Collectors.toMap(Hub::getHubId, Function.identity()));

        for (RoutePairDto pair : missing) {
            try {
                Hub departureHub = hubCache.get(pair.departureId());
                Hub arrivalHub = hubCache.get(pair.arrivalId());

                Long durationMin = DistanceTimeUtil.estimateDurationMinutes(departureHub.getLatitude(),departureHub.getLongitude(),arrivalHub.getLatitude(),arrivalHub.getLongitude());
                Double distanceKm = DistanceTimeUtil.calculateDistanceKm(departureHub.getLatitude(),departureHub.getLongitude(),arrivalHub.getLatitude(),arrivalHub.getLongitude());

                HubRouteInfo routeInfo = HubRouteInfo.create(pair.departureId(),pair.arrivalId(),durationMin,distanceKm);
                hubRouteInfoRepository.save(routeInfo);
                createdCount++;
            } catch (BusinessException e) {
                log.warn("ErrorCode : {}, Message: {}",e.getErrorCode(),e.getMessage());
            } catch (DataIntegrityViolationException e) {
                log.warn("유니크 제약 조건 위반 departureId: {}, arrivalId: {}",pair.departureId(),pair.arrivalId());
            } catch (Exception e) {
                 log.warn("Route create failed: {} -> {}", pair.departureId(), pair.arrivalId(), e);
            }
        }

        long elapsed = System.currentTimeMillis() - start;
        log.info("[HubRouteInfoScheduler] finished at {} — created {} new routes in {} ms",
            LocalDateTime.now(), createdCount, elapsed);
    }
}

@SchedulerLock 어노테이션을 통해 shedlock을 적용할 수 있습니다.

참고

• https://github.com/lukas-krecan/ShedLock
• Redis, JDBC, Mongo 등의 많은 Provider 를 제공하고 있다.

양방향 연관관계에서 toString()이 양쪽 필드 모두 출력하려 하면 무한 순환을 통해 StackOverflowError가 발생한다.

@Getter
@ToString(onlyExplicitlyIncluded = true)
@Entity
class Member {
  @Id Long id;
  @ToString.Include String name;

  @OneToMany(mappedBy = "member")
  @ToString.Exclude               // 🔴 순환 방지
  private List<Order> orders = new ArrayList<>();
}

Entity에 @Setter를 달면 안되는 이유

1. 양방향 연관관계 일관성이 깨진다.
   • 전용 메서드로 두 쪽을 함께 갱신해야 안전
2. 식별자/감사 필드 변경 가능성
   • id(PK) 변경으로 DB 무결성이 깨질 수 있다.
   • createdAt, modifiedAt 등 감사 로그 왜곡

.authorizeRequests() → .authorizeHttpRequests() 
.antMatchers() → .requestMatchers()
.access("hasAnyRole('ROLE_A','ROLE_B')") → .hasAnyRole("A", "B")

메서드 체이닝이 사라지고 람다식을 통해 함수형으로 설정

분산 추적

Metric : 상태, 성능, 안정성을 나타내는 지표

Micrometer

• Spring 기반 애플리케이션에서 메트릭을 수집하고 모니터링하기 위한 라이브러리
• 다양한 메트릭 수집, 유연한 연동(Prometheus, Grafana)
  1. 수집된 메트릭을 보관할 DB ( = 프로메테우스 )
  2. 수집된 메트릭을 시각화 할 대시보드 ( = 그라파나 )
• 추적 기능

Zipkin

• 트레이스 데이터: 개별 요청(트랜잭션)의 흐름을 따라가는 데이터
• 트레이스 데이터를 수집하고 시각화하는 분산 추적 시스템
• 시각화, 검색 및 필터링 제공

• 클로즈드:
  • 기본 상태, 모든 요청 통과
  • 실패율이 설정된 임계값을 초과하면 오픈 상태로 전환
• 오픈:
  • 모든 요청을 즉시 실패로 처리 에러 응답 반환
  • 설정된 대기 시간이 지난 후, 하프-오픈 상태로 전환
• 하프-오픈:
  • 제한된 수의 요청을 허용하여 시스템이 정상 상태로 복구되었는지 확인
  • 요청이 성공하면 클로즈드로 전환, 다시 실패하면 오픈 상태로 전환
  • 예시: 하프-오픈 상태에서 3개의 요청을 허용하고, 모두 성공하면 클로즈드 상태로 전환. 만약 하나라도 실패하면 다시 오픈 상태 전환.
• Fallback: 호출 실패시 대체 로직

Spring Cloud Gateway 필터링

• Global Filter: 모든 요청에 대해 작동하는 필터
• Gateway Filter: 특정 라우트에만 적용되는 필터

필터 시점별 종류

• pre filter: 요청 처리되기 전에 실행한 다음 체인의 다음 필터로 요청을 전달.

• post filter: Post 필터는 요청이 처리된 후, 응답이 반환되기 전에 실행됩니다. Post 필터에서는 체인의 다음 필터가 완료된 후에 실행되어야 하는 추가적인 작업을 수행해야 합니다.

• 게이트웨이 라우트에서 lb://product 같은 서비스 ID 기반 URI를 쓰면, 게이트웨이는 Eureka에 등록된 인스턴스 목록을 받아 라운드로빈(기본 전략) 으로 선택합니다. Feign이나 Ribbon을 “직접” 설정하지 않아도, Gateway 내부가 이미 “로드밸런싱 클라이언트”(Spring Cloud LoadBalancer)를 사용합니다.

Spring Cloud

1. 서비스 등록 및 디스커버리(Eureka)

   마이크로서비스 아키텍처에서 각 서비스의 위치를 동적으로 관리

   • 서비스 레지스트리: 모든 서비스 인스턴스 위치를 저장하는 중앙 저장소
   • 헬스체크: 서비스 인스턴스의 상태를 주지적으로 확인하여 가용성을 보장

2. 로드 밸런싱(Ribbon)

   서비스 인스턴스 간의 부하를 분산

   • 서버 리스트 제공자
   • 로드 밸런싱 알고리즘: 라운드 로빈, 가중치 기반 등
   • Failover: 요청 실패 시 다른 인스턴스로 자동 전환

3. 서킷 브레이커(Hystrix, Resilience4j)

   서비스 간의 호출 실패를 감지하고 시스템의 전체적인 안정성을 유지

   Resilience4j 특징

   • 서킷 브레이커: 호출 실패를 감지하고 서킷을 열어 추가적인 호출을 차단하여 시스템의 부하를 줄임
   • Fallback: 호출 실패 시 대체 로직을 실행하여 시스템의 안정성을 유지
   • 타임아웃 설정: 호출의 응답 시간을 설정하여 느린 서비스 호출에 대응할 수 있음
   • 재시도: 재시도 기능을 지원하여 일시적인 네트워크 문제 등에 대응할 수 있음

4. API 게이트웨이(Zuul, Cloud gateway)

   • 라우팅 및 필터링
   • 보안
   • 효율성

5. Spring Cloud Config

   중앙 집중식 설정 관리를 제공

   • Config 서버
   • Config 클라이언트
   • 설정 갱신: 설정 변경 시 서비스 재시작 없이 실시간으로 반영 (@RefreshScope, Spring Cloud Bus)

1. NAT 테이블/체인 생성

   sudo nft add table ip nat
   sudo nft 'add chain ip nat prerouting { type nat hook prerouting priority 0; }'
   sudo nft 'add chain ip nat postrouting { type nat hook postrouting priority 100; }'

2. 네트워크 인터페이스 확인

   ip link show

3. 포트포워딩 실행

   sudo nft add rule ip nat prerouting iif {2번의 네트워크 인터페이스이름:ens5} tcp dport 80 redirect to 8080

4. 설정 확인

   sudo nft list ruleset
   // 아래처럼 나와야 합니다.
   table ip nat {
        chain prerouting {
                type nat hook prerouting priority filter; policy accept;
                iif "ens5" tcp dport 80 redirect to :8080
        }

5. 인스턴스 재부팅 이후에도 반영되도록 설정

   sudo apt install nftables -y
   sudo systemctl enable nftables
   sudo sh -c "nft list ruleset > /etc/nftables.conf"

Java 빌드 war에서 jar로 변경하기

build.gradle
/* ⛔️ 제거: WAR 프로젝트 전용 설정
id 'war'
providedRuntime 'org.springframework.boot:spring-boot-starter-tomcat'
*/


bootJar { enabled = true }      // (기본값이지만 명시 OK)
jar { enabled = false }         // plain.jar 만들지 않으려면 유지

• CascadeType.ALL : 모든 Cascade 옵션을 적용합니다.
• CascadeType.PERSIST : 엔티티를 영속화할 때, 연관된 엔티티도 함께 영속화합니다.
• CascadeType.REMOVE : 엔티티를 제거할 때, 연관된 엔티티도 함께 제거합니다.
• CascadeType.MERGE : 엔티티 상태를 병합할 때, 연관된 엔티티도 함께 병합합니다.
• CascadeType.REFRESH : 부모 엔티티를 Refresh하면, 연관된 엔티티도 함께 Refresh됩니다.
• CascadeType.DETACH : 부모 엔티티를 Detach하면, 연관된 엔티티도 함께 Detach됩니다.

고아 Entity 제거

orphanRemoval = true

Scheduler

// 초, 분, 시, 일, 월, 주 순서

@Scheduled(cron = "0 0 1 * * *")

@EnableScheduling 달기

@Transactional

@Transactional이 없으면:

조회 자체는 되지만, 영속성 컨텍스트 범위가 보장되지 않아 Lazy Loading 시 문제가 생김.

사실상 "트랜잭션 바깥"에서 실행되는 것과 같음.

@Transactional(readOnly = true)가 있으면:

조회 트랜잭션을 열어서 Lazy 로딩도 안전하고, 변경 감지도 생략해 성능도 최적화됨.

@NotNotBlank, @Valid

validation 예외 발생하면 BindingResult 객체에 오류가 담겨져 들어온다.

List<FieldError> fieldErrors = bindingResult.getFieldErrors();
        if(fieldErrors.size() > 0) {
            for (FieldError fieldError : bindingResult.getFieldErrors()) {
                log.error(fieldError.getField() + " 필드 : " + fieldError.getDefaultMessage());
            }
            return "redirect:/api/user/signup";
        }

RestTemplate

동기식 HTTP 클라이언트

WebClient

비동기+논블로킹(리액터 기반) HTTP 클라이언트

영속성 컨텍스트

1차 캐시, 쓰기 지연 저장소, 변경 감지

지연 로딩 n+1 문제

fetch join을 통해 방지

클라이언트에 저장되는 key-value 형태의 데이터 파일. 유효 시간을 통해 브라우저 종료를 해도 인증 유지가 가능하다.

세션

서버측에 저장하는 쿠키. 클라이언트가 요청을 보내면 Session ID를 발급.

필터

웹 애플리케이션에서 관리되는 영역으로 Client로부터 오는 요청과 응답에 대해 최초/최종 단계의 위치, 요청과 응답의 정보를 변경하거나 부가적인 기능을 추가할 수 있다.

• NLP 자연어 처리 기술의 한 분야이자 굉장히 큰 데이터 셋을 사용한다.
• 방대한 양의 데이터로부터 인간의 언어와 유사한 텍스트를 이해하고 만들어내는 기술
• Transformer 구조 기반
• Self-Attention: 문장 안의 단어들의 관계를 파악해서 중요한 단어에 집중하는 메커니즘
• Word-Embedding: 단어를 벡터로 표현하는 기술, 비슷한 의미의 단어는 비슷한 벡터값을 가진다.

한계점

1. 유지 비용이 많이 든다.
2. 잘못되거나 나쁜 정보의 필터링 필요성

• 헤더 도입
• 응답에 상태코드 추가
• Content-Type 도입 HTML 이외 문서 전송 가능

  한계

• 커넥션 하나당 요청 하나와 응답 하나만 처리 가능

HTTP 1.1

• Keep-Alive: TCP연결을 끊지 않고 재사용
• Pipelining: 앞 요청의 응답을 기다리지 않고 순차적으로 요청을 보내고 그 순서에 맞춰 응답을 받는 방식

  한계

• Head of Line Blocking(HOL): 앞 요청의 응답이 너무 오래 걸리면 뒷 요청은 Blocking된다.
• Header 중복: 연속된 요청의 헤더 많은 중복이 발생

HTTP 2.0

• Binary Framing 계층
  1. Frame: HTTP 2.0에서 통신의 최소 단위, Header나 Data가 들어있다.
  2. Message: 요청과 응답의 단위이고 다수의 Frame으로 이루어짐.
  3. Stream: 연결된 Connection 내에서 양방향으로 Message를 주고받는 흐름. ID가 있음.
  • Message를 Frame 단위로 분할하며, Binary(이진)로 인코딩. 바이너리 형식 사용으로 파싱속도 및 전송 속도가 빠르고 오류 발생 가능성이 낮아졌다.
  • HTTP1.1은 텍스트 기반 프로토콜
• Multiplexing: 여러 개의 HTTP 요청과 응답을, 하나의 TCP 연결(Connection) 안에서 동시에 처리할 수 있도록 하는 기술. 응답이 요청의 순서에 상관없이 Stream으로 주고 받아 HOL 해결(병렬 처리).
• Stream Prioritization: 리소스간 우선순위를 설정해 클라이언트가 먼저 필요한 리소스부터 보내준다.
• Server Push: 서버는 클라이언트가 요청하지 않았지만 추가적으로 필요한 리소스를 보내줄 수 있다. 캐시에 저장.
• Header Compression: HPACK 압축 알고리즘 사용. Header Table(Static, Dynamic)과 호프만 인코딩 기법을 사용해 압축하여 전송 효율 상승.

HTTP 3.0

• QUIC: UDP 기반 전송 프로토콜

기본 중심 행위

형태별 엔티티 유형

유형 개념 사건

식별자의 대체 여부 분류

본질 식별자 - 인조 식별자

비식별자 관계

부모 엔터티로부터 속성을 받았지만, 자식 엔터티의 주식별자로 사용하지 않고 일반적인 속성으로만 사용한다.

데이터 모델링

• 데이터 모델링의 3 요소 Things, Attributes, Relationships
• 실제 데이터베이스 구축시 참고 물리적 데이터 모델링
• 논리 모델링의 외래키는 물리 모델에서 선택 사항

데이터 모델링 관점

• 데이터 관점: What, Data
• 프로세스 관점: How,Process
• 데이터와 프로세스의 상관 관점: interaction

ERD 관계 표기법

관계명, 관계차수, 관계 선택사항

서브쿼리 종류

• Access Subquery: 쿼리의 변형이 없고 제공자의 역할을 하는 서브쿼리
• Filter Subquery: 쿼리의 변형이 없고 확인자 역할을 하는 서브쿼리
• Early Filter Subquery: 쿼리의 변형이 없고 서브쿼리가 먼저 실행하여 데이터를 걸러낸다.

Natural join

두 테이블 간에 동일한 칼럼 이름을 가지는 것을 모두 출력하는 조인 등가 조인 가능 비등가조인 불가능

Null 값 인덱스

SQL Server는 null값을 인덱스 맨 앞에 저장 SQL Server는 인덱스 구성 칼럼이 모두 null인 레코드도 인덱스에 저장 Oracle은 null값을 인덱스 맨 뒤에 저장 Oracle은 인덱스 구성 칼럼이 모두 null인 레코드는 인덱스에 저장하지 않는다.

슈퍼타입 서브타입 변환 방법

OneToOne Type , Plus Type, Single Type

3층 스키마

외부(사용자뷰), 개념(통합 뷰), 내부(물리장치)

데이터 모델링 관점

데이터관점 -구조분석 프로세스 관점- 업무시나리오분석 데이터와 프로세스의 상관 관점-CRUD메트릭스

outer join (+) 데이터가 전부 포함되지 않는 쪽에 표시

데이터 모델링

개념적 데이터 모델링(높은 추상화 수준) 논리적 데이터 모델리(정규화, 재사용성) 물리적 데이터 모델링(반정규화, 성능/보안/저장)

nullif(a,b) a,b 같으면 null반환

NVL2(a,b,c) a가 null이 아니면 b null이면 c

그룹함수

group by rollup(a,b) = grouping sets((a,b),(a),()) group by cube(a,b) = grouping sets((a),(b),(a,b),())

풀이

• DFS, BFS 두 방식 다 제출했는데 비슷한 속도로 통과했다.

  코드

• BFS

  import java.io.*;
  import java.util.*;
  

public class Main {

public static void main(String[] args) throws IOException {
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

    StringTokenizer st=new StringTokenizer(br.readLine());
    String a=st.nextToken();
    long b=Long.parseLong(st.nextToken());
    Queue<Item> q=new LinkedList<>();
    q.add(new Item(a,1));
    int ans=-1;
    while(!q.isEmpty()){
        Item item=q.poll();
        long n=Long.parseLong(item.num);
        if(n==b){
            ans=item.cnt;
            break;
        }
        if(2*n<=b)q.add(new Item(String.valueOf(2*n),item.cnt+1));
        StringBuilder sb=new StringBuilder(item.num);
        sb.append(1);
        if(Long.parseLong(sb.toString())<=b)q.add(new Item(sb.toString(),item.cnt+1));
    }
    System.out.println(ans);
}

static class Item{
    String num;
    int cnt;

    public Item(String num, int cnt) {
        this.num = num;
        this.cnt = cnt;
    }
}

}

- DFS
```java
import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st=new StringTokenizer(br.readLine());
        String a=st.nextToken();
        long b=Long.parseLong(st.nextToken());
        Queue<Item> q=new LinkedList<>();
        q.add(new Item(a,1));
        int ans=-1;
        while(!q.isEmpty()){
            Item item=q.poll();
            long n=Long.parseLong(item.num);
            if(n==b){
                ans=item.cnt;
                break;
            }
            if(2*n<=b)q.add(new Item(String.valueOf(2*n),item.cnt+1));
            StringBuilder sb=new StringBuilder(item.num);
            sb.append(1);
            if(Long.parseLong(sb.toString())<=b)q.add(new Item(sb.toString(),item.cnt+1));
        }
        System.out.println(ans);
    }

    static class Item{
        String num;
        int cnt;

        public Item(String num, int cnt) {
            this.num = num;
            this.cnt = cnt;
        }
    }
}

#dfs #bfs

풀이

1. pre 배열에는 본인보다 앞에서 서야 하는 학생의 수를 저장
2. v 배열은 학생이 줄에 섰는지 체크
3. post[i]에는 i번째 학생이 선행되어야 하는 학생들의 번호를 저장
4. pre[i]==0인 선행되어야 하는 학생 수가 0인 학생들을 반복적으로 확인해주며 모두 완료되면 종료

   코드

   import java.io.*;
   import java.util.*;
   

public class Main {

public static void main(String[] args) throws IOException {
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

    StringTokenizer st=new StringTokenizer(br.readLine());
    int n=Integer.parseInt(st.nextToken());
    int m=Integer.parseInt(st.nextToken());

    int[] pre=new int[n+1];
    int[] v=new int[n+1];
    ArrayList<Integer>[] post=new ArrayList[n+1];
    for(int i=1;i<n+1;i++)post[i]=new ArrayList<>();
    ArrayList<Integer> ans=new ArrayList<>();

    for(int i=0;i<m;i++){
        st=new StringTokenizer(br.readLine());
        int a=Integer.parseInt(st.nextToken());
        int b=Integer.parseInt(st.nextToken());
        pre[b]++;
        post[a].add(b);
    }

    while(ans.size()!=n){
        for(int i=1;i<n+1;i++){
            if(v[i]==0 && pre[i]==0){
                v[i]=1;
                ans.add(i);
                for(int a:post[i])pre[a]--;
            }
        }
    }

    BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
    for(int a:ans)bw.write(a+" ");
    bw.flush();
}

}

``` #위상정렬

풀이

1. 우선순위큐를 사용하여 크루스칼 알고리즘 구현
2. 유니온파인드를 통해서 연결된 노드를 한 그룹으로 묶어줬다.

   코드

   import java.io.*;
   import java.util.*;
   

public class Main {

static int[] group;
static int groupCnt;

public static void main(String[] args) throws IOException {
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

    int n=Integer.parseInt(br.readLine());
    int m=Integer.parseInt(br.readLine());
    group=new int[n+1];
    groupCnt=n;
    for(int i=1;i<n+1;i++)group[i]=i;
    PriorityQueue<Line> pq=new PriorityQueue<>();
    for(int i=0;i<m;i++){
        StringTokenizer st=new StringTokenizer(br.readLine());
        int a=Integer.parseInt(st.nextToken());
        int b=Integer.parseInt(st.nextToken());
        int c=Integer.parseInt(st.nextToken());
        pq.add(new Line(a,b,c));
    }

    int ans=0;
    while(!pq.isEmpty()){
        if(groupCnt==1)break;
        Line line=pq.poll();
        if(line.a==line.b)continue;
        boolean ret=union(line.a, line.b);
        if(ret)ans+=line.cost;
    }
    System.out.println(ans);
}

static int find(int x){
    if(x!=group[x]){
        group[x]=find(group[x]);
    }
    return group[x];
}

static boolean union(int a,int b){
    a=find(a);
    b=find(b);
    if(a==b)return false;
    if(a<b)group[b]=a;
    else group[a]=b;
    groupCnt--;
    return true;
}

static class Line implements Comparable<Line>{
    int a,b,cost;

    public Line(int a, int b, int cost) {
        this.a = a;
        this.b = b;
        this.cost = cost;
    }

    public int compareTo(Line o){
        return this.cost-o.cost;
    }
}

}

``` #MST #유니온파인드

풀이

1. 물건들을 무게순으로 오름차순 정렬
2. dp 2차원 배열의 행은 물건 열은 무게
3. dp 배열의 값은 해당 무게에서 가치의 최댓값이다.
4. j-물건의 무게가 0 이상과 0 미만일 경우 구분해서 구해준다.

   코드

   import java.io.*;
   import java.util.*;
   

public class Main {

public static void main(String[] args) throws IOException {
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

    StringTokenizer st=new StringTokenizer(br.readLine());
    int n=Integer.parseInt(st.nextToken());
    int k=Integer.parseInt(st.nextToken());
    Goods[] goods=new Goods[n];
    for(int i=0;i<n;i++){
        st=new StringTokenizer(br.readLine());
        int w=Integer.parseInt(st.nextToken());
        int v=Integer.parseInt(st.nextToken());
        goods[i]=new Goods(w,v);
    }
    Arrays.sort(goods);
    int[][] dp=new int[n+1][k+1];
    int ans=0;
    for(int i=1;i<n+1;i++){
        Goods item=goods[i-1];
        for(int j=1;j<k+1;j++){
            if(j-item.w>=0){
                dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-item.w]+item.v);
            }
            else dp[i][j]=dp[i-1][j];
            ans=Math.max(ans,dp[i][j]);
        }
    }

    System.out.println(ans);
}

static class Goods implements Comparable<Goods>{
    int w;
    int v;

    public Goods(int w, int v) {
        this.w = w;
        this.v = v;
    }

    @Override
    public int compareTo(Goods o) {
        return this.w-o.w;
    }
}

}

``` #dp

풀이

1. 이분탐색
   • B 배열만 정렬해주고 A 배열 각 원소마다 이분탐색 진행
2. 원포인터
   • A,B 둘다 정렬 원포인터 사용
   • a[i] 원소보다 큰거나 같은 것 발견할때까지 포인터 이동, 멈추면 다음 원소로 포인터부터 시작해서 다시 진행

코드

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
//        System.out.println(new Solution().solution(elements));
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

        int t=Integer.parseInt(br.readLine());
        while(t-->0){
            StringTokenizer st=new StringTokenizer(br.readLine());
            int n=Integer.parseInt(st.nextToken());
            int m=Integer.parseInt(st.nextToken());
            int[] a=new int[n];
            int[] b=new int[m];

            st=new StringTokenizer(br.readLine());
            for(int i=0;i<n;i++)a[i]=Integer.parseInt(st.nextToken());
            st=new StringTokenizer(br.readLine());
            for(int i=0;i<m;i++)b[i]=Integer.parseInt(st.nextToken());
            Arrays.sort(b);

            //이분탐색
            int ans=0;
            for(int num:a){
                int l=0;
                int r=m-1;
                int mid=(l+r)/2;
                while(l<=r){
                    mid=(l+r)/2;
                    if(num<=b[mid]){
                        r=mid-1;
                    }
                    else if(num>b[mid]){
                        l=mid+1;
                    }
                }
                ans+=l;
            }

                // 원포인터
//            Arrays.sort(a);
//            int ans=0,pointer=0;
//            for(int num:a){
//                while( pointer<m && num>b[pointer]){
//                    pointer++;
//                }
//                ans+=pointer;
//            }
            System.out.println(ans);
        }
    }
}

#이분탐색

풀이

• 처음에 Set을 이용하여 구현했지만, 집합에 같은 번호 스시가 여러개 포함되어 있을 때 remove를 하면 한번에 삭제되는 문제가 있었다.
• 그래서 DAT로 변경하여 개수로 체크해줬다.
• 원형을 고려해서 인덱스를 % n 을 해줘서 인덱스 에러 방지

  코드

  import java.io.*;
  import java.util.*;
  

public class Main {

public static void main(String[] args) throws IOException {
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

    StringTokenizer st=new StringTokenizer(br.readLine());
    int n=Integer.parseInt(st.nextToken());
    int d=Integer.parseInt(st.nextToken());
    int k=Integer.parseInt(st.nextToken());
    int c=Integer.parseInt(st.nextToken());

    int[] sushi=new int[n];
    for(int i=0;i<n;i++)sushi[i]=Integer.parseInt(br.readLine());

    int[] dat=new int[d+1];
    int max=0;
    for(int i=0;i<k;i++){
        if(dat[sushi[i]]==0)max++;
        dat[sushi[i]]++;
    }
    int cnt=max;
    for(int i=1;i<=n;i++){
        dat[sushi[i-1]]--;
        if(dat[sushi[i-1]]==0)cnt--;
        if(dat[sushi[(i+k-1)%n]]==0)cnt++;
        dat[sushi[(i+k-1)%n]]++;
        if(dat[c]==0)max=Math.max(max,cnt+1);
        else max=Math.max(max,cnt);
    }
    System.out.println(max);
}

}

``` #슬라이딩윈도우

풀이

1. 숫자 정렬
2. l=0 r=n-1부터 투포인터 진행
3. 두 용액 더했을 때 절댓값이 작으면 정답 갱신, 더한 값이 0보다 작으면 l++ 0보다 크면 r--

   코드

   import java.io.*;
   import java.util.*;
   

public class Main {

public static void main(String[] args) throws IOException {
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    int n=Integer.parseInt(br.readLine());
    int[] arr=new int[n];
    StringTokenizer st=new StringTokenizer(br.readLine());
    for(int i=0;i<n;i++)arr[i]=Integer.parseInt(st.nextToken());
    Arrays.sort(arr);

    int l=0;
    int r=n-1;
    int sum=Math.abs(arr[0]+arr[n-1]);
    int ans1=arr[0];
    int ans2=arr[n-1];
    while(l<r){
        int a=arr[l]+arr[r];
        if(Math.abs(a)<sum){
            sum=Math.abs(a);
            ans1=arr[l];
            ans2=arr[r];
        }
        if(a<0)l++;
        else r--;
    }
    System.out.println(ans1+" "+ans2);
}

}

``` #투포인터