cobin_dev.log

Kafka Listener의 LazyInitializationException 트러블슈팅

Sun, 15 Jun 2025 12:18:08 GMT

오류 상황

Kafka로 주문 완료 메시지를 주고받는 스마트ETA 시스템을 개발 중이었다.
Spring Boot + JPA 기반의 애플리케이션에서 Kafka 메시지를 수신한 후, Order 엔티티를 조회하고 관련 Store 정보를 활용해 지연 통계를 갱신하는 로직을 구현했다.
하지만 메시지 수신 처리 도중 예상치 못한 예외가 발생했다.

오류 내용

Kafka 메시지 리스너에서 예외 발생:

org.hibernate.LazyInitializationException: Could not initialize proxy [com.example.delivery.store.domain.Store#1] - no session

오류 코드

OrderService.java 일부

/**
     * 배달을 완료하는 메서드
     * @param orderId 주문 ID
     * @param deliveredAt 배달 완료 시각
     */
    public void completeDelivery(Long orderId, LocalDateTime deliveredAt) {
        Optional order = orderRepository.findById(orderId);
        if(order.isEmpty()) throw new RuntimeException("주문을 찾을 수 없습니다.");

        Order o = order.get();
        o.completeDelivery(deliveredAt);
        orderRepository.save(o);

        // Kafka 메시지 발행
        DeliveryCompletedEvent event = new DeliveryCompletedEvent(o.getId(), deliveredAt);
        producer.send("delivery-status", event);
    }

DeliveryCompletedListener.java 일부

    /**
     * Kafka로부터 배달 완료 이벤트를 수신하고 처리하는 리스너
     *
     * - 토픽: delivery-status
     * - 그룹 ID: smarteta-group
     * - 메시지 형식: DeliveryCompletedEvent (주문 ID, 배달 완료 시간 포함)
     *
     * 처리 로직:
     * 1. 전달받은 주문 ID로 Order를 조회
     * 2. 해당 Order의 배달 완료 시간(deliveredAt)을 업데이트
     * 3. StoreDelaySummaryService를 통해 지연 통계를 갱신
     */
    @KafkaListener(topics = "delivery-status", groupId = "smarteta-group")
    public void listen(DeliveryCompletedEvent event) {
        try {
            log.info("배달 완료 메시지 수신: {}", event);

            Optional optionalOrder = orderRepository.findById(event.orderId());
            if (optionalOrder.isEmpty()) {
                log.warn("주문 ID={} 에 해당하는 주문을 찾을 수 없습니다.", event.orderId());
                return;
            }

            Order order = optionalOrder.get();
            order.completeDelivery(event.deliveredAt());
            summaryService.processCompletedOrder(order);

            log.info("주문 처리 완료 → 주문 ID: {}", order.getId());
        }catch (Exception e){
            log.error(" Kafka 메시지 처리 중 예외 발생", e);
        }
    }

Order.java의 일부

/* 주문 도메인 */
@Table(name = "orders")
public class Order {

    // 주문 아이디
    @Id
    @GeneratedValue(strategy = GenerationType.IDENTITY)
    private Long id;

    // 유저 ID
    private Long userId;

    // 매장
    @ManyToOne(fetch = FetchType.LAZY)
    @JoinColumn(name = "store_id")
    private Store store;

    // 매장과 목적지까지의 거리
    private double distanceKm;

하나의 EC2 안에 Kafka, MySQL, 그리고 Spring 서버(Docker 컨테이너)가 포함되어 있음
Spring 서버는 Kafka 메시지를 수신하여 JPA를 통해 DB 조회 후 지연 통계 업데이트 로직을 실행함

현재 흐름

Kafka Listener가 비동기적으로 메시지를 수신함
Listener는 orderRepository.findById(event.getOrderId()) 로 Order 객체를 가져옴
이 Order는 내부에 Store를 갖고 있지만, 아직 store는 프록시 상태
store.getName()을 호출하는 순간 JPA가 Store를 로딩하려 함
문제는 이 시점엔 이미 Hibernate 세션이 닫혀 있음 (Kafka Listener는 트랜잭션 바깥에서 실행됨) → 따라서 DB에 접근할 수 없어 LazyInitializationException 예외 발생

예상 원인

LazyInitializationException이란?

JPA는 @ManyToOne(fetch = LAZY) 관계에서 실제 연관 객체(Store)를 처음부터 조회하지 않고, 프록시 객체로 감싸 놓는다.
이 프록시는 실제 데이터가 필요한 시점(getName() 호출 등)에 DB에 접근해 데이터를 가져오려 한다.

하지만 이 시점에 JPA 세션(Session) 이 이미 닫혀 있으면 프록시가 초기화되지 못하고 예외가 발생한다.

LazyInitializationException 발생원인

Kafka 메시지를 수신하는 메서드 listen() 내부에서는 트랜잭션이 자동으로 생성되지 않는다.
따라서 orderRepository.findById(orderId)로 조회한 Order는 프록시 상태로 존재하며,
해당 Order에 연결된 Store를 조회하려고 할 때 세션이 이미 닫혀 예외가 발생했다.

즉,

Order order = orderRepository.findById(...).get();
order.getStore().getName(); // 여기서 LazyInitializationException 발생

실제 해결 방법

@Transactional 추가

@Transactional
public void listen(DeliveryCompletedEvent event) {
    ...
}

Kafka 메시지를 처리하는 메서드에 @Transactional을 붙이면,
Spring은 해당 메서드 수행 중 JPA 세션을 유지시켜 프록시 초기화가 가능하도록 한다.

결과적으로 LazyInitializationException이 해결되었다.

트랜잭션 없이 세션이 닫히는 기준은?

JPA의 세션(Session)은 트랜잭션 단위로 열리고 닫힌다.
트랜잭션이 없을 경우, Spring Data JPA가 리포지토리 메서드 수행 중 임시로 세션을 열고 바로 닫는다.
따라서 리포지토리에서 반환된 엔티티는 더 이상 DB 접근이 불가능한 "프록시 객체"로 남게 된다.

🧾 참고

Spring Boot + Kafka 연동 (with Docker)

Sat, 14 Jun 2025 13:33:15 GMT

배달 관련 프로젝트를 진행하며 도커와 카프카 도입이 필요했다.

1. Kafka를 도입한 이유

배달 ETA는 주문 상태 변화에 따라 유동적으로 조정된다.
Kafka는 이런 이벤트 기반 아키텍처에서 핵심 역할을 하는 메시지 브로커이기 때문

2. Kafka 환경 구성 (Docker Compose)

version: '3.8'

services:
  zookeeper:
    image: bitnami/zookeeper:latest
    container_name: zookeeper
    ports:
      - "2181:2181"  # Zookeeper는 Kafka를 위한 메타데이터 저장소 역할
    environment:
      - ALLOW_ANONYMOUS_LOGIN=yes

  kafka:
    image: bitnami/kafka:3.5.1
    container_name: kafka
    ports:
      - "9092:9092"  # Kafka 브로커가 외부로 노출되는 포트
    environment:
      - KAFKA_CFG_ZOOKEEPER_CONNECT=zookeeper:2181  # Zookeeper 연결 설정
      - KAFKA_CFG_LISTENERS=PLAINTEXT://:9092  # 내부용 Listener
      - KAFKA_CFG_ADVERTISED_LISTENERS=PLAINTEXT://localhost:9092  # 외부용 Listener
      - ALLOW_PLAINTEXT_LISTENER=yes  # 인증 없이 허용 (개발용)
      - KAFKA_ENABLE_KRAFT=no  # KRaft 모드 비활성화 → Zookeeper 기반 Kafka 사용
    depends_on:
      - zookeeper  # Kafka는 Zookeeper가 먼저 실행되어야 함

실행하기 (실행 명령어)

docker compose up -d

도커에서 잘 실행되고 있다!

3. Spring Boot 설정

Gradle 의존성 추가

implementation 'org.springframework.kafka:spring-kafka'

application.yml 설정

spring:
  kafka:
    bootstrap-servers: localhost:9092
    consumer:
      group-id: smarteta-group
      auto-offset-reset: earliest

4. Kafka 프로듀서/리스너 코드

Producer: Kafka 메시지를 보내는 역할

@Component
public class DeliveryEventProducer {

    private final KafkaTemplate kafkaTemplate;

    public DeliveryEventProducer(KafkaTemplate kafkaTemplate) {
        this.kafkaTemplate = kafkaTemplate;
    }

    public void send(String topic, String message) {
        kafkaTemplate.send(topic, message);
        System.out.println("보낸 카프카 메시지 → " + message);
    }
}

Listener: Kafka 메시지를 받는 역할

@Component
public class DeliveryEventListener {

    @KafkaListener(topics = "test-topic", groupId = "smarteta-group")
    public void listen(String message) {
        System.out.println("받은 카프카 메시지: " + message);
    }
}

테스트용 Controller

@RestController
@RequestMapping("/kafka")
public class KafkaTestController {

    private final DeliveryEventProducer producer;

    public KafkaTestController(DeliveryEventProducer producer) {
        this.producer = producer;
    }

    @GetMapping("/send")
    public ResponseEntity send() {
        producer.send("test-topic", "스프링과 카프카 연동 완료!");
        return ResponseEntity.ok("Sent!");
    }
}

5. Postman으로 테스트

요청 정보

항목	값
Method	GET
URL	http://localhost:8080/kafka/send

결과 (콘솔)

백준 1953번 팀배분

Mon, 28 Oct 2024 12:32:08 GMT

문제

백준 1953번 팀배분 링크

처음에 문제를 보고 유니온 파인드가 떠올랐다. 그런데 잘보니 유니온이 아니라 다른 팀이 되야하는 연산을 해야하므로 유니온 파인드로 풀기는 어려웠다.

이후 아래 코드를 구현했다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N;
    static int [] parent;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());

        parent = new int[N+1];
        Arrays.fill(parent, 1); // 1과 -1로 구분

        for(int i=1; i<=N; i++){
            st = new StringTokenizer(br.readLine());
            int total = Integer.parseInt(st.nextToken());
            int nowTeam = parent[i];
            for(int k=0; k firstTeam = new ArrayList<>();
        List secondTeam = new ArrayList<>();
        for(int i=1; i<=N; i++){
            if(parent[i] == 1) firstTeam.add(i);
            else secondTeam.add(i);
        }

        Collections.sort(firstTeam);
        Collections.sort(secondTeam);

        sb.append(firstTeam.size()).append("\n");
        for(int num : firstTeam) sb.append(num).append(" ");
        sb.append("\n");

        sb.append(secondTeam.size()).append("\n");
        for(int num : secondTeam) sb.append(num).append(" ");

        System.out.print(sb);
    }
}

그런데 이 코드는 통과할 수 없다. 반례를 구하기 어려워 내가 직접 반례를 찾아야했다.

위와 같은 입력을 하면 내가 작성한 코드에서는 아래와 같이 출력된다.

1번은 분명 2, 3번과 같은팀이 되면 안되는데 말이다,,,,

이유는 간단하다. 내가 1번을 보고 2번과 3번을 -1로 초기화 했을 떄 4번은 1인 상태이다. 그런데 4번이 1을 싫어한다는 것을 보는 순간 4번의 값(1)에 -를 붙임 -1을 1의 값으로 설정하게 되어 배열이 -1 -1 -1 1 이 되어버리는 것이다.

따라서 우리는 DFS를 통해 풀어야한다. 왜냐하면 하나가 결정되면 cascade로 결정을 해주고, 또 결정된 것을 cascade로 싫어하는 사람을 -한 값으로 저장해야하기 때문이다. 이러한 과정에서 중요한 것은 visited를 사용해야한다는 것이다. 이미 팀을 배정받은 사람이 다시 팀을 배정받으면 모든 규칙이 엉망이 되어버리기 때문이다.

풀이 방법

1. 싫어하는 사람들을 인접 리스트 배열로 양방향 저장하기

싫어하는 사람들을 인접 리스트 배열로 저장해야한다. 이때 양방향으로 저장해야함에 주의하자.

        for(int i=1; i<=N; i++){
            st = new StringTokenizer(br.readLine());
            int total = Integer.parseInt(st.nextToken());
            for(int k=0; k


2. 1번은 1번팀에 고정하고, DFS 돌리기
어차피 2개의 팀밖에 주어지지 않으므로 1번은 1번팀에 고정한다.
이후 DFS를 돌린다.
team[1] = 1; // 1번은 1번 팀
        for(int i=1; i<=N; i++){
            if(!visited[i]) DFS(i, team[i]);
        }
static void DFS(int num, int nowTeam){
        visited[num] = true;
        for(int n : arr[num]){
            if(!visited[n]) {
                team[n] = - nowTeam;
                DFS(n, - nowTeam);
            }
        }
    }
3. 순서대로 출력하기
이제 각 팀의 인원을 계산한 뒤 오름차 순으로 출력한다.
int firstTeam = 0; // 첫번째 팀 인원수
        for(int i=1; i<=N; i++){
            if(team[i] == 1) firstTeam++;
        }
        sb.append(firstTeam).append("\n");

        int secondTeam = N - firstTeam; // 두번째 팀 인원수

        // 첫번째 팀 출력
        for(int i=1; i<=N; i++){
            if(team[i] == 1) sb.append(i).append(" ");
        }
        sb.append("\n");

        sb.append(secondTeam).append("\n");
        // 두번째 팀 출력
        for(int i=1; i<=N; i++){
            if(team[i] == -1) sb.append(i).append(" ");
        }

        System.out.print(sb);

정답 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class p1953 {
    static int N;
    static int [] team;
    static List [] arr;
    static boolean[] visited;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());

        arr = new List[N+1];
        team = new int[N+1];
        visited = new boolean[N+1];
        for(int i=1; i<=N; i++) arr[i] = new ArrayList<>();


        for(int i=1; i<=N; i++){
            st = new StringTokenizer(br.readLine());
            int total = Integer.parseInt(st.nextToken());
            for(int k=0; k



백준 16472번 고냥이
Fri, 06 Sep 2024 14:44:19 GMT
문제
백준 16472번 고냥이 링크



풀이 방법
먼저 문제를 잘 읽어야한다. 사실 나는 처음에 문제를 잘못 읽어서 틀렸기 때문이다.
입력으로 받은 문자열 종류 최대 개수 안에서 최대 문자열 길이를 출력해야한다.
1. 알파벳 제일 최근 출현 배열 만들기
먼저 알파벳 최근 출현 배열을 만들어야한다. 그 이유는 새로 검사한 알파벳을 추가했을 때 현재 인식 중인 알파벳의 종류에는 없는 알파벳인 경우 문제에서 주어진 N을 초과하게된다. 따라서 이 경우 제일 알파벳 종류 중 1개를 제거해야하는데, 이 때 출현이 가장 오래된 알파벳을 제거할 것이기 때문에 알파벳이 나오면 해당 알파벳의 최근 출현 위치를 기록할 배열이 필요하다.
배열의 길이는 알파벳의 개수만큼 만들면 된다.int배열의 기본 값인 0으로 초기화 되면 마지막 출현 위치가 헷갈릴 수 있으므로 -1로 초기화해주었다.
2. 현재 출현 알파벳 종류를 세기 위한 Set 만들기
현재 인식 중인 알파벳의 종류를 세기 위해서 set을 사용한다. 
3. 다음 알파벳을 추가했을 때 최대 알파벳 종류의 개수를 넘어가면 문자열 길이 업데이트 하기
새로운 알파벳을 검사했을 때 3가지 경우로 나뉜다.
3-1. 현재 인식가능한 알파벳에 종류에 포함되어 있지 않은데, 이 알파벳을 인식하면 최대 인식 종류 개수를 넘는 경우
1) 정답과 비교하여 최대 인식 길이를 업데이트 해준다.
2) 최종 출현 위치가 가장 낮은(일찍인) 문자를 찾아야한다. 알파벳 출현 배열에서 -1이 아닌 가장 작은 값을 찾으면 그 알파벳일 것이다. 
3) 현재 인식 길이를 현재 위치 - 찾은 알파벳의 최종 출현 위치로 업데이트 한다.
4) 찾은 알파벳의 최종 출현 위치 배열에서의 값을 -1로 업데이트 한다.
5) 인식 가능한 문자 set 에서 찾은 알파벳을 제거한다.
6) 새 문자를 인식 가능한 문자 set에 넣는다.
3-2. 현재 인식가능한 알파벳에 종류에 포함되어 있지 않은데, 이 알파벳을 인식해도 최대 인식 종류 개수를 넘지 않는 경우
1) 새 문자를 인식 가능한 문자 set에 넣는다.
2) 현재 인식 가능한 문자 종류 플래그를 1 증가시킨다.
3) 현재 인식 길이를 +1 해준다.
4) 최대 인식 길이를 업데이트 해준다.
3-3. 현재 인식가능한 알파벳에 종류에 포함된 경유
1) 새 문자를 인식 가능한 문자 set에 넣는다.
2) 현재 인식 길이를 +1 해준다.
3) 최대 인식 길이를 업데이트 해준다.

정답 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class p16472 {
    static int [] alpha;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String line = br.readLine();
        alpha = new int ['z'-'a'+1]; // 각 알파벳의 마지막 출현 위치 배열

        Arrays.fill(alpha,-1); // 마지막 출현 위치를 -1로 초기화

        // 찾기
        Set set = new HashSet<>(); // 현재 인식가능한 알파벳들을 넣어둔 집합
        int result = 1; // 정답
        int nowKind = 1; // 현재 인식하고 있는 문자열의 종류 (첫번째꺼를 넣으므로 초기값은 1)
        int nowLen = 1; // 현재 인식하고 있는 문자열의 길이 (첫번째꺼를 넣으므로 초기값은 1)

        // 첫번째 꺼 미리 넣어두기
        set.add(line.charAt(0));
        alpha[line.charAt(0)-'a'] = 0;

        for(int i=1; i




백준 1987번 알파벳
Mon, 19 Aug 2024 06:37:45 GMT
문제
백준 1987번 알파벳 링크



풀이 방법
간단한 DFS 문제다. visited[] 배열을 각 문자열에 대해서 만들고 이미 방문한 문자를 방문하지 않게 하는 방식으로 풀어나가면 된다.
1. 문자열에 대해 visited 배열 만들기
문제에서 대문자들로 배열이 주어지므로 아스키 코드로 65번부터 90번까지의 문자이다. 따라서 visited[] 배열의 크기를 26으로 만들고 각각 인덱스를 문자 - 65로 생각하면된다.
2. DFS 구현하기
일반적인 DFS와 똑같이 구현하면 된다.
static void DFS(int r, int c, boolean[] visited) {
    int idx = arr[r][c] - 65; // 현재 문자의 아스키 코드
    if(!visited[idx]) { // 방문한 적 없으면
        visited[idx] = true;
        for(int i=0 ;i<4; i++) {
            int newX = c + dx[i];
            int newY = r + dy[i];
            if(check(newX, newY)) {
                DFS(newY, newX, visited);
            }
        }
        // 나올 때는 visited를 false로 바꿔줌
        visited[idx] = false;
    }else { // 방문 했으면
        // max 업데이트
        int cnt = 0;
        for(int i=0; i<26; i++) {
            if(visited[i]) {
                cnt++;
            }
        }
        if(max < cnt) max = cnt;
    }
}
3. max 업데이트 후 출력하기
만약 이미 방문한 문자라면 현재 visited[] 배열에서 방문한 것들을 센 후 max와 비교하여 max를 업데이트 해준다. 여기서 max는 최대 몇칸을 갈 수 있는지를 나타낸다.

정답 코드
package 백준;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class p1987 {
    static int R, C;
    static int [] dx = {-1, 0, 0, 1};
    static int [] dy = {0, 1, -1, 0};
    static char [][] arr;
    static int max = 1;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        arr = new char [R][C];

        for(int i=0; i=0 && x=0;
    }
}



백준 28107번 회전초밥
Sun, 18 Aug 2024 12:41:23 GMT
문제
백준 28107번 회전초밥 링크



간단한 문제라고 생각한다. 특별한 알고리즘 기법이 들어가기보다는 문제 조건대로 큐를 사용해서 구현하면 된다.
또한 초밥 리스트 배열과 손님별 먹은 초밥 수 배열을 사용해야겠다는 아이디어만 있으면 충분히 풀 수 있다.
풀이 방법
1. 초밥 리스트 배열 만들기
먼저 그래프를 구현하는 것처럼 초밥 리스트 배열을 구현했다. 1 ~ N 손님들은 각 순서대로 우선순위가 있기 때문에 우선순위 큐 대신 그냥 큐를 사용했다. 따라서 초밥마다 먹을 사람을 링크드 리스트에 저장하는 형식이다.
// 초밥 리스트 배열 초기화
LinkedList[] sushi = new LinkedList[200_001];
for (int i = 1; i <= 200_000; i++) {
    sushi[i] = new LinkedList<>();
}
2. 초밥 리스트 배열 채우기
이제 주어진 손님 리스트에 따라 초밥 리스트를 채운다.
// 초밥 리스트 배열 채우기
for (int i = 1; i <= N; i++) {
    st = new StringTokenizer(br.readLine());
    int dishes = Integer.parseInt(st.nextToken());
    for (int j = 0; j < dishes; j++) {
        int now = Integer.parseInt(st.nextToken());
        sushi[now].add(i);
    }
}
3. 요리사가 만든 초밥을 먹을 사람 구하기
이제 우선순위가 저장되었으므로 요리사가 초밥을 만들 때마다 초밥을 먹을 사람을 정해주어야한다. 따라서 요리사가 초밥을 만들면 초밥 리스트에서 해당 초밥의 리스트를 확인하여 사이즈가 0보다 크면 해당 사람을 리스트에서 삭제하고, 손님별 먹은 초밥 수 배열에서 해당 손님을 +1 한다.
// 요리사가 초밥을 만드는 과정
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= M; i++) {
    int now = Integer.parseInt(st.nextToken()); // 요리사가 현재 만든 초밥
    if (sushi[now].size() > 0) { // 초밥을 먹을 사람이 있으면
        int eatPerson = sushi[now].remove(0);
        eat[eatPerson]++;
    }
}
4. 각 사람이 먹은 초밥의 개수 출력하기
이제 손님별 먹은 초밥 수 배열을 순서대로 출력한다.
for (int i = 1; i <= N; i++) {
    sb.append(eat[i]).append(" ");
}


정답 코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class p28107 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        // 손님 수와 초밥 수 입력받기
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); // 손님 수
        int M = Integer.parseInt(st.nextToken()); // 초밥 수

        // 손님별 먹은 초밥 수 배열 초기화
        int[] eat = new int[N + 1];
        // 초밥 리스트 배열 초기화
        LinkedList[] sushi = new LinkedList[200_001];
        for (int i = 1; i <= 200_000; i++) {
            sushi[i] = new LinkedList<>();
        }

        // 초밥 리스트 배열 채우기
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            int dishes = Integer.parseInt(st.nextToken());
            for (int j = 0; j < dishes; j++) {
                int now = Integer.parseInt(st.nextToken());
                sushi[now].add(i);
            }
        }

        // 요리사가 초밥을 만드는 과정
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= M; i++) {
            int now = Integer.parseInt(st.nextToken()); // 요리사가 현재 만든 초밥
            if (sushi[now].size() > 0) { // 초밥을 먹을 사람이 있으면
                int eatPerson = sushi[now].remove(0);
                eat[eatPerson]++;
            }
        }

        for (int i = 1; i <= N; i++) {
            sb.append(eat[i]).append(" ");
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}




백준 1106번 호텔
Fri, 16 Aug 2024 12:34:58 GMT
문제
백준 1106번 호텔 링크



보자마자 DP 문제라는 것을 알았다. 그리고 DP중에서도 냅색 문제라고 생각했다. 그런데 일반적인 냅색 문제와는 달랐다.

일반적인 냅색 문제는 0-1 냅색문제로 짐이 1번 들어가거나 0번들어가거나 둘 중 하나의 경우인 상황이다.

그러나 이 문제를 보면 짐(여기서는 도시)이 1번이 아닌 여러번 들어갈 수 있다.

따라서 이 문제는 0-1 냅색 문제를 응용해야한다는 것을 느꼈다.

풀이 방법
1. DP 배열을 어떻게 만들지 구상하기
먼저 DP 배열을 어떻게 만들지 구상해야한다. 기존의 냅색 문제는 DP 배열을 두가지로 만들 수 있다.

1차원 배열


dp[i]
행: 최대 허용 가능한 무게
dp[i]: 는 무게가 최대 i까지 허용될 때 모든 짐을 고려하여 얻을 수 있는 최대 효용


2차원 배열


dp[i][j]
열: 각 짐들의 개수(각 짐)
행: 최대 허용 가능한 무게
dp[i][j]: 는 무게가 최대 j까지 허용될 때 짐 i개(예를 들어 1번짐부터 i번짐)를 고려했을 때 얻을 수 있는 최대 효용 

그렇다면 현재 문제에서는 dp배열을 어떻게 만들어야할까?
이번 문제에서는 1차원 배열을 만들고 각 행은 최대 허용 가능한 무게를, dp[i]의 값은 i가 최대 허용 가능 무게일 때 최소 비용이다.
이 문제에서 주어진 조건을 바꿔서 말하면 다음과 같다.

1차원 배열


dp[i]
행 고객 수
dp[i] 고객수가 i명을 유치하기 위한 최소 비용

배열의 길이는 몇으로 해야할까?
언뜻보면 C라고 생각할 수 있다. 하지만 결과적으로 C+100으로 해주어야한다. 배열에서 각 인덱스의 의미는 고객 수이다. i가 100이면 100명의 고객을 유치할 때의 최소 비용이 dp[i]이고, i가 101이면 101명의 고객을 유치할 때의 최소 비용이 dp[i]이다.
예를 들어 A도시는 3명을 유치하는 데에 5의 비용이 들고, B도시는 1명을 유치하는 데에 10의 비용이 든다고 가정해보자.
dp[1] = 10 이고 dp[2] = 20 인데 dp[3] = 5이다.
정확히 i명을 유치하는 데에 필요한 비용이므로 C명을 유치하는 데에 필요한 비용은 dp[C]이지만 최소 C명을 유치하는 비용은 dp[C+a] 일 수 있다.
그럼 여기서 a는 어떻게 정할까?
최대 사람 수가 100이므로 C+100을 해주면 더이상 유치할 수 없는 경우까지 안전하게 계산해준다. 
2. DP 배열을 어떻게 채울지 구상하기
이제 DP배열을 만들었으니 어떻게 채울지를 결정해야한다.
기존의 0-1냅색 문제의 1차원 배열은 아래와 같은 식으로 채워주었다.
for(int i=1; i<=N; i++){
    for(int w=Limit; w>=value[i]; w--){
        dp[w] = Math.Max(dp[w], dp[w - weigth[i]]+ value[i]);
    }
}
이번에는 최소를 구해주어야하므로 Min을 사용해야한다. 그런데 0-1 냅색 문제에서는 따로 배열을 초기화하지 않았는데 그 이유는 배열을 선언하면 0으로 초기화 되기 때문이다. 그리고 Math.max()를 사용하므로 0으로 초기화해주는 것이 맞다.
하지만 이번에는 Math.min()을 사용해야하므로 배열들을 MAX_VALUE로 초기화해주어야한다. 또한 dp[0] = 0으로 초기화해준다. 이 의미는 0명을 유치하기 위한 비용은 0이라는 의미이다.
이제 초기화는 했으니 dp[1]부터 채워나가야한다.
dp[i]는 i명을 유치하기 위한 최소 비용이므로 dp[i]와 dp[i-현재 도시의 유치 가능한 사람 수]+ 현재 도시의 사람들을 유치하는 데에 드는 비용 중 최소값을 dp[i]로 설정해야한다.

그런데 이 때 주의할 점이 있다. 바로 dp[i-현재 도시의 유치 가능한 사람 수]가 우리가 초기화한 MAX_VALUE가 아닌 경우에만 위 점화식을 사용해야한다는 것이다.

왜냐하면 우리가 초기화한 MAX_VALUE는 해당 사람을 유치하는 방법이 없다는 것을 의미하기 때문이다. 따라서 i-현재 도시의 유치 가능한 사람 수명을 유치하는 방법은 존재하지 않은 것이므로 계산할 수 없다.

따라서 코드는 아래와 같이 된다.
            // DP 배열 채우기
            for (int j = v; j < C + 100; j++) {
            //만약 dp배열에서 현재 사람 수를 뺀 사람 명수의 비용이 초기 비용이 아니면 (초기 비용으로 초기화한 것은 만족시킬 수 없는 상태를 나타냄으로)
                if(dp[j-v] != Long.MAX_VALUE){ 
                //현재 배열 값과 현재 배열에서 v명을 빼고 i번째 사람을 넣었을 때의 비용 중 작은 것으로 결정
                    dp[j] = Math.min(dp[j], dp[j - v] + c); 
                }
            }
3. DP 배열을 통해 답을 어떻게 도출할지 생각하기
그렇다면 이렇게 DP배열을 만들었을 때 답은 어떻게 구할까?
아까 말했듯 dp[C]는 답이 될 수도 있고 아닐 수도 있다. 따라서 C ~ C+99까지의 dp[i] 중 가장 작은 것을 답으로 설정해야한다.
이번 문제는 DP의 응용이어서 상당히 오랜 시간이 걸렸지만, 실제 코테에서는 DP를 심화하여 내기가 어려움으로 너무 걱정하진 않아도 될 것 같다.

정답 코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class p1106_2 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        // 입력 받기
        st = new StringTokenizer(br.readLine());
        int C = Integer.parseInt(st.nextToken()); // 목표 인원 수
        int N = Integer.parseInt(st.nextToken()); // 도시 수

        long[] dp = new long[C + 100]; //DP 배열  -> 최대 손님은 100명인데 103명을 하는게 더 최소일 수도 있고, 104명을 하는게 더 최소일 수도 있어서 C에 100을 더함
        // dp[i] =  i명의 사람을 유치하기 위한 최소 비용
        Arrays.fill(dp, Long.MAX_VALUE); // 초기화를 최대값으로 함 -> 나중에 min을 할 것이기 때문에 음수 값으로 하면 안됨

        // dp[0]을 0으로 초기화
        dp[0] = 0; // 0명을 유치하기 위한 비용은 0임

        // 비용과 인원 데이터 받기
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int c = Integer.parseInt(st.nextToken()); // 비용
            int v = Integer.parseInt(st.nextToken()); // 모집 가능한 인원 수

            // DP 배열 채우기
            for (int j = v; j < C + 100; j++) {
                if(dp[j-v] != Long.MAX_VALUE){ //만약 dp배열에서 현재 사람 수를 뺀 사람 명수의 비용이 초기 비용이 아니면 (초기 비용으로 초기화한 것은 만족시킬 수 없는 상태를 나타냄으로)
                    dp[j] = Math.min(dp[j], dp[j - v] + c); //현재 배열 값과 현재 배열에서 v명을 빼고 i번째 사람을 넣었을 때의 비용 중 작은 것으로 결정
                }
            }
        }

        // 답 찾기
        long min = Long.MAX_VALUE;
        for (int i = C; i < C + 100; i++) { //C명 이상을 유치하는 비용 중 가장 작은 비용을 값으로 설정
            min = Math.min(dp[i], min);
        }

        // 출력
        bw.write(min + "\n");
        bw.flush();
        bw.close();
    }
}




백준 17352번 여러분의 다리가 되어 드리겠습니다!
Thu, 15 Aug 2024 12:24:38 GMT
문제
백준 17352번 여러분의 다리가 되어 드리겠습니다! 링크



전형적인 유니온 파인드 문제다. 유니온 파인드를 사용해서 풀었다.
풀이 방법
1. 대표노드 배열 생성하기
유니온 파인드는 대표노드 배열이 필요하다. 따라서 대표노드 배열을 N+1 길이로 생성해야한다.
2. 유니온 연산과 파인드 연산 구현하기
유니온 파인드 문제는 사실 유니온 연산과 파인드 연산을 구현하면 80프로는 끝난다. 따라서 유니온 연산과 파인드 연산을 구현해준다.
3. 첫 노드와 연결되어 있지 않은 노드를 찾아 출력하기
이 문제에서는 다리가 1개만 잘렸고, 어떤 노드끼리 연결할지는 아무거나 출력하라고 했으므로 기준을 첫번째 노드로 잡는다. 왜냐하면 결국 어딘가는 연결되어있지 않기 때문에 1번노드가 포함된 그룹과 1번노드가 포함되지 않은 그룹으로 나뉠 것이기 때문이다. 따라서 1번노드와 대표노드가 같지 않은 노드를 찾으면 해당 노드를 출력하고 종료한다.

정답 코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class p17352 {
    static int [] arr;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(st.nextToken()); // 섬의 개수
        arr = new int[N+1];

        for(int i=1; i




백준 11265번 끝나지 않는 파티
Wed, 14 Aug 2024 06:35:23 GMT
문제
백준 11265번 끝나지 않는 파티 링크



풀이 방법
처음 접근 방식
처음에는 BFS로 접근했었다. 그래프 문제인건 확실했고, 최단거리를 통해서 갈 수 있는지 여부를 확인해야했기 때문이다.
아래가 내가 처음에 작성한 코드이다.
package algo;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class p11265 {
    static List [] arr;
    static int N = 0;
    static long cnt = 0;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();


        //1 입력 받기

        // 1-1. N과 M 입력 받기
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());     // 파티장의 개수(1~)
        int M = Integer.parseInt(st.nextToken());    // 사람 수 (1~)

        // 1-2. 진입 배열 만들기
        arr = new List[N+1];

        //초기화
        for(int i=1; i();

        // 진입 배열로 만들기
        for(int t = 1; t<=N; t++) {
            st = new StringTokenizer(br.readLine());
            for(int j=1; j start로 가야함
    Queue q = new LinkedList<>();

    for(Node n : arr[end]) {
        q.add(new Person(start, n.from, time + n.weight));
    }

    long min = Long.MAX_VALUE;

    while(!q.isEmpty()) {
        Person poll = q.poll();
        visited[poll.end] = true;

        // 만약 도착했으면
        if(poll.start == poll.end) {
            // min보다 작으면 업데이트
            if(min > poll.time) min = poll.time;
        }else { //도착하지 않았으면
            for(Node n : arr[end]) { //자기 자신으로 진입가능한 것들 중에서
                if(!visited[n.from] && maxTime >= (poll.time + n.weight)) {
                    q.add(new Person(start, n.from, poll.time + n.weight));
                }
            }
        }
    }
    return min;
    }
}
class Node{
    int weight;
    int from;

    public Node(int weight, int next) {
        this.weight = weight;
        this.from = next;
    }
}

class Person{
    int start;
    int end;
    long time;

    public Person(int start, int end, long time) {
        this.start = start;
        this.end = end;
        this.time = time;
    }
}

그런데 시간초과가 났다. 
위 코드를 보면 calculate()에서 아래 코드 부분이 O(N * N)이다. 
while(!q.isEmpty()) {
        Person poll = q.poll();
        visited[poll.end] = true;

        // 만약 도착했으면
        if(poll.start == poll.end) {
            // min보다 작으면 업데이트
            if(min > poll.time) min = poll.time;
        }else { //도착하지 않았으면
            for(Node n : arr[end]) { //자기 자신으로 진입가능한 것들 중에서
                if(!visited[n.from] && maxTime >= (poll.time + n.weight)) {
                    q.add(new Person(start, n.from, poll.time + n.weight));
                }
            }
        }
    }

여기서는 N이 500이다. 그런데 calculate()를 M만큼 반복하므로 O(500 * 500 * 100,000) 이다. 따라서 200,000,000을 넘으므로 시간초과가 나는 것이다.

최종 해결 방안
결국 나는 플로이드 워셜 알고리즘을 사용해야한다는 것을 알았다. O(V^3)이긴 하지만 V가 500이므로 충분히 가능하다. 따라서 플로이드 워셜 알고리즘을 사용하여 해결했다.
1. 입력을 받아 2차원 거리 배열 만들기
플로이드 워셜은 2차원 배열을 선언해야한다. 이후 행과 열을 각각 출발 노드와 목적지 노드로 생각하며 문제를 해결한다. 따라서 2차원 배열을 선언하였다.
또한 각 배열의 초기값은 -1로 초기화하고(일반적으로 무한대로 하지만 여기서는 음수 값이 주어지지 않으므로 편의상 -1로 했다), 행과 열이 같으면 자기 자신 노드로 가는 경우이므로 0으로 초기화했다.
이후 2차원 배열에 거리 입력 값을 받았다.
//1 입력 받기

        // 1-1. N과 M 입력 받기
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());     // 파티장의 개수(1~)
        int M = Integer.parseInt(st.nextToken());    // 사람 수 (1~)

        long [][] arr = new long [N+1][N+1];

        // 자기 자신은 0으로 초기화하고 나머지는 -1로 초기화
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                if(i==j) arr[i][j] = 0;
                else arr[i][j] = -1;
            }
        }

        // 각 거리 입력 받기
        for(int i=1; i

2. 플로이드 워셜을 사용하여 거리 배열 업데이트 하기
플로이드 워셜은 아래와 같은 3중 for문으로 이루어진다.
for(1 ~ N) { //K에 대해서 (중간 노드)
    for(1 ~ N){ // S에 대해서(출발 노드)
        for(1 ~ N){ // E에 대해서(목적지 노드)
        }
    }
}
따라서 위 구조를 따라서 아래 코드처럼 거리 배열을 업데이트하였다.
//플로이드워셜로 거리 배열 업데이트
        for(int k=1; k<=N; k++) {    // K
            for(int s=1; s<=N; s++) {    // S
                for(int e=1; e<=N; e++) {    // E
                    arr[s][e] = Math.min(arr[s][e], arr[s][k] + arr[k][e]);
                }                
            }
        }
3. 각 손님에 대해 거리 배열을 참조하여 파티 참석 여부 출력하기
플로이드 워셜 알고리즘을 통해서 거리배열이 완성되었으므로 이제 각 손님에 대해서 해당 파티가 참석 가능한지 출력하는 코드를 작성했다.
//손님들에 따라 가능한지 여부 출력하기
        for(int i=0; i= arr[start][end]) { //시간 안에 가는 경우
                sb.append("Enjoy other party\n");
            }else { //시간 안에 못가는 경우
                sb.append("Stay here\n");
            }
        }

정답 코드
package algo;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class p11265_2 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();


        //1 입력 받기

        // 1-1. N과 M 입력 받기
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());     // 파티장의 개수(1~)
        int M = Integer.parseInt(st.nextToken());    // 사람 수 (1~)

        long [][] arr = new long [N+1][N+1];

        // 자기 자신은 0으로 초기화하고 나머지는 -1로 초기화
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                if(i==j) arr[i][j] = 0;
                else arr[i][j] = -1;
            }
        }

        // 각 거리 입력 받기
        for(int i=1; i= arr[start][end]) { //시간 안에 가는 경우
                sb.append("Enjoy other party\n");
            }else { //시간 안에 못가는 경우
                sb.append("Stay here\n");
            }
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}



백준 19951번 태상이의 훈련소 생활
Mon, 12 Aug 2024 12:38:08 GMT
문제
백준 19951번 태상이의 훈련소 생활 링크



풀이 방법
처음엔 문제를 쉽게 생각해서 1차원 배열에 연병장 높이들을 넣은 뒤 각 작업마다 연산을 해주려고 했다. 그런데 문제 조건을 보면 N과 M이 최대 100,000이기 때문에 1초를 초과한다.
M은 작업의 수라서 무조건 반복해야하기 때문에 N을 줄이는 방식을 택해야한다.
바로 누적합이다.
1. 연병장 배열과 누적합 배열 입력 받기
먼저 연병장 높이들을 받기 위해 1차원 배열을 생성하여 연병장 높이들을 받아준다. 이후 누적합 배열에 시작과 끝을 입력 받는다.
이 때 주의해야하는 점이 우리는 누적합을 추후에 계산할 것이기 때문에 예를 들어 1 ~ 5까지 4만큼 더하기 위해서는 누적합 배열의 1번 인덱스에 4를 더해주어야한다. 또한 6번 인덱스에 4를 빼주어야한다. 누적합 배열을 순회하면서 이전 인덱스의 값을 현재 인덱스의 값에 더해줄 것이기 때문에 이런 방식으로 값을 주어야한다.
2. 누적합 적용하기
누적합 배열은 1번에서 완성되었으므로 누적합 배열을 돌면서 이전 인덱스의 값을 현재 인덱스에 더해준다.
3. 출력하기
마지막으로 누적합 배열에서 각 인덱스에 해당하는 값들을 공백으로 나누어 출력하면 된다.

정답 코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class p19951 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(st.nextToken()); // 연병장 길이
        int M = Integer.parseInt(st.nextToken()); // 작업 개수

        int[] arr = new int[N+1]; // 연병장 배열
        int[] sum = new int[N+1]; // 누적합 배열

        st = new StringTokenizer(br.readLine());

        // 연병장 입력 받기
        for(int i=1; i




백준 2225번 합분해
Sat, 10 Aug 2024 09:17:02 GMT
문제
백준 2225번 합분해 링크



풀이 방법
1. 패턴 파악하기
이 문제는 잘 보면 패턴을 파악할 수 있다. b개의 숫자를 더해서 a를 만드는 방식은 b-1개의 숫자로 c를 만들어 놓고 c와 마지막 숫자 d를 더하면 된다.
즉 마지막 숫자를 0 ~ a 중에서 하나로 잡고 b-1개의 숫자로 b-a를 만드는 방법들을 다 더해주면 된다.
전에 계산한 값들을 통해 다음 값을 계산할 수 있으므로 DP문제에 해당한다.
2. DP 배열 만들고 채우기
2차원 DP 배열을 만든다. 
int [][] arr = new int[num+1][target+1]; // DP 배열 arr[i][j] -> i를 개를 더해서 j를 만들기
나는 위와 같이 선언해주었다. i는 몇개를 더할지를 의미하고 j는 더해서 몇을 만들지를 의미한다.
배열을 만든 뒤 배열을 채워주어야한다.
2-1. 1개로 만드는 경우를 1로 초기화
몇을 만들든 1개로 만드는 경우는 자기 자신을 더하는 경우밖에 없으므로 1로 초기화한다.
//1개로 만드는 경우
for(int i=0 ;i<=target; i++){
    arr[1][i] = 1; //1으로 초기화
}
2-2. 전의 계산한 값을 이용하도록 코드 작성
설명보다는 아래 코드를 보는 것이 도움이 될 것이다.
i는 몇개를 더할지를 의미하고 j는 무엇을 만들지를 의미한다. k는 마지막 수를 의미한다.
따라서 i는 1개부터 더할 수 있으므로 1부터 시작해서 주어진 최대 개수까지 반복하고, j는 0부터 target까지 만드는 경우를 모두 계산하기 위해 0부터 target까지 반복했다.
k는 마지막 수이므로 0부터 최대 현재 더할 수 있는 최대값인 j까지의 값을 가질 수 있으므로 0부터 j까지 반복했다.
// DP 적용
        for(int i=1; i<=num; i++){ // i개를 더해서
            for(int j=0; j<=target; j++){ // j를 만듦
                // arr[i][j] = arr[i-1]들 다 더하기
                for(int k = 0; k<=j; k++){
                    arr[i][j] = (arr[i][j] +  arr[i-1][j-k]) % 1_000_000_000;
                }
            }
        }
3. 답 출력하기
이제 DP 배열이 완성되었으므로 우리가 구하려는 값인 arr[num][target]을 출력해주면 된다. 이는 num개를 더해 target을 만드는 방법의 개수이다.

정답 코드
import java.io.*;
import java.util.StringTokenizer;

public class p2225 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw  = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st= new StringTokenizer(br.readLine());
        int target = Integer.parseInt(st.nextToken()); // 만들 수
        int num = Integer.parseInt(st.nextToken()); // 더할 개수
        int [][] arr = new int[num+1][target+1]; // DP 배열 arr[i][j] -> i를 개를 더해서 j를 만들기

        //1개로 만드는 경우
        for(int i=0 ;i<=target; i++){
            arr[1][i] = 1; //1으로 초기화
        }

        // DP 적용
        for(int i=1; i<=num; i++){ // i개를 더해서
            for(int j=0; j<=target; j++){ // j를 만듦
                // arr[i][j] = arr[i-1]들 다 더하기
                for(int k = 0; k<=j; k++){
                    arr[i][j] = (arr[i][j] +  arr[i-1][j-k]) % 1_000_000_000;
                }
            }
        }

        bw.write(arr[num][target]+"");
        bw.flush();
        bw.close();
    }
}




백준 1213번 팰린드롬 만들기
Sat, 10 Aug 2024 06:01:59 GMT
문제
백준 1213번 팰린드롬 만들기 링크



풀이 방법
백준을 풀다보면 팰린드롬 문제를 많이 만난다. 팰린드롬이란 뒤집어도 같은 문자열을 말한다. 따라서 홀수개인 알파벳이 0개이거나 1개만 있어야한다. 이것만 알고 있다면 이번 문제는 어렵지 않아 쉽게 풀 수 있다.
전반적인 흐름은 입력받은 알파벳들을 출현 횟수 / 2 만큼 A부터 더하고 Z까지 완료하면 만든 문자열을 뒤집어서 변수에 저장한 뒤
홀수인 알파벳이 1개이면 현재 문자열 + 홀수인 알파벳 + 뒤집은 문자열을 출력하고
홀수인 알파벳이 없으면 현재 문자열 + 뒤집은 문자열을 출력한다.
1. 알파벳을 배열로 입력 받기
대문자 알파벳만 주어지는데 대문자 A는 아스키코드로 65이고 Z는 90 이다. 따라서 26개짜리 int 배열을 선언하고 각 인덱스를 A부터 Z라고 생각하고 각 값은 해당 알파벳의 출현 숫자로 생각하면 된다. 

따라서 배열을 입력 받을 때 문자열의 각 요소를 char로 바꾼 뒤 65를 뺀 인덱스 값을 +1 하도록 했다.




2. 출현 횟수가 홀수인 알파벳의 개수 세기 및 홀수일 경우 해당 알파벳 기록해두기
홀수인 알파벳은 1개까지는 허용된다. 따라서 홀수인 알파벳이 생겼을 경우 기록해두고 int 변수를 잡아서 홀수인 알파벳의 개수를 세야한다. 만약 홀수인 알파벳이 1개를 초과하면 I'm Sorry Hansoo를 출력하고 종료한다.
홀수인 알파벳이 1개만 있다면 두가지 경우로 나뉜다.
1. 해당 알파벳의 출현 횟수가 1인 경우
만약 출현횟수가 1인 경우 해당 알파벳이 어떤 알파벳인지 변수에 저장만 해둔다.
2. 해당 알파벳의 출현 횟수가 1을 초과하는 홀수일 경우
만약 출현횟수가 3 이상인 홀수라면 1개를 빼고는 현재 만들고 있는 문자열에 더해주어야한다. 예를 들어 5번 출현했으면 1개를 뺸 4개에서 2를 나는 2개를 더해주어야한다. 4개를 안더하고 2개만 더하는 이유는 어차피 뒤집은 문자열을 나중에 더할 것이기 때문에 지금 더한 횟수 * 2만큼 최종 문자열에 출현하기 때문이다.




3. 출현 횟수가 짝수인 알파벳의 경우 출현횟수 / 2 만큼 더하기
출현 횟수가 짝수이면 출현횟수 / 2 만큼 현재 만들고 있는 문자열에 더해주면 된다.




4. Z까지 완료한 뒤 현재 만든 문자열을 뒤집어서 변수에 저장해두기
A ~ Z까지 완료한 뒤 팰린드롬을 만들기 위해 현재까지 만든 문자열을 뒤집고 변수에 저장해두어야한다. 나중에 더해주어야하기 때문이다.




5. 출현 횟수가 홀수인 알파벳이 있으면 현재 문자열에 더해주기
만약 출현 횟수가 홀수인 알파벳이 있으면 2번에서 1개를 빼고는 더해주었으므로 홀수인 알파벳 1개를 현재 문자열에 더해준다.




6. 현재까지 만든 문자열에 아까 저장한 뒤집은 문자열을 더한 뒤 출력하기
현재까지 만든 문자열에 아까 저장한 뒤집은 문자열을 더한 뒤 출력하면 정답이 나온다.

정답 코드
import java.io.*;

public class p1213 {
    public static void main(String[] args) throws IOException {
        int [] alphabets = new int[26]; // idx 0은 65인 A부터 시작
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        // 입력 받기
        String line = br.readLine();
        String[] inputs = line.split("");
        for (String s : inputs){
            char c = s.charAt(0);
            int idx = c-65;
            alphabets[idx] ++;
        }
        int noPair = 0; // 홀수인 것의 개수
        char noPairAlphabet = 0;
        for(int i=0; i<26; i++){
            int alphabetCnt = alphabets[i];
            char alpha = (char) (i+65);
            if(alphabetCnt % 2 != 0){
                if(alphabetCnt / 2 > 0){ //홀수이지만 1개는 아닌 경우
                    for(int j=0; j1){ // 홀수개인 알파벳이 1개를 초과하는 경우
                    bw.write("I'm Sorry Hansoo");
                    bw.flush();
                    bw.close();
                    return;
                }
            }else {
                // 짝수개인 경우
                for(int j=0; j




백준 21608 상어 초등학교
Thu, 08 Aug 2024 11:34:21 GMT
문제
백준 21608번 상어 초등학교 링크

오늘은 문제가 길어서 입출력만 올렸다.

풀이 방법
문제를 보면 입력값의 범위가 최대 20이므로 굉장히 작은 것을 알 수 있다. 따라서 매번 완전탐색을 해도 제한시간을 넘지 않는다는 것을 생각했다.
1. 좋아하는 사람들을 리스트 배열로 저장
먼저 문제를 보자마자 든 생각은 방향이 있는 그래프라고 생각했다. 따라서 인접리스트 배열처럼 각 사람의 인덱스에 있는 리스트에 그 사람이 좋아하는 사람들을 추가하였다.
2. 자리를 바꿀 순서의 사람마다 교실을 한칸식 검사 후 우선순위 큐에 사용하기
자리를 순서의 사람마다 2차원 배열 교실을 검사한다. 1칸씩 잡고, 그 자리가 비어있으면 그 자리로부터 4방향 탐색을 통해 인접한 사람의 개수와 인접한 비어있는 자리의 개수를 구한다. 이후 이 값들을 클래스로 만들어 우선순위 큐에 저장한다.
3. 우선순위 큐에서 우선순위 적용 후 우선순위 큐 비우기
각 사람마다 자리를 정해주기 위해서 우선순위 큐에서 우선순위가 가장 높은 자리를 하나 뽑는다. 이때 문제에서 제시한 우선순위가 적용되도록 우선순위큐를 좋아하는 인접 개수 > 비어있는 인접 개수 > 행 > 열 우선순위로 비교하도록 한다.
또한 한 사람은 한자리밖에 못앉으므로 자리를 뽑고난 뒤 큐를 초기화한다(비운다).
4. 자리배치가 끝난 후 점수 다시 계산하기
자리배치가 끝난 뒤 2차원 배열인 교실을 돌면서 4방향 탐색을 통해 점수를 계산한다. 

자리배치 시에 계산한 인접점수를 사용하면 되지 않겠냐고 생각할 수 있지만 내가 좋아하는 사람이 나보다 자리 정하는 순서가 낮으면서 나의 자리와 인접하게 앉을 수 있으므로 점수는 바뀔 수 있다. 
*따라서 자리배치 후 다시 점수를 계산해주어야한다. *


정답 코드
import java.io.*;
import java.util.*;

public class p21608 {
    static int total;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        total = Integer.parseInt(st.nextToken()); // 가로 및 세로 줄
        int totalPerson = total * total; //전체 학생 수
        List [] likes = new List[totalPerson+1]; // 좋아하는 학생 인접 리스트
        int [] seq = new int[totalPerson]; // 자리 지정 순서 배열
        int [][] classroom = new int[total][total]; // 교실 현재 자리 2차원 배열
        int result = 0; // 정답

        int [] dx = {-1, 0, 0, 1};
        int [] dy = {-0, -1, 1, 0};
        // A형 PQ  우선순위: adj > vacant > row > col
        PriorityQueue pq = new PriorityQueue<>((o1, o2) -> {
            if(o1.adjNum != o2.adjNum) return o2.adjNum - o1.adjNum;
            if(o1.vacantNum != o2.vacantNum) return o2.vacantNum - o1.vacantNum;
            if(o1.row != o2.row) return o2.row - o1.row;
            return o2.col - o1.col;
        });

        // 좋아하는 학생 인접 리스트 초기화
        for(int i=0; i<=totalPerson; i++){
            likes[i] = new ArrayList<>();
        }
        // 좋아하는 학생 인접 리스트 입력 받기
        for(int t = 0; t likeFour = likes[p];
                    int vac = 0; // 비어있는 인접한 개수
                    int adj = 0; // 좋아하는 인접한 개수
                    for(int k=0; k<4; k++){
                        int newX = j+dx[k];
                        int newY = i+dy[k];
                        if(check(newX, newY)){ //범위 안에 있으면
                            if(classroom[newY][newX] == 0) vac++; // 비어있으면
                            else if(likeFour.contains(classroom[newY][newX])) adj++; //좋아하는 인접한 사람이면
                        }
                    }
                    // 4방 탐색후 PQ에 넣기
                    pq.add(new A(adj, vac, nowY, nowX));
                }
            }
            A poll = pq.poll(); //앉을 사람
            classroom[poll.row][poll.col] = p; //착석
            pq.clear();
        }

        //정답 구하기
        for(int i=0; i likeFour = likes[nowPerson];
                for(int k=0; k<4; k++){
                    int newX = j+dx[k];
                    int newY = i+dy[k];
                    if(check(newX, newY)){ //범위 안에 있으면
                        if(likeFour.contains(classroom[newY][newX])) cnt++; //좋아하는 인접한 사람이면
                    }
                }
            result += calResult(cnt);
            }
        }
        bw.write(result+"");
        bw.flush();
        bw.flush();
    }
    // 범위 내에 있는지 체크
    static boolean check(int x, int y){
        return x>=0 && x=0 && y




백준 3164번 패턴
Wed, 07 Aug 2024 08:54:40 GMT
문제
백준 3164번 패턴 문제 링크



풀이 방법
문제를 보고 바로 든 생각은 좌표 대신 사각형으로 생각해서 풀어야겠다는 것이었다. 실제로 회색 상자의 개수를 구하는 것이므로 그렇게 푸는게 편할 것 같기도 했고, 더 직관적일 것이라 생각했다.
1. 입력 받은 좌표들 변형(좌표가 아닌 사각형으로 생각하기 위해)
입력 받은 좌표들을 사각형 중 가장 왼쪽 아래에 포함된 크기 1짜리 사각형과 가장 오른쪽 위에 포함된 크기 1짜리 사각형의 인덱스로 바꾸어주었다. 인덱스로 생각하므로 첫번째 사각형은 0부터 시작한다고 생각하고 계산하였다.
2. 규칙 찾기
규칙을 보니 사각형으로 생각했을 때 (i,i) 사각형에서부터 사각형의 세로 최소 인덱스와 가로 최소 인덱스를 빼고 1을 더하면 된다는 생각을 했다. 따라서 가로와 세로를 따로 따로 구하도록 코드를 구현했다.

또한 중요한 것이 i와 세로(가로) 최대 인덱스 중 작은 것에서 빼야한다는 것이다. 만약 i가 세로 최대 인덱스보다 크다면 세로 최대인덱스 - 세로 최소 인덱스 +1을 해주어야한다는 말이다.

3. 중복된 개수 빼기
만약 (i,i)에서 개수를 구할 때 세로에서도 (i,i)를 포함하고 가로에서도 (i,i)를 포함하기 때문에 세로 개수 > 0 이고 가로 개수 > 0 이면 중복된 1개를 빼주어야한다.
사실 아이디어만 있다면 구현은 간단하므로 설명이 이해가 안된다면 어떤 식으로 푸는지 대략적으로 생각해보고 구현하면 된다.
4. long으로 변수 잡기(중요)

생각해보면 0 0 1,000,000 1,000,000 을 넣으면 int로 선언 시에 오버플로우가 발생한다. 따라서 result 변수는 long으로 선언해야한다. 


정답 코드
package Solution;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class p3164_1 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()); //한 줄 읽기

        int x1 = Integer.parseInt(st.nextToken()); // 주어지는 사각형을 이루는  사각형 중 제일 왼쪽 아래 1칸짜리 사각형의 x인덱스(0부터 시작)
        int y1 = Integer.parseInt(st.nextToken()); // 주어지는 사각형을 이루는  사각형 중 제일 왼쪽 아래 1칸짜리 사각형의 y인덱스(0부터 시작)
        int x2 = Integer.parseInt(st.nextToken()) -1; // 주어지는 사각형을 이루는  사각형 중 제일 오른쪽 위  1칸짜리 사각형의 x인덱스(0부터 시작)
        int y2 = Integer.parseInt(st.nextToken()) -1; // 주어지는 사각형을 이루는  사각형 중 제일 오른쪽 위  1칸짜리 사각형의 y인덱스(0부터 시작)

        int min = Math.min(x1, y1); //탐색을 위한 최소값
        int max = Math.max(x2, y2); // 탐색을 위한 최대값

        long result = 0; //최종 결과 long으로 해야함

        for(int i=min; i<=max; i++) { //최소부터 최대 까지 탐색
            if(i % 2 == 1) { // 인덱스가 홀수번째이면(홀수 번째이면 색칠됨)
                int column = 0; // 세로
                int row = 0; // 가로

                // 세로 계산
                if(i>= x1 && i<= x2 && i >= y1) { // 가로의 범위 안에 있고 세로의 최소범위보다 크면
                    int tmp = Math.min(i, y2);
                    if(tmp>0) column = tmp - y1 +1;    // 양수개인 경우만 더하기
                }

                // 가로 계산
                if(i>= y1 && i<= y2 && i >= x1) { // 세로의 범위 안에 있고 가로의 최소범위보다 크면
                    int tmp = Math.min(i, x2);
                    if(tmp>0) row = tmp - x1 +1; // 양수개인 경우만 더하기        
                }

                //중복 제거
                if(row >0 && column>0) result--; // 만약 가로에서도 계산하고 세로에서도 계산하면 두번 계산하므로 1개 빼주기
                // 결과 업데이트
                result = result + row + column;                            
            }
        }
        bw.write(result+"");
        bw.flush();
        bw.close();
    }

}




Arrays.toString(배열) VS 배열.toString()
Wed, 24 Jul 2024 05:14:03 GMT
[Movie.java]
public class Movie {
    private int id;
    private String title;
    private String director;
    private String genre;
    private int runningTime;

    public Movie() {
    }

    public Movie(int id, String title, String director, String genre, int runningTime) {
        super();
        this.id = id;
        this.title = title;
        this.director = director;
        this.genre = genre;
        this.runningTime = runningTime;
    }

    @Override
    public String toString() {
        return "Movie [id=" + id + ", title=" + title + ", director=" + director + ", genre=" + genre + ", runningTime="
                + runningTime + "]";
    }


}

[MovieTest.java]
public class MovieTest {
    public static void main(String[] args) {

        IMovieManager mg = MovieManagerImpl.getInstance();
        // 영화들 삽입
        mg.add(new Movie(1, "제목1", "감독1", "장르1", 100));
        mg.add(new Movie(2, "제목2", "감독2", "장르2", 200));
        mg.add(new Movie(3, "제목3", "감독3", "장르3", 300));
        mg.add(new SeriesMovie(4, "제목4", "감독4", "장르4", 400, 4, "ep4"));
        mg.add(new SeriesMovie(5, "제목5", "감독5", "장르5", 500, 5, "ep5"));



        // 리스트 가져오기
        Movie[] list = mg.getList();
        System.out.println("***********************getList()***********************");
        System.out.println(Arrays.toString(list));
        System.out.println(list.toString());
        System.out.println();

    }
}
위 코드를 작성하다가 궁금한 점이 생겼다. 코드를 보면 Movie에서 toString() 메서드를 override하고 있다. 

그렇다면 System.out.println(Arrays.toString(list)); 와 System.out.println(list.toString());의 출력값은 같을까?


그렇지 않음을 볼 수 있다. 윗줄의 출력이 System.out.println(Arrays.toString(list));의 결과이고, 아랫줄의 출력이 System.out.println(list.toString());의 결과이다.

둘다 toString()메서드를 호출했는데 왜 이런 차이점이 발생할까?


Arrays.toString(arr)
Arrays.toString(arr)는 java.util.Arrays 클래스에 정의된 정적 메서드이다. 이 메서드는 배열의 각 요소에 대해 toString() 메서드를 호출하고, 이를 문자열로 변환하여 반환한다. 즉, *배열의 모든 요소를 문자열로 변환하여 [element1, element2, ...] 형식의 문자열을 반환한다. *
또한 override를 하였을 경우 override된 메서드가 호출된다.
arr.toString()
arr.toString()은 배열 객체 자체의 toString() 메서드를 호출하는 것이다. 자바에서 배열의 기본 toString() 메서드는 배열의 요소를 문자열로 변환하지 않고, 단순히 배열의 타입과 해시 코드를 포함하는 문자열을 반환한다. 이는 Object 클래스에서 상속된 기본 toString() 메서드를 사용하기 때문이다. 
자바에서 배열 객체의 자체의 toString()은 override할 수 없다. 배열은 자바의 기본 데이터 타입으로, 배열 클래스(java.lang.Object를 상속받은 배열 클래스)는 내부적으로 JVM에 의해 관리되기 때문이다.
따라서 배열 객체 자체의 toString()을 출력하면 무조건 배열타입과 해시코드를 포함하는 문자열이 반환된다.
결론적으로 내가 어떤 클래스에 toString()을 오버라이드 했고, 해당 클래스 배열을 오버라이드 한 메서드를 통해 출력하고 싶다면 Arrays.toString()을 사용해야한다.
참고

https://www.geeksforgeeks.org/arrays-tostring-in-java-with-examples/
자바의 정석 3판(남궁 성,2016)




자바에서 래퍼클래스는 어떻게 저장될까
Tue, 23 Jul 2024 01:17:56 GMT
자바에서는 2가지 형태로 값을 저장한다.
기본 자료형

위 사진에서 볼 수 있는 10개의 기본 자료형은 값을 그대로 저장한다. 예를 들어 클래스 필드로 
int a = 20;
이라는 값을 갖는다고 생각해보자. 그럼 아래 그림처럼 힙 영역에 a를 저장하고, 20이라는 값 자체를 2진수로 바꾸어 저장한다.


참조 자료형
int a = 20;
A b = new A();
이번엔 위와 같은 코드가 작성되었다고 가정해보자. 아래에서 볼 수 있듯 new를 통해 인스턴스 A를 생성한 뒤 A의 주소값을 변수 b에 저장한다.

기본자료형이 아닌 참조 자료형은 이렇게 주소값이 저장됨을 알 수 있다.
그렇다면 래퍼클래스(Integer, Double, Byte, Character 등)는 어떻게 저장될까?

래퍼클래스도 참조 자료형이다.
결론부터 말하자면 참조자료형과 똑같이 저장된다. 기본 자료형 외에는 모두 참조 자료형이므로 위에서 본 참조자료형이 저장되는 방식으로 저장된다.
int a = 20; // 기본 자료형
Integer b = new Integer(20); // 래퍼클래스(참조자료형)


위에 그림에서 볼 수 있듯 int(기본 자료형)로 20을 선언하면 20에 해당하는 값을 a에 2진수로 저장한다.
반면 Integer(래퍼클래스)로 20을 선언하면 20에 해당하는 인스턴스를 생성한 뒤 그 인스턴스의 주소값을 b에 저장한다.

그럼 int c = (int)b;를 하면 어떻게 될까?


위 그림처럼 힙에 c가 생성되고 c의 값은 주소값이 아닌 b가 가리키는 인스턴스의 값을 읽어서 c에 값으로 저장한다.
참고

https://adjh54.tistory.com/119




백준 12904번 A와 B
Thu, 18 Jul 2024 00:57:50 GMT
문제
백준 12904번 A와 B 문제 링크


풀이 방법
되게 간단한 문제라서 이게 왜 골드5지? 싶었다. 그런데 함정이 있었다. 바로 시간복잡도다.
S -> T로 갈 때 두가지 경우가 있고 입력 조건에 따라서 S가 1이고 T가 1000일 경우 최대 2^1000의 시간복잡도를 가진다. 그래서 이렇게 풀면 당연히 틀린다.
그럼 어떻게 풀어야할까?
처음에는 S -> T로 가는 과정 중 중간 종료 조건을 생성해야겠다는 생각을 했다. 그런데 S -> T 과정에서 중간에 유망도를 판단하기는 어려웠다.
그래서 좀 더 고민하다가 결국 생각해냈다.

T -> S로 가는 역발상

T -> S로 가는 과정을 구현하면 된다. 얼핏보면 이것도 2^1000의 시간복잡도 아니야? 라고 할 수 있지만 T -> S로 간다고 생각하면 두가지 경우 중 하나의 경우만 일어난다.

T의 끝자리가 A인 경우 : T의 끝자리에서 A를 뺀다.

T의 끝자리가 B인 경우 : T의 끝자리에서 B를 뺀 후 문자열을 뒤집는다.


T의 끝자리는 A또는 B 이므로 최대 시간복잡도는 1000이다. 

정답 코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    //12904번
    public static void main(String[] args) throws Exception {
        // 입력받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        Stack stack = new Stack<>();
        String from = br.readLine();
        String to = br.readLine();
        int fromLength = from.length();
        int result = 0;

        stack.push(to);

        while(true) {
            String now = stack.pop();
            if(now.equals(from)) {
                result = 1;
                break;
            }
            else if(now.length()>fromLength) {
                if(now.charAt(now.length()-1) == 'A') {
                    stack.push(now.substring(0, now.length()-1));
                }
                //리버스
                else {
                    stack.push(reverse(now.substring(0, now.length()-1)));
                }
            }else if(stack.size() ==0) break;
        }
        bw.write(result+"\n");
        bw.flush();

    }
    static String reverse(String s) {
        String newS ="";
        for(int i=s.length()-1; i>=0; i--) {
            newS += s.charAt(i);
        }
        return newS;
    }

}




백준 11000번 강의실 배정
Wed, 17 Jul 2024 01:36:29 GMT
문제
백준 11000번 강의실 배정 문제 링크


풀이 방법
위 문제를 보고 크게 2가지를 떠올릴 수 있었다. 바로 정렬과 우선순위 큐이다.
1. 입력값들을 배열에 저장
먼저 입력값들을 배열에 저장해야한다. 
2. 배열을 정렬
이후 저장한 배열을 정렬해야한다. 그런데 여기서 중요한 점이 있다. 강의 시작 시각을 기준으로 정렬해야할지, 강의 종료 시각을 기준으로 정렬해야할지다. 사실 나는 직관적으로 강의 종료 시각을 기준으로 정렬해서 틀렸었다...
결론적으로 강의 시작 시각을 기준으로 정렬해야한다.

강의 시작 시각을 기준으로 정렬해야하는 이유
우리가 우선순위 큐를 어떻게 사용할지 매커니즘을 그림으로 그려보면 명확해진다.


<우선순위 큐를 사용하는 매커니즘>

1) 우선순위 큐에 정렬된 첫번째 수업을 삽입

2) 정렬된 두번째 수업의 시작시각과 우선순위 큐에서 가장 우선순위가 높은 수업의 종료시각을 비교

2-1) 종료시각 > 시작시각 -> 우선순위 큐에 해당 수업을 삽입

2-2) 종료시각 <= 시작시각 -> 우선순위 큐 요소를 뺀 뒤 해당 수업을 삽입

3) 2번 과정을 모든 요소에 대해 반복


결국 우리는 2-1에서 정렬된 배열의 시작시간을 우선순위 큐의 우선 요소와 비교한다. 따라서 우리는 강의 종료시각이 아닌 강의 시작시간으로 배열을 정렬해야하는 것이다.

따라서 배열을 강의 시작 시간을 기준으로 오름차순 정렬한다. 또한 만약 시작 시간이 같다면 종료시간으로 오름차순 정렬한다.
3. 우선순위 큐 사용
위의 예시에서 우선순위 큐를 어떻게 사용해야하는지는 보았다. 따라서 우리는 우선순위 큐의 우선순위는 종료시각임을 알 수 있다.
따라서 우선순위 큐를 생성한 뒤 우선순위를 정할 때 종료 시각이 작은 값이 우선순위를 갖게한다.
4. 우선순위 큐에 남은 요소 개수 출력
총 필요한 강의실의 개수는 우선순위 큐에 남은 요소 개수이다.
나는 처음에는 이게 이해가 안됐었다.

실행 중간에 100개의 수업이 동시에 있어서 우선순위 큐의 크기가 100까지 커졌다가 실행이 종료되기 전 수업들이 끝나서 마지막에 큐 크기가 5개면 답이 틀리지 않을까?

라는 의문이 있었기 때문이다.
하지만 이렇게 생각한다면 우리가 우선순위큐를 어떻게 사용할지 제대로 이해하지 못한 것이다. 우리는 우선순위 큐에서 요소를 뺄 때 종료 시각이 지났다고 무조건 빼는 것이 아니다. 종료 시각 이루에 시작하는 요소가 배열에 있을 때 우선순위 큐에서 요소를 뺀다. 
따라서 모든 수업이 종료될 때 큐에 남아있는 요소들의 개수가 정답이 된다.
만약 이 글을 읽고도 이해가 안된다면 실제 사례를 그림을 그려서 생각해보면 금방 이해할 수 있을 것이다.

정답 코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        PriorityQueue pq = new PriorityQueue<>(
                (o1, o2) -> {
                    // 시작시간 오름차순 정렬, 시작시간 같다면 종료시간 오름차순 정렬
                    if (o1.end == o2.end) {
                        return o1.start - o2.start;
                    } else {
                        return o1.end - o2.end;
                    }
                });
        int N = Integer.parseInt(st.nextToken());
        Class [] arr = new Class[N];
        // 입력 받기
        for(int i=0; i{
        int start, end;
        public Class(int start, int end) {
            this.start = start;
            this.end = end;
        }
        public int compareTo(Class c) {
            if(this.start == c.start) return this.end - c.end;
            return this.start - c.start;
        }
    }
}




[EC2] NAT 루핑(헤어핀) 오류
Sun, 14 Jul 2024 13:19:22 GMT
CI/CD를 구축하면서 계속 문제가 발생했다.

사...살려줘....

오류 상황
오류 내용

내 프로젝트는 간단하게 그리면 위 그림처럼 구성되어있다.
설명해보자면 하나의 EC2안에 MySQL 서버를 설치하여 3306포트로 구동 중이고, 도커 컨테이너 안에 스프링 서버가 있다. 
그런데 스프링 서버를 실행하면 아래와 같이 DB에 연결할 수 없다는 오류가 계속 발생했다.
Cannot invoke "org.hibernate.engine.jdbc.spi.SqlExceptionHelper.convert(java.sql.SQLException, String)" because the return value of "org.hibernate.resource.transaction.backend.jdbc.internal.JdbcIsolationDelegate.sqlExceptionHelper()" is null
*이상한 점은 로컬 PC에서 EC2의 MYSQL에 연결하여 스프링 부트를 돌리는 것은 잘 돌아간다는 것이다 😓
*
오류 코드
이 상황에서 스프링 서버에서 application.yml을 통해 MySQL과 연결을 할 때 public IP 주소를 입력했더니 계속 오류가 발생했다.
spring:
  datasource:
    url: jdbc:mysql://{public IP 주소}:3306/{DB 이름}
    username: {유저이름}
    password: {비밀번호}
    driver-class-name: com.mysql.cj.jdbc.Driver

예상 원인
인바운드 규칙 설정 및 방화벽 설정
그런데 저번 게시물에서 이미 인바운드 규칙과 방화벽 설정을 통해 MySQL Workbench로 서버에 접속하였다.
그래서 예상원인을 찾기 어려워서 하루동안 고민했다.

실제 해결 방법
public IP 주소가 아닌 private IP 주소를 사용하기

AWS 콘솔에 접속하여 사진의 주황색 부분에 있는 프라이빗 ip 주소를 application.yml에 적어주면 된다.
spring:
  datasource:
    url: jdbc:mysql://{priavte IP 주소}:3306/{DB 이름}
    username: {유저이름}
    password: {비밀번호}
    driver-class-name: com.mysql.cj.jdbc.Driver
의외로 간단한 해결방안이다.
그런데 왜 이렇게 해야할까? 왜 public IP 주소를 사용하면 안될까??

NAT 루핑(헤어핀) 문제
NAT란
NAT는 Network Address Translation의 약자로 내부 네트워크의 여러 장치가 하나의 공인 IP 주소를 공유하여 인터넷에 접속할 수 있도록 해주는 기술이다. 일반적으로 라우터에서 실행된다.
NAT 루핑(헤어핀) 문제란

NAT 루핑(헤어핀) 문제는 동일한 네트워크 내의 장치가 자신의 외부 IP 주소를 통해 통신하려고 할 때 발생하는 문제이다.
헤어핀 문제라고 불리는 이유는 네트워크 트래픽이 내부 네트워크를 떠나 외부로 나갔다가 다시 내부로 돌아오는 경로가 마치 머리핀(Hairpin)처럼 구부러져 있는 모양을 닮았기 때문이다.

나의 상황으로 예를 들어보자.
주어진 상황

하나의 EC2 인스턴스가 있고, 인스턴스에는 MySQL 서버가 설치되어 있으며 Docker 컨테이너 안에서 Spring Boot 애플리케이션이 실행되고 있다.
인스턴스의 프라이빗 IP 주소는 10.0.0.1이고, 퍼블릭 IP 주소는 203.0.113.1이다.

통신 시도 상황

Docker 컨테이너 안의 Spring Boot 애플리케이션이 MySQL 서버에 접속하려고 할 때, 퍼블릭 IP 주소 203.0.113.1을 사용하여 연결을 시도한다.

라우팅 과정

1. Spring Boot 애플리케이션에서 203.0.113.1로 패킷을 보낸다.
2. 이 패킷은 NAT 라우터를 통해 외부로 나가야 하지만, 결국에는 동일한 인스턴스 내로 다시 들어오게 된다.
3. NAT 라우터는 이 패킷을 처리하는 과정에서 루핑(Loopback)이 발생하고, 이를 처리할 수 없는 네트워크 설정에서 연결이 실패한다.

루핑(헤어핀) 문제의 원인
라우터의 제한
대부분의 NAT 라우터는 내부 네트워크의 트래픽을 외부로 내보내고 다시 내부로 받아들이는 헤어핀 트래픽을 처리하는 기능을 갖추고 있지 않다. 이는 보안 상의 이유이기도 하며, 일반적인 네트워크 사용 패턴에서는 필요 없는 기능이기 때문이다.
불필요한 트래픽 증가
동일한 네트워크 내의 통신이 외부 네트워크를 경유하게 되어 네트워크 성능이 저하될 수 있다.
복잡한 네트워크 설정
헤어핀 NAT 문제를 해결하기 위해 추가적인 네트워크 설정이 필요할 수 있다.
루칭(헤어핀) 문제의 해결방법
프라이빗 IP 사용
내부 네트워크 내에서 통신할 때는 프라이빗 IP 주소를 사용하여 직접 통신하면 된다.

간단하긴 한데 'Private IP와 Public IP가 뭐가 다르길래 이게 해결방안이지?' 싶을 수 있다.


프라이빗 IP를 사용하면 헤어핀 NAT 문제를 해결할 수 있는 이유는 내부 네트워크 내에서 직접 통신할 수 있기 때문이다. 프라이빗 IP를 사용하는 방식은 NAT 라우터를 통하지 않으므로, 트래픽이 외부 네트워크로 나갔다가 다시 내부 네트워크로 돌아올 필요가 없다. 따라서 루핑 문제가 발생하지 않는 것이다.

하루동안 삽질했지만, 그래도 생각지도 못한 문제를 해결했고, 네트워크개론에서 배웠던 NAT도 오랜만에 다시 공부할 수 있어서 좋았다.
참고

Wikipedia: Network Address Translation

쉽게 이해하는 NAT (공유기) 원리로 NAT 루프백(헤어핀 NAT)을 알아보기





LOTTO-PILOT 프로젝트 1일차
Sun, 14 Jul 2024 11:43:53 GMT
오늘은 개발 환경 설정과 요구사항 명세서 작성이 주된 목표이다.
개발 환경 설정
Spring Boot

사진처럼 필요한 의존성을 넣어주었다.
GitHub
1. 깃허브 레포 생성 및 연동
깃허브 레포 주소와 로컬 개발 폴더를 연동 시켜두었다.
2. 자동 CI / CD 구축
GitHub Actions를 이용하여 구축하였다.

CI.yml
name: CI

on:
  push:
    branches: [ "main" ]
  pull_request:
    branches: [ "main" ]

jobs:
  build:
    runs-on: ubuntu-22.04
    env:
      working-directory: lotto-pilot

    steps:
      - name: 체크아웃
        uses: actions/checkout@v3

      - name: Set up JDK 21
        uses: actions/setup-java@v3
        with:
          distribution: 'temurin'
          java-version: '21'

      - name: application.yml 생성
        run: |
          mkdir ./src/main/resources # resources 폴더 생성
          cd src/main/resources 
          echo "${{ secrets.APPLICATION }}" > ./application.yml

      - name: 빌드
        run: |
          chmod +x gradlew
          ./gradlew build -x test
        shell: bash
CD.yml
name: CD

on:
  push:
    branches: [ "main" ]

jobs:
  deploy-ci:
    runs-on: ubuntu-22.04
    env:
      working-directory: lotto-pilot

    steps: 
    - uses: actions/checkout@v3

    - name: Set up JDK 21
      uses: actions/setup-java@v3
      with:
        distribution: 'temurin'
        java-version: '21'

    - name: application.yaml 생성
      run: | 
          mkdir ./src/main/resources # resources 폴더 생성
          cd src/main/resources
          echo "${{ secrets.APPLICATION }}" > ./application.yml

    - name: 빌드
      run: |
          chmod +x gradlew
          ./gradlew build -x test
      shell: bash

######## 여기까지는 CI.yaml와 동일 #########

    - name: docker build 가능하도록 환경 설정
      uses: docker/setup-buildx-action@v2.9.1

    - name: docker hub에로그인
      uses: docker/login-action@v2.2.0
      with:
        username: ${{ secrets.DOCKERHUB_LOGIN_USERNAME }}
        password: ${{ secrets.DOCKERHUB_LOGIN_ACCESSTOKEN }}

    - name: docker image 빌드 및 푸시
      run: |
        docker build --platform linux/amd64 -t alenjb/lotto-pilot .
        docker push alenjb/lotto-pilot

  deploy-cd:
    needs: deploy-ci
    runs-on: ubuntu-22.04
    steps:
    - name: 도커 컨테이너 제거
      uses: appleboy/ssh-action@master
      with:
        host: ${{ secrets.RELEASE_HOST }}
        username: ${{ secrets.RELEASE_USERNAME }}
        key: ${{ secrets.RELEASE_KEY }}
        script: |
            docker rm -f lotto-pilot-8080 || true

    - name: 도커 컨테이너 실행
      uses: appleboy/ssh-action@master
      with:
        host: ${{ secrets.RELEASE_HOST }}
        username: ${{ secrets.RELEASE_USERNAME }}
        key: ${{ secrets.RELEASE_KEY }}
        script: |
            cd ~
            ./deploy.sh
deploy.sh
#!/bin/bash

nginx_config_path="/etc/nginx"
all_port=("8080" "8081")
available_port=()
server_name=lotto-pilot

docker_ps_output=$(docker ps | grep $server_name)
running_container_name=$(echo "$docker_ps_output" | awk '{print $NF}')
blue_port=$(echo "$running_container_name" | awk -F'-' '{print $NF}')
web_health_check_url=/actuator/health

if [ -z "$blue_port" ]; then
    echo "> 실행 중인 서버의 포트: 없음"
else
    echo "> 실행 중인 서버의 포트: $blue_port"
fi

# 실행 가능한 포트 확인 ( all_port 중 blue_port를 제외한 port )
for item in "${all_port[@]}"; do
    if [ "$item" != "$blue_port" ]; then
        available_port+=("$item")
    fi
done

# 실행 가능한 포트 없으면 끝내기
if [ ${#available_port[@]} -eq 0 ]; then
    echo "> 실행 가능한 포트가 없습니다."
    exit 1
fi

green_port=${available_port[0]}

echo "----------------------------------------------------------------------"
# docker image pull
echo "> 도커 이미지 pull 받기"
docker pull alenjb/${server_name}

# green_port로 서버 실행
echo "> ${green_port} 포트로 서버 실행"
echo "> docker run -d --name ${server_name}-${green_port} -p ${green_port}:8080 -e TZ=Asia/Seoul alenjb/${server_name}"
docker run -d --name ${server_name}-${green_port} -p ${green_port}:8080 -e TZ=Asia/Seoul alenjb/${server_name}
echo "----------------------------------------------------------------------"

# green_port 서버 제대로 실행 중인지 확인
sleep 10
for retry_count in {1..10}
do
    echo "> 서버 상태 체크"
    echo "> curl -s http://localhost:${green_port}${web_health_check_url}"
        # http://localhost:{그린포트}{health check 주소} -> nginx
    response=$(curl -s http://localhost:${green_port}${web_health_check_url})
    up_count=$(echo $response | grep 'UP' | wc -l)

    if [ $up_count -ge 1 ]
    then
        echo "> 서버 실행 성공"
        break
    else
        echo "> 아직 서버 실행 안됨"
        echo "> 응답 결과: ${response}"
    fi
    if [ $retry_count -eq 10 ]
        then
        echo "> 서버 실행 실패"
        docker rm -f ${server_name}-${green_port}

        exit 1
    fi
    sleep 2
done
echo "----------------------------------------------------------------------"

# nginx switching
echo "> nginx 포트 스위칭"
echo "set \$service_url http://127.0.0.1:${green_port};" | sudo tee ${nginx_config_path}/conf.d/service-url.inc
sudo nginx -s reload

sleep 1

echo "----------------------------------------------------------------------"
# nginx를 통해서 서버 접근 가능한지 확인
response=$(curl -s http://localhost${web_health_check_url})
up_count=$(echo $response | grep 'UP' | wc -l)
if [ $up_count -ge 1 ]
then
    echo "> 서버 변경 성공"
else
    echo "> 서버 변경 실패"
    echo "> 서버 응답 결과: ${response}"
    exit 1
fi

# blue_port 서버 있다면 중단
if [ -n "$blue_port" ]; then
    echo "> 기존 ${blue_port}포트 서버 중단"
    echo "> docker rm -f ${server_name}-${blue_port}"
    sudo docker rm -f ${server_name}-${blue_port}
fi

요구사항 명세서
이 프로그램의 핵심 기능은 크게 4가지다.

1. 정해진 알고리즘에 따라 로또 번호 추출


2. 추출된 번호를 통해 자동 로또 구매


3. 로또 번호 당첨 내역 조회


4. 동행복권 잔액 부족 여부 알림

따라서 이러한 기능들을 제공하기 위해 아래와 같이 요구사항 명세서를 정의하였다.