이분 탐색 문제를 접근할 때, 백준 블로그를 참고하면 정말 도움이 된다.

블로그 내용을 요약하면,

"결정 문제"를 풀어낼 때 이분적으로 답이 두 구간으로 나뉠 때 이분 탐색 알고리즘을 이용할 수 있다는 것이다. 또한, 많은 최적화 문제를 풀어낼 수 있음.

최적화 문제란?

어떤 조건 Check(x)를 만족하는 x의 최댓값 또는 최솟값을 찾는 문제를 말함. 이 경우, Check(x)가 x에 대해 이분적이면 이분 탐색을 사용할 수 있다는 것이다.

내용 핵심 정리

1. [lo, hi]가 Check(lo) ≠ Check(hi)가 되도록 구간을 설정
2. while(lo + 1 < hi) 동안 mid = (lo + hi) / 2에서 Check(mid) = Check(lo)라면 lo = mid, 아니라면 hi = mid
3. 구한 경계에서 답이 lo인지 hi인지 생각해보고 출력하기

문제

https://www.acmicpc.net/problem/17951 내용을 요약하자면 시험지의 개수 N과 나눌 그룹의 수 K가 정수로 주어졌을 때, K개의 그룹으로 나눈 뒤 각각의 그룹에서 맞은 문제의 개수의 합을 구하여 그중 최솟값을 시험 점수로 하기로 하였다.

따라서 우리가 구해야 할 핵심은 K개의 그룹으로 나눌 수 있을 때, 최솟값들 중 최댓값을 구해야 한다는 것이다.

주의사항: 시험지를 현재 순서 그대로 K개의 그룹으로 나눈다는 것이다.

정렬되어 있지 않는 시험지 점수들 때문에 어떻게 이분 탐색으로 최적화할 수 있을까?를 고민할 수 있지만 이 문제의 접근 핵심은 최소 점수와 최대 점수의 합을 이용하여 각 그룹이 가질 수 있는 임계값, 즉 최댓값을 지정해주면 된다

1. 내용 핵심 정리에서 설명한대로, 경계를 설정해야 한다. 왼쪽 경계, 즉 lo에 대해 0으로 설정하자. 그러면 각 그룹이 가질 수 있는 최댓값이 0으로 지정된다. 이 말은 시험 점수 각각 하나씩이 그룹이 되어버린다.
2. hi에 대해 점수의 총합 + 1 로 설정하자. 그러면 각 그룹이 가질 수 있는 최댓값이 전체 총합 + 1로 지정된다. 이 말은 모든 시험 점수를 더해도 최댓값을 넘지 못하기 때문에 하나의 그룹만 생성된다.

그 결과, 왼쪽 경계는 K개보다 그룹이 많거나 같다를 항상 만족하고, 오른쪽 경계는 K개보다 작다. 이에 대한 check 함수를 작성하자면

public static boolean check(int K, int mid, int[] scores) {
    int sum = 0, cnt = 0;

    for (int score : scores) {
        sum += score;

        if (sum >= mid) {
            cnt++;
            sum = 0;
        }
    }

    return cnt >= K;
}

이를 말로 설명하자면, cnt >= K 를 만족한다는 것은 그룹의 최댓값으로 설정된 mid로는 K개 이상의 그룹을 만들 수 있다는 것이기 때문에 lo = mid로 만들어서 더 큰 왼쪽 경계를 만들어주면 된다. 그 결과, cnt == K가 될 때 까지 왼쪽 경계를 TTTTTTTT.. FFF 로 만들어간다는 것이다.

반대로 cnt < K보다 작다면 반대로 hi = mid가 되어 경계를 조절한다.

lo + 1 == hi 가 되었을 떄, 경계에서 어느쪽이 정답일까?를 생각하고 정답을 구하면 된다.

해당 문제에서는 왼쪽 경계가 조건을 만족할 때까지 최대로 조절하기 때문에 lo가 정답이 된다.

전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

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

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int[] scores = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        int min = 0, max = 1;

        for (int score : scores) {
            max += score;
        }

        while (min + 1 < max) {
            int mid = (min + max) / 2;

            if (check(K, mid, scores)) {
                min = mid;
            } else {
                max = mid;
            }
        }

        System.out.println(min);
    }

    public static boolean check(int K, int mid, int[] scores) {
        int sum = 0, cnt = 0;

        for (int score : scores) {
            sum += score;

            if (sum >= mid) {
                cnt++;
                sum = 0;
            }
        }

        return cnt >= K;
    }
}

내가 작성한 코드, 팀원이 작성한 코드 등을 신뢰할 수 있도록 보조해주는 장치가 무엇일까? 대표적으로 테스트가 존재합니다. 졸업 프로젝트, 사이드 프로젝트 등을 수행하면서 테스트 코드를 많이 작성하는가? 에 대해 네 라고 대답하기에는 어렵습니다. 빠듯한 일정, 경험 부족, 테스트를 잘 수행하고 있는지...

그럼에도 최근에 들어 사이드 프로젝트에서는 의식적인 테스트 작성을 하면서 느낀 명확한 장점들이 있습니다. 1. 내가 생각한 논리를 명확하게 검증할 수 있다 2. 예외 케이스 테스트를 생각하고 작성하면서 기존 코드 개선을 시도하게 된다 3. 프론트엔드 개발자들과 협업하며 불안 요소를 줄였고, 반복하는 작업이 줄었다

테스트에 대해 소홀하게 할수록 반복적인 작업이 늘어나고 시간을 낭비하게 되는데 이에 대해 많이 개선해보았던, 그리고 도움을 받았던 스토리를 소개합니다.

Unit Test 수행

내가 정의한 데이터 형태를 기반으로 의존 관계는 걷어내고 테스트 하고자 하는 하나의 기능, 메서드의 로직을 빠르게 검증할 수 있다. 순서와 논리를 통해 호출 여부를 검증할 수도, 데이터의 상태 값을 통해 명확한 비교도 가능하기에 작은 단위에서부터의 시작은 쌓여가는 테스트 코드들의 신뢰성을 더 높일 수 있다고 생각합니다.

서적을 읽다보면, 테스트에 대한 런던파 스타일과 고전파 스타일이 존재하는데, 제가 수행한 방법은 Mockito를 통해 의존성을 테스트 대역으로 대체하고 고립시켜서 수행했습니다.

Data Layer Test 수행

Database를 액세스하는 쿼리에 대한 테스트도 검증할 수 있는데, 이는 실제 데이터베이스에 잘 저장됐는지, 원하는 데이터들이 조회되는지, 수정됐는지 등등 기본적인 CRUD를 확인할 수 있을 뿐만 아니라 쿼리가 복잡해질수록 신뢰를 보장해줄 수 있다.

Test Fixture의 반복적인 문제

시스템에 넘어오는 데이터의 형태는 항상 똑같거나, 개발자가 생각한 형태만 존재할까? 모르는 일이라고 생각합니다. 따라서, 변수를 항상 염두해두고 안전하게 코드를 작성하는 것도 개발자의 책임이라고 생각됩니다. 테스트 코드만 작성했다고 코드의 급격하게 신뢰성이 올라가지는 않기에, Input으로 들어오는 데이터를 Random하게 생성해주고 검증 장치가 정확하게 동작하는지 여부를 확인할 수 있습니다.

이를 도와주는 도구가 있습니다. 저희 프로젝트 팀은 이 도구를 도입하여 실제 큰 효과를 보고 있습니다. 해당 도구: Naver Fixture Monkey

1. 내가 수행했던 테스트는 통과하더라도, 갑작스럽게 CI과정에서 테스트가 실패했던 경험이 있습니다. 검증 장치를 통해 데이터가 필터링 되어 개발자가 정의한 데이터의 형태 또는 값의 범위 등을 벗어나 테스트 코드를 개선해 나아간 사례가 있습니다.

2. 기존에는 Fixture를 만드는 코드가 중복이 발생하기도 하고, 다양한 예외 검증을 하지 못했습니다. 기술의 도움을 받아서 Fixture를 간단하게 생성할 수 있었고 생산성을 높일 수 있었습니다.

Integration Test

프로젝트에서 사용하는 기술들이 많이 존재하면 존재할수록 통합 테스트를 위한 환경 구축이 까다롭습니다. 매번 반복적으로 불필요한 시간 낭비를 줄이고 테스트에 집중할 수 있는 방법이 있습니다. TestContainers를 이용하면 개인 환경에 Docker Engine만 설치되어 있다면, 통합 테스트를 쉽게 실행할 수 있습니다. Database, Cache 등 구성만 요구사항에 맞게 설정한다면 쉽게 실행됩니다. 해당 설정 방법은 TestContainers 공식 문서에서 확인할 수 있습니다.

자동화

1. 환경 구성 설정을 작성하기 Ex) Database : MySQL, Cache: Redis

2. CI 과정에서 테스트 자동화 및 커버리지 측정

수행하는 프로젝트: https://github.com/CAKK-DEV/cakk-server

알아가면 좋은 내용 TestContainers 동작을 위해서는 Container Engine이 필요하다고 했다. Github Actions를 통해 CI를 구성하게 되면, Default로 Docker Environment를 제공받기 때문에 추가적으로 환경 제공을 명시할 필요가 없어서 편하다.

개선점

• Data Access까지 SQL Script를 통해 필요한 데이터들을 준비하고 전체적인 통합 테스트를 수행할 수 있기 때문에 기능 전체에 대해 검증이 가능해서 생산성을 높일 수 있었습니다.
• Test Running을 위한 애플리케이션 구성을 독립적으로 관리할 수 있어서 유지보수가 용이해졌다고 생각합니다. 즉, 구성이 변경되더라도 환경 구성 코드만 변경해주면 관리가 쉽습니다.
• CI 환경에서도 기존에는 통합 테스트 수행을 위해 실제 필요한 Docker Image를 가져오는 구성부터 버전 관리 등 유지보수 해야 할 범위가 넓었는데 이를 제거할 수 있게 되었습니다.

간단하게 사이드 프로젝트를 소개하자면, 수제 케이크샵들을 사용자 위치 기반으로 제공해주고 있는 것이 메인 기능이다. 케이크 샵 사장님들은 자신의 케이크 샵에 대해 사장님 인증을 할 수 있는 기능을 제공하고 있다.

애플리케이션 다운로드 또는 살펴보기

기획에 따라, 백엔드 로직은 다음과 같은 Flow를 진행해야 한다.

1. "유저는 케이크 샵에 대해 사장님 인증을 요청한다"
2. "케이크샵과 유저 정보를 담는다"
3. "외부 서비스에 인증 요청을 보낸다"

PHASE 1단계에서 외부 서비스는 Slack이라는 외부 메신저 툴에게 웹훅을 활용하여 요청 메시지가 전송되도록 구현을 해야 했다.

리팩토링을 하기 이전에는 확장 가능성을 고려하지 않고 그냥 구현을 했다. 쉽게 말해서 추상화에 의존하여 구현한 것이 아니라 구체적인 기능에 의존하여 개발하였다.

리팩토링 이전의 코드

import lombok.RequiredArgsConstructor;

import com.cakk.api.annotation.ApplicationEventListener;
import com.cakk.api.service.slack.SlackService;
import com.cakk.domain.mysql.event.shop.CertificationEvent;

@RequiredArgsConstructor
@ApplicationEventListener
public class CertificationEventListener {

    private final SlackService slackService;

    @Async
    @TransactionalEventListener(phase = TransactionPhase.AFTER_COMMIT)
    public void sendMessageToSlack(CertificationEvent certificationEvent) {
        slackService.sendSlackForCertification(certificationEvent);
    }
}

객체지향 프로그래밍에 대해 조금이라도 관심이 있다면 책임, 역할, 행동 이라는 키워드에 많이 노출되었을 것이다. CertificationEventListener에서 보면 slackService라는 구현체 자체에 의존하고 있다.

사이드 프로젝트에서는 개발자가 알고 있는 범위가 작고 변동에도 사실 코드를 그냥 고치면 되지만, 학습을 하면서 전략 패턴을 도입해보고 싶기도 했다. 이게 문제가 될 것인가? 라는 질문에 대해서는 다음과 같은 이유를 설명하고 싶다.

CertificationEventListener는 클라이언트라고 할 수 있다. 클라이언트는 SlackService에게 인증 요청을 보내줘라는 메시지를 보내고 있는데 만약, 구체적인 목적지가 변경된다면 어떻게 되는가? 예를 들어, 어드민 앱에 인증 요청을 보내야 한다던가 또는 이메일로 전송되어야할 수도 있다. 실제로, 다음 기획 논의에서 변경이 확정되었기도 하다. 코드 레벨에서의 변경이 생긴다. 정확히는 추상화된 인터페이스가 아닌 구현체에 의존하기 때문에 sendMessageToSlack 메서드의 네이밍이 변경될 뿐만 아니라, 책임에서의 구현도 변경되어야 한다. 여기서 책임이란? 메서드의 구체적인 내용이라고 정의하겠습니다. 또 변경되는 것이 있습니다. 의존하고 있는 import에서도 SlackService에 대한 의존이 제거되어야 하고, 클라이언트가 구체화를 알아야 한다는 점이 문제될 수 있다고 설명하고 싶습니다.

또다른 문제가 있습니다.

1. 목적지에 메시지를 전송하기 위한 메시지 형태를 만드는 것
2. 만들어진 메시지를 담아 외부 api를 호출하는 것

1번과 2번이 합쳐져서 slackService에서 sendMessageToSlack 메서드가 구현되었습니다. 저는 1번과 2번을 분리하고 외부 api가 무엇인지에 따라 유연하게 변경될 수 있게 Strategy로 활용하여 리팩토링하는 목표를 세웠습니다.

변경 전 코드

public void sendSlackForCertification(CertificationEvent certificationEvent) {
        if (!isEnable) {
            return;
        }

        SlackAttachment slackAttachment = new SlackAttachment();
        slackAttachment.setColor("good");
        slackAttachment.setFallback("OK");
        slackAttachment.setTitle("Request Certification");
        slackAttachment.setFields(List.of(
            new SlackField().setTitle("요청자 PK").setValue(String.valueOf(certificationEvent.userId())),
            new SlackField().setTitle("요청자 이메일").setValue(certificationEvent.userEmail()),
            new SlackField().setTitle("요청자 비상연락망").setValue(certificationEvent.emergencyContact()),
            new SlackField().setTitle("요청자 신분증 이미지").setValue(certificationEvent.idCardImageUrl()),
            new SlackField().setTitle("요청자 사업자등록증 이미지").setValue(certificationEvent.businessRegistrationImageUrl()),
            new SlackField().setTitle("요청 사항").setValue(certificationEvent.message()),
            new SlackField().setTitle("가게 이름").setValue(certificationEvent.shopName()),
            new SlackField().setTitle("가게 위치 위도").setValue(String.valueOf(certificationEvent.location().getY())),
            new SlackField().setTitle("가게 위치 경도").setValue(String.valueOf(certificationEvent.location().getX()))
        ));

        SlackMessage slackMessage = new SlackMessage();

        slackMessage.setAttachments(List.of(slackAttachment));
        slackMessage.setChannel("#cs_사장님인증");
        slackMessage.setText("%s 사장님 인증 요청".formatted(profile));

        slackApi.call(slackMessage);
    }

메시지 형태를 만드는 메서드와 호출하는 메서드를 분리

//슬랙으로 전송하기 위한 메시지 추출
public SlackMessage extract(CertificationMessage certificationMessage) {
        SlackAttachment slackAttachment = new SlackAttachment();
        slackAttachment.setColor("good");
        slackAttachment.setFallback("OK");
        slackAttachment.setTitle("Request Certification");

        slackAttachment.setFields(List.of(
            new SlackField().setTitle("요청자 PK").setValue(String.valueOf(certificationMessage.userId())),
            new SlackField().setTitle("요청자 이메일").setValue(certificationMessage.userEmail()),
            new SlackField().setTitle("요청자 비상연락망").setValue(certificationMessage.emergencyContact()),
            new SlackField().setTitle("요청자 신분증 이미지").setValue(certificationMessage.idCardImageUrl()),
            new SlackField().setTitle("요청자 사업자등록증 이미지").setValue(certificationMessage.businessRegistrationImageUrl()),
            new SlackField().setTitle("요청 사항").setValue(certificationMessage.message()),
            new SlackField().setTitle("가게 이름").setValue(certificationMessage.shopName()),
            new SlackField().setTitle("가게 위치 위도").setValue(String.valueOf(certificationMessage.latitude())),
            new SlackField().setTitle("가게 위치 경도").setValue(String.valueOf(certificationMessage.longitude()))
        ));

        SlackMessage slackMessage = new SlackMessage();
        slackMessage.setAttachments(List.of(slackAttachment));
        slackMessage.setChannel("#cs_사장님인증");
        slackMessage.setText("사장님 인증 요청");

        return slackMessage;
    }

//api 호출하여 슬랙 메시지를 전송
public void send(SlackMessage message) {
    if (!isEnable) {
        return;
    }

    slackApi.call(message);
}

메서드를 분리했지만, 여전히 남은 숙제

extract 메서드와 send 메서드의 구현이 변경되어야 한다면 SlackService가 아니라 새로운 Service를 만들고 해당 목적지를 위한 extract와 send를 또 구현하여 Class를 생성해야 합니다. Client가 또 새롭게 바뀐 구현체 Class를 알아야 할 의무가 있을까? 저의 생각은 알아야 할 의무가 없고, 인터페이스에 의존하도록 변경하는 게 좋은 코드라고 생각했습니다.

Java에서는 Strategy를 위해 Interface와 Abstract Method를 통해 콜백 패턴을 활용할 수 있습니다. 이렇게 되면, 해당 메서드를 람다로도 처리할 수 있고 구현체를 만들어서 Spring Container를 활용한 의존성 주입을 해줄 수 있습니다.

// 목적지의 형식에 맞게 메시지를 추출하는 Extractor
package com.cakk.external.extractor;

import com.cakk.external.vo.CertificationMessage;

public interface CertificationMessageExtractor<T> {
    T extract(CertificationMessage certificationMessage);
}

// 인증을 위한 ApiExecutor
package com.cakk.external.executor;

public interface CertificationApiExecutor<T> {
    void send(T message);
}

마지막으로, Template을 통한 메서드에서 위 인터페이스를 활용하여 로직을 수행하면 됩니다.

// 사장님 인증 요청을 위한 Template
package com.cakk.api.template;

import lombok.RequiredArgsConstructor;

import com.cakk.external.executor.CertificationApiExecutor;
import com.cakk.external.extractor.CertificationMessageExtractor;
import com.cakk.external.vo.CertificationMessage;

@RequiredArgsConstructor
public class CertificationTemplate {

    private final CertificationApiExecutor certificationApiExecutor;
    private final CertificationMessageExtractor certificationMessageExtractor;

    public void sendMessageForCertification(CertificationMessage certificationMessage) {
        this.sendMessageForCertification(certificationMessage, certificationMessageExtractor, certificationApiExecutor);
    }

    public <T> void sendMessageForCertification(
        CertificationMessage certificationMessage,
        CertificationMessageExtractor certificationMessageExtractor,
        CertificationApiExecutor certificationApiExecutor
    ) {
        T extractMessage = (T)certificationMessageExtractor.extract(certificationMessage);
        certificationApiExecutor.send(extractMessage);
    }
}

이렇게 추상화에 의존하게 된다면, 인터페이스인 CertificationMessageExtractor와 CertificationApiExecutor를 통해 메시지를 전달하기만 하면 됩니다.

OCP인 개방 폐쇄 원칙을 지킬 수도 있고 의존 방향에서도 추상화에 의존하고 있는 특징을 살펴볼 수 있습니다.

그렇다면, 기존의 CertificationEventListener에서도 의존 방향이 Template으로 변경되고 메시지를 보내기만 하면 됩니다. 여기서 말하는 메시지란? 템플릿에게 사장님 인증을 위한 메시지를 보내줘를 수행하게 됩니다.

CertificationEventListener에서 변경된 코드

import lombok.RequiredArgsConstructor;

import com.cakk.api.annotation.ApplicationEventListener;
import com.cakk.api.mapper.EventMapper;
import com.cakk.api.template.CertificationTemplate;
import com.cakk.domain.mysql.event.shop.CertificationEvent;
import com.cakk.external.vo.CertificationMessage;

@RequiredArgsConstructor
@ApplicationEventListener
public class CertificationEventListener {

    private final CertificationTemplate certificationTemplate;

    @Async
    @TransactionalEventListener(phase = TransactionPhase.AFTER_COMMIT)
    public void sendMessageToSlack(CertificationEvent certificationEvent) {
        CertificationMessage certificationMessage = EventMapper.supplyCertificationMessageBy(certificationEvent);
        certificationTemplate.sendMessageForCertification(certificationMessage);
    }
}

external-module에서 가지고 있는 CertificationMessage로 Mapper를 통해 변환한 후 Template를 통해 메시지를 전달하기만 하면 됩니다. 결과적으로, Template에게 의존하는 코드로 변경되었습니다.

결과, 기획이 변경되더라도 기존 코드는 수정되지 않는 설계

따라서 우리는 Template에서 의존하고 있는 인터페이스에 따라 새로운 구현체를 만들더라도 의존성 주입만 다른 객체로 변경해주면 되고 기존 코드는 수정되지 않게 됩니다. 이를 Configuration에서 관리할 수 있습니다.

package com.cakk.api.config;

import org.springframework.beans.factory.annotation.Value;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;

import net.gpedro.integrations.slack.SlackApi;

import com.cakk.api.template.CertificationTemplate;
import com.cakk.external.executor.CertificationApiExecutor;
import com.cakk.external.executor.CertificationSlackApiExecutor;
import com.cakk.external.extractor.CertificationMessageExtractor;
import com.cakk.external.extractor.CertificationSlackMessageExtractor;

@Configuration
public class CertificationTemplateConfig {

    private final SlackApi slackApi;
    private final boolean isEnable;

    public CertificationTemplateConfig(
        SlackApi slackApi,
        @Value("${slack.webhook.is-enable}")
        boolean isEnable) {
        this.slackApi = slackApi;
        this.isEnable = isEnable;
    }

    @Bean
    public CertificationTemplate certificationTemplate() {
        return new CertificationTemplate(certificationApiExecutor(), certificationMessageExtractor());
    }

    @Bean
    public CertificationApiExecutor certificationApiExecutor() {
        return new CertificationSlackApiExecutor(slackApi, isEnable);
    }

    @Bean
    CertificationMessageExtractor certificationMessageExtractor() {
        return new CertificationSlackMessageExtractor();
    }
}

예를 들어, 어드민 앱을 활용하여 사장님 인증 요청을 보낸다고 가정할 수 있습니다. 이때, 어드민 앱을 위한 CertificationMessageExtractor, CertificationApiExecutor를 구현하여 위 클래스에서 CertificationTemplate의 생성자에 주입만 변경해주면 대응할 수 있는 코드가 완성됩니다.

만약, 구현체로 구현하여 클래스를 만들고 싶지 않다면 아래의 두가지 메서드에서 오버로딩된 아래 메서드를 호출하여 람다로 기능을 구현할수도 있습니다.

public void sendMessageForCertification(CertificationMessage certificationMessage) {
        this.sendMessageForCertification(certificationMessage, certificationMessageExtractor, certificationApiExecutor);
    }

public <T> void sendMessageForCertification(
        CertificationMessage certificationMessage,
        CertificationMessageExtractor certificationMessageExtractor,
        CertificationApiExecutor certificationApiExecutor
    ) {
        T extractMessage = (T)certificationMessageExtractor.extract(certificationMessage);
        certificationApiExecutor.send(extractMessage);
    }

람다 예시

@Async
@TransactionalEventListener(phase = TransactionPhase.AFTER_COMMIT)
public void sendMessageToSlack(CertificationEvent certificationEvent) {
    CertificationMessage certificationMessage = EventMapper.supplyCertificationMessageBy(certificationEvent);
    certificationTemplate.sendMessageForCertification(certificationMessage, message -> {
            // 메시지 추출 로직 수행..
            return message;
        }, message -> {
            // 외부 서비스 호출 로직 수행...
    });
}

마무리

이것이 좋은 설계인가? 에 대해서는 논리적으로 설명할 수 있으나 이론을 학습하고 프로젝트에 도입해본 것은 처음이라 운영을 해보면서 추가적인 문제점이나 한계를 마주칠 수 있을 것 같습니다. 명확한 것은 인터페이스를 활용한 추상화와 템플릿 제공, 전략의 변경에 따라 구현체를 교체할 수 있으며 클라이언트(기능을 호출하는 주체)는 구체화에 의존하지 않고 코드의 수정에는 닫혀 있고 확장에는 열려있는 설계를 했다고 할 수 있을 것 같습니다.

자세한 코드를 보고 싶다면 Github을 방문해주세요!

"아는 만큼 보인다"라는 말이 지식을 쌓을수록 얻는 재미 중 하나인 것 같다.

쿼리 실행 계획 절차

MySQL 서버에서는 쿼리가 실행되는 과정을 크게 3가지로 나눌 수 있음

1. 사용자로부터 요청된 SQL 문장을 잘게 쪼개서 MySQL 서버가 이해할 수 있는 수준으로 분리(파스 트리)함
2. SQL의 파싱 정보를 확인하면서 어떤 테이블부터 읽고 어떤 인덱스를 이용해 테이블을 읽을지 선택함
3. 두 번째 단계에서 결정된 테이블의 읽기 순서나 선택된 인덱스를 이용해 스토리지 엔진으로부터 데이터를 가져옴

첫 번째 단계를 SQL 파싱이라고 하며, MySQL 서버의 "SQL 파서"라는 모듈로 처리 SQL문장이 잘못됐다면, 이 단계에서 걸러지며, 해당 단계에서 "SQL 파스 트리"가 만들어짐. MySQL은 SQL 문장 자체가 아니라 SQL 파스 트리를 이용해 쿼리를 실행함

두 번째 단계는 "최적화 및 실행 계획 수립" 단계이며, MySQL 서버의 "옵티마이저"에서 처리함. 또한 두 번째 단계가 완료되면 쿼리의 "실행 계획"이 만들어짐.

• 구체적으로는 불필요한 조건 제거 및 복잡한 연산의 단순화
• 여러 테이블의 조인이 있는 경우, 어떤 순서로 테이블을 읽을지 결정
• 각 테이블에 사용된 조건과 인덱스 통계 정보를 이용해 사용할 인덱스를 결정
• 가져온 레코드들을 임시 테이블에 넣고 다시 한번 가공해야 하는지 결정 합니다.

세 번째 단계는 수립된 실행 계획대로 스토리지 엔진에 레코드를 읽어오도록 요청하고, MySQL 엔진에서는 스토리지 엔진으로부터 받은 레코들을 조인하거나 정렬하는 작업을 수행. 첫 번째 단계와 두 번째 단계는 거의 MySQL 엔진에서 처리하고, 세 번째 단계는 MySQL 엔진과 스토리지 엔진이 동시에 참여하여 처리함.

옵티마이저 종류

옵티마이저는 데이터베이스 서버에서 두뇌와 같은 역할을 함.

• 비용 기반 최적화
• 규칙 기반 최적화

규칙 기반 최적화는 기본적으로 레코드 건수나 선택도 등을 고려하지 않고 옵티마이저에 내장된 우선순위에 따라 실행 계획을 수립하는 방식임 -> 이미 오래전부터 많은 DBMS에서 사용하지 않음

비용 기반 최적화는 쿼리를 처리하기 위한 여러 가지 가능한 방법을 만들고, 각 단위 작업의 비용 정보와 대상 테이블의 예측된 통계 정보를 이용해 실행 계획별 비용을 산출함.

풀 테이블 스캔과 풀 인덱스 스캔

풀 테이블 스캔이란?

인덱스를 사용하지 않고 테이블의 데이터를 처음부터 끝까지 읽어서 요청된 작업을 처리하는 작업을 의미함. MySQL 옵티마이저는 다음과 같은 조건이 일치할 때 주로 풀 테이블 스캔을 선택함

• 테이블의 레코드 건수가 너무 작아서 인덱스를 통해 읽는 것보다 풀 테이블 스캔을 하는 편이 더 빠른 경우(일반적으로 테이블이 페이지 1개로 구성된 경우)
• WHERE 절이나 ON 절에 인덱스를 이용할 수 있는 적절한 조건이 없는 경우
• 인덱스 레인지 스캔을 사용할 수 있는 쿼리라고 하더라도 옵티마이저가 판단한 조건 일치 레코드 건수가 너무 많은 경우

일반적으로, 테이블의 전체 크기는 인덱스보다 훨씬 크기 때문에 테이블을 처음부터 끝까지 읽는 작업은 상당히 많은 디스크 읽기가 필요함 대부분의 DBMS는 풀 테이블 스캔을 실행할 때 한꺼번에 여러 개의 블록이나 페이지를 읽어오는 기능을 내장하고 있음 하지만, MySQL에는 풀 테이블 스캔을 실행할 때 한꺼번에 몇개씩 페이지를 읽어올지 설정하는 시스템 변수는 없음

나도 단순하게 생각하고 있던 것은 디스크로부터 페이지를 하나씩 읽어오는 것이라고 생각했는데, 잘못된 생각이었다.

MySQL에서 InnoDB 스토리지 엔진은 특정 테이블의 연속된 페이지가 읽히면 백그라운드 스레드에 의해 리드 어헤드(Read Ahead) 작업이 자동으로 시작된다. 리드 어헤드란 어떤 영역의 데이터가 앞으로 필요해지리라라는 것을 예측해서 요청이 오기 전에 미리 디스크에서 읽어 InnoDB의 버퍼 풀에 가져다 두는 것을 의미함. 즉, 풀 테이블 스캔이 실행되면 처음 몇 개의 데이터 페이지는 포그라운드 스레드(Forground Thread, 클라이언트 스레드)가 페이지 읽기를 실행하지만 특정 시점부터는 읽기 작업을 백그라운드 스레드로 넘긴다.

ORDER BY 처리

레코드를 가져올 때, 정렬은 필수적으로 많이 사용된다. 정렬을 위해 사용되는 여러 메커니즘들이 있는데 정확히 이해하고 옵티마이저가 어떻게 수행하는지 아는 것 또한 중요하다고 할 수 있다.

정렬을 처리하는 방법에는 인덱스를 이용하는 방법과 Filesort라는 별도의 처리 방식이 있습니다.

• MySQL 서버에서 인덱스를 이용하지 않고 별도의 정렬 처리를 수행했는지는 실행 계획의 Extra 칼럼에 "Using Filesort" 메시지가 표시되는지 여부로 판단할 수 있음.

Sort Buffer

MySQL은 정렬을 수행하기 위해 별도의 메모리 공간을 할당받아서 사용하는데, 이 메모리 공간을 Sort Buffer(소트 버퍼)라고 함. 소트 버퍼는 정렬이 필요한 경우에만 할당됨 -> 인덱스를 활용한 정렬은 굳이 Sort Buffer가 필요 없다는 뜻. 왜냐하면, 이미 인덱스를 통해 정렬되어 있기 때문

따라서, 메모리의 Sort Buffer에서 정렬을 수행하고, 그 결과를 임시로 디스크에 기록해 둔다. 그리고 다음 레코드를 가져와서 다시 정렬해서 반복적으로 디스크에 임시 저장함. 이처럼 각 버퍼 크기만큼 정렬된 레코드를 다시 병합하면서 정렬을 수행해야 함. 이 병합 작업을 멀티 머지(Multi-Merge)라고 표현한다

다음 포스트는 정렬 처리 방법에서 조인에서 드라이빙 테이블만 정렬과 조인에서 조인 결과를 임시 테이블로 저장 후 정렬할 때, 일어나는 과정을 다루어보겠습니다.

Reference

• Real MySQL 8.0(백은빈, 이성욱 지음)

위치 기반의 서비스를 제공하는 애플리케이션에서 위도와 경도를 기반으로 주변 케이크 샵을 제공해야 하는 서비스를 구현해야 하는 상황이었습니다.

제가 생각한 방법은 2가지가 있습니다. 첫 번째, 조건에 맞는 케이크 샵들을 모두 영속성 컨텍스트로 불러와서 위도와 경도 값을 기반으로 반경 km 내에 있는 케이크 샵들을 필터링하는 로직 두 번째, 데이터가 저장된 디스크 즉, 데이터베이스에서 데이터들을 필터링하고 검색하여오는 로직

모두가 예상할 수 있지만, 데이터 크기가 커질수록 JPA를 활용하는 Spring Boot 애플리케이션 로직에서 필터링하는 작업은 매우 큰 부담입니다. 우리가 페이징하는 이유도 비슷한 이유라고 할 수 있을 것 같습니다.

이를 줄이기 위해 데이터베이스에서 제공하는 인덱스와 함수를 바탕으로 성능을 최적화시킬 수 있습니다.이에 적합한 방법이 MySQL에서 제공하는 위도와 경도를 기반으로 한 Data Type인 Geometry를 활용하는 것입니다.

Hibernate와 MySQL

Hibernate

우리가 사용하는 JPA는 ORM프레임워크를 단순하게 Java 진영에서 사용할 수 있도록 제공해주는 API일 뿐이지 프레임워크가 아닙니다. 구체적으로는 Hibernate라는 ORM 프레임워크를 통해 이용하는 것이고 더 나아가, JDBC를 통해 사용하는 쿼리들이 객체지향 Mapping이 되어 있는 즉, 추상화되어있는 것입니다. 이에 대해, 깊이 이야기하기에는 주제와 맞지 않기 때문에 넘어가겠습니다.

따라서, Hibernate Spatial은 geographic data를 핸들링하기 위해 개발되었음. 5.0 버전 이후로, Hibernate Spatial은 Hibernate ORM 프로젝트 일부가 되었고, 표준적인 방법에서 geographic data를 다룰 수 있게 해줍니다.

Spatial data type는 Java standard library의 일부도 아니고, JDBC 명세에도 없음.

Hibernate Spatial은 두 가지의 geometry models를 지원합니다. JTS(https://www.tsusiatsoftware.net/jts/main.html)와 geolatte-geom(https://github.com/GeoLatte/geolatte-geom)

Geolatte-geom(A geometry model for Java)은 데이터베이스 네이티브 타입을 위해 encoder/decoder을 구현하였습니다. hibernate-spatial type를 사용하기 위해서는 의존성을 추가해야 합니다.

Dependencies에 추가

implementation 'org.hibernate.orm:hibernate-spatial:6.4.4.Final'
implementation 'com.querydsl:querydsl-spatial'

MySQL

MySQL에서는 다음과 같은 Geometry 타입을 지원합니다. 또한, MySQL에서 지원하는 Spatial Index(공간 인덱스) R-Tree 인덱스 알고리즘을 이용해 2차원의 데이터를 인덱싱하고 검색할 수 있습니다 내부 메커니즘은 B-Tree와 흡사합니다 R-Tree 알고리즘에서는 MBR(Minimum Bounding Rectangle) 즉, 해당 도형을 감싸는 최소 크기의 사각형을 기반으로 동작합니다 고도화함에 따라 다른 TYPE를 선택할 수 있겠지만 쉽고 빠르게 적용하기 위해 POINT를 선택한 이유가 될 수 있습니다.

즉, POINT를 중심으로 최소 크기의 사각형이 생긴다고 바라볼 수 있습니다 예를 들어, 해당 POINT를 중심으로 5km 이내에 POINT를 검색한다고 할 때, 반지름 5km, 지름 10km의 원을 그리게 됩니다. 이후, 원을 기반으로 사각형을 그리면 최소 크기의 사각형을 만들 수 있습니다 결과적으로, 이 사각형 내에 있는 POINT를 탐색할 수 있습니다.

대표적인 함수들 https://dev.mysql.com/doc/refman/8.0/en/spatial-function-reference.html

주의사항

MySQL Documentation을 참고하자면, For comparisons to work properly, each column in a SPATIAL index must be SRID-restricted. That is, the column definition must include an explicit SRID attribute, and all column values must have the same SRID.

SRID 속성에 대해 Column Definition을 포함해야 한다고 정의되어 있습니다. 그래서 우리 팀은 Entity에서도 해당 Definition을 정의하고 있습니다.

@Getter
@AllArgsConstructor(access = AccessLevel.PRIVATE)
@NoArgsConstructor(access = AccessLevel.PROTECTED)
@Entity
@Table(name = "cake_shop")
public class CakeShop extends AuditEntity {
      @Id
      @GeneratedValue(strategy = GenerationType.IDENTITY)
      @Column(name = "shop_id", nullable = false)
      private Long id;

      @Column(name = "thumbnail_url", length = 200)
      private String thumbnailUrl;

      @Column(name = "shop_name", length = 30, nullable = false)
      private String shopName;

      @Column(name = "shop_address", length = 50)
      private String shopAddress;

      @Column(name = "shop_bio", length = 40)
      private String shopBio;

      @Column(name = "shop_description", length = 500)
      private String shopDescription;

      @Column(name = "location", nullable = false, columnDefinition = "POINT SRID 4326")
      private Point location;
    ...
 }

여기서 4326은 4326(WGS84)를 의미하며, 우리가 흔히 아는 위도 경도 좌표 시스템을 의미합니다. Naver, Kakao 등 Map API에서도 위도 경도를 제공할 때, 해당 표준을 따라서 제공하고 있습니다.

요구사항

사용자 위치를 중심으로 반경 5km내의 케이크 샵 가게들을 조회해야 하는 요구사항이 발생했을 때, 우리는 Hibernate에서 제공하는 dwithin(Returns true if the geometries are within the specified distance of one another)를 활용할 수 있습니다.

따라서 아주 쉽게 구현할 수 있다고 생각했지만 가장 큰 이슈는 MySQL 데이터베이스에 대해서는 지원하지 않는다는 점입니다. 여기서 자꾸 에러가 터져서 분석하느라 많은 시간을 소비했고, 문서를 읽으면서 알 수 있었습니다.

문서를 잘 읽고 개발하는 습관은 중요한 것 같습니다😅

따라서 MBR을 기반으로 Spatial Index를 활용할 수 있는 함수들은 MySQL 공식 문서에 의하면, ST_Contains(g1, g2)를 활용할 수 있겠습니다.

• ST_Contains(g1, g2): 첫 번째 파라미터는 탐색하고 싶은 범위, 두 번째 파라미터는 존재하는지 확인하고 싶은 Geometry Type
• ST_BUFFER(:point, 5000)은 첫번째 파라미터가 Point 변수. 즉, 사용자 위치를 통해 경도와 위도를 담고 있는 point를 중심으로 5000 meter 즉 반경 5KM의 사각형을 범위로 만드는 함수입니다

따라서, 서버에서는 ST_BUFFER 함수를 활용해 사용자 기반 위도와 경도 값을 받으면 Point변수를 만들 수 있습니다.

이를 기반으로 데이터베이스에 저장되어 있는 케이크 샵들을 탐색하는 쿼리를 아래에서 소개하겠습니다

JPQL을 활용한 방법

import java.util.List;

import org.locationtech.jts.geom.Point;
import org.springframework.data.jpa.repository.JpaRepository;
import org.springframework.data.jpa.repository.Query;

import com.cakk.domain.mysql.entity.shop.CakeShop;

public interface CakeShopJpaRepository extends JpaRepository<CakeShop, Long> {

    @Query(value = "select CS from CakeShop as CS where ST_CONTAINS(ST_BUFFER(:point, 5000), CS.location)")
    List<CakeShop> findByLocationBased(Point point);
}

JPQL을 활용하는 방법은 간단하지만, 우리 팀에서는 추가적으로 요구하는 조건들이 존재했습니다.

조건1. 페이지 크기를 입력 받으면 해당 크기만큼 페이징 해주기 조건2. 검색어가 존재하면, 해당 검색어를 통해 만족하는 케이크 샵 가져오기 조건3. 사용자가 위치 기반 반경 5km내 케이크 샵 가져오기

이런 조건들을 동적으로 만족시켜주기 위해서 많은 프로젝트에서 QueryDSL을 활용하고 있습니다. QueryDSL에서는 해당 ST_CONTAINS를 활용하기 위해서는 Expressions.booleanTemplate을 활용할 수 있습니다.

QueryDSL을 활용한 방법

public List<CakeShop> findByKeywordWithLocation(
        Long cakeShopId,
        String keyword,
        Point location,
        Integer pageSize
    ) {
        return queryFactory
            .selectFrom(cakeShop)
            .innerJoin(cakeShop.businessInformation).fetchJoin()
            .leftJoin(cakeShop.cakes).fetchJoin()
            .leftJoin(cakeShop.cakeShopOperations).fetchJoin()
            .where(
                includeDistance(location).and(containKeyword(keyword)), ltCakeShopId(cakeShopId)
            )
            .orderBy(cakeShopIdDesc())
            .limit(pageSize)
            .fetch();
    }

    private BooleanExpression includeDistance(Point location) {
        if (isNull(location)) {
            return null;
        }

        return Expressions.booleanTemplate("ST_Contains(ST_BUFFER({0}, 5000), {1})", location, cakeShop.location);
    }


    private BooleanBuilder containKeyword(String keyword) {
        BooleanBuilder builder = new BooleanBuilder();

        if (nonNull(keyword)) {
            builder.or(containsKeywordInShopBio(keyword));
            builder.or(containsKeywordInShopDesc(keyword));
        }

        return builder;
    }

    private BooleanExpression ltCakeShopId(Long cakeShopId) {
        if (isNull(cakeShopId)) {
            return null;
        }

        return cakeShop.id.lt(cakeShopId);
    }

다음 목표

1. 쿼리 실행 계획과 Spatial Index를 통해 성능 개선해보기
2. 서비스 운영과 함께 쿼리 로그 분석해보기

감사합니다.

자세한 코드를 보고 싶다면 Github을 방문해주세요!

Reference

• https://docs.jboss.org/hibernate/orm/5.2/userguide/html_single/Hibernate_User_Guide.html#spatial
• https://www.tsusiatsoftware.net/jts/main.html
• https://dev.mysql.com/doc/refman/8.4/en/spatial-index-optimization.html
• https://dev.mysql.com/doc/refman/8.0/en/spatial-relation-functions-mbr.html
• 그림 출처: Real MySQL8.0(백은빈 , 이성욱 저자(글))

문제 설명

선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다.

함수 R은 배열에 있는 수의 순서를 뒤집는 함수이고, D는 첫 번째 수를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다.

함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 수를 버리는 함수이다.

배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 최대 100이다.

각 테스트 케이스의 첫째 줄에는 수행할 함수 p가 주어진다. p의 길이는 1보다 크거나 같고, 100,000보다 작거나 같다.

다음 줄에는 배열에 들어있는 수의 개수 n이 주어진다. (0 ≤ n ≤ 100,000)

다음 줄에는 [x1,...,xn]과 같은 형태로 배열에 들어있는 정수가 주어진다. (1 ≤ xi ≤ 100)

전체 테스트 케이스에 주어지는 p의 길이의 합과 n의 합은 70만을 넘지 않는다.

시간제한 1초 안에 문제를 해결해야 한다 T가 최대 100이고, 1 <= p <= 100,000 배열의 요소도 최대 100,000

이런 문제를 접근할 때, 실제로 뒤집기를 하거나 O(N*N) 시간 복잡도로 문제를 해결하려고 접근하면 절대 안된다.

따라서, 어떻게 O(N)에 해결할 수 있을지를 고민하는게 핵심 포인트다.

결과적으로 배열의 요소 시작과 끝을 기준으로

1. IF 뒤집기라면 Then D를 만났을 때 끝의 요소는 - 1
2. IF 뒤집히지 않았다면 Then D를 만났을 때 시작 요소 + 1
3. 최종적으로 뒤집힌 상태인지 아닌지를 판별하고 뒤집히지 않은상태라면 시작 요소부터 끝 요소까지 읽기 뒤집혔다면 끝 요소부터 시작 요소까지 읽기

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

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));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());
        int n;
        int[] arr;
        String inputArr;
        for (int i = 0; i < T; i++) {
            String function = br.readLine(); // 1 <= function <= 100,000
            n = Integer.parseInt(br.readLine());
            if (n == 0) {
                inputArr = br.readLine();
                if (function.contains("D")) sb.append("error").append("\n");
                else sb.append("[]").append("\n");
                continue;
            }
            inputArr = br.readLine().replace("[", "").replace("]", "");
            arr = Arrays.stream(inputArr.split(",")).mapToInt(Integer::parseInt).toArray();

            sb.append(getResult(arr, function)).append("\n");
        }

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

    private static String getResult(int[] arr, String function) {
        int start = 0, end = arr.length - 1;
        boolean isFront = true;
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < function.length(); i++) {
            if(function.charAt(i) == 'R') isFront = !isFront;
            else {
                if (isFront) start++;
                else end--;
            }
        }
        if (start - 1 == end || end + 1 == start) {
            sb.append("[]");
            return sb.toString();
        }

        if (end < start) {
            return "error";
        }
        sb.append("[");

        if (isFront) {
            for (int i = start; i <= end; i++) {
                if (i == end) sb.append(arr[i]);
                else sb.append(arr[i]).append(",");
            }
        } else {
            for (int i = end; i >= start; i--) {
                if(i == start)  sb.append(arr[i]);
                else sb.append(arr[i]).append(",");
            }
        }

        sb.append("]");

        return sb.toString();
    }
}

NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복도로 빠져나온 학생들은 선생님의 감시에 들키지 않는 것이 목표이다.

각 선생님들은 자신의 위치에서 상, 하, 좌, 우 4가지 방향으로 감시를 진행한다. 단, 복도에 장애물이 위치한 경우, 선생님은 장애물 뒤편에 숨어 있는 학생들은 볼 수 없다. 또한 선생님은 상, 하, 좌, 우 4가지 방향에 대하여, 아무리 멀리 있더라도 장애물로 막히기 전까지의 학생들은 모두 볼 수 있다고 가정하자.

다음과 같이 3x3 크기의 복도의 정보가 주어진 상황을 확인해보자. 본 문제에서 위치 값을 나타낼 때는 (행,열)의 형태로 표현한다. 선생님이 존재하는 칸은 T, 학생이 존재하는 칸은 S, 장애물이 존재하는 칸은 O로 표시하였다. 아래 그림과 같이 (3,1)의 위치에는 선생님이 존재하며 (1,1), (2,1), (3,3)의 위치에는 학생이 존재한다. 그리고 (1,2), (2,2), (3,2)의 위치에는 장애물이 존재한다.

이 때 (3,3)의 위치에 존재하는 학생은 장애물 뒤편에 숨어 있기 때문에 감시를 피할 수 있다. 하지만 (1,1)과 (2,1)의 위치에 존재하는 학생은 선생님에게 들키게 된다.

학생들은 복도의 빈 칸 중에서 장애물을 설치할 위치를 골라, 정확히 3개의 장애물을 설치해야 한다. 결과적으로 3개의 장애물을 설치하여 모든 학생들을 감시로부터 피하도록 할 수 있는지 계산하고자 한다. NxN 크기의 복도에서 학생 및 선생님의 위치 정보가 주어졌을 때, 장애물을 정확히 3개 설치하여 모든 학생들이 선생님들의 감시를 피하도록 할 수 있는지 출력하는 프로그램을 작성하시오.

이 문제는 전형적인 Combination 문제라고 생각한다. 그 이유에 있어서 3<=N<=6, N*N 정사각형 배열에 3개의 장애물을 놓는 경우의 수를 확인하면서 탐색하는 완전 탐색의 문제 유형이기 때문이다. 36C3 자체가 2초 이내에 완료할 수 있는 시간 복잡도이다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    private static char[][] map;
    private static boolean[] visited;
    private static int[] answer;
    private static int N;
    private static List<int[]> teachers = new ArrayList<>();
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        map = new char[N][N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = st.nextToken().charAt(0);
                if (map[i][j] == 'T') {
                    teachers.add(new int[]{i, j});
                }
            }
        }

        visited = new boolean[N * N];
        answer = new int[3];

        if(combinations(0,0)) {
            System.out.println("YES");
        } else System.out.println("NO");
    }

    private static boolean combinations(int start, int cnt) {
        if (cnt == 3) {
            if (checkPossible()) {
                layObstacle();
                if(canVoid()) {
                    return true;
                } else getRidOfObstacle();
            }
            return false;
        }

        for (int i = start; i < N * N; i++) {
            if(visited[i]) continue;
            visited[i] = true;
            answer[cnt] = i;
            if(combinations(start + 1, cnt + 1)) return true;
            visited[i] = false;
        }

        return false;
    }

    private static boolean checkPossible() {
        for (int i = 0; i < 3; i++) {
            int num = answer[i];
            int row = num / N;
            int column = num % N;
            if(map[row][column] != 'X') return false;
        }
        return true;
    }

    private static boolean canVoid() {
        for (int[] teacher : teachers) {
            if(moveUp(new int[]{teacher[0], teacher[1]})) return false;
            if(moveDown(new int[]{teacher[0], teacher[1]})) return false;
            if(moveLeft(new int[]{teacher[0], teacher[1]})) return false;
            if(moveRight(new int[]{teacher[0], teacher[1]})) return false;
        }
        return true;
    }

    private static void layObstacle() {
        for (int i = 0; i < 3; i++) {
            int num = answer[i];
            int row = num / N;
            int column = num % N;
            map[row][column] = 'O';
        }
    }

    private static void getRidOfObstacle() {
        for (int i = 0; i < 3; i++) {
            int num = answer[i];
            int row = num / N;
            int column = num % N;
            map[row][column] = 'X';
        }
    }

    private static boolean moveUp(int[] teacher) {
        teacher[0] = teacher[0] - 1;
        int nx = teacher[0], ny = teacher[1];
        if(nx < 0) return false;
        else if(map[nx][ny] == 'O') return false;
        else if(map[nx][ny] == 'X') return moveUp(teacher);
        else if(map[nx][ny] == 'T') return moveUp(teacher);
        return true;
    }
    private static boolean moveDown(int[] teacher) {
        teacher[0] = teacher[0] + 1;
        int nx = teacher[0], ny = teacher[1];
        if(nx >= N) return false;
        else if(map[nx][ny] == 'O') return false;
        else if(map[nx][ny] == 'X') return moveDown(teacher);
        else if(map[nx][ny] == 'T') return moveDown(teacher);
        return true;
    }
    private static boolean moveLeft(int[] teacher) {
        teacher[1] = teacher[1] - 1;
        int nx = teacher[0], ny = teacher[1];
        if(ny < 0) return false;
        else if(map[nx][ny] == 'O') return false;
        else if(map[nx][ny] == 'X') return moveLeft(teacher);
        else if(map[nx][ny] == 'T') return moveLeft(teacher);
        return true;
    }
    private static boolean moveRight(int[] teacher) {
        teacher[1] = teacher[1] + 1;
        int nx = teacher[0], ny = teacher[1];
        if(ny >= N) return false;
        else if(map[nx][ny] == 'O') return false;
        else if(map[nx][ny] == 'X') return moveRight(teacher);
        else if(map[nx][ny] == 'T') return moveRight(teacher);
        return true;
    }
}

• 사전순이라는 의미는 배열의 원소를 기준으로 내림차순으로 정리하면 가장 큰 값이 되기 때문에 사전순으로 뒷선다고 표현할 수 있다

잘못된 방법은 배열의 시작부터 차례대로 S번 이내로 해당 인덱스의 값이 다음 인덱스의 값보다 작으면 바꿔주려고 하면 틀리게 된다

올바른 방법은 S번 이내의 원소 중, 현재 인덱스의 값보다 큰 값중, 가장 큰 값과 교환을 해야 한다. 그 이후, S값을 움직인 거리만큼 감소시켜주면 된다.

그 이유는 앞자리의 값이 가장 클수록 사전순으로 가장 뒷서기 때문이다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Main {
    static class Status implements Comparable<Status> {
        int value;
        int index;

        public Status(int value, int index) {
            this.value = value;
            this.index = index;
        }

        @Override
        public int compareTo(Status o) {
            return Integer.compare(this.value, o.value);
        }
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine()); // 크키가 N인 배열 A
        int[] arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray(); // 배열에 있는 모든 수는 서로 다름
        int S = Integer.parseInt(br.readLine()); // S
        StringBuilder sb = new StringBuilder();
        PriorityQueue<Status> pq;


        for (int i = 0; i < N; i++) {
            pq = new PriorityQueue<>(Comparator.reverseOrder());
            int cnt = 0;
            for (int j = i + 1; j < N; j++) {
                if(cnt >= S) break;

                if (arr[j] > arr[i]) {
                    pq.add(new Status(arr[j], j));
                }
                cnt++;
            }

            if (!pq.isEmpty()) {
                Status status = pq.poll();
                changeValue(arr, status, i);
                S -= (status.index - i);
            }
        }

        for (int i = 0; i < N; i++) {
            sb.append(arr[i]).append(" ");
        }
        System.out.println(sb);
    }

    private static void changeValue(int[] arr, Status status, int index) {
        for (int i = status.index; i > index; i--) {
            int value = arr[i];
            arr[i] = arr[i - 1];
            arr[i - 1] = value;
        }
    }
}

개발자로서 MySQL을 사용한다면

InnoDB Storage에 대해서 이해를 하고 → 동시성 처리를 위해 인덱스 잠금 방식에 대해서 이해하고 있는 것이 기본일 필요가 있다.

먼저 Disk 읽기 방식

하드 디스크 드라이브(HDD)와 솔리드 스테이트 드라이브(SSD)

• 기계식 하드 디스크 드라이브를 대체하기 위해 전자식 저장 매체인 SSD가 많이 출시
  • 기존 하드 디스크 드라이브에서 데이터 저장용 플래터를 제거하고 그 대신 플래시 메모리를 장착하고 있음 디스크 원판을 회전시킬 필요가 없으므로 아주 빨리 데이터를 읽고 쓸 수 있음

결론이 무엇인가?

INDEX 그러면 무조건 사용하면 좋은가?

B - Tree 인덱스

B-Tree 인덱스는 대표적인 인덱스 알고리즘 중 하나입니다. 이진 트리(Binary Tree)와 유사하지만, 트리의 균형을 맞추기 위한 다양한 구현 방법이 존재합니다. 이 구현 방법들로 인해 B-Tree 인덱스는 대부분의 DBMS에서 사용되고 있습니다. B-Tree 인덱스는 각 노드가 여러 개의 키 값을 가지고 있으며, 이 키 값으로 정렬된 데이터에 대한 탐색을 가능하게 합니다. 이진 트리와 달리, B-Tree 인덱스는 매우 큰 데이터셋에서도 효율적인 탐색을 보장합니다.

• B - Tree 인덱스 키 추가
  • 테이블의 스토리지 엔진에 따라 새로운 키 값이 즉시 인덱스에 저장될 수도 있고 그렇지 않을 수도 있다. B - Tree에 저장될 때는 저장될 키 값을 이용해 B- Tree상의 적절한 위치를 검색
  • 저장될 위치가 결정되면 레코드의 키 값과 대상 레코드의 주소 정보를 B - Tree 리프 노드에 저장
  • 리프 노드가 꽉 차서 더는 저장할 수 없을 때는 리프 노드가 분리돼야 하는데, 이는 상위 브랜치 노드까지 처리의 범위가 넓어짐
  • 비용이 높음
• B - Tree 인덱스 삭제
  • 해당 키 값이 저장된 B - Tree의 리프 노드를 찾아서 그냥 삭제 마크만 하면 작업이 완료
• B - Tree 인덱스 키 변경
  • 단순히 인덱스 상의 키 값만 변경하는 것은 불가능
  • 먼저 키 값을 삭제한 후, 다시 새로운 키 값을 추가하는 형태로 처리
• B - Tree 인덱스 검색
  • INSERT, UPDATE, DELETE 작업을 할 떄 인덱스 관리에 추가 비용을 감당하면서 인덱스를 구축하는 이유는 빠른 검색을 위해서다. 루트 노드부터 최종 리프 노드까지 이동하면서 비교 작업을 수행 → 이 과정을 “트리 검색”이라고 함
  • SELECT 뿐만 아니라 UPDATE, DELETE를 처리하는데도 먼저 검색이 필요할 경우가 있음

MBR

전문 검색 인덱스

일반적인 용도의 B - Tree 인덱스를 사용할 수 없음

문서 전체에 대한 분석과 검색을 위한 인덱싱 알고리즘을 전문 검색(Full Text Search) 인덱스

사용자가 검색하게 될 키워드를 분석해 내고, 빠른 검색용으로 사용할 수 있게 키워드로 인덱스를 구축

키워드를 인덱싱하는 기법에 따라 어근 분석과 n - gram 분석으로 분류

어근 분석

• 불용어 처리 (가치가 없는 내용들은 필터링해서 제거하는 작업)
• 어근 분석 ( 오픈 소스를 활용한 형태소 분석 -> 시간과 비용)

n - gram

• 단순히 키워드 검색해 내기 위한 인덱싱 알고리즘
• 보통 2 - gram, 생성된 토큰들에 대해 불용어 처리 + 사용자 정의도 가능

SELECT * FROM 테이블 WHERE doc_body LIKE '%애플%';

SELECT * FROM 테이블 WHERE MATCH(doc_body) AGAINST('애플' IN BOOLEAN MODE);

가상 칼럼을 이용한 인덱스와 함수를 이용한 인덱스

• 가상 칼럼을 추가하여 검색에 대한 효과 : virtual
• 함수를 이용한 인덱스를 통해 테이블의 구조 변경 없이 함수를 직접 사용하는 인덱스를 생성할 수 있음
  • 주의 사항 : 함수 생성시 명시된 표현식과 쿼리의 WHERE 조건절에 사용된 표현식이 일치해야함

Multi - Value Index

JSON의 배열 타입의 필드에 저장된 원소들에 대한 인덱스 요건들이 발생

EX) 몽고 DB -> JSON 형태로 데이터를 보여주고 저장, 검색기능을 사용할때도 JSON 문법에 맞게 출력해줌

MySQL -> JSON 타입의 칼럼만 지원했지만 8.0넘어오면서 JSON 관리 기능이 MongoDB에 비해서도 부족함이 없는 상태

• MEMBER OF()
• JSON_CONTAINS()
• JSON_OVERLAPS()

트랜잭션은 작업의 완전성을 보장해 주는 것이다. 즉 논리적인 작업 셋을 모두 완벽하게 처리하거나, 처리하지 못할 경우에는 원 상태로 복구해서 작업의 일부만 적용되는(Partial Update)이 발생하지 않게 만들어주는 기능

Lock과 트랜잭션은 서로 비슷한 개념 같지만 잠금은 동시성을 제어하기 위한 기능이고 트랜잭셔은 데이터의 정합성을 보장하기 위한 기능

Keyword Partial Update → 정합성을 맞추는 데 상당히 어려운 문제

• MyISAM테이블과 InnoDB와의 차이

트랜잭션은?

• 트랜잭션 또한 DBMS의 커넥션과 동일하게 꼭 필요한 최소의 코드에만 적용하는 것이 좋음
• 즉, 트랜잭션의 범위를 최소화

트랜잭션 처리에 좋지 않은 영향을 미치는 부분들

• 커넥션의 시간이 길어지는 경우
• 메일 전송이나 FTP 파일 전송 작업 또는 네트워크를 통해 원격 서버와 통신하는 등과 같은 작업은 DBMS의 트랜잭션 내에서 제거하는 것이 좋음
• 중요한 것은 프로그램의 코드가 데이터베이스 커넥션을 가지고 있는 범위와 트랜잭션이 활성화돼 있는 프로그램의 범위를 최소화해야 한다는 것이다.
• 특히 네트워크 작업이 있는 경우 트랜잭션에서 배제해야 함

MySQL 엔진의 잠금

• mysql engine 레벨과 storage engine 레벨로 구분할 수 있음
  • MySQL 엔진 레벨의 잠금은 모든 스토리지 엔진에 영향을 미치지만, 스토리지 엔진 레벨의 잠금은 스토리지 엔진 간 상호 영향을 미치지는 않음
  • MySQL 엔진에서는 테이블 데이터 동기화를 위한 테이블 Lock 이외에도 테이블의 구조를 잠그는 메타 데이터 락 그리고 사용자의 필요에 맞게 사용할 수 있는 Named Lock이라는 잠금 기능도 제공
  • Table Lock은 DDL(Create, Alter, drop 등) 구문과 함께 사용 DDL Lock이라고도 함

GLOBAL LOCK

• FLUSH TABLES WITH READ LOCK 명령으로 획득할 수 있으며 MySQL에서 제공하는 잠금 가운데 가장 범위가 크다.
• 서버 전체에 영향, 작업 대상 테이블이나 데이터베이스가 다르더라도 동일하게 영향을 미침

MySQL 8.0으로 넘어오면서

• GLOBAL LOCK이 장시간 실행되는 쿼리와 함께 사용된다면 최악의 케이스로 아주 오랫동안 다른 쿼리들이 실행되지 못한다.
• 서버가 업그레이드 되면서 InnoDB 사용이 일반화 → 조금 더 가벼운 글로벌 락의 필요성이 생김
• Xtrabackup이나 Enterprise Backup과 같은 백업툴 들의 안정적인 실행을 위한 백업 락이 도입

Table Lock

InnoDB 테이블의 경우 잠금

Named Lock

사용자의 필요에 맞게 사용할 수 있는 Lock, GET_LOCK() 함수를 이용해 임의의 문자열에 대해 잠금을 설정할 수 있다. 이 잠금의 특징은 대상이 테이블이나 레코드 또는 AUTO_INCREMENT와 같은 데이터베이스 객체가 아니라는 것이다.

사용자가 지정한 문자열에 대해 획득하고 반납하는 잠금인데 자주 사용하지 않는다.

InnoDB 스토리지 엔진 잠금

Record Lock

레플리카 서버: 백업을 실행하는 서버

• InnoDB의 갭 락이나 넥스트키 락은 바이너리 로그에 기록되는 쿼리가 레플리카 서버에서 실행될 때 소스 서버에서 만들어낸 결과와 동일한 결과를 만들어내도록 보장하는 것이 주 목적

하지만 의외로 넥스트 키 락과 갭 락으로 인해 데드락이 발생하거나 다른 트랜잭션을 기다리게 만드는 일이 자주 발생함 따라서, ROW 형태로 바꿔서 넥스트 키 락이나 갭 락을 줄이는 것이 좋다.

AUTO_INCREMENT 락

하지만 이 내용은 MySQL 5.0 이하 버전에서 사용하던 방식

• innodb_autoinc_lock_mode = 0

  • 5.0과 동일한 잠금 방식으로 모든 INSERT 문장은 자동 증가 락을 사용한다.

• innodb_autoinc_lock_mode =1

  • 단순히 한 건 또는 여러 건의 레코드를 INSERT하는 SQL 중에서 MySQL 서버가 INSERT되는 레코드의 건수를 정확히 예측할 수 있을 때는 훨씬 가볍고 빠른 래치(Mutex)를 이용해 처리 → 개선된 래치는 자동 증가 락과 달리 아주 짧은 시간 동안만 잠금을 걸고 필요한 자동 증가 값을 가져오면 즉시 잠금이 해제된다

• innodb_autoinc_lock_mode = 2

  • mode가 2로 설정되면 innoDB 스토리지 엔진은 절대 자동 증가 락을 걸지 않고 경량화된 래치를 사용. 하지만 INSERT 문장으로 INSERT되는 레코드라고 하더라도 연속된 자동 증가 값을 보장하지는 않는다. 그래서 이 설정 모드를 인터리빙 모드라고도 한다.
  • 이 설정 모드에서는 INSERT … SELECT와 같은 대량 INSERT 문장이 실행되는 중에도 다른 커넥션에서 INSERT를 수행할 수 있으므로 동시 처리 성능이 높아짐
  • 하지만 이 설정에서 작동하는 자동 증가 기능은 유니크한 값이 생성된다는 것만 보장

MySQL 8.0부터 바이너리 로그 포맷이 STATEMENT가 아니라 ROW 포맷이 기본 값이 됐기 때문에 innodb_autoinc_lock_mode의 기본 값이 2로 바뀌었다.

인덱스와 잠금

InnoDB에서의 레코드 잠금은 인덱스를 활용한다고 언급했기 때문에 상당히 중요하다.

즉, 변경해야 하는 쿼리 수행을 위해

1. 레코드를 찾아야함
   1. 레코드를 찾기 위해서 검색한 인덱스의 레코드를 모두 락을 걸어야 함.

EXAMPLE

KEY ix_fisrtname (first_name) 멤버로 담긴 ix_fisrtname이라는 인덱스가 준비돼 있다.

SELECT COUNT(*) FROM employees where first_name='Georgi';

253개의 쿼리 결과

SELECT COUNT(*) FROM employees where first_name='Georgi' AND last_name='Klassen';
1개의 쿼리 결과

//UPDATE -> employees 테이블에서 first_name='Georgi' 이고 last_name='Klassen'인 사원의
입사 일자를 오늘로 변경하는 쿼리를 실행
UPDATE employees SET hire_date=NOW() WHERE first_name='Georgi' AND last_name='Klassen';

Update가 실행되었다면?

1건의 레코드가 업데이트될 것이다.

하지만 서버 성능에 대해서 생각해보고 몇 개의 레코드에 락을 걸어야 할지를 생각해보자

이 업데이트 조건에서 인덱스를 이용할 수 있는 조건은 first_name=’Georgi’이며, last_name 칼럼은 인덱스가 없기 때문에 first_name=’Georgi’인 253건의 레코드가 모두 잠긴다.

이러한 부분을 잘 모르고 개발한다면?

MySQL 서버를 제대로 이용하지 못할 것이다. 이 예제에서는 몇 건 안되는 레코드만 잠그지만 UPDATE 문장을 위해 적절히 인덱스가 준비돼 있지 않다면 각 클라이언트 간의 동시성이 상당히 떨어져서 UPDATE 작업을 하는 중에는 다른 클라이언트는 그 테이블을 업데이트하지 못하고 기다려야 하는 상황이 발생

즉 → 성능이 떨어지는 현상, 클라이언트에게 직결

테이블에 인덱스가 하나도 없다면?

만약 어떤 행에 있는 램프가 모두 켜져있을 때, 그 행이 켜져있다고 말한다. 지민이는 스위치를 K번 누를 것이다. 서로다른 스위치 K개를 누르지 않아도 된다. 지민이는 스위치를 K번 눌러서 켜져있는 행을 최대로 하려고 한다.

지민이의 탁자에 있는 램프의 상태와 K가 주어졌을 때, 스위치를 K번 누른 후에 켜져있는 행의 최댓값을 구하는 프로그램을 작성하시오.

이 문제를 접근할때, 먼저 시간복잡도를 생각해봤다.

N, M은 1 <= N, M <= 50 이다. 따라서 스위치가 켜지고 꺼지는 것에 대한 경우의 수는 2^50 이다.

그렇다면 브루트포스를 통해 알고리즘을 구현하면 시간초과가 난다.

따라서, 어떻게 시간 안에 문제를 풀어낼 수 있을까? 했지만 도저히 떠올릴 수 없어서 풀이를 참고했다.

1. 초기에 상태가 다른 행은 조작 횟수와 상관없이 같아질 수 없다.
2. 따라서, 하나의 행에서 0의 갯수를 확인하고 초기 상태가 같은 행의 갯수를 통해 문제를 풀 수 있다.

단, 조건이 있다. 하나의 행에서 0의 갯수가 조직 횟수인 K보다 작거나 같아야 하고 0의 갯수를 2로 나눈 나머지와 K를 2로 나눈 나머지가 같아야 한다.

그 이유는 스위치를 짝수번 눌러야 결국 처음이랑 똑같아지기 때문이다.

다양한 접근을 접해봤어야 했는데 아쉬웠다

package baekjoon;

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

public class BOJ_1034 {
    private static int N, M, K;
    private static int[][] arr;
    private static String[] temp;
    private static boolean[] check;
    private static int answer = 0;

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

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new int[N][M];
        temp = new String[N];
        check = new boolean[N];

        for (int i = 0; i < N; i++) {
            temp[i] = br.readLine();
            for (int j = 0; j < M; j++) {
                arr[i][j] = Character.getNumericValue(temp[i].charAt(j));
            }
        }

        K = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {
            int cnt = 0;

            for (int j = 0; j < M; j++) {
                if(arr[i][j] == 0) cnt++;
            }

            if ((cnt % 2 == K % 2) && cnt <= K) {
                check[i] = true;
            }
        }

        for (int i = 0; i < N; i++) {
            if (check[i]) {
                int cnt = 0;

                for (int j = 0; j < N; j++) {
                    if (temp[i].equals(temp[j])) {
                        cnt++;
                    }
                }

                if (cnt > answer) {
                    answer = cnt;
                }
            }
        }

        System.out.println(answer);
    }
}

점화식을 찾는건 어렵지 않은데

문제 조건이 1 <= N <= 500 이기 때문에 N = 1일때, 답을 출력하는 것을 주의해야 한다.

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

public class Main {
    private static int[][] arr;
    private static int[][] dp;
    private static int answer;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        arr = new int[N + 1][];
        dp = new int[N + 1][N + 1];

        for (int i = 1; i <= N; i++) {
            arr[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }

        answer = dp[1][0] = arr[1][0];

        for (int i = 2; i <= N; i++) {
            for (int j = 0; j < i; j++) {
                if (j == 0) {
                    dp[i][j] = dp[i - 1][j] + arr[i][j];
                } else if (j == i - 1) {
                    dp[i][j] = dp[i - 1][j - 1] + arr[i][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]) + arr[i][j];
                }
                answer = Math.max(answer, dp[i][j]);
            }
        }
        System.out.println(answer);
    }
}

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.

INPUT

트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다.

먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 입력으로 주어진다. 주어지는 거리는 모두 10,000 이하의 자연수이다.

OUTPUT

첫째 줄에 트리의 지름을 출력한다.

제가 생각한 문제의 의도는 결과적으로 트리의 지름, 즉 트리의 특성에 대해 정확하게 이해하고 있는지가 핵심이라고 생각합니다.

트리의 특징

1. 싸이클이 존재하지 않음
2. 노드가 N개인 트리는 항상 N - 1 개의 간선을 가짐
3. 임의의 두 노드 간의 경로는 유일하다. 즉 두 개의 노드 사이에 반드시 1개의 경로만을 가짐

그렇다면 지름을 구하기 위해서,

어떤 임의의 정점에서 출발하여 가장 거리가 먼 정점까지의 거리를 구할때, 경로가 겹치는 부분이 필연적으로 존재함

이 말을 이해해야 합니다. 왜냐하면, 트리에서는 싸이클이 존재하지 않기 때문에 겹치는 경로가 존재할 수 밖에 없습니다.

1. 즉, 임의의 정점에서 거리가 가장 먼 임의의 정점까지의 거리를 구하기
2. 해당 거리가 가장 먼 정점에서 가장 거리가 먼 임의의 정점까지 거리를 구하기

이 둘의 거리를 비교하여 가장 먼 거리가 트리에서 지름이 됩니다.

간선의 개수만큼의 시간복잡도로 끝낼 수 있습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Main {
    static class Node {
        int index;
        Map<Integer, Integer> cost = new HashMap<>();
        List<Node> adjacent = new ArrayList<>();

        public Node(int index) {
            this.index = index;
        }
    }

    private static List<Node> graph = new ArrayList<>();
    private static int tempIndex;
    private static long answer = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] input;
        int V = Integer.parseInt(br.readLine());

        for (int i = 0; i <= V; i++) {
            graph.add(new Node(i));
        }


        for (int i = 0; i < V; i++) {
            input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

            int x = input[0];

            for (int j = 1; j < input.length - 1; j = j + 2) {
                int y = input[j];
                Node nodeA = graph.get(x);
                Node nodeB = graph.get(y);

                if (nodeA.cost.getOrDefault(nodeB.index, 0) == 0 ||
                        nodeB.cost.getOrDefault(nodeA.index, 0) == 0) {
                    nodeA.cost.put(nodeB.index, input[j + 1]);
                    nodeB.cost.put(nodeA.index, input[j + 1]);

                    nodeA.adjacent.add(nodeB);
                    nodeB.adjacent.add(nodeA);
                }
            }
        }

        System.out.println(getMaxDistance());
    }

    private static long getMaxDistance() {
        long[] costs = new long[graph.size()];

        boolean[] visited = new boolean[graph.size()];

        dfs(1, visited, 0);

        visited = new boolean[graph.size()];

        dfs(tempIndex, visited, 0);

        return answer;
    }

    private static void dfs(int index, boolean[] visited, long cost) {
        visited[index] = true;

        if (cost > answer) {
            answer = cost;
            tempIndex = index;
        }

        Node node = graph.get(index);

        for (Node next : node.adjacent) {
            if(visited[next.index]) continue;
            dfs(next.index, visited, cost + node.cost.get(next.index));
        }
    }
}

N개의 전구들의 현재 상태와 우리가 만들고자 하는 상태가 주어졌을 때, 그 상태를 만들기 위해 스위치를 최소 몇 번 누르면 되는지 알아내는 프로그램을 작성하시오.

제한 사항 N(2 <= N <= 100,000) 주어진다.

이 문제에 대해 Brute Force를 진행한다고 하면 시간 복잡도를 고려했을 때, 시간 초과가 난다.

그렇다면 어떻게 문제를 해결해야할지, 딱히 알고리즘이 생각나지 않는다면 Greedy하게 접근해봐야 한다.

현재 상황에서의 최적의 해 -> 부분 최적 해를 만들어 나가는 것이 핵심이다.

바로 직전 인덱스가 가리키는 배열의 요소가 같지 않다면 현재 인덱스의 전구를 바꿔주면 같은 것으로 바꿔줄 수 있는 것이다. 반대로, 바로 직전 인덱스가 가리키는 배열의 요소가 같다면 현재 인덱스의 전구를 바꿔 줄 필요가 없기 때문에 현재 인덱스까지 만들고자 하는 스위치의 부분 최적해를 만족할 수 있는 것이다.

단 주의할 점으로 첫번째 전구의 상태를 바꾼 것과 바꾸지 않은 것을 고려하여 코드를 작성하면 된다

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

public class Main {
    private static int N;
    private static int[] original;
    private static int[] target;
    private static int answer = Integer.MAX_VALUE;

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

        // 2 <= N <= 100,000
        N = Integer.parseInt(br.readLine());

        original = Arrays.stream(br.readLine().split("")).mapToInt(Integer::parseInt).toArray();
        target = Arrays.stream(br.readLine().split("")).mapToInt(Integer::parseInt).toArray();

        answer = Math.min(answer, change(original, 0));

        original[0] = 1 - original[0];
        original[1] = 1 - original[1];

        answer = Math.min(answer, change(original, 1));

        if(answer == Integer.MAX_VALUE) System.out.println(-1);
        else System.out.println(answer);
    }

    private static int change(int[] A, int count) {
        A = A.clone();

        for (int i = 1; i < N; i++) {
            if(target[i - 1] == A[i - 1]) continue;

            for (int j = i - 1; j < i + 2; j++) {
                if (j < N) {
                    A[j] = 1 - A[j];
                }
            }
            count++;
        }

        for (int i = 0; i < N; i++) {
            if(A[i] != target[i]) return Integer.MAX_VALUE;
        }
        return count;
    }
}

문제의 요구 사항은 중간인 구슬이 절대 될 수 없는 구슬의 개수를 구하는 것이다. 이 말은 즉, 각 구슬이 무거운 것 또는 가벼운 것이 중간인 구슬의 순서 번호보다 많거나 같으면 절대 중간이 될 수 없다는 말이다

따라서

1. 그래프를 만들 줄 알아야함
2. 탐색하여 개수를 세면 됨

나는 방문기록을 체크하지 않아서 처음에 시간초과가 났다! 이런 실수하면 안된다...

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {

    static class Node {
        Set<Node> prev = new HashSet<>();
        int index;
        Set<Node> next = new HashSet<>();

        public Node(int index) {
            this.index = index;
        }
    }
    private static int N, M, middle;
    private static List<Node> graph = new ArrayList<>();
    private static boolean[] nextVisited;
    private static boolean[] prevVisited;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int answer = 0;
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        for (int i = 0; i <= N; i++) {
            graph.add(new Node(i));
        }

        middle = (N + 1) / 2; // 중간이 되는 구슬 번호

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int heavy = Integer.parseInt(st.nextToken()), light = Integer.parseInt(st.nextToken());

            Node heavyNode = graph.get(heavy);
            Node lightNode = graph.get(light);

            lightNode.next.add(heavyNode);
            heavyNode.prev.add(lightNode);
        }


        for (int i = 1; i <= N; i++) {
            Node node = graph.get(i);
            prevVisited = new boolean[N + 1];
            nextVisited = new boolean[N + 1];

            if (dfs(node, 0) >= middle) {
                answer++;
            } else if (revDfs(node, 0) >= middle) {
                answer++;
            }
        }

        System.out.println(answer);
    }

    private static int dfs(Node node, int count) {
        nextVisited[node.index] = true;

        for (Node next : node.next) {
            if (!nextVisited[next.index]) {
                count = dfs(next, count + 1);
            }
        }
        return count;
    }

    private static int revDfs(Node node, int count) {
        prevVisited[node.index] = true;

        for (Node prev : node.prev) {
            if (!prevVisited[prev.index]) {
                count = revDfs(prev, count + 1);
            }
        }
        return count;
    }
}

Lovebird 애플리케이션의 다이어리 타임라인 화면에서 조회 시 페이지네이션을 할 필요성을 느꼈다. 작성 날짜(memory_date)를 기준으로 이전 또는 이후의 데이터를 pageSize만큼 조회한다는 요구사항에 따라 커서 페이지네이션을 활용하여 빠르게 개발하였다. 아래는 처음에 개발한 코드이다.

 . . .
    fun findBeforeNowUsingCursor(param: DiaryListRequestParam): List<DiaryResponseParam> {
        return queryFactory
            .from(diary)
            .innerJoin(user)
            .on(eqUserId(user.id))
            .innerJoin(diaryImage)
            .on(eqDiary(diaryImage.diary))
            .where(eqCouple(param.userId, param.partnerId), loeMemoryDate(param.memoryDate))
            .orderBy(descMemoryDate(), descCreatedAt())
            .limit(param.pageSize)
            .transform(
                groupBy(diary.id)
                    .list(
                        Projections.constructor(
                            DiaryResponseParam::class.java,
                            diary.id,
                            user.id,
                            diary.title,
                            diary.memoryDate,
                            diary.place,
                            diary.content,
                            list(
                                Projections.constructor(
                                    String::class.java,
                                    diaryImage.imageUrl
                                )
                            )
                        )
                    )
            )
    }
. . .

팀원과 Pull Request를 통해 코드 리뷰를 진행하다가 index나 scan에 대해서 의구심이 들어서 문제를 제시했다. 따라서, 이를 기반으로 문제 상황과 고려했던 방안에 대해 살펴보자

문제

일반적으로 query 성능을 개선하기 위해 인덱스를 활용하고 있고, Lovebird팀의 다이어리 페이지 조회 또한 인덱스를 생성 및 활용하려 한다. 문제는 타임라인 특성상 memory_date를 기준으로 조회를 해야하는데, 하루에 일기를 여러 개 작성할 수 있으므로, memory 컬럼의 카디널리티는 하루에 작성하는 일기 갯수와 반비례하여 낮아진다. 일반적으로 카디널리티가 낮은 컬럼에 대해서는 인덱스 효율이 떨어지기 때문에 테스트 이전에 두 가지 방안을 세워보았다.

• memory_date에 Index를 건다. (지장이 갈 정도로 하루에 많은 일기를 작성하진 않을 것이라 가정)
• diary_id와 memory_date를 묶어 Multiple Column Index를 건다.

행동1: memory_date에 Index를 건다.

CREATE INDEX idx_memory_date
ON diary (memory_date);

위와 같이 인덱스를 생성해 봤지만, 전혀 인덱스를 타지 않는 쿼리가 계속 발생했다. 그 이유는 postgreSQL에서는 table의 데이터 존재 유무도 함께 고려해서 실행 계획을 만들기 때문이었다. 따라서 Dummy Data를 생성해보았다.

-- users
INSERT INTO users(user_id, device_token, provider, provider_id, role) 
VALUES (1, 'sdfsdf', 'NAVER', 1, 'ROLE_USER');

-- diary
INSERT INTO diary
(diary_id, content, title, place, user_id, memory_date)
SELECT n, 'content ' || n as content, 'title ' || n as title, 'place ' || n as place, 1, '2023-12-15'
FROM generate_series(1, 1000000) as n;

-- diary_image
INSERT INTO diary_image
(diary_image_id, diary_id, image_url)
SELECT n, n, 'imageUrl ' || n as image_url
FROM generate_series(1, 1000000) as n;

Dummy Data를 삽입한 후의 Query Plan은 다음과 같다.

Execution Time(16226.902 ms)

행동2:인덱스를 부여하지 않고, PK(diary_id)를 활용한다.

SELECT d.diary_id, d.user_id, d.title, d.place, d.content, di.image_url
FROM diary d
INNER JOIN diary_image di
ON d.diary_id = di.diary_id
WHERE (d.memory_date <= '2023.12.15' and d.diary_id <= 10) and (d.user_id = 1 or d.user_id = 2)
ORDER BY d.memory_date desc, d.created_at desc
LIMIT 10;

diary_image에서는 Parallel 하게 Full Scan을 하지만, Diary를 가져올 때는 Index Condition이 걸려서 Index Scan을 하는 것을 확인할 수 있다. 따라서 행동 3을 채택하기로 하였고, 추가적으로 diary_image에 대한 인덱스로 살펴보도록 하겠다.

→ Execution Time (138.383 ms)

행동3:diary_id와 memory_date를 묶어 Multiple Column Index를 건다.

CREATE INDEX multiple_column_index
ON diary (diary_id, memory_date);

위와 같이 인덱스를 생성한 후의 Query Plan은 다음과 같다. 실행 시간은 커졌지만, 이는 memory_date의 다양화를 위해 Query 실행 이전에 데이터를 더 추가했기 때문에 크게 고려할 사항은 아니라고 생각 들었다. 이 Query Plan에서 포인트는 Index Scan에서 diary_id와 memory_date를 이용한 multiple column index를 활용하지 않는다는 점이다.

추가:diary_image에는 왜 Index가 없을까?

사실 diary_image의 Foreign Key인 diary_id에 Index가 있는줄 았았다. 하지만 테스트 과정에서 확인한 결과, 없음을 확인했고, postgreSQL에서는 Foreign Key에 대한 Index를 자동 생성해주지 않는다는 것을 알게 되었다.

CREATE INDEX idx_fk_diary_image_diary_id
ON diary_image(diary_id);

위와 같은 인덱스를 생성한 후 실행했을 때의 Query Plan은 다음과 같다. Execution Time이 대폭 줄어든 것을 확인할 수 있었다. 이를 통해 초기의 Seq Scan * Seq Scan에서 Index Scan * Index Scan으로 성능을 향상 시킬 수 있었다.

실제 코드

@Entity
@Table(
    name = "diary_image",
    indexes = [
        Index(name = "idx_fk_diary_image_diary_id", columnList = "diary_id")
    ]
)
class DiaryImage(
    diary: Diary,
    imageUrl: String
) {
. . .

PK를 활용한 쿼리 구현

. . .
    fun findAfterNowUsingCursor(param: DiaryListRequestParam): List<DiaryResponseParam> {
        return queryFactory
            .from(diary)
            .innerJoin(user)
            .on(eqUserId(user.id))
            .where(
                eqCouple(param.userId, param.partnerId),
                eqMemoryDateAndGtDiaryId(param.memoryDate, param.diaryId),
                gtMemoryDate(param.memoryDate)
            )
            .orderBy(ascMemoryDate(), ascDiaryId())
            .limit(param.pageSize)
            .transform(
                groupBy(diary.id)
                    .list(
                        Projections.constructor(
                            DiaryResponseParam::class.java,
                            diary.id,
                            user.id,
                            diary.title,
                            diary.memoryDate,
                            diary.place,
                            diary.content,
                            list(
                                Projections.constructor(
                                    String::class.java,
                                    diaryImage.imageUrl
                                )
                            )
                        )
                    )
            )
    }

    private fun eqCouple(userId: Long, partnerId: Long?): BooleanExpression {
        val expression: BooleanExpression = eqUserId(userId)

        return if (partnerId != null) {
            expression.or(eqUserId(partnerId))
        } else {
            expression
        }
    }

    private fun eqMemoryDateAndGtDiaryId(memoryDate: LocalDate, diaryId: Long): BooleanExpression {
        return gtDiaryId(diaryId).and(eqMemoryDate(memoryDate))
    }

    private fun eqMemoryDate(memoryDate: LocalDate): BooleanExpression = diary.memoryDate.eq(memoryDate)

    private fun gtDiaryId(diaryId: Long): BooleanExpression = diary.id.gt(diaryId)

    private fun gtMemoryDate(memoryDate: LocalDate): BooleanExpression = diary.memoryDate.gt(memoryDate)
. . .

다음과 같은 로직으로 PK와 memory_date를 활용한 쿼리를 작성했다.

• 처음 조회 시 (=오늘 날짜 조회)
  • 요청

    * diaryId : 0 or -1
    * memoryDate : 오늘 날짜

• 조회 데이터
  • 요청 받은 날짜와 동일하고, 요청 받은 아이디보다 큰 아이디를 가진 데이터(eqMemoryDateAndGtDiaryId)
  • 요청 받은 날짜 이후, 혹은 이전의 데이터 (ltMemoryDate or gtMemoryDate)
  • 데이터 갯수 : pageSize

• 처음 이후의 조회 시 요청
  • diaryId : 이전 조회에서 응답으로 받은 diaryId
  • memoryDate : 이전 조회에서 응답으로 받은 memoryDate 조회 데이터
  • 요청 받은 날짜와 동일하고, 요청 받은 아이디보다 큰 아이디를 가진 데이터 (eqMemoryDateAndGtDiaryId)
  • 요청 받은 날짜 이후, 혹은 이전의 데이터 (ltMemoryDate or gtMemoryDate)
  • 데이터 갯수 : pageSize

2021 카카오 채용연계형 인턴십 문제 중 LV.3 표 편집 문제를 풀며 해결한 방법을 풀이하겠습니다.

해당 문제를 고민하다가 풀지 못해서 힌트를 참고해서 제 것으로 만들기 위해 노력했습니다.

해결하지 못한 근본적인 이유는

1. n의 범위 : 5 ≤ n ≤ 1,000,000 에 대해서 ArrayList나 LinkedList를 이용해서 remove연산을 할 경우 시간을 초과하는 현상이 있습니다.
2. 삭제 연산에 대해 Stack 자료 구조를 활용해야 하는 것은 떠올렸습니다. 문제는 해당 위치를 기억할 수 있지만 Insert 연산을 위해 컬렉션을 이용한다면, 최악의 경우 시간 복잡도가 O(n) 만큼 발생합니다.

카카오에서 제공하는 근본적인 풀이

해설링크

LinkedList 자료구조를 구현할 수 있는지가 핵심 이라고 할 수 있습니다. Node의 prev Node, next Node를 활용하면 되고 복구 연산을 할 경우에도 가장 마지막에 삭제된 노드가 복구되므로, 삭제된 노드의 이전 노드와 다음 노드의 연결을 다시 재구성해주면 됩니다.

O, X 출력을 위한 방법

현재 Node를 이용해 최상단 노드로 이동해서 startIndex부터 현재 노드의 value와 맞는지 비교 연산을 수행하며 출력하면 됩니다.

import java.util.*;

class Node {
    Node prev = null;
    int index;
    Node next = null;

    public Node(int index) {
        this.index = index;
    }
}

class Solution {
    private static Node currentNode;
    private static Map<Integer, Node> map = new HashMap<>();
    private static Stack<Node> stack = new Stack<>();

    public String solution(int n, int k, String[] cmd) {
        StringBuilder sb = new StringBuilder();
        init(n);
        currentNode = map.get(k);

        for(String order : cmd) {
            String[] arr = order.split(" ");

            if(arr[0].equals("U")) {
                selectUp(Integer.parseInt(arr[1]));
            } else if(arr[0].equals("D")) {
                selectDown(Integer.parseInt(arr[1]));
            } else if(arr[0].equals("C")) {
                delete();
            } else if(arr[0].equals("Z")) {
                restore();
            }
        }

        while(currentNode.prev != null) { // 최상단 노드로 이동하기
            currentNode = currentNode.prev;
        }

        int startIndex = 0;

        while(startIndex < n) { // 출력 연산을 위한 동작
            if(startIndex == currentNode.index) {
                sb.append("O");
                startIndex++;
                if(currentNode.next != null) {
                    currentNode = currentNode.next;
                }
            } else if(startIndex != currentNode.index) {
                sb.append("X");
                startIndex++;
            }
        }

        return sb.toString();
    }

    private static void init(int n) {
        Node prev = null;
        Node node = null;
        for (int i = 0; i < n; i++) {
            if (i == 0) {
                node = new Node(i);
                prev = node;
            } else if (i == n) {
                node = new Node(i);
                prev.next = node;
                node.prev = prev;
            } else {
                node = new Node(i);
                prev.next = node;
                node.prev = prev;
                prev = node;
            }
            map.put(i, node);
        }
    }

    private static void selectUp(int number) {
        for(int i = 0; i < number; i++) {
            currentNode = currentNode.prev;
        }
    }

    private static void selectDown(int number) {
        for(int i = 0; i < number; i++) {
            currentNode = currentNode.next;
        }
    }

    private static void delete() {
        // 스택에 담기
        stack.push(currentNode);

        if(currentNode.prev == null) { // 맨 위 노드인 경우
            currentNode = currentNode.next;
            currentNode.prev = null;
        } else if(currentNode.next == null) { // 맨 아래 노드인 경우
            currentNode = currentNode.prev;
            currentNode.next = null;
        } else { // 나머지
            Node prev = currentNode.prev;
            Node next = currentNode.next;
            prev.next = next;
            next.prev = prev;
            currentNode = currentNode.next;
        }
    }

    private static void restore() {
        Node back = stack.pop(); // 삭제된 노드 불러오기
        Node next = back.next;
        Node prev = back.prev;

        if(next != null) { // 삭제된 노드의 다음이 null이 아니라면
            next.prev = back;
        }

        if(prev != null) { // 삭제된 노드의 이전이 null이 아니라면
            prev.next = back;
        }
    }
}

실무 경험은 없지만 프로젝트 경험들을 통해 Test를 작성하지 않은 경험, Dependency를 제거하여 Mockito를 활용한 Test 방식, Repository Layer 즉 Database를 접근하는 단계까지 포함한 Test들을 경험해봤습니다.

테스트 코드에 대해 많은 의견들이 있고 중요성을 개발자들이 강조하지만 이론으로 접하는 것과 직접 작성하면서 얻는 경험은 다르다고 생각합니다.

문제

간단한 비즈니스 로직, 쿼리문만 존재하는 로직, 의존성을 가지고 있는 로직 등등 다양한 스타일의 로직이 존재합니다.

간단한 로직이고 많이 해봤으니까 문제 없겠지? 버그가 생길 일이 없어.

라고 단정지은 경험 있지 않으신가요?

이런 자신감에서 비롯되는 버그는 필연적으로 존재한다고 생각합니다.

개발이라는 것은 '혼자'서도 하겠지만 보통은 '팀' 의 단위로 작업하기 때문에 모든 상황들을 스스로 인지하고 있지 못할때가 많기 때문이라고 생각합니다.

문제1

테스트 코드를 작성하지 않으면 유지 보수 비용이 더 든다. 정말 무지했던 시절, Postman을 이용해 하나하나 API 호출을 해보며 테스트 했습니다.

빌드하고... 배포하고 .. (시간 비용이 어마어마 합니다)

문제2

다양한 상황들을 만들어가며 테스트하기 힘들다. 다양한 케이스 들이 존재할텐데, 하나하나 요청하면서 테스트를 할 것인가? 에 대해 막막합니다.

상황을 애플리케이션 코드 레벨에서 관리하고 유지보수한다면 비용이 그만큼 줄어든다고 생각합니다.

문제3

Behavior, Status 개발자가 작성한 로직에서 발생해야할 행위와 상태 -> 예상한대로 동작하는가?

테스트 코드를 작성하지 않으면 검증하기가 매우 힘듭니다. 이러한 경험을 통해 테스트 코드의 이점을 느낄 수 있었습니다.

결과

다음으로는 실제 프로젝트에 참여하며 테스트 커버리지 유지를 해봤던 경험을 소개하고자 합니다.

개선된 점1

해당 프로젝트에서는 Unit Test라기 보다 실제 Database까지 접근하여 테스트하는 통합 테스트에 가까운 방식을 채택했습니다.

의존성이 제거된 테스트 방식이 아니라 실제 결과물을 보여주기 때문에 내가 작성한 코드에 대한 신뢰도가 대폭 올라갔으며 높은 커버리지를 통해 팀원들과 생산성 있는 리뷰를 경험했습니다.

개선된 점2

테스트 코드는 비즈니스 로직이 어떻게 동작하는지에 대한 이해도도 높여준다는 것이었습니다. 상황 설명과 테스트에 활용되는 인스턴스 상태와 행위를 직접 확인하면서 리뷰의 즐거움을 느낄 수 있었습니다.

더 나아갈 점

시간에 쫒기는 프로젝트를 하다 보니, 사실 소나큐브 지표 그래프가 예쁘지가 않습니다. 테스트를 먼저 작성하고 개발을 해보는 경험도 필요할 것 같습니다.

• 나는 Unit Test를 잘하고 있을까?에 대해서도 고민하고 성장하고자 합니다. 런던파, 고전파의 견해를 책에서 읽어본 적이 있는데 아직 갈길이 멀다고 생각합니다...
• 테스트 코드에서 활용되는 Fixture를 잘 활용할 수 없을까? 초기에 전역으로 사용하면서 Fixture의 상태가 변경되며 테스트 코드의 실패를 겪었던 케이스들도 있었습니다.

테스트 코드에 많은 시간 비용을 투자해야 성장한다고 생각합니다.

상황

백엔드 개발자로서 1 + N 문제, 쿼리 튜닝, 인덱스, 캐싱 등등 서비스의 품질을 개선하기 위해 노력할 수 있는 고려할 수 있는 상황들이 있습니다. 조금은 무모했던, 더 나은 방법들을 고민할 수 있었던 저의 개발 경험을 소개할까 합니다.

nGrinder 소개에 의하면 Groovy로 작성된 Script를 활용하여 stress를 줄 수 있다고 설명되어 있습니다. 필자는 Docker를 활용하여 nGrinder Agent와 Controller를 운영해서 부하 테스트를 진행했습니다.

문제

낮은 TPS

/todos/feed/following 유저가 팔로잉 하고 있는 피드를 조회할때, 피드가 가지고 있는 Nag 즉 NagLike 유무와 해당 Nag에 대한 초성 해제(NagUnlock) 유무에 대한 테이블까지 함께 조회하는 쿼리가 발생하면서 낮은 TPS를 확인할 수 있었습니다.

개선의 노력

테이블 역정규화

개선 내용 (NagLike와 NagUnlock에 대한 역정규화 진행 → NagInteraction

테이블 역정규화 작업으로도 높은 성능 개선을 느낄 수 있었습니다.

복합 INDEX

사실 데이터 크기가 크지 않아서 복합 INDEX가 크게 효과적일까 라는 생각을 했었으나 역시 개선할 수 있었습니다.

개선해야 할 상황

올바른 성능 테스트와 개선 방향

필자는 부하 테스트를 해보고 싶었던 마음도 있었고 눈에 보이는 수치들을 보면서 개발을 하고 싶었던 마음이 컸습니다. 하지만 프로젝트 기간동안 순차적인 단계를 밟지 않고 무리하게 진행했다는 생각이 들었습니다.

오만한 판단 Redis를 활용한 Caching, 역정규화 등등 이런 부분들을 바로 적용하면 좋은 서비스를 만들 수 있겠지! 라는 생각을 했습니다.

1. 서버에는 문제가 없는지? CPU 사용률 등등...
2. 쿼리는 쿼리 실행계획대로 잘 발생하고 있는지?
3. 병목 현상은 없는지?
4. 이중화는 고려해봤는지?

이런 기초적인 고민들도 하지 않고 개발했다는 점입니다.

앞으로는 테이블 풀 스캔 여부, 페이징에서 발생할 수 있는 쿼리 개선 등등

기초적인 부분들을 놓치지 않고 개발해야겠다고 생각했습니다.

더하여, 실무에서는 이런 부분들을 전문적으로 모니터링하고 개선하기 위한 팀들이 있겠다는 것을 느꼈습니다

(취업해서 이런 일들을 느껴보고 싶다..)

참고 자료

• https://naver.github.io/ngrinder/

SSR, 테스트 서버, 운영 서버를 운영하면서 CORS를 피할 수 없었습니다. 경험이 부족했을 때 학자형 스타일로 문제를 직면하기보다 전투형으로 개발하면서 무지했던 상황들을 기록하고자 합니다.

누구나 웹 개발을 하며 개발자 도구를 열어볼텐데 시뻘건 줄을 마구마구 마주합니다. CORS ERROR, 정확히 이해해보자!

문제

자바스크립트에서 요청은 기본적으로 서로 다른 도메인에 대한 요청을 보안상 제한합니다. 브라우저는 또한 기본적으로 하나의 서버 연결만 허용되도록 설정되어 있습니다.

Same Origin과 Cross Origin 정책 -> 바로 이러한 정책이 존재하기 때문에 CORS ERROR가 발생하는 것입니다. Cross-Origin Resource Sharing이라는 단어로서 "교차 출처 리소스 공유 정책" 을 의미합니다.

기본적으로 요청에 의해 에러가 발생하면 서버 문제라고 생각하지만 출처를 비교하는 로직 자체는 브라우저에서 구현된 스펙입니다. 따라서 서버에서는 요청에 대한 응답을 해주는데 브라우저가 응답을 분석해 에러를 뿜는다고 생각하면 됩니다.

지식 담기

필자가 작성한 쿠키의 도메인 설정과 관련해서도 출처, 즉 Origin에 대해 이해 해야 합니다. Same Origin이라는 의미는 URL의 구성 요소 중에서도 Protocol, Host, Port 3가지가 동일하면 Same Origin이라고 판단합니다.

브라우저 정책이라면 서버끼리 통신할때는 문제가 없지 않을까?

실제로, 브라우저가 아닌 서버 간에 통신을 할때는 정책이 적용되지 않습니다. 그래서, 서버 단 코드에서 서버로 API를 요청하면 CORS 에러로부터 자유로워질 수 있습니다.

실제로, Next JS를 활용해 SSR을 하게 되면 API 서버와 서버 간의 통신을 하기 때문에 CORS와 같은 정책 문제를 해결할 수 있습니다.

해결

상황 인지

브라우저가 동일 출처 정책에 따라서 다른 출처의 리소스를 차단하며 에러가 발생했더라도 CORS, 다른 출처 리소스 공유에 대한 허용과 비허용 정책에 따라서 SOP 정책을 회피하면 된다.

브라우저는 HTTP 요청 Header에 Origin을 담아서 전달합니다. 그렇다면, 서버는? 서버 또한 Access-Control-Allow-Origin을 담아서 클라이언트로 전달합니다.

그렇다면 클라이언트는 Origin과 서버가 보내준 Accss-Control-Allow-Origin을 비교하여 유효성을 판단합니다.

서버에서 작업

필자는 Spring Boot 프레임워크를 활용해서 개발하였다. 따라서 Access-Control-Allow-Origin, Access-Control-Allow-Methods, Access-Control-Allow-Headers를 통해 브라우저에게 요청이 안전하다는 것을 알려줍니다.

if (CorsUtils.isPreFlightRequest(request)) {
    return true;
}

위와 같이, 브라우저는 예비 요청을 통해 서버와 잘 통신되는지 확인하는데 이 역할은 안전한 요청인지 미리 확인하는 것이다.

@Override
    public void addCorsMappings(CorsRegistry registry) {
        registry.addMapping("/**")
                .allowedOrigins("http://localhost:3001")
                .allowedOrigins("http://www.ssafsound.com")
                .allowedOrigins("https://www.ssafsound.com")
                .allowedOrigins("https://test.ssafsound.com")
                .allowedOrigins("https://api.ssafsound.com")
                .allowedOrigins("http://ssafsound.com")
                .allowedOrigins("https://ssafsound.com")
                .allowedMethods(ALLOWED_METHOD_NAMES.split(","))
                .allowedHeaders("*")
                .allowCredentials(true)
                .exposedHeaders("*");
    }