GOSE_KOSE

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 마이크로 서비스 패턴 5장 - 비즈니스 로직 설계 정리를 작성하고자 합니다.

해당 챕터는 애그리거트라는 개념으로 비즈니스 로직을 설계하는 과정을 설명하고 있습니다.

JPA 등을 활용한 객체지향적인 개발은 MSA에서 복잡성을 야기할 수 있기에,

애그리거트를 활용한 도메인 이벤트 발행을 통해 느슨한 결합을 유지하며 비즈니스 로직을 처리할 수 있습니다.

예제는 제가 작성한 예제로 책의 내용과 다를 수 있습니다!

1. 애그리거트란?

애그리거트

- 애그리거트는 연관된 객체들의 집합을 의미하며, 해당 집합의 데이터 무결성을 일관성 경계 내에서 보장하기 위한 설계 패턴입니다.

- 주문 애그리거트는 주문, 주문 항목 등으로 구성될 수 있습니다.

애그리거트 루트

- 애그리거트의 집합 중에서 외부와의 통신을 담당하는 주요 객체를 의미합니다.

- 애그리거트 루트는 애그리거트 내의 다른 객체들을 직접 참조할 수 있지만, 애그리거트 밖에서는 애그리거트 루트만을 참조해야 합니다.

- 주문이 주문 애그리거트의 루트라면, 외부에서 주문 항목을 직접 참조하는 것은 허용되지 않습니다 (캡슐화)

애그리거트는 연관된 객체를 일관성 있는 경계 내에서 보장하도록 설계합니다.

즉, 경계가 분명하여 연관성이 적은 객체는 느슨하게 유지한다는 의미입니다.

애그리거트를 유지하려면 적용해야 하는 규칙이 있습니다.

2. 애그리거트 규칙

1) 애그리거트 루트만 참조하라.

- 외부 클래스는 반드시 애그리거트의 루트 엔티티만 참조할 수 있도록 제한해야 합니다.

- 가령 어떤 서비스가 리포지토리를 통해 DB에서 애그리거트를 로드하고 애그리거트의 루트 래퍼런스를 얻고자 하면,

애그리거트 루트에 있는 메서드를 호출하여 애그리거트를 업데이트해야 합니다.

애그리거트를 수정해야 할 때, 애그리거트 루트를 통해 수정해야 객체의 캡슐화를 지킬 수 있습니다.

PaymentInfo는 Order의 애그리거트에 속하는 객체입니다.

PaymentInfo를 임의로 수정한다면, 이를 참조하는 객체들의 불변성이 깨져 데이터의 정합성이 맞지 않을 수 있습니다.

따라서, Order의 내부 함수를 통해 Order의 객체 값을 변경하는 방법을 채택할 수 있습니다.

2) 애그리거트 각 참조는 반드시 기본키를 사용하라.

- 애그리거트는 객체 래퍼런스 대신 신원으로 서로를 참조해야 합니다.

Restaurant는 order 자체의 객체 레퍼런스 참조가 아닌, orderId라는 식별자를 통해 간접 참조 하고 있습니다. 

이렇게 식별자를 통한 참조는 느슨한 결합을 유지할 수 있습니다.

그 이유는 다음과 같습니다.

MSA는 각 서비스에 특화적인 데이터베이스 테이블을 가지고 있습니다.

만약 레스토랑 서비스와 주문 서비스가 분리되어 있다면, 레스토랑 서비스는 주문에 대한 테이블은 따로 가지고 있지 않을 수 있습니다.

따라서, 객체 자체의 참조를 설정하게 된다면 복잡성이 커질 수 있습니다. 

위 코드처럼 해당 도메인의 엔티티는 orderId를 참조가 아닌 객체 식별자로 가짐으로써,

Lazy 조인 혹은 fetch 조인 등 다른 객체의 참조에 의존하지 않고 필요한 객체만 DB로부터 가져올 수 있습니다.

만약 객체의 식별자가 아닌 객체 자체의 참조를 사용한다면,

외부 서비스로부터 order를 가져와야 하는 경우, order에 대한 정보를 가져온 후 이를 객체화하는 작업이 수행되어야 할 것입니다.

3) 하나의 트랜잭션으로 하나의 애그리거트를 생성/수정하라

주문이라는 트랜잭션을 처리하면, 각 마이크로서비스별로 로컬 트랜잭션을 적용합니다.

이에 따라, 계속 요청을 수행하거나 요청을 중단하고 보상 트랜잭션을 처리하는 과정이 수행될 수 있습니다.

애그리거트를 이용한다면 이러한 사가패턴의 라이프사이클에 맞춰서 트랜잭션을 처리할 수 있습니다.

서비스 A는 애그리거트 X를 로컬 트랜잭션 1에서 처리하고, 이벤트를 발행합니다.

서비스 B는 서비스 A의 이벤트를 수신하고 애그리거트 Y를 로컬 트랜잭션 2에서 처리하고 이벤트를 발행합니다.

이러한 방식으로 사가패턴을 적용하여 하나의 트랜잭션에서 하나의 애그리거트를 처리할 수  있습니다.

3. 도메인 이벤트 발행

DDD 맥락에서 도메인 이벤트는 애그리거트에 발생한 사건입니다.

Order가 애그리거트라면 주문 생성, 주문 취소, 주문 배달 등 상태가 바뀌는 이벤트가 발생합니다.

애그리거트의 상태가 전이될 때마다 이에 관련된 컨슈머를 위해 적절한 이벤트를 발행합니다.

이벤트는 발행의 이벤트를 표현하는 id, type, 그리고 발행에 필요한 객체 등을 추가로 넣을 수 있습니다.

이벤트 강화

주문 결제 생성 이벤트를 수신할 때, 결제 내역이 필요할 수 있습니다.

이벤트에 결제 내역이 존재하지 않는다면, 주문 서비스 혹은 결제 서비스로 결제 내역에 대한 요청을 다시 수행해야 합니다.

이러한 문제를 방지하고자, 이벤트 발생 시에 수신자에게 필요한 정보를 제공하는 것이 이벤트 강화 방식입니다.

앞 서 구현한 OrderPaymentCreationPublishEvent는 필요한 결제 내역등을 이벤트로 제공하고 있습니다.

컨슈머는 이벤트 메시지 형태로 이벤트를 수신하고 필요한 이벤트를 T 타입으로 정의한 message로부터 얻을 수 있습니다.

이처럼 이벤트 강화 방식에 제네릭을 활용한다면 확장성이 높아지고, 이벤트를 발행한 서비스를 다시 쿼리 해서 데이터를 가져올 필요가 없으므로 이벤트 컨슈머가 간단해질 수 있습니다.

4. 도메인 이벤트 생성 및 발행

도메인 이벤트를 이용한 통신은 비동기 메세징 형태를 취하지만,

비즈니스 로직이 도메인 이벤트를 메시지 브로커에 발행하려면 먼저 도메인 이벤트를 생성해야 합니다.

도메인 이벤트 생성

도메인 이벤트는 애그리거트가 발행합니다. 애그리거트가 도메인 이벤트를 발행함으로써, 애그리거트의 경계를 명확하게 하고, 하나의 애그리거트 (예시로 주문)의 책임을 명확하게 분리할 수 있습니다. 이 도메인을 활용하는 application 계층이나 api 계층은 이를 호출하는 방법으로 의존관계 주입을 받을 수 있습니다.

도메인의 유즈케이스에 속하는 애그리거트는 createOrder()로 주문을 생성하고,

createOrderUserPublishEvent()라는 함수를 호출하여 orderUserEvent를 생성합니다.

이어서, orderUserPublishEventHander를 호출하여 이벤트를 처리하는 process 함수를 호출합니다.

이 함수는 실제 이벤트를 발행하는 역할을 수행합니다.

5. 도메인 이벤트 소비

도메인 이벤트는 메시지로 바뀌어 아파치 카프카 같은 메세지 브로커에 발행됩니다.

카프카 컨슈머는 메세지로 바뀐 이벤트를 수신하고, 이를 디스패처로 넘깁니다.

디스패처는 이벤트의 타입을 메시지의 메타데이터를 통해 식별하여 적절하게 캐스팅한 후

필요한 이벤트 핸들러로 위임할 수 있습니다.

현재 저는 이벤트 강화 방식을 적용하였기 때문에 캐스팅하는 과정에서 어떠한 클래스로 캐스팅이 필요한지 메타데이터를

JSON으로 직렬화하는 과정에 추가하였습니다.

이를 통해 카프카 컨슈머는 @Payload에 있는 message를 수신할 때 적절한 타입으로 캐스팅할 수 있었습니다.

6. 정리하며!

애그리거트는 도메인 모델을 모듈화 하고, 서비스 간 객체 참조 가능성을 배제하며,

전체 ACID 트랜잭션을 서비스 내부에 국한시키므로 유용하게 사용할 수 있습니다.

실제 사가패턴을 적용하는 코드를 작성했을 때, 이러한 애그리거트 패턴이 익숙하지 않았습니다.

어느 단계까지 해당 서비스의 애그리거트로 정의할 것인지, 한 번의 이벤트에 어떠한 정보까지 제공해주어야 하는지 등

많은 고민을 하며 코드를 작성했습니다.

해당 개념을 읽고 나서 다시 코드를 보니,

그 당시에 고민했었던 내용이 애그리거트의 경계와 이벤트 강화 방식이었음을 알게 되었습니다.!

다음 챕터는 이벤트 소싱을 적용하는 챕터입니다!

다음 장도 너무 기대됩니다~!

읽어주셔서 감사합니다!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 문자열 문제 - 디지털시계 코틀린 풀이를 진행하고자 합니다.

문제 출처: https://www.acmicpc.net/problem/1942

1. 풀이 소스

import java.io.*

const val LAST_TIME_SECONDS_OF_DAY: Int = 3600 * 23 + 59 * 60 + 59
const val START_TIME_SECONDS_OF_DAY: Int = 0

fun main() = BufferedReader(InputStreamReader(System.`in`)).use {

    val sb = StringBuilder()
    repeat(3) {
        val (startTimeSeconds, endTimeSeconds) = readlnOrNull()!!.split(" ").map { it.toTimeSeconds() }

        val result = when {
            startTimeSeconds <= endTimeSeconds -> calculateMultipleOfThreeBetween(startTimeSeconds, endTimeSeconds)
            else -> calculateMultipleOfThreeBetween(startTimeSeconds, LAST_TIME_SECONDS_OF_DAY) +
                    calculateMultipleOfThreeBetween(START_TIME_SECONDS_OF_DAY, endTimeSeconds)
        }

        sb.append(result).append("\n")
    }

    println(sb)
}

private fun calculateMultipleOfThreeBetween(startTimeSeconds: Int, endTimeSeconds: Int): Int {
    var targetTimeSeconds = startTimeSeconds
    var result = 0

    while (targetTimeSeconds <= endTimeSeconds) {

        val longOfTime = targetTimeSeconds.transformTimeToLiteralNumber()
        if (longOfTime % 3 == 0) {
            result++
        }

        if (targetTimeSeconds == LAST_TIME_SECONDS_OF_DAY) {
            break
        }

        targetTimeSeconds++
    }

    return result
}

fun Int.transformTimeToLiteralNumber(): Int {
    val hours = this / 3600
    val minutes = (this % 3600) / 60
    val seconds = this % 60
    return hours * 10000 + minutes * 100 + seconds
}

fun String.toTimeSeconds(): Int {
    val (hours, minutes, seconds) = this.split(":").map { it.toInt() }
    return hours * 3600 + minutes * 60 + seconds
}

2. 풀이 중점사항

- 시작 시간과 종료 시간의 대수 비교

시작 시간이 종료 시간보다 클 경우 (ex: 23:59:59, 00:00:01) 시작 시간 ~ 23:59:59, 00:00:00 ~ 종료 시간 으로 구획을 나눠서 진행해야합니다.

만약, 시작 시간보다 종료 시간이 클 경우는 시작 시간 <= 종료 시간이 될 때 까지 순회하면 됩니다.

val result = when {
    startTimeSeconds <= endTimeSeconds -> calculateMultipleOfThreeBetween(startTimeSeconds, endTimeSeconds)
    else -> calculateMultipleOfThreeBetween(startTimeSeconds, LAST_TIME_SECONDS_OF_DAY) +
            calculateMultipleOfThreeBetween(START_TIME_SECONDS_OF_DAY, endTimeSeconds)
}

-시작 시간과 종료 시간 사이의 범위구하기

시작 시간과 종료 시간은 초(단위)로 바꿔서 구할 수 있습니다. 

예를 들어 00:00:00 ~ 00:01:03이 있다면 이를 초(단위)로 표현하면 0 ~ 63이 됩니다.

fun String.toTimeSeconds(): Int {
    val (hours, minutes, seconds) = this.split(":").map { it.toInt() }
    return hours * 3600 + minutes * 60 + seconds
}

0 ~ 63까지 순회하되, 순회한 숫자를 시간 문자 그대로의 숫자로 바꿔주어야 합니다.

0 -> 00:00:00 -> 0

63 -> 00:01:03 -> 103

이를 위해 시간, 분, 초로 바꾼 후 각 단위에 맞게 10의 제곱승을 곱해줄 수 있습니다.

fun Int.transformTimeToLiteralNumber(): Int {
    val hours = this / 3600
    val minutes = (this % 3600) / 60
    val seconds = this % 60
    return hours * 10000 + minutes * 100 + seconds
}

이렇게 구한 문자 그대로의 시간을 표현하는 정수를 3의 배수인지 파악하고 결과를 리턴하면 결과를 얻을 수 있습니다!

private fun calculateMultipleOfThreeBetween(startTimeSeconds: Int, endTimeSeconds: Int): Int {
    var targetTimeSeconds = startTimeSeconds
    var result = 0

    while (targetTimeSeconds <= endTimeSeconds) {

        val longOfTime = targetTimeSeconds.transformTimeToLiteralNumber()
        if (longOfTime % 3 == 0) {
            result++
        }

        if (targetTimeSeconds == LAST_TIME_SECONDS_OF_DAY) {
            break
        }

        targetTimeSeconds++
    }

    return result
}

이상으로 백준 디지털시계 문제 풀이를 마치도록 하겠습니다. 감사합니다!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 문자열 문제 - 경고 풀이를 진행하도록 하겠습니다.

문제 출처: https://www.acmicpc.net/problem/3029

1. 풀이 소스

import java.io.*

fun main() = BufferedReader(InputStreamReader(System.`in`)).use {

    val startTime = readlnOrNull()?.timeToSeconds() ?: throw IllegalArgumentException()
    val endTime = readlnOrNull()?.timeToSeconds() ?: throw IllegalArgumentException()

    val result = when {
        endTime - startTime <= 0 -> (endTime + 24 * 3600 - startTime).toTimeString()
        else -> (endTime - startTime).toTimeString()
    }

    println(result)
}


fun String.timeToSeconds(): Int {
    val (hour, minute, seconds) = this.split(":").map { it.toInt() }
    return hour * 3600 + minute * 60 + seconds
}

fun Int.toTimeString(): String {
    val hours = this / 3600
    val minutes = (this % 3600) / 60
    val seconds = this % 60

    return String.format("%02d:%02d:%02d", hours, minutes, seconds)
}

2. 풀이 과정

- 확장 함수 사용

코틀린 확장함수를 사용하여 String, Int 등 기본 타입에 추가로 커스텀한 함수를 만들 수 있습니다.

timeToSeconds()라는 확장함수를 정의하여 시간, 분, 초를 초단위 정수로 변환하였습니다.

toTimeString()은 정수를 필요한 포맷인 00:00:00 형태로 바꿔주는 함수입니다.

만약 숫자를 그대로 출력하면 2자리가 아닌 한자리 숫자(ex 8)는 그대로 한자리가 됩니다.

String.format("%02d:%02d:%02d", hours, minutes, seconds)로 필요한 공백은 0으로 만들어서 리턴할 수 있습니다.

- when 사용

endTime - startTime이 0이하인 경우는 endTime에 24시간을 더 한 후 startTime에서 빼면 시간 차이를 구할 수 있습니다.

문제에서 최소 1초는 대기한다고 하였으므로 만약 startTime과 endTime이 시간이 같다면 endTime은 날짜가 하루 지난 것이라고 보아야 합니다.

이상으로 백준 경계 문제 풀이를 마치도록 하겠습니다.

감사합니다!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 이전 포스팅에서 작성한 리플리카 서버를 데이터베이스에 연동하는 과정을 정리하고자 합니다.

1. 스프링부트 의존성 주입과 application.yml 설정하기

해당 테스트는 스프링부트 3.1.0, Mysql 8.x로 구성되어 있습니다. 마스터 서버와 슬레이브 서버를 설정하는 과정은 하단 블로그 링크를 첨부하였습니다.

https://gose-kose.tistory.com/131

현재 설정된 Mysql은 local의 3307 포트에 연결된 order_master 서버와, 3308 포트에 연결된 order_slave 서버입니다.

build.gradle

implementation 'org.springframework.boot:spring-boot-starter-data-jpa'
implementation 'org.springframework.boot:spring-boot-starter-validation'
implementation 'org.springframework.boot:spring-boot-starter-web'

// mysql
runtimeOnly 'com.mysql:mysql-connector-j'
implementation 'mysql:mysql-connector-java:8.0.33'

compileOnly 'org.projectlombok:lombok'
developmentOnly 'org.springframework.boot:spring-boot-devtools'

annotationProcessor 'org.projectlombok:lombok'
testImplementation 'org.springframework.boot:spring-boot-starter-test'

jpa, mysql을 활용하기 위해 의존성 주입을 적용하였습니다.

application.yml

server:
  port: 8081

spring:
  datasource:
    source:
      driver-class-name: com.mysql.cj.jdbc.Driver
      jdbc-url: jdbc:mysql://localhost:3307/orders
      username: root
      password: 1234
    replica:
      driver-class-name: com.mysql.cj.jdbc.Driver
      jdbc-url: jdbc:mysql://localhost:3308/orders
      username: root
      password: 1234

  jpa:
    hibernate:
      ddl-auto: create
    properties:
      hibernate:
        format_sql: true
    show-sql: true

  main:
    allow-bean-definition-overriding: true

logging:
  level:
    org:
      hibernate:
        type: trace

스프링 부트는 source 서버와 replica 서버의 데이터베이스 커넥션을 각각 설정해야 하므로

driver-class-name, jdbc-url, username, password를 각각 설정하였습니다.

참고한 블로그에서 master - slave라는 표현은 윤리적인 문제로 최근에는 Source - Replica를 사용한다고 설명해 주셨습니다.

따라서 저도 master: source, slave: replica로 표현하였습니다.

2. Configuration 작성하기

전체 소스를 먼저 작성한 후, 하나씩 주요 메서드 및 기능을 정리하도록 하겠습니다.

@Slf4j
public class RoutingDataSource extends AbstractRoutingDataSource {

    @Nullable
    @Override
    protected Object determineCurrentLookupKey() {
        String lookupKey = TransactionSynchronizationManager.isCurrentTransactionReadOnly() ? "replica" : "source";
        log.info("Current DataSource is {}", lookupKey);
        return lookupKey;
    }
}

@Slf4j
@Configuration
public class DataSourceConfig {

    private static final String SOURCE_SERVER = "source";
    private static final String REPLICA_SERVER = "replica";

    @Bean
    @Qualifier(SOURCE_SERVER)
    @ConfigurationProperties("spring.datasource.source")
    public DataSource masterDataSource() {
        log.info("source register");
        return DataSourceBuilder.create().build();
    }

    @Bean
    @Qualifier(REPLICA_SERVER)
    @ConfigurationProperties("spring.datasource.replica")
    public DataSource replicaDataSource() {
        log.info("replica register");
        return DataSourceBuilder.create().build();
    }

    @Bean
    public DataSource routingDataSource(@Qualifier(SOURCE_SERVER) DataSource masterDataSource,
                                        @Qualifier(REPLICA_SERVER) DataSource slaveDataSource) {

        RoutingDataSource routingDataSource = new RoutingDataSource();

        HashMap<Object, Object> dataSourceMap = new HashMap<>();
        dataSourceMap.put(SOURCE_SERVER, masterDataSource);
        dataSourceMap.put(REPLICA_SERVER, slaveDataSource);

        routingDataSource.setTargetDataSources(dataSourceMap);
        routingDataSource.setDefaultTargetDataSource(masterDataSource);

        return routingDataSource;
    }

    @Bean
    @Primary
    public DataSource dataSource() {
        DataSource determinedDataSource = routingDataSource(masterDataSource(), replicaDataSource());
        return new LazyConnectionDataSourceProxy(determinedDataSource);
    }
}

sourceDataSource() 메서드는 spring.datasource.source로 시작하는 설정을 이용하여 DataSource 인스턴스를 생성하고 반환하는 역할을 합니다. 

@ConfigurationProperties 어노테이션은 스프링 부트에서 제공하는 기능으로 외부 구성 파일에 정의된 값을 활용하여 특정 클래스의 필드와 자동으로 바인딩하도록 돕습니다.

replicaDataSource()는 replica 서버에 대한 DataSource 인스턴스를 생성하고 반환하는 역할을 수행합니다.

routingDataSource() 메서드에 각각 정의한 Datasource를 Qualifier를 통해 인자로 주입한 후, RoutingDataSource 객체를 생성합니다.

RoutingDataSource는 위에서 추상클래스인 AbstractRoutingDataSource를 확장한 클래스입니다.

AbStractRoutingDataSource는 데이터 소스의 라우팅을 처리하는 Spring의 클래스로서, 다중 데이터베이스에 대한 접근을 동적으로 제어하는 역할을 수행합니다. 이를 활용하여 트랜잭션 당 하나의 데이터베이스만 사용하도록 설정할 수 있습니다.

이 클래스를 활용함으로써 읽기와 쓰기를 분리할 수 있습니다.

구현해야 하는 추상 메서드는 determineCurrentLookupKey()입니다. 설명에 따르면 현재 데이터베이스의 키 타입에 따라 매칭시킬 수 있도록 하는 역할을 수행합니다. 현재 데이터베이스 연결이 읽기 전용인지 아닌지 판단하여 source와 replica를 반환합니다.

서비스 로직에서 자주 사용하는 @Transactional 어노테이션에 readOnly를 설정할 수 있습니다. 이 값의 설정 여부에 따라, 호출된 현재 트랜잭션이 읽기 전용인지 아닌지 판단할 수 있는 로직을 구현한 것입니다.

TransactionSynchronizationManager.isCurrentTransactionReadOnly() ? "replica" : "source";

다시 routingDataSource로 돌아가서, 이렇게 키 값에 따라 다른 데이터소스를 적용할 수 있도록 돕는 routingDataSource 객체를 생성한 후, HashMap으로 키와, 소스를 매핑하여 setTargetDayaSource에 맵을 주입 합니다.

routingDataSource.setTargetDataSources(dataSourceMap);
routingDataSource.setDefaultTargetDataSource(masterDataSource);

setDefaultTargetDataSource는 기본 데이터소스를 설정할 수 있습니다. 일반적인 쓰기 작업 등은 source 서버에서 진행해야 하므로 기존 값을 설정하였습니다.

마지막으로 datasource() 메서드에서 LazyConnectionDataSourceProxy를 반환하는 것을 확인할 수 있습니다. 이 프록시는 실제 데이터베이스 연결이 필요할 때까지 실제 데이터베이스 연결의 생성을 지연시킵니다. 이 부분에 대해 이해가 되지 않아서 지연 연결 생성 방식에 대한 정리를 해보았습니다.

제가 기존에 알고 있는 DBCP는 미리 데이터베이스의 연결을 생성한 후 필요에 따라 그 연결을 제공합니다. 하지만 LazyConnectionDataSourceProxy는 데이터베이스 연결이 필요할 때까지 실제 데이터베이스 연결의 생성을 지연시킨다는 것에 혼란이 왔습니다.

두 기능은 기본적으로 차이가 존재합니다. DBCP는 연결 생성의 오버헤드를 줄이기 위한 역할이라면, LazyConnectionDayaSourceProxy는 연결 사용 시점을 지연하는 것입니다. 즉, DBCP로 미리 연결을 만들어 놓았지만 실제 SQL 작업이 필요한 시점까지 그 연결을 사용하지 않도록 하는 것이 LazyConnectionDataSourceProxy입니다.

예를 들어 methodA()가 있다고 가정하겠습니다.

void methodA() {

// for 문 등 기타 로직
// 문자열 파싱 등 기타 로직
	memberRepository.findById(id);
}

여기서 for문이나 문자열 파싱 작업은 SQL 작업을 요구하지 않기 때문에 즉각적으로 커넥션을 여는 것이 아니라 memberRepsitory.findyId와 같이 실제 SQL 작업을 요하는 작업이 도달할 때까지 지연하는 것이 LazyConnectionDayaSourceProxy의 역할입니다.

이 객체를 활용함으로써 다음의 장점을 얻을 수 있습니다.

1. 자원 최적화: 데이터베이스 연결은 자원을 많이 요구하는 작업이다. 모든 요청에 대해 연결을 즉시 만들지 않고, 필요한 상황에만 연결을 하도록 최대한 지연시키는 것은 자원 사용률을 줄이는데 도움을 줍니다.

2. 트랜잭션 관리의 향상: 트랜잭션 범위 내에서 실제 SQL 작업이 발생할 때 까지 데이터베이스 연결을 얻지 않음으로써 트랜잭션 시간을 줄일 수 있습니다.

3. 읽기/쓰기 분산 시나리오 지원: 읽기와 쓰기 작업을 분리하는 시나리오에 도움을 주는 역할을 수행합니다. 예를 들어 트랜잭션이 시작되는 지점에는 해당 트랜잭션이 읽기 혹은 쓰기 인지 알 수 없습니다. LazyConnectionDataSourceProxy로 연결을 지연한다면 SQL 요청이 요하는 시점에 어떤 연결이 필요한지 파악할 수 있습니다.

3. 테스트로 읽기 쓰기 테스트 확인하기

@Service
@Transactional
@RequiredArgsConstructor
public class MemberService {

    private final MemberRepository memberRepository;

    public Long save(MemberDto memberDto) {
        return memberRepository.save(Member.builder().name(memberDto.getName()).build()).getId();
    }

    @Transactional(readOnly = true)
    public Member findById(Long id) {
        return memberRepository.findById(id).orElseThrow();
    }

    @Transactional(readOnly = true)
    public Member findByName(String name) {
        return memberRepository.findByName(name).orElseThrow();
    }
}

@SpringBootTest
class MemberServiceTest {

    @Autowired MemberService memberService;
    @Autowired
    private MemberRepository memberRepository;

    @AfterEach
    void clear() {
        memberRepository.deleteAll();
    }

    @Test
    @DisplayName("저장 및 조회하기")
    public void save_find() throws Exception {
        //given
        String memberName = "gose";

        //when
        Long memberId = memberService.save(new MemberDto(memberName));
        Member member = memberService.findById(memberId);

        //then
        Assertions.assertThat(member.getName()).isEqualTo(memberName);
    }
}

테스트 과정에서 중요한 사항은 @Transactional 어노테이션을 사용하지 않고 @AfterEach를 사용하여 데이터를 지우는 작업을 수행하였습니다. 테스트에서 Transactional 어노테이션이 메서드 단위를 하나의 트랜잭션으로 묶어버리는 역할을 수행할 수 있기 때문에 readOnly가 적용되지 않을 수도 있습니다. 따라서, @AfterEach를 활용하여 롤백하는 작업을 처리하였습니다.

Hibernate: 
    insert 
    into
        member
        (name,member_id) 
    values
        (?,?)
2023-06-11T00:04:31.111+09:00  INFO 108103 --- : Current DataSource is master
Hibernate: 
    select
        m1_0.member_id,
        m1_0.name 
    from
        member m1_0 
    where
        m1_0.member_id=?
2023-06-11T00:04:31.157+09:00  INFO 108103 --- : Current DataSource is slave

로그를 확인해 보면 insert 로직은 source 서버에서, select는 replica 서버에서 진행하는 것을 확인할 수 있습니다.

이상으로 스프링부트에 리플리카 서버를 연동하는 방법을 마치도록 하겠습니다.! 

감사합니다.!!!

자료 출처: https://hudi.blog/database-replication-with-springboot-and-mysql/

안녕하세요. 기술적 겸손함으로 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 리플리카 서버를 적용하는 일련의 과정을 시도해 보는 글을 작성하고자 합니다.

저는 ubuntu22.04, docker 24.0.2,  MySql lastest 버전을 사용하였습니다.

1. 리플리케이션

데이터베이스의 리플리케이션은 마스터-슬레이브 구조를 가집니다. 마스터 데이터베이스는 쓰기 작업, 슬레이브 데이터베이스는 읽기 작업을 처리하는 방식입니다.

리플리케이션을 적용하면 다음의 장점을 가질 수 있습니다.

- 부하 분산: 리플리케이션은 슬레이브 서버가 읽기 요청, 마스터 서버가 쓰기 요청을 수행하므로 데이터베이스 부하를 줄일 수 있습니다.

- 고가용성: 마스터 데이터베이스에 문제가 생긴 경우, 슬레이브 서버는 상태를 유지하고 있으므로 데이터 손실의 위험성을 줄일 수 있습니다.

- 읽기 성능 향상: 슬레이브 데이터베이스는 독립적인 읽기 작업을 수행하므로, 읽기 성능을 향상할 수 있습니다.

하지만 고려해야 하는 상황은 다음과 같습니다.

- 쓰기 성능 이슈: 마스터 데이터베이스에 쓰기 요청을 수행한 후, 슬레이브 서버로 데이터를 업데이트하는 과정이 수반되므로, 쓰기 이슈가 발생할 수 있습니다.

구현 목적

1. 스케일 아웃:

수직적으로 서버의 사양을 높이는 것을 스케일 업이라고 한다면, 수평적으로 서버를 증설하는 방법을 스케일 아웃이라고 표현합니다. 스케일 아웃을 적용한다면 스케일 업 방식보다 갑자기 늘어나는 트래픽을 대웅하는데 유연한 구조를 가질 수 있습니다.

2. 데이터 백업:

DB서버에는 다양한 종류의 데이터가 저장이 됩니다. 이 과정에서 DB에 저장된 데이터들을 주기적으로 백업하는 것이 필수적입니다. 따라서, 데이터 백업의 절차등을 리플리케이션 서버에서 진행합니다.

3. 데이터 분석:

특정 데이터 집단에 대해 인사이트를 얻기 위해 분석용 쿼리등을 실행하기도 합니다. 이러한 분석용 쿼리는 대량의 데이터를 조회하는 경우가 많습니다. 집계 연산 등의 복잡하고 무거운 연산을 진행할 수 있으므로 복제를 사용해 여분의 레플리카 서버를 구축하기 위한 용도로도 사용합니다.

4. 데이터의 지리적 분산

서비스에서 사용되는 에플리케이션 서버와 DB는 지리적으로 근접하거나 멀 수 있습니다. DB 서버와 에플리케이션 서버의 거리에 따라 통신 시간이 달라질 수 있으므로 다양한 지점에 대한 DB 서버를 위치함으로써 응답 속도를 개선시킬 수 있습니다.

2. 리플리케이션 서버의 작동 원리

1) Binary Log, Replay Log 두 가지 메커니즘

MYSQL에서 데이터 복제는 Binary Log, Replay Log 두 가지 메커니즘으로 동작합니다.

Binary Log: 마스터 서버에 있는 바이너리 로그는 데이터 변경에 대한 정보를 기록합니다. 테이블에 새로운 데이터가 삽입되거나, 기존 데이터가 수정 또는 삭제될 때 정보를 기록합니다. 이 로그를 바탕으로 슬레이브 서버의 데이터를 업데이트합니다.

Relay Log: 슬레이브 서버는 마스터 서버에서 보낸 Binary Log를 기반으로 자신의 Relay Log에 저장합니다. 이 로그를 바탕으로 데이터를 업데이트합니다.

2) I/O 스레드, SQL 스레드

데이터 복제는 I/O 스레드와 SQL 스레드가 비동기적으로 작동하여 처리됩니다.

I/O 스레드(Slave I/O Thread): I/O 스레드는 슬레이브에서 실행되며 미스터 서버로부터 binary Log Events를 읽어오는 역할을 합니다. 마스터 서버의 Binary Log를 슬레이브의 Relay Log로 복사합니다.

SQL 스레드(Slave SQL Thread): SQL 스레드는 슬레이브에서 실행되며, I/O 스레드가 relay Log에 기록한 이벤트를 읽고 실행하는 역할을 수행합니다. 

3) 특정 데이터 값 변경에 대한 Binary Log와 읽기 작업

MYSQL 복제에서 마스터의 Binary Log에서 슬레이브의 Relay Log로 데이터를 복제하는 I/O 스레드와 이를 실제 슬레이브 DB에서 적용하는 SQL 스레드는 비동기적으로 동작합니다.

I/O 스레드가 마스터의 Binary Log를 읽어 Relay Log에 기록하는 동안 Relay Log는 이전 이벤트를 읽어서 데이터를 업데이트할 수 있습니다. 이 과정에서 데이터 업데이트 간 지연이 발생한다면 최신 변경 사항이 적용되지 않은 데이터를 읽을 수 있습니다.

따라서, 만약 금전과 관련된 정보가 마스터 서버에는 업데이트되어 잔액 부족이 발생할 수 있지만, 지연 문제로 슬레이브 서버에는 잔액이 있다고 나올 수 있습니다. 따라서, 이러한 리플리카 서버의 형태는 마스터 서버에서 쓰기 작업을 수행하고, 리플리카 서버는 읽기 작업의 용도로 활용할 수 있습니다.

4) 슬레이브 서버는 커밋된 트랜잭션을 받아서 복제 처리

슬레이브 서버는 마스터 서버에서 커밋 혹은 롤백된 결과를 바탕으로 복제를 진행합니다. 즉, 마스터 서버에서는 커밋되지 않은 결과를 슬레이브 서버에 보내지 않음으로써 데이터의 원자성을 보존할 수 있습니다.

3. 마스터 서버와 슬레이브 서버 생성하기 

마스터 서버와 슬레이브 서버를 서로 분리하기 위해 도커를 활용하여 마스터 서버, 슬레이브 서버를 분리하였습니다.

절차는 다음과 같습니다.

1) 도커로 마스터 서버 역할을 하는 mysql 컨테이너 생성

2) 마스터 서버에 database 생성 및 table 생성 후 dump.sql 생성

3) 마스터 서버에 연결할 슬레이브 mysql 서버 생성

4) 슬레이브 서버에 dump.sql 파일을 복제한 후, 마스터 서버에 슬레이브 연결

5) 마스터 서버에서 insert 한 결과가 슬레이브에 저장되는지 파악하기

1) 마스터 서버 도커파일 - mysql-master.dockerfile

FROM mysql:latest

ENV MYSQL_ROOT_PASSWORD root
ENV MYSQL_DATABASE sample
ENV MYSQL_USER user
ENV MYSQL_PASSWORD password

COPY my.cnf /etc/mysql/my.cnf

EXPOSE 3306

CMD ["mysqld"]

도커파일이 있는 폴더 내부에 my.cnf 파일을 추가하였습니다.

[mysqld]
log-bin=mysql-bin
server-id=1

도커파일을 빌드하면 다음의 절차를 따르게 됩니다.

docker build -t mysql_master -f mysql-master.dockerfile .

도커 이미지가 생성되면, 도커 내부의 mysql 포트와 호스트 os의 포트를 연결하기 위해 다음의 커멘드를 입력합니다.

docker run -p 3307:3306 --name order_master -e MYSQL_ROOT_PASSWORD=1234 -d mysql-master

이후 도커 내부 쉘에 접속하기 위해 다음의 코드를 작성합니다.

docker exec -it order_master /bin/bash

# bash 이동 후
mysql -u root -p
password : 1234

# mysql 내부 

CREATE USER 'orderroot'@'%' IDENTIFIED BY '1234';
ALTER USER 'orderroot'@'%' IDENTIFIED WITH mysql_native_password BY '1234';
GRANT REPLICATION SLAVE ON *.* TO 'orderroot'@'%';
FLUSH PRIVILEGES;

grant replcation slave on *.* to 'orderrot'@'%'; 은 

사용자에게 복제(slave) 권한을 부여하는 구문입니다. 복제 권한은 마스터 서버에서 변경 사항을 읽을 수 있도록 허용하는 권한입니다. 이는 슬레이브 서버가 마스터 서버의 데이터 변경을 추적할 수 있게 합니다.

2) 데이터베이스 및 테이블 생성 후 dump.sql 생성

마스터 서버에서 데이터베이스 및 테이블을 생성하면 다음과 같습니다.

# mysql 쉘 
create database orders;

CREATE TABLE member (
    member_id BIGINT PRIMARY KEY,
    name VARCHAR(255)
);

insert into member value (1, 'kose');
insert into member value (2, 'gose');

exit

# bash 쉘
mysqldump -u root -p orders < dump.sql;

ls // dump.sql이 있어야 함
exit

이어진 로컬의 쉘에서 다음의 명령어를 입력합니다.

docker cp order_master:dump.sql .
>> Successfully copied 3.58kB to /home/gosekose/.

3) 슬레이브 서버 생성하기

마스터 서버와 마찬가지로 도커파일을 생성하되(위에 있던 마스터 도커 파일과 동일합니다.)

my.cnf를 수정해서 빌드하여야 합니다.

[mysqld]
log-bin=mysql-bin
server-id=2

마스터 서버와 분리되는 고유한 id를 설정하기 위해 slave 서버는 server-id=2로 한 후 도커 빌드를 진행합니다.

docker build -t mysql_slave -f mysql-slave.dockerfile .

이어서 빌드가 완료되면 마스터 서버와 연결하기 위해 --link를 추가하여 다음의 명령어를 실행합니다.

--link는 서로 다른 컨테이너 간 연결을 돕는 도커 명령어입니다.

docker run -p 3308:3306 --name order_slave -e MYSQL_ROOT_PASSWORD=1234 --link order_master -d mysql-slave

4) 슬레이브 서버에 덤프 파일 적용

이전에 생성한 덤프파일을 도커로 복사한 후, (cp) 데이터 베이스를 생성하여 dump.sql을 복사합니다.

docker cp dump.sql order_slave:.
docker exec -it order_slave /bin/bash

mysql -u root -p

mysql> CREATE DATABASE orders;

mysql> exit

mysql -u root -p orders < dump.sql

기존에 있는 데이가 슬레이브에 덤프 되었습니다.

5) 슬레이브 서버에 마스터 서버 연결하기

order_master의 mysql로 이동한 후 현재 master 서버의 status를 확인합니다.

mysql> SHOW MASTER STATUS\G

여기서 기억할 부분은 mysql-bin.000003, position 2193입니다. 

이어서 슬레이브 서버의 order_slave의 mysql로 이동하여 마스터 서버를 연결합니다.

CHANGE MASTER TO MASTER_HOST='order_master', MASTER_USER='orderroot', MASTER_PASSWORD='1234', MASTER_LOG_FILE='mysql-bin.000003', MASTER_LOG_POS=2193;

마스터 서버가 연결된 것을 확인하기 위해 하단의 명령어를 입력합니다.

SHOW SLAVE STATUS\G

Master_LOG_FILE 및 Read_Master_Log_Pos가 모두 마스터 서버의 값이 잘 기입되었습니다.

하단에 SlaveI_IO_Running, Slave_SQL_Running이 모두 Yes가 떠야 성공입니다.

이는 위에서 설명했던 슬레이브 서버에서 작용하는 스레드 두 가지가 모두 완료되어야 하는 것을 의미합니다.

5) 마스터 서버에 쓰기 진행

마스터 서버에 새로운 member를 저장합니다.

insert into member value(3, 'gosekose');

마스터 서버

슬레이브 서버

값이 잘 저장된 것을 확인할 수 있습니다.

이번 포스팅은 MySQL 리플리카 서버를 적용하는 과정에 대한 글을 작성하였습니다. 다음 글은 리플리카 서버를 바탕으로 스프링 부트 서버를 기동하여 리플리카 서버를 활용하는 글을 작성하고자 합니다. 이상으로 포스팅을 마치도록 하겠습니다. 감사합니다!

사진 출처: https://tgyun615.com/118

참고 자료: https://escapefromcoding.tistory.com/710

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 별자리 만들기 자바 풀이를 진행하도록 하겠습니다.

문제 출처: https://www.acmicpc.net/problem/4386

1. 풀이 소스

import java.util.*;
import java.io.*;
import static java.lang.Double.parseDouble;
public class Main {
    
    static int n; // n개의 별
    static int[] parent; // 부모 노드
    static int[] count; // 자식 노드 개수
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        parent = new int[n]; // 초기화
        count = new int[n];
        double[][] star = new double[n][2];
        
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            double x = parseDouble(st.nextToken());
            double y = parseDouble(st.nextToken());
            star[i][0] = x;
            star[i][1] = y;
            parent[i] = i; // 초기화는 부모 노드 = 자식 노드
            count[i] = 1; // 자신을 포함해야하므로 개수 1로 초기화
        }
        if (n == 1) {
            System.out.println(0.00); // n == 1이라면 거리 측정 불가 0
            return;
        }
        
        System.out.printf("%.2f", getDistance(star));
    }

    // 우선순위 큐에 거리를 입력한 후 하나씩 빼며 유니온 파인드 진행
    // count[p1]이 n개를 만족한다면 모든 자식 노드가 하나의 루트를 공유하므로 mst 완성
    static double getDistance(double[][] star) {
        Queue<Star> queue = new PriorityQueue<>(Comparator.comparing((Star s) -> s.distance));
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                double distance = Math.sqrt(Math.pow((star[i][0] - star[j][0]), 2) + Math.pow((star[i][1] - star[j][1]), 2));
                queue.add(new Star(i, j, distance)); // 우선순위 큐에 별 간의 거리 입력
            }
        }
        
        double distance = 0.0;
        while(!queue.isEmpty()) {
            Star s = queue.poll();
            int p1 = find(s.idx1);
            int p2 = find(s.idx2);

            if (p1 != p2) { // 두 부모가 다른 경우에만 유니온 (사이클 방지)
                union(p1, p2); // 유니온
                distance += s.distance; // 거리 업데이트
            }

            if (count[p1] == n) break; // 만약 개수가 n개가 된다면 탐색 종료
        }
        
        return distance; // 거리 리턴
    } 
    
    
    static int find(int child) { // 경로 압축으로 find
        if (parent[child] == child) return child;
        return parent[child] = find(parent[child]);
    }
    
    static void union(int p1, int p2) { // 유니온
        parent[p2] = p1;
        count[p1] += count[p2]; // p2를 부모로 가지는 자식 노드들의 개수를 count[p1]에 더해주기
        count[p2] = 0;
    }
    
    static class Star {
        int idx1; // 별 첫번째
        int idx2; // 별 두번째
        double distance; // 두 별 간의 거리
        
        Star (int idx1, int idx2, double distance) {
            this.idx1 = idx1;
            this.idx2 = idx2;
            this.distance = distance;
        }
    }
}

2. 풀이 중점 사항

이번 문제는 MST 문제로, 두 별사이의 거리를 우선순위 큐에 저장한 후, 모든 노드가 하나의 경로로 이어질 수 있도록 유니온 파인드를 적용하는 방법으로 해결할 수 있었습니다.

우선순위 큐

MST에서 크루스칼 알고리즘을 사용한다면 우선순위 큐를 활용하여 간선의 가중치를 오름차순 형태로 빼낼 수 있습니다.

다른 문제와 달리 이 문제는 간선의 길이를 제공하지 않으므로 두 별자리의 계산 공식 (두 점 사이의 거리)를 활용하여 값을 구하고 이를 우선순위 큐에 넣는 방법을 활용해야 합니다.

Queue<Star> queue = new PriorityQueue<>(Comparator.comparing((Star s) -> s.distance));

for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        double distance = Math.sqrt(Math.pow((star[i][0] - star[j][0]), 2) + Math.pow((star[i][1] - star[j][1]), 2));
        queue.add(new Star(i, j, distance)); // 우선순위 큐에 별 간의 거리 입력
    }
}

람다를 활용하여 distance로 정렬할 수 있도록 한 후, 두 점사이의 거리 공식을 활용하고 큐에 넣습니다.

유니온 파인드

static int find(int child) { // 경로 압축으로 find
    if (parent[child] == child) return child;
    return parent[child] = find(parent[child]);
}

static void union(int p1, int p2) { // 유니온
    parent[p2] = p1;
    count[p1] += count[p2]; // p2를 부모로 가지는 자식 노드들의 개수를 count[p1]에 더해주기
    count[p2] = 0;
}

find(), union()은 정형화된 메서드입니다. 경로압축으로 자식 노드가 가리키는 부모 노드를 찾으면서 업데이트합니다.

union()은 찾은 두 부모를 하나로 연결하는 과정으로, parent[p2]의 값을 p1으로 업데이트하여, p2의 부모가 p1이 되도록 합니다.

하단에 count[]코드는 n개의 별자리를 만족시키면 종료해야 합니다. 이 경우, 부모 노드가 가지고 있는 자식 노드들의 개수를 합치는 (더 커지는) 부모 노드에 업데이트해주어야 합니다. 

따라서, p1에 p2의 자식 노드들의 개수를 더해주고, p2는 더 이상 루트 노드가 아니므로 0으로 업데이트합니다.

double distance = 0.0;
while(!queue.isEmpty()) {
    Star s = queue.poll();
    int p1 = find(s.idx1);
    int p2 = find(s.idx2);

    if (p1 != p2) { // 두 부모가 다른 경우에만 유니온 (사이클 방지)
        union(p1, p2); // 유니온
        distance += s.distance; // 거리 업데이트
    }

    if (count[p1] == n) break; // 만약 개수가 n개가 된다면 탐색 종료
}

return distance; // 거리 리턴

만약 이미 부모가 같은 경우는, distance를 증가시키면 안 됩니다 (사이클)

이미 같은 부모를 공유한다는 의미는 두 별자리에 대한 distance를 더했음을 의미합니다.

따라서, 이 경우는 패스하고 두 부모가 다른 경우에만 적용할 수 있도록 하였습니다.

이상으로 백준 별자리 만들기 풀이를 마치도록 하겠습니다.

감사합니다!!!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 LIS 문제 - 가장 긴 증가하는 부분 수열5 자바 풀이를 진행하도록 하겠습니다.

문제 출처: https://www.acmicpc.net/problem/14003

1. 풀이 소스

import java.io.*;
import java.util.*;
import static java.lang.Integer.parseInt;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = parseInt(br.readLine());
        int[] arr = new int[n]; // 입력 배열
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        for (int i = 0; i < n; i++) arr[i] = parseInt(st.nextToken()); // 배열 초기화
        List<Integer> result = search(arr);
        
        StringBuilder sb = new StringBuilder();
        sb.append(result.size()).append("\n");
        for (Integer i : result) sb.append(i).append(" ");
        System.out.print(sb);
    }
    
    static List<Integer> search(int[] arr) {
        List<Integer> dp = new ArrayList<>();
        
        int[] idxs = new int[arr.length]; // 인덱스 저장
        int[] preIdxs = new int[arr.length]; // 다음으로 이동할 임시 인덱스
        
        for (int i = 0; i < arr.length; i++) {
            if (dp.isEmpty() || arr[i] > dp.get(dp.size() - 1)) {
                if (!dp.isEmpty()) preIdxs[i] = idxs[dp.size() - 1]; // dp가 비지 않은 경우 업데이트하는 인덱스와 다음으로 이동할 인덱스 업데이트
                dp.add(arr[i]); // dp에 추가
                idxs[dp.size() - 1] = i; // 인덱스 업데이트
            } else { // 이분 탐색
                int left = 0, right = dp.size() - 1;
                while (left < right) {
                    int mid = left + (right - left) / 2;
                    if (dp.get(mid) < arr[i]) left = mid + 1;
                    else right = mid;
                }
                dp.set(right, arr[i]);
                idxs[right] = i;
                if (right > 0) preIdxs[i] = idxs[right - 1];
            }            
        }
        
        List<Integer> lis = new ArrayList<>();
        int idx = idxs[dp.size() - 1];
        while (lis.size() < dp.size()) {
            lis.add(arr[idx]);
            idx = preIdxs[idx];
        }
        Collections.reverse(lis); // 마지막 역순 출력
        return lis;
    }
}

2. 풀이 중점 사항

해당 문제는 이전에 풀었던 LIS 풀이에서 자세하게 설명하였습니다!

해당 풀이에서 그림과 함께 자세하게 설명하여서 링크를 남기도록 하겠습니다!

https://gose-kose.tistory.com/103

이상으로 풀이를 마치겠습니다 감사합니다!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 LCS 문제 - LCS2 자바 풀이를 진행하도록 하겠습니다.

문제 출처: https://www.acmicpc.net/problem/9252

1. 풀이 소스

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));

        String str1 = br.readLine(); // 문자열 1
        String str2 = br.readLine(); // 문자열 2
        int[][] dp = new int[str1.length() + 1][str2.length() + 1];

        for (int i = 1; i <= str1.length(); i++) { // LCS 공식
            for (int j = 1; j <= str2.length(); j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }

        StringBuilder sb = new StringBuilder();
        if (dp[str1.length()][str2.length()] == 0) sb.append(0); // 만약 값이 0 -> LCS가 없음
        else {
            sb.append(dp[str1.length()][str2.length()]).append("\n");

            Stack<Character> stack = new Stack<>();
            int row = str1.length(), col = str2.length();
            while (row > 0 && col > 0) { // 역추적 --> LCS 공식에 따라, (행 - 1)과 같다면 행--, (열 - 1)과 같다면 열 --

                if (dp[row][col] == dp[row - 1][col]) row--;
                else if (dp[row][col] == dp[row][col - 1]) col--;
                else { // 행 혹은 열 하나씩 뺀 것과 같지 않다면, 나머지는 대각선
                    stack.push(str1.charAt(row - 1)); // 스택에 넣기
                    row--;
                    col--;
                }
            }

            while(!stack.isEmpty()) sb.append(stack.pop()); // 후입선출로 맨 마지막부터 출력
        }
        System.out.println(sb);
    }
}

2. 풀이 중점 사항 

LCS 공식 적용

for (int i = 1; i <= str1.length(); i++) { // LCS 공식
    for (int j = 1; j <= str2.length(); j++) {
        if (str1.charAt(i - 1) == str2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1] + 1;
        else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
    }
}

이전 LCS 문제에서 풀이했던 방식을 그대로 활용할 수 있습니다. 이전 블로그에서 자세하게 작성하였습니다. 혹시 LCS 공식이 헷갈리신다면 참고 부탁드립니다.!

https://gose-kose.tistory.com/119 

LCS 역추적하기

Stack<Character> stack = new Stack<>();
int row = str1.length(), col = str2.length();
while (row > 0 && col > 0) { // 역추적 --> LCS 공식에 따라, (행 - 1)과 같다면 행--, (열 - 1)과 같다면 열 --

    if (dp[row][col] == dp[row - 1][col]) row--;
    else if (dp[row][col] == dp[row][col - 1]) col--;
    else { // 행 혹은 열 하나씩 뺀 것과 같지 않다면, 나머지는 대각선
        stack.push(str1.charAt(row - 1)); // 스택에 넣기
        row--;
        col--;
    }
}

while(!stack.isEmpty()) sb.append(stack.pop()); // 후입선출로 맨 마지막부터 출력

LCS를 만들 때, 만약 두 문자열의 값이 같다면 대각선을 활용하고, 아니라면 행 혹은 열은 하나씩 줄여서 최대값으로 이어 가는 것을 확인할 수 있었습니다. 이를 그대로 활용하여, 최대값을 기준으로 대각선과 값이 같다면 stack에 값을 넣고, row, col을 각각 -- 해줍니다. 만약 행이 하나 작은 것과 같다면, 행을 줄이고, 열이 하나 작은 것과 같다면 열을 줄여서 최대값이 적용된 흐름대로 움직이는 것입니다.

이러한 방법으로 LCS의 값을 역추적할 수 있습니다. 이상으로 풀이를 마치겠습니다. 감사합니다!!!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 이분탐색 문제 - 공유기 설치 자바 풀이를 진행하도록 하겠습니다.

문제 출처: https://www.acmicpc.net/problem/2110

1. 풀이 소스

import java.io.*;
import java.util.*;
import static java.lang.Integer.parseInt;

public class Main {
    static int n;
    static int[] house;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = parseInt(st.nextToken());
        int m = parseInt(st.nextToken());

        house = new int[n];
        for (int i = 0; i < n; i++) house[i] = parseInt(br.readLine());
        Arrays.sort(house);

        int left = 1; // 최소 거리는 1
        int right = house[n - 1] - house[0] + 1; // 최대 거리는 양끝 값 차이 + 1

        while (left < right) { // upper bound로 찾기
            int mid = left + (right - left) / 2; // 두 거리의 중점으로 거리 업데이트

            int count = installWifi(mid);
            if (count < m) right = mid; // 설치된 개수가 m에 만족하지 않는 경우 더 설치 해야하므로 최소 거리 줄이기
            else left = mid + 1; // 최소 거리를 만족하므로 더 길게 가능한지 파악하기 위해 left 업데이트
        }

        System.out.println(left - 1);
    }

    static int installWifi(int distance) {
        int lastLoc = house[0]; // lastLoc은 맨 처음집으로 설정
        int count = 1; // lastLoc은 1번 집 설정하므로 개수 1

        for (int i = 0; i < n; i++) {
            int nowLoc = house[i];

            if (nowLoc - lastLoc >= distance) { // 최소 거리보다 크다면
                count++; // 개수 증가
                lastLoc = nowLoc; // 마지막 위치 업데이트
            }
        }
        return count;
    }
}

2. 풀이 중점 사항

해당 문제는 이분탐색을 어느 것으로 설정하느냐가 중요한 포인트였습니다.

m개의 공유기를 설치해야 하므로, 공유기 위치를 콤비네이션으로 정의하게 된다면 그 경우의 수가 10억 C 20만 까지 될 수 있으므로 시간초과가 발생할 수 있습니다.

따라서, 최단 거리를 이분탐색하여, m개의 공유기를 만족하는 가장 큰 값을 찾는 방법으로 문제를 정의할 수 있습니다.

예를 들어 이분탐색한 결과 집 간 인접한 두 공유기의 사이의 최대 거리가 3일 때, 10개의 공유기를 설치할 수 있습니다.

이는 곳 1, 4, 10, 15 .... 혹은 1, 4, 7, 14...로 10개를 설치했음을 의미합니다.

m개의 공유기를 만족하기 때문에 mid 값인 3에 +1을 하여 길이를 4로 만들고 다시 탐색하여 공유기 10개를 설치할 수 있는지 판단합니다. 만약 m개를 만족하지 않는다면 right = 4를 설정하여 다시 이분탐색을 진행하는 것입니다.

이 원리를 적용하면,

집의 개수 최대 20만,

공유기 개수 최대 20만

이분 탐색 0 ~ 10억 사이의 거리이므로 log10억  = 약 28 ~ 30 사이쯤

이분탐색하는 횟수 * 집을 탐색하며 공유기를 설치하는 횟수 

= O(20만 * 30) = O(600만) 정도로 생각할 수 있습니다.

3. 코드로 확인하기

int left = 1; // 최소 거리는 1
int right = house[n - 1] - house[0] + 1; // 최대 거리는 양끝 값 차이 + 1

따라서, 길이의 최소 거리를 의미하는 1과 각 집의 가장 양끝에 있는 거리를 left, right로 설정하여, mid를 구합니다.

mid를 최단 거리로 설정하여, 마지막 설치된 공유기의 길이에서 지금 설치하는 공유기 길이가 최소거리보다 큰 경우에만 업데이트합니다. (만약 최소 거리보다 작다면 카운트 개수가 증가하지 않으므로, m 개수를 만족하지 않는다면 이분탐색을 다시 실행)

static int installWifi(int distance) {
    int lastLoc = house[0]; // lastLoc은 맨 처음집으로 설정
    int count = 1; // lastLoc은 1번 집 설정하므로 개수 1

    for (int i = 0; i < n; i++) {
        int nowLoc = house[i];

        if (nowLoc - lastLoc >= distance) { // 최소 거리보다 크다면
            count++; // 개수 증가
            lastLoc = nowLoc; // 마지막 위치 업데이트
        }
    }
    return count;
}

while (left < right) { // upper bound로 찾기
    int mid = left + (right - left) / 2; // 두 거리의 중점으로 거리 업데이트

    int count = installWifi(mid);
    if (count < m) right = mid; // 설치된 개수가 m에 만족하지 않는 경우 더 설치 해야하므로 최소 거리 줄이기
    else left = mid + 1; // 최소 거리를 만족하므로 더 길게 가능한지 파악하기 위해 left 업데이트
}

이렇게 얻은 count로 m개에 만족, 불만족하는지 판단한후 upper bound 형식으로 이분탐색을 진행합니다.

이상으로 백준 공유기 설치 자바 풀이를 마치도록 하겠습니다. 감사합니다.! 

참고 블로그: https://st-lab.tistory.com/277

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 나무 자르기 자바 풀이를 진행하도록 하겠습니다.

문제 출처: https://www.acmicpc.net/problem/2805

1. 풀이 소스

import java.util.*;
import java.io.*;
import static java.lang.Integer.parseInt;

public class Main {
    static int[] trees;
    static int m;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = parseInt(st.nextToken());
        trees = new int[n]; // n개의 나무
        
        m = parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int max = 0;
        for (int i = 0; i < n; i++) {
            trees[i] = parseInt(st.nextToken());
            max = Math.max(trees[i], max); // 가장 긴 나무를 선택하여 자를 위치 선정
        }
        
        System.out.println(find(max));
    }
    
    static long find(int max) {
        long value, left, mid; // 이분 탐색을 위한 long 값 20억 이상 될 수 있음
        long right = max; // right 최대값 선정
        value = left = mid = 0L; // value, left 초기화

        while(left < right) {
            mid = left + (right - left) / 2; // 이분탐색 중간 값 최대 40억

            for (int tree : trees) {
                if (tree > mid) value += tree - mid; // 잘리는 위치보다 큰 경우 더하기
            }
            
            if (value >= m) left = mid + 1; // 목표로 하는 값보다 같거나 크다면 upper bound
            else right = mid; // 아니라면 right
            value = 0; // value 초기화
        }
        
        return right - 1;
    }
}

2. 시간 복잡도 계산

이번 문제는 앞 서 풀었던 랜선 자르기와 비슷한 문제로 이분 탐색의 upper bound를 설정하여 해결할 수 있습니다.

최대 100만 개의 N을 가지고, 20억 개의 범위를 탐색해야 하므로 일반적으로 for문을 돌린다면 시간초과가 날 수 있습니다.

총나무의 수가 최대 100만 개이므로 찾은 최적의 값을 가지고 100만 번을 연산해야 합니다. 만약 아니라면 값을 바꿔서 다시 진행해야 하므로 100만 * 나무를 찾는 횟수가 시간 복잡도가 됩니다.

이분 탐색은 logM의 시간 복잡도를 가지므로. 이분 탐색의 upper bound를 활용한다면,

O(N * logM)  = O(100만 * 약 31) = 대략 O(3100만) 의 시간을 가진다고 볼 수 있습니다. 

3. upper bound로 계산하기

static long find(int max) {
    long value, left, mid; // 이분 탐색을 위한 long 값 20억 이상 될 수 있음
    long right = max; // right 최대값 선정
    value = left = mid = 0L; // value, left 초기화

    while(left < right) {
        mid = left + (right - left) / 2; // 이분탐색 중간 값 최대 40억

        for (int tree : trees) {
            if (tree > mid) value += tree - mid; // 잘리는 위치보다 큰 경우 더하기
        }
        
        if (value >= m) left = mid + 1; // 목표로 하는 값보다 같거나 크다면 upper bound
        else right = mid; // 아니라면 right
        value = 0; // value 초기화
    }
    
    return right - 1;
}

upper bound는 찾아야 하는 값 a에 가장 근접하게 큰 수를 찾도록 돕는 알고리즘입니다.

이분탐색을 수행하면서 경계점을 찾아야 하는 경우 사용할 수 있습니다.

mid의 값을 left + (right - left) / 2로 업데이트한 후, value가 크거나 같다면 left = mid + 1 하여 upper 경계를 올립니다.

value가 크거나 같다는 말은 충분한 양을 획득했다는 의미이므로 높이를 올려서 잘라야 하는 양을 줄이는 것입니다.

(기기의 높이를 올리면 잘리는 길이가 줄어듬)

반면, 작다면 right = mid로 수정하여 value를 증가시키는 방법으로 이분탐색을 진행합니다.

left가 right보다 같거나 커지는 시점이 오면 루프를 종료하고, upper의 경계를 설정했으므로 right의 값에서 -1을 하여 리턴합니다.

-1을 하는 이유는 다음과 같습니다.

left 35

right 37

mid 36 

value >= m

-> left = mid + 1;

left <= right 이므로 종료하게 됩니다. 여기서 right는 찾아야 하는 target의 값보다 1이 크게 되므로(자연수)

이와 같은 로직을 작성할 수 있게 됩니다.

이상으로 백준 나무 자르기 자바 풀이를 마치도록 하겠습니다.

감사합니다.!!!