청년벙커는 공유주방, 라운지, 의사당 같은 공간을 온라인으로 신청하고 관리자가 승인하는 공공기관 웹 서비스다.

서비스를 개발하고 운영하면서 관리자 페이지에서 공간 목록을 불러오는게 유독 느리다는 걸 느꼈다.

코드를 확인해보니

// 현재 코드
const itemsRaw = await rentalCol.find(filter).sort(...).toArray();

for (const rental of itemsRaw) {
    const user = await userCol.findOne({ _id: rental.userId }); // 😱
    rental.userName = user?.username;
    rental.userEmail = user?.email;
}

대여 목록을 불러온 뒤, 각 대여 건마다 유저 정보를 따로 조회하고 있었다.

대여 100건이면 DB를 101번 호출하는 구조였다.


문제 1: N+1 쿼리

N+1이 뭔지

대여 목록 조회 1회
    ↓
대여 건마다 유저 조회 N회

총 1 + N회 DB 호출
→ N+1 쿼리 문제

처음에 왜 이렇게 짰는지 생각해보면, 당시엔 "대여 가져오고 → 유저 정보 붙이면 되지"라는 생각이었다. 기능은 동작하니까 문제를 인식하지 못했다.

데이터가 적을 땐 체감이 안 됐다. 하지만 대여 건수가 쌓이면서 관리자 페이지가 점점 느려졌고, 원인이 바로 이 코드였다.

해결: $lookup으로 한 번에 조인

MongoDB의 $lookup 파이프라인을 사용하면 DB 1회 호출로 해결된다.

// 변경 후
const items = await rentalCol.aggregate([
    { $match: filter },
    { $sort: { date: 1, spaceType: 1, startTime: 1 } },
    { $skip: skip },
    { $limit: limit },
    {
        $lookup: {
            from: 'users',
            localField: 'userId',
            foreignField: '_id',
            as: '_user'
        }
    },
    { $unwind: { path: '$_user', preserveNullAndEmptyArrays: true } },
    {
        $addFields: {
            userName: '$_user.username',
            userEmail: '$_user.email'
        }
    },
    { $project: { _user: 0 } }
]).toArray();

$lookup은 SQL의 JOIN과 같은 역할을 한다. 별도의 반복 조회 없이 한 번의 파이프라인으로 대여 정보와 유저 정보를 함께 가져온다.

 

SQL로 보면

-- 기존 방식 (N+1)
SELECT * FROM rental;  -- 1번
SELECT * FROM user WHERE id = 1;  -- 2번
SELECT * FROM user WHERE id = 2;  -- 3번
...

-- 개선 방식 (JOIN)
SELECT rental.*, user.username, user.email
FROM rental
JOIN user ON rental.userId = user.id;  -- 1번으로 끝

 

변경 전: DB 101회 호출 (대여 100건 기준)
변경 후: DB 2회 호출 (목록 1회 + 전체 카운트 1회)

 


문제 2: 누락된 인덱스

인덱스가 없으면 풀스캔이 발생한다

코드를 더 들여다보니 인덱스 문제도 있었다.

settings 컬렉션: 공휴일, 휴무일 조회 시 매번 풀스캔

// 매번 이렇게 조회하는데
const doc = await settings.findOne({ key: 'closedDays', year: 2026 });
// settings 컬렉션에 인덱스가 없어서 전체를 뒤진다

users 컬렉션: 관리자 유저 검색 시 regex 풀스캔

// 검색할 때 이렇게 regex로 조회하는데
{ username: { $regex: keyword, $options: 'i' } }
// 인덱스 없이 전체를 순차 탐색한다

인덱스를 걸면 된다... 근데 어떻게?

단순히 "인덱스 추가하면 되겠지"가 아니라, 어떤 인덱스를 어떻게 걸어야 하는지가 중요했다.

settings 컬렉션: 항상 key와 year를 함께 조회하므로 복합 인덱스가 적합

await settings.createIndex(
    { key: 1, year: 1 },
    { name: 'settings_key_year', background: true }
);

background: true 옵션은 인덱스 생성 중에도 다른 작업이 가능하게 해준다. 운영 중인 서비스에서 인덱스를 추가할 때 중요한 옵션이다.

users 컬렉션: 텍스트 검색에는 텍스트 인덱스가 효과적

await users.createIndex(
    { username: 'text', email: 'text' },
    {
        name: 'user_text_search',
        background: true,
        weights: { username: 10, email: 5 }  // username 검색이 더 중요
    }
);

weights로 각 필드의 검색 가중치를 설정했다. username으로 검색하는 게 email보다 더 중요하다고 판단했기 때문이다.


문제 3: 반복되는 I/O

인덱스를 추가해도 해결 안 되는 문제가 있었다.

캘린더 열 때마다 DB 조회
예약 가능 여부 확인할 때마다 DB 조회
공휴일 조회할 때마다 외부 API 호출

자주 조회되는데 잘 안 바뀌는 데이터들이었다. 이런 데이터를 매번 DB에서 가져오는 건 낭비다.

Redis 캐싱 도입

캐시 레이어를 만들어서 모든 캐싱 로직을 통일했다.

// cacheService.js
async function cacheOrFetch(key, ttlSeconds, fallbackFn) {
    try {
        const cached = await redis.get(key);
        if (cached) return JSON.parse(cached);  // 캐시 히트

        const data = await fallbackFn();        // 캐시 미스 → DB 조회
        await redis.setex(key, ttlSeconds, JSON.stringify(data));
        return data;
    } catch (e) {
        // Redis 장애 시 DB 직접 조회 (서비스 중단 방지)
        console.error('캐시 오류, DB 직접 조회:', e.message);
        return fallbackFn();
    }
}

Redis가 죽어도 서비스는 계속 동작한다. catch 블록에서 DB 직접 조회로 fallback하기 때문이다.

 

데이터 성격에 따라 TTL을 다르게

모든 데이터를 같은 TTL로 캐싱하는 건 옳지 않다.

예약 가능 여부 → 10분 TTL
  (대여 승인/취소 시 자주 바뀔 수 있음)

캘린더 데이터 → 30분 TTL
  (한 번 불러오면 꽤 오래 유효)

공휴일 → 24시간 TTL
  (1년에 한 번 업데이트됨)

공지/프로그램 목록 → 5~10분 TTL
  (가끔 바뀜)

캐시 무효화도 중요하다

TTL 외에도 데이터가 바뀌는 시점에 캐시를 직접 무효화해야 한다.

// 대여 승인/취소 시
await invalidate('rental:avail:*');    // 예약 가능 여부 캐시 삭제
await invalidate('rental:calendar:*'); // 캘린더 캐시 삭제

캐시가 있는데 데이터가 바뀌면 오래된 정보를 보여주는 정합성 문제가 발생한다. 변경이 일어나는 시점에 관련 캐시를 함께 지워줘야 한다.

 

그런데 데이터가 아예 없는 경우는?

캐싱을 적용하다가 한 가지 더 고민이 생겼다.

특정 연도의 휴무일 설정이 아직 등록되지 않은 경우를 생각해보자.

 

2026년 휴무일 조회 요청
    ↓
Redis에 없음 → DB 조회
    ↓
DB에도 없음 (아직 설정 안 됨)
    ↓
캐시에 저장 안 됨
    ↓
다음 요청도 똑같이 DB 두드림
→ 요청마다 DB 조회 반복 

 

이걸 캐시 관통(Cache Penetration) 이라고 한다. 데이터가 없는 경우 캐시를 우회해서 계속 DB에 부하를 주는 문제다.

해결: "없음"도 캐싱한다

해결은 단순했다. DB에서 데이터를 찾지 못해도 그 결과 자체를 캐싱하는 것이다.

async function getClosedDays(year, db) {
    return cacheOrFetch(`holidays:closed:${year}`, 3600, async () => {
        const settings = db.collection('settings');
        const doc = await settings.findOne({ key: 'closedDays', year });

        // null이어도 빈 배열로 캐싱
        // "이 연도 휴무일 설정 없음" 자체를 저장
        return doc?.dates || [];
    });
}

doc?.dates || [] 이 한 줄이 핵심이다. DB에 데이터가 없어도 빈 배열 []을 반환하고, 이 빈 배열이 Redis에 저장된다. 다음 요청은 DB까지 가지 않고 캐시에서 []를 바로 반환한다.

물론 나중에 실제로 휴무일이 등록되면 캐시를 무효화해줘야 한다.

// 휴무일 설정 변경 시
await invalidate('holidays:closed:*');

TTL도 짧게 설정하는 게 중요하다. 나중에 실제 데이터가 생길 수 있으니, 빈 배열이 너무 오래 캐시에 남아있으면 안 된다.


전체 흐름

사용자 요청
    ↓
[브라우저 캐시] → hit: 응답 (0ms, 서버 무부하)
    ↓ miss
[Redis 캐시] → hit: 응답 (~1ms)
    ↓ miss
[MongoDB 인덱스 스캔] → 결과 → Redis 저장 → 응답
    ↓
[캐시 무효화] ← 데이터 변경 시

 

캘린더 조회 요청
        ↓
Redis에 'rental:calendar:2026-04:공유주방' 있어?
        ↓ 있으면
바로 반환 ⚡ (~1ms)
        ↓ 없으면
MongoDB 조회 → Redis에 저장 (30분) → 반환

나중에 대여 승인되면?
→ rental:calendar:* 캐시 삭제
→ 다음 요청 시 최신 데이터로 다시 캐싱

개선 효과

구간 변경 전 변경 후

관리자 대여 목록 (100건) DB 101회 DB 2회
캘린더 로드 매번 DB + JS 그루핑 Redis 히트 (~1ms)
예약 가능 여부 확인 매번 DB 조회 Redis 히트 (~1ms)
공휴일 조회 서버 재시작마다 외부 API Redis 24시간 유지

배운 것

1. 기능이 동작한다고 끝이 아니다

N+1 쿼리는 기능상 문제없이 동작한다. 데이터가 적으면 느린지도 모른다. 하지만 데이터가 쌓이면 서비스가 버티질 못한다. 코드가 어떻게 DB를 호출하는지 항상 의식해야 한다.

2. 인덱스는 왜 거는지가 중요하다

단순히 "느리니까 인덱스 걸자"가 아니라, 어떤 쿼리가 어떤 패턴으로 실행되는지 파악하고 그에 맞는 인덱스를 설계해야 한다. 복합 인덱스, 텍스트 인덱스는 상황에 따라 다르게 쓰인다.

3. "없음"도 캐싱해야 한다

데이터가 없는 경우를 캐싱하지 않으면, 없는 데이터를 조회할 때마다 DB를 계속 두드리는 캐시 관통 문제가 발생한다. 빈 배열이나 특수값으로 "없음" 자체를 캐싱하고, 데이터가 실제로 생기면 캐시를 무효화하는 방식으로 처리해야 한다.

4. 캐시는 성능 도구지 생명줄이 아니다

Redis가 죽어도 서비스는 계속 동작해야 한다. fallback을 반드시 구현하자. 그리고 데이터가 바뀌는 시점에 캐시 무효화를 빠뜨리지 말자. 오래된 데이터를 보여주는 게 아무것도 보여주지 않는 것보다 더 나쁠 수 있다.

"결제 버튼 눌렀는데 돈은 나갔고, 서비스는 이용 못 하면 어떡하죠?"

TokNow 서비스를 개발하면서 포트원(PortOne)을 연동해 결제 시스템을 구현했다. 당시에는 잘 동작하는 것처럼 보였다.

하지만 최근 결제 시스템을 공부하면서 내가 짠 코드가 꽤 위험한 구조였다는 걸 뒤늦게 깨달았다.

이 글은 그 과정에서 시도한 것과 학습한 것을 기록했다


TokNow의 결제 구조

TokNow는 소상공인의 SNS 마케팅을 자동화해주는 서비스다. 콘텐츠 생성 기능을 사용하려면 크레딧이라는 자체 포인트가 필요하고, 크레딧은 포트원을 통해 결제해서 충전할 수 있다.

결제 방식은 크게 두 가지였다.

1. 크레딧 결제 (내부 시스템)
   → 보유한 크레딧을 차감해서 서비스 이용

2. 포트원 결제 (외부 PG사 연동)
   → 카드 결제로 크레딧 충전

얼핏 보면 비슷해 보이는 두 방식. 하지만 트랜잭션 설계는 완전히 달라야 했다.


크레딧 결제: 하나의 원자적 트랜잭션으로 묶어라

크레딧 결제는 외부 시스템이 전혀 개입하지 않는다. 우리 DB 안에서 모든 것이 완결된다.

크레딧 차감 → 콘텐츠 생성 이력 저장 → 잔여 크레딧 업데이트

이 세 가지는 모두 성공하거나, 모두 실패해야 한다. 크레딧은 차감됐는데 이력이 저장 안 되거나, 이력은 저장됐는데 잔여 크레딧이 업데이트 안 되면 데이터가 꼬인다.

이런 경우엔 하나의 @Transactional로 묶는 것이 당연하고 올바른 설계다.

@Transactional
public void useCreditForContent(Long userId, int creditAmount) {
    // [1] 크레딧 차감
    creditService.deduct(userId, creditAmount);

    // [2] 콘텐츠 생성 이력 저장
    contentHistoryRepository.save(...);

    // [3] 잔여 크레딧 업데이트
    creditService.updateBalance(userId);

    // 셋 중 하나라도 실패하면? 전부 롤백 → 데이터 정합성 유지 ✅
}

외부 시스템이 없으니 롤백하면 깨끗하게 원상복구된다. 이게 바로 @Transactional을 쓰는 이유 !


포트원 결제: 내가 짰던 위험한 코드

포트원 결제는 달랐다. 프론트에서 포트원 결제창을 띄우고, 고객이 결제를 완료하면 imp_uid(결제 고유번호)를 서버로 보내준다. 서버는 이 imp_uid로 포트원 서버에 검증 요청을 보내 실제 결제가 완료됐는지 확인한다.

당시 내가 짰던 코드는 이랬다.

@Transactional
public void verifyAndCharge(String imp_uid, Long userId) {

    // [1] 포트원 서버에 결제 검증 요청 (외부 API)
    PaymentResponse response = portoneClient.verify(imp_uid);

    // [2] DB에 결제 내역 저장
    paymentRepository.save(Payment.of(response, userId));

    // [3] 크레딧 충전
    creditService.charge(userId, response.getAmount());
}

 

 

왜 위험한가: @Transactional의 롤백은 DB에만 적용된다

다음 상황을 생각해보자.

[1] 포트원 검증 성공 ✅
    → 실제로 고객 카드에서 돈이 출금된 상태

[2] DB 저장 실패 💥
    → 예외 발생
    → @Transactional이 전체 롤백

결과:
→ 고객 카드에서 돈은 나갔다
→ 우리 DB에는 결제 기록이 없다
→ 크레딧도 충전 안 됐다
→ 고객 입장에서는 돈만 나가고 서비스를 못 쓰는 상황

더 최악의 시나리오도 있다.

[1] 포트원 검증 성공 ✅ (돈 나감)
[2] DB 저장 성공 ✅
[3] 포트원 서버에서 응답이 오다가 네트워크 끊김 💥
    → 우리 서버는 예외로 인식
    → 전체 롤백
    → DB 기록도 사라짐

결과:
→ 돈은 나갔고
→ DB 기록도 없고
→ 크레딧도 없고

@Transactional의 롤백은 우리 DB에만 적용된다. 이미 호출된 외부 API는 절대 되돌릴 수 없다.

이 사실을 당시엔 제대로 인식하지 못했다.


어떻게 개선해야 할까: 트랜잭션을 쪼개라

핵심 원칙은 두 가지다.

1. 외부 API 호출을 트랜잭션 밖으로 분리하라 2. 결제 시도 기록을 PENDING 상태로 먼저 남겨라

// PaymentFacade - 트랜잭션 없음, 흐름만 조율
public PaymentResult charge(String imp_uid, Long userId) {
    return paymentProcessor.process(imp_uid, userId);
}

// PaymentProcessor - 트랜잭션을 짧게 쪼갬
public PaymentResult process(String imp_uid, Long userId) {

    // ★ [트랜잭션 1] PENDING으로 먼저 저장 → 즉시 커밋
    // 이 순간부터 무슨 일이 생겨도 "결제 시도 기록"은 살아있다
    Payment payment = paymentService.create(imp_uid, userId, PENDING);

    try {
        // ★ [트랜잭션 없음] 포트원 검증 (외부 API)
        // 네트워크가 끊겨도 위의 PENDING 기록은 DB에 남아있다
        PaymentResponse response = portoneClient.verify(imp_uid);

        // ★ [트랜잭션 2] 성공 → PAID 업데이트 + 크레딧 충전 → 커밋
        paymentService.update(payment.getId(), PAID);
        creditService.charge(userId, response.getAmount());

    } catch (Exception e) {
        // ★ [트랜잭션 3] 실패 → FAILED 업데이트 → 커밋
        paymentService.update(payment.getId(), FAILED);
        throw e;
    }

    return PaymentResult.from(payment);
}

// PaymentService - 짧은 단위의 트랜잭션
@Service
public class PaymentService {

    @Transactional
    public Payment create(String imp_uid, Long userId, PaymentStatus status) {
        return paymentRepository.save(Payment.create(imp_uid, userId, status));
        // 메서드 끝나면 즉시 커밋
    }

    @Transactional
    public void update(Long id, PaymentStatus status) {
        Payment payment = paymentRepository.findById(id).orElseThrow();
        payment.updateStatus(status);
        // 메서드 끝나면 즉시 커밋
    }
}

PENDING이 왜 중요한가

[기존 방식 - 위험]
포트원 성공 → DB 저장 실패 → 롤백 → 기록 없음 💥

[개선 방식 - 안전]
PENDING 저장 → 커밋 ✅
포트원 성공 → 네트워크 끊김
→ DB에 PENDING 기록은 살아있음
→ 배치로 주기적으로 확인
→ "PENDING인데 실제로 결제됐나?" 포트원에 확인
→ 됐으면 PAID로 복구 ✅

PENDING 상태로 먼저 커밋해두면, 어떤 상황에서도 "결제 시도가 있었다"는 기록은 반드시 남는다.

배치는 @Scheduled를 이용해 주기적으로 PENDING 상태를 확인하고 복구한다.

@Component
public class PaymentRecoveryBatch {

    // 5분마다 자동 실행
    @Scheduled(fixedDelay = 300000)
    public void recoverPendingPayments() {

        List<Payment> pendingList =
            paymentRepository.findByStatus(PENDING);

        for (Payment payment : pendingList) {
            // 포트원에 실제 결제 여부 확인
            boolean isApproved =
                portoneClient.confirm(payment.getImpUid());

            if (isApproved) {
                paymentService.update(payment.getId(), PAID);
                creditService.charge(payment.getUserId(), payment.getAmount());
            } else {
                paymentService.update(payment.getId(), FAILED);
            }
        }
    }
}

두 방식을 나란히 놓고 보면

크레딧 결제 포트원 결제

외부 API ❌ 없음 ✅ 있음 (포트원)
트랜잭션 설계 하나로 묶기 쪼개서 분리
롤백 시 깨끗하게 원상복구 기록 손실 위험
핵심 전략 @Transactional 하나 PENDING + 상태 업데이트

마무리하며

처음에는 두 방식을 동일하게 생각했다. 결제니까 다 똑같이 @Transactional로 묶으면 되겠다 했는데 외부 api가 끼어들면 위험하다는 것을 알았다.

@Transactional의 롤백은 우리 DB에만 적용된다는 것, 외부 API는 절대 롤백할 수 없다는 것. 이 두 가지 사실이 트랜잭션 설계의 중요점이다.

외부 API가 포함된 결제 로직에서 @Transactional을 하나로 묶는 건 위험하다. 트랜잭션을 쪼개고, 기록을 먼저 남겨라.

 

백준 문제 바로가기

실버2

2주동안 BFS/DFS 문제를 쉬운 것 부터 풀어보고 실버 -> 골드까지 풀어볼 예정이다.

먼저 해당 유형의 기본 문제를 풀어보자.

 

 

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

 

 

풀이

길이 기록용 리스트를 1로 만들어서 각 요소의 길이를 기록

i와 j를 사용해서 현재값i과 이 전 값들(j들)의 요소 크기를 비교하고 현재값이 크다면 이전 값 요소의 길이 + 1과 현재값을 비교해서 큰 값을  현재값의 길이로 저장.

이 전 값들의 데이터를 재사용하여 dp로 풀 수 있다.

import sys
input = sys.stdin.readline

N = int(input())

lst = list(map(int, input().split()))

# lst 수열과 같은 수열을 만들어
lenlst = [1] * len(lst)

#i번째랑 이 전 값을 비교해서 크면 lenlst에 길이로 큰 값을 저장, 작으면 ㅃㅇ
#max()로 비교해서 넣는 이유는 현재 자신의 길이값 vs 나보다 작은 요소의 길이 뒤에 붙으면 큰 값 중 큰 것에 붙는 것

for i in range(len(lst)):
  j = 0
  for j in range(i):
    
    if lst[j] < lst[i] :
      lenlst[i] = max( lenlst[i], lenlst[j]+1 )

print(max(lenlst))

 

처음에 접근할 때에 어떻게 비교를 해야할지 판단이 안 섰다.

i를 늘려가면서 j를 0으로 초기화하고 i전까지 j하나씩 비교를 해가면 된다.

그리고 길이 리스트를 만들어서 1로 초기화해서 길이를 저장해두고, 

j<i일 때에 해당 j의 길이 뒤에 붙을 수 있기 때문에 i의 길이값을 j길이값+1 과 i길이값을 비교해서 큰 쪽에 붙는다.

 

*길이 수열 만들기, 탐색을 이중포문으로 현재값과 이전값 비교

 

*왜 이전값을 기준으로 탐색할까? 왜 다음 j는 i범위 전에서만 확인할까?

 i=0을 계산할 때 j=2(미래)를 참조하면

→ lenlst[2]는 아직 제대로 계산이 안 된 초기값 1

→ 나중에 lenlst[2]가 업데이트돼도 lenlst[0]은 이미 틀린 값으로 고정

i 이전에 있는 것들이 다 확정된 후에 계산되어야 하는데, range(len(lst))는 아직 확정 안 된 미래 값을 미리 참조해버리는 것이기 때문

백준 문제 바로가기

실버1

2주동안 BFS/DFS 문제를 쉬운 것 부터 풀어보고 실버 -> 골드까지 풀어볼 예정이다.

먼저 해당 유형의 기본 문제를 풀어보자.

 

 

 

문제

# 문제
1,2,3 더하기
정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
1+3
3+1
정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

# 입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

# 출력
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

 

 

풀이

Top-down 풀이

 

dp 딕셔너리 구조를 사용한다.

N을 나타내는 방법의 수를 구하려면 (N-1) + (N-2) + (N-3)을 구해야한다.

초기식은 3까지 구해놓는다.

import sys
input = sys.stdin.readline

#갯수 입력
N = int(input())

#Top-dowm
memo = {}

def dfs(K) :
  #base case
  if K == 1 : return 1
  if K == 2 : return 2
  if K == 3 : return 4

  #memo
  if K in memo:
    return memo[K]

  #memoization
  if K not in memo:
    memo[K] = dfs(K-1) + dfs(K-2) + dfs(K-3)
    return memo[K]
  
for _ in range(N):
  K = int(input())
  print(dfs(K))

 

 

 

bottom-up 풀이

dp[] 배열 자료구조를 사용한다. 탑다운은 필요한 것만 계산하되 느리지만, 바텀업은 전부를 계산하되 빠르다. 이 문제는 최대가 10이므로 이 방법이 더 적절할 수 있다.

 

빈 배열을 크기에 맞게 먼저 선언한다

dp[3]까지 초기식에 값을 넣어준다.

점화식 - 범위의 수를 미리 다 계산한다.

이후에 바로 찾아서 리턴한다.

#갯수 입력
N = int(input())

#배열
dp = [0] * 11

#초기식
dp[1] = 1
dp[2] = 2
dp[3] = 4

#점화식 - 미리 다 계산
for i in range(4, 11) :
  dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

for _ in range(N) :
  k = int(input())
  print(dp[k])

서비스 소개

이 프로젝트는 청년 커뮤니티 공간을 운영하는 공공기관 웹 서비스입니다.

공유주방, 라운지, 의사당 같은 공간을 온라인으로 신청하고 관리자가 검토 후 승인/거절하는 방식으로 운영되고 있습니다.

 

공공기관 특성상 서비스가 중단되면 된다고 생각했습니다. 그래서 AWS ALB(Application Load Balancer) 뒤에 서로 다른 가용 영역 EC2 인스턴스 2대를 배치해 고가용성 구조를 만들었습니다.

  인터넷                                                                                                                                                                                                          
    ↓                                                                                           
  ALB (Application Load Balancer)                                                                                                                                                                                 
    ├── EC2 Instance 1 (ap-northeast-2a)  ← 가용 영역 A                                         
    └── EC2 Instance 2 (ap-northeast-2c)  ← 가용 영역 C                                                                                                                                                           
                ↓                                                                                                                                                                                                 
         MongoDB Atlas (Replica Set)

인스턴스 하나가 죽어도 ALB 헬스체크가 이를 감지하고 나머지 인스턴스로 트래픽을 자동 전환합니다.

하지만 2대가 동시에 실행된다는 환경이 예약 승인 과정에서 동시성 문제를 만들어냈습니다.

 

예약 시스템의 구조

공간 대여는 30 단위 슬롯, 최대 연속 3시간(6슬롯) 으로 신청할  있습니다.

신청 - 승인 흐름은 아래와 같이 진행됩니다.

사용자 신청 → pending(대기)                                                                   
                    ↓                                                                                                                                                                                             
           관리자 검토                                                                          
           ├── approved(승인)                                                                                                                                                                                     
           ├── rejected(거절)                                                                   
           └── cancelled(취소)

 

중요한 설계 결정이 하나 있습니다. 같은 시간대에 여러 개의 pending 신청이 공존하는 것을 의도적으로 허용했습니다.

관리자가 검토하기 전까지는 누가 그 시간대를 사용할지 확정되지 않기 때문입니다. 실제 공간 점유 여부는 오직 approved 상태만을 기준으로 판단합니다.

// Rental.js - checkAvailability()                                                            
  async checkAvailability(spaceType, date, startTime, endTime) {                                                                                                                                                  
    const conflictingRentals = await this.collection.find({                                                                                                                                                       
      spaceType,                                                                                                                                                                                                  
      date,                                                                                                                                                                                                       
      status: 'approved',  // approved만 충돌 대상으로 본다                                     
      $or: [
        { startTime: { $lte: startTime }, endTime: { $gt: startTime } },
        { startTime: { $lt: endTime },    endTime: { $gte: endTime } },                                                                                                                                           
        { startTime: { $gte: startTime }, endTime: { $lte: endTime } }
      ]                                                                                                                                                                                                           
    }).toArray();                                                                               
                                                                                                                                                                                                                  
    return conflictingRentals.length === 0;                                                     
  }

 

 

문제

문제가 되는가 — TOCTOU Race Condition 

아래는 관리자 승인 로직입니다.

// rentalController.js - 관리자 승인 처리
  const updateRentalStatus = async (req, res) => {                                                                                                                                                                
    const { id } = req.params;                                                                                                                                                                                    
    const { status } = req.body;  // 'approved' or 'rejected'                                                                                                                                                     
                                                                                                                                                                                                                  
    const rentalData = await rental.findById(id);                                               
                                                                                                                                                                                                                  
    if (status === 'approved') {                                                                
      // STEP 1. 해당 시간대에 이미 승인된 예약이 있는지 확인 (READ)
      const isAvailable = await rental.checkAvailability(                                                                                                                                                         
        rentalData.spaceType,
        rentalData.date,                                                                                                                                                                                          
        rentalData.startTime,                                                                   
        rentalData.endTime                                                                                                                                                                                        
      );                                                                                        

      if (!isAvailable) {
        return res.status(409).json(
          createErrorResponse('해당 시간대에 이미 승인된 예약이 있습니다.')
        );                                                                                                                                                                                                        
      }
    }                                                                                                                                                                                                             
                                                                                                
    // STEP 2. 상태를 approved로 변경 (WRITE)                                                                                                                                                                     
    const updatedRental = await rental.updateStatus(id, status);
                                                                                                                                                                                                                  
    return res.status(200).json(createSuccessResponse('승인 완료', { rental: updatedRental }));                                                                                                                   
  };

 

코드를 읽으면 논리적으로 문제없어 보입니다. 확인하고 → 승인하는 구조입니다. 그런데 STEP 1과 STEP 2 사이에 아무런 보호 장치가 없습니다. 이 두 줄이 완전히 분리된 별개의 DB 연산이라는 게 문제의 핵심입니다.

 

이 문제를 TOCTOU(Time-Of-Check-Time-Of-Use) 라고 부릅니다. 확인(Check)하는 시점과 실제로 사용(Use)하는 시점이 다르기 때문에 그 사이에 상태가 바뀔 수 있다는 의미입니다.

단일 서버 환경에서 Node.js는 단일 스레드 이벤트 루프로 동작하기 때문에 이 문제가 실제로 발생할 가능성이 낮습니다. 그러나 ALB 뒤에 EC2가 2대 있는 지금 환경은 다릅니다.

ALB는 들어오는 요청을 두 인스턴스에 번갈아가며 분배합니다. 두 관리자가 거의 동시에 승인 버튼을 누르면 각각 다른 인스턴스가 요청을 받아 동시에 처리합니다.

 

전제: 공유주방 10:00~12:00 시간대에 pending 상태의 신청 A와 신청 B가 존재

관리자 Park이 신청 A를 승인 → ALB가 Instance 1으로 라우팅                                                                                                              관리자 Choi가 신청 B를 승인 → ALB가 Instance 2로 라우팅                                                                                                               

 

T=0ms  Instance 1: checkAvailability('공유주방', '2026-03-30', '10:00', '12:00') → DB 조회: approved인 예약 없음 → true 반환

T=1ms  Instance 2: checkAvailability('공유주방', '2026-03-30', '10:00', '12:00') → DB 조회: approved인 예약 없음 → true 반환 (Instance 1이 아직 approved로 바꾸기 전이라 없는 것으로 읽힘)

 

T=2ms  Instance 1: updateStatus(A, 'approved') → 성공                                                                                                              T=3ms  Instance 2: updateStatus(B, 'approved') → 성공 ← 이중 승인 발생

                                                                            

최종 DB 상태:                                                                                 

    신청 A: approved (공유주방 10:00~12:00)

    신청 B: approved (공유주방 10:00~12:00) ← 같은 시간대에 개의 approved 존재 

 

두 관리자 모두 409 에러 없이 200 성공 응답을 받습니다. 서비스 입장에서는 같은 공간, 같은 날짜, 같은 시간대에 두 명의 사용자가 승인된 상태로 공존하게 되는겁니다. 공공기관 서비스에서 이런 데이터 정합성 오류는 심각한 민원으로 이어질 있습니다.

 

해결 방법 탐색

방법 1: MongoDB 트랜잭션

가장 먼저 떠오른 방법이었습니다. MongoDB Atlas는 Replica Set 기반이라 트랜잭션을 지원합니다. STEP 1과 STEP 2를 하나의 트랜잭션으로 묶으면 되지 않을까 생각했습니다.

const session = client.startSession();                                                                                                                                                                          
  session.startTransaction();                                                                   

  try {
    const isAvailable = await checkAvailability(..., { session });
    if (!isAvailable) throw new ConflictError();                                                                                                                                                                  
    await updateStatus(id, 'approved', { session });
    await session.commitTransaction();                                                                                                                                                                            
  } catch (e) {                                                                                 
    await session.abortTransaction();                                                                                                                                                                             
  }

 

MongoDB 트랜잭션의 격리 수준은 Snapshot Isolation(스냅샷 격리) 입니다. 트랜잭션이 시작되는 순간의 DB 스냅샷을 기준으로 데이터를 읽습니다.                                                                    

 

문제는 Instance 1은 신청 A를 approved로 바꾸고, Instance 2는 신청 B를 approved로 바꾼다는 점입니다. 즉, 서로 다른 도큐먼트를 수정합니다. MongoDB는 다른 도큐먼트를 동시에 수정하는 두 트랜잭션에 대해 충돌로 인식하지 않습니다.

                                                                       

이를 데이터베이스 이론에서 Write Skew(쓰기 왜곡) 라고 합니다. 두 트랜잭션이 공유 조건(같은 시간대에 approved가 없어야 한다)을 각자 확인하고 각자 다른 도큐먼트를 수정하면서 그 조건을 깨뜨리는 이상 현상입니다.

Snapshot Isolation은 이 문제를 원천적으로 방지하지 못합니다.

 

방법 2: Redis Redlock (분산 락)                                                                   

두 인스턴스가 공유할 수 있는 외부 락을 도입하는 방법입니다. Redis의 SET NX(값이 없을 때만 저장) 특성을 활용해 분산 환경에서 락을 구현하는 Redlock 알고리즘이 이 목적에 적합합니다.

// AWS ElastiCache(Redis) 도입 후                                                                                                                                                                               
  const redlock = new Redlock([redisClient]);                                                                                                                                                                     
                                                                                                                                                                                                                  
  const lock = await redlock.acquire(                                                                                                                                                                             
    [`lock:rental:공유주방:2026-03-30`],  // 락 키                                                                                                                                                                
    5000  // 5초 안에 처리 못 하면 자동 해제 (데드락 방지)                                                                                                                                                        
  );                                                                                                                                                                                                              
                                                                                                                                                                                                                  
  try {                                                                                                                                                                                                           
    const isAvailable = await checkAvailability(...);                                           
    if (!isAvailable) throw new ConflictError();
    await updateStatus(id, 'approved');                                                                                                                                                                           
  } finally {
    await lock.release();                                                                                                                                                                                         
  }

                                                                                                             

Instance 1이 이 키로 락을 잡으면 Instance 2는 같은 키로 락을 시도할 때 Redis에서 이미 점유됨을 확인하고 대기하거나 즉시 실패를 반환합니다. Instance 1이 처리를 완료하고 락을 해제한 뒤에야 Instance 2가 진행할 수 있습니다.

 

기술적으로는 정석적인 해결책입니다. 그러나 AWS ElastiCache 인스턴스 추가가 필요합니다. 인프라 운영 포인트가 늘어나고 비용도 발생합니다. 무엇보다 이 서비스에서 두 관리자가 밀리초 단위로 동시에 같은 시간대를 승인할 현실적인 빈도를 생각했을 때 그 비용이 합리적인지 의문이 들었습니다.

 

물론 트래픽이 커지거나 관리자가 늘어난다면 Redis 도입이 필수가 됩니다. 현 시점에서는 더 가벼운 해결책을 먼저 탐색하기로 했습니다.

 

방법 3: 데이터 모델 변경 + findOneAndUpdate 원자 연산

문제를 다른 각도에서 바라봤습니다. Race Condition이 발생하는 근본 원인은 확인과 점유가 두 번의 분리된 연산이기 때문입니다. 이 두 단계를 하나의 연산으로 합칠 수 있다면 어떨까 생각했습니다.                           

                                                                                                

MongoDB의 findOneAndUpdate는 filter 조건 평가와 update 적용이 MongoDB 서버 내부에서 하나의 분리 불가능한 단위로 실행됩니다. 즉, filter를 평가하는 도중에 다른 연산이 끼어들 수 없습니다.

                                                                                                                                                                                                           

두 인스턴스가 동시에 이 연산을 요청해도 MongoDB는 같은 도큐먼트에 대한 write를 직렬로 처리합니다. 먼저 처리된 요청이 도큐먼트를 수정하고, 이후 요청은 이미 바뀐 도큐먼트를 보고 filter 불일치로 실패를 반환받습니다.

                                                                                                                                                                                                             이를 적용하려면 예약 가능 여부와 슬롯 점유를 같은 도큐먼트에서 처리할 수 있는 데이터 구조가 필요했습니다. 이 서비스는 30분 단위 슬롯이라는 제약이 있기때문에 날짜별, 공간별로 슬롯 상태를 하나의 도큐먼트에 담을 수 있었습니다.

 

구현

1. daily_slots 컬렉션

하루치 슬롯 상태를 도큐먼트 하나에 담았습니다.

// daily_slots 컬렉션 도큐먼트 예시                                                                                                                                                                             
  {                                                                                             
    _id: ObjectId("..."),                                                                                                                                                                                         
    spaceType: '공유주방',
    date: '2026-03-30',                                                                                                                                                                                           
    slots: {                                                                                    
      '09:00': null,           // null = 예약 가능                                                                                                                                                                
      '09:30': null,                                                                                                                                                                                              
      '10:00': 'rentalId_A',  // rentalId 문자열 = 해당 예약이 점유 중                                                                                                                                            
      '10:30': 'rentalId_A',                                                                                                                                                                                      
      '11:00': 'rentalId_A',                                                                    
      '11:30': 'rentalId_A',                                                                                                                                                                                      
      '12:00': null,                                                                            
      '12:30': null,                                                                                                                                                                                              
      '13:00': null,
      // ... 운영 시간 끝까지                                                                                                                                                                                     
      '21:30': null                                                                                                                                                                                               
    }
  }

30분 단위로 09:00부터 21:30까지 총 26개의 슬롯이 있습니다. 점유된 슬롯에는 어떤 렌탈 ID가 사용 중인지 기록합니다. 하루의 전체 예약 현황을 이 도큐먼트 하나만 읽으면 즉시 파악할 수 있습니다.

 

2. 승인 로직 핵심 - 확인과 점유를 단일 원자 연산으로

  // filter: 필요한 슬롯이 모두 null인 경우에만 매칭 (확인)                                                                                                                                                       
  // update: 해당 슬롯을 rentalId로 채움 (점유)                                                                                                                                                                   
  // 이 두 단계가 MongoDB 내부에서 하나의 단위로 실행됨                                                                                                                                                           
                                                                                                                                                                                                                  
  const claimed = await db.collection('daily_slots').findOneAndUpdate(                                                                                                                                            
    { spaceType, date, 'slots.10:00': null, 'slots.10:30': null, ... },                                                                                                                                           
    { $set: { 'slots.10:00': rentalId, 'slots.10:30': rentalId, ... } }                                                                                                                                           
  );
                                                                                                                                                                                                                  
  if (!claimed) {                                                                                                                                                                                                 
    // filter 불일치 = 슬롯이 이미 점유됨
    return res.status(409).json(createErrorResponse('이미 승인된 예약이 있습니다.'));                                                                                                                             
  }

 

이 연산이 동시에 두 인스턴스에서 실행되면:                                                                                                                                           Instance 1: filter 평가 → 슬롯 모두 null → $set 적용 → 성공                                                                                                    Instance 2: filter 평가 → 슬롯이 이미 rentalId → 조건 불일치 → null 반환 → 409                                                                              두 컬렉션의 일관성은 트랜잭션으로 보장됩니다.                            

 

슬롯 점유 성공 후 서버가 죽으면 daily_slots은 점유됐지만 rentals는 여전히 pending인 불일관 상태가 됩니다. 두 작업을 트랜잭션으로 묶어 All or Nothing을 보장했습니다.                        

여기서 트랜잭션의 역할을 명확히 구분하는 것이 중요합니다.                                                                                                                    findOneAndUpdate → Race Condition 방지                                                                                                                                     트랜잭션 컬렉션 데이터 일관성 보장 (All or Nothing) 

취소나 거절 처리에서도 슬롯을 null로 되돌리는 작업을 동일하게 트랜잭션으로 처리합니다.

session.startTransaction();                                                                                                                                                                                     
  try {                                                                                                                                                                                                           
    const claimed = await daily_slots.findOneAndUpdate(filter, update, { session });            
    if (!claimed) throw new ConflictError();                                                                                                                                                                      
   
    await rentals.updateOne({ _id }, { $set: { status: 'approved' } }, { session });                                                                                                                              
                                                                                                
    await session.commitTransaction(); // 둘 다 성공해야 확정                                                                                                                                                     
  } catch (e) {                                                                                 
    await session.abortTransaction();  // 하나라도 실패하면 둘 다 롤백                                                                                                                                            
  }

 

적용 전후 비교

[ 수정 전 구조]                                                                                 

                                                                                                                                                                                                                
  ALB                                                                                           
   ├─ Instance 1 ─→ checkAvailability()   ← READ  (별도 쿼리)
   │                      ↓                                                                                                                                                                                       
   │               updateStatus()         ← WRITE (별도 쿼리)                                                                                                                                                     
   │                                                                                                                                                                                                              
   └─ Instance 2 ─→ checkAvailability()   ← READ  ← 이 사이에 끼어들 수 있음                                                                                                                                      
                          ↓                                                                                                                                                                                       
                   updateStatus()         ← WRITE

결과: 두 인스턴스가 동시 처리 시 이중 승인 가능

 

[ 수정 후 구조 ]                                                                                 

ALB
  ├─ Instance 1 ─→ findOneAndUpdate(filter, $set)  ← READ+WRITE 단일 원자 연산
  │                                                                                                                                                                                                              
  └─ Instance 2 ─→ findOneAndUpdate(filter, $set)  ← MongoDB가 직렬 처리

결과: 먼저 처리된 인스턴스만 성공, 나머지는 구조적으로 409 반환. 인스턴스가 몇 대로 늘어나도 동일하게 보장됩니다.

 

 

가용 여부 조회 변화    

[ 수정 전 ]

rentals 컬렉션 스캔 + 시간 범위 겹침을 3가지 케이스로 계산                                                                 

  const conflicts = await rentals.find({                                                                                                                                                                          
    spaceType, date, status: 'approved',
    $or: [ ...시간 겹침 3가지 케이스... ]                                                                                                                                                                         
  }).toArray();


[ 수정 후 ]

슬롯 도큐먼트 하나 조회 + null 여부만 확인

const doc = await daily_slots.findOne({ spaceType, date });                                   
const isAvailable = requiredSlots.every(slot => doc.slots[slot] === null);

 

캘린더 렌더링처럼 가용 여부를 반복 조회하는 경우 특히 차이가 납니다. 이전에는 매 요청마다 rentals 컬렉션을 스캔하고 복잡한 시간 겹침 계산을 해야 했지만, 이제는 슬롯 도큐먼트 하나를 읽으면 그날의 전체 현황을 즉시 파악할 수 있습니다.

 

 

해결한 문제 정리                                                                              

 

  Before

    - 분산 서버 환경에서 이중 승인 가능

    - 동시성 문제 발생 여부를 코드만 보고 예측하기 어려움

    - 가용 여부 확인 시 rentals 컬렉션 스캔 필요                                                                                                                                          

  After  

    - findOneAndUpdate 원자 연산으로 이중 승인 구조적 불가  

    - MongoDB Atlas 트랜잭션으로 두 컬렉션 일관성 보장 

    - 슬롯 도큐먼트 단일 조회로 가용 여부 확인              

    - 인스턴스가 N대로 늘어나도 동일하게 보장

 

남은 과제와 앞으로의 개선 방향 

현재는 특정 날짜의 첫 번째 예약 신청이 들어오는 시점에 daily_slots 도큐먼트를 생성하고 있습니다. 두 인스턴스가 동시에 최초 요청을 처리하면 생성 시점에도 미세한 race condition이 발생할 수 있습니다.

매일 자정 향후 N일치 슬롯 도큐먼트를 일괄 생성해두면 생성 시점의 문제가 제거됩니다. 더 나아가 공휴일 예약 불가, 특정일 운영 중단 같은 운영 정책을 슬롯 생성 단계에서 통합 관리할 수 있어 정책 변경이 생겨도 슬롯 생성 로직 한 곳만 수정하면 되는 구조로 발전시킬 수 있습니다.

백준 문제 바로가기

실버1

2주동안 BFS/DFS 문제를 쉬운 것 부터 풀어보고 실버 -> 골드까지 풀어볼 예정이다.

먼저 해당 유형의 기본 문제를 풀어보자.

문제

문제:
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.


입력: 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력: 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

예제: 5 17
예제 출력: 4

힌트: 수빈이가 5-10-9-18-17 순으로 가면 4초만에 동생을 찾을 수 있다.

 

풀이

#최단거리 찾기
#초는 움직인 수 카운트
#K에 도달할 수 있는 방법 중 가장 빨리 도착하는 것을 찾으면 됨
# 간선 루프 돌 수 있으니 방문 리스트를 만들어 표시해
# 탐색 범위가 0 ≤ N ≤ 100,000 이므로 방문리스트의 크기는 100,001개

#BFS
#수빈과 동생 위치 입력받고
# 방문 리스트 만들어
#이동위치 N+1, N-1 , N*2
#큐에 수빈 위치 넣어. + 카운트(시간)도 / 시작 위치 방문했으니 큐 넣을 때에 true
#큐 빌동안 팝, 카운트 1 하고, 이동위치로 이동해봐.
#팝 했을 때 K랑 동일하면 out, 카운트 리턴
#예외? N,K 위치가 같은 경우 -> 0, K의 위치가 0인 경우..?

 

최단거리 구하는거니까 BFS로 풀어야겠다고 생각함.

계단문제처럼 DP쓰면 안되나? 했는데 사이클이 있어서 뱅뱅 돌 수 있으니 BFS.

그리고 방문했던 곳을 다시 방문하면 무한루프 돌 수 있으니 방문 리스트 만들어서 표시해둬야 함.

 

 

코드

from collections import deque
import sys
input = sys.stdin.readline

N,K = map(int, input().split())

visited = [False] * 100001

def bfs (N,K) :
  q = deque()
  visited[N] = True
  q.append((N, 0))

  while q: 
    x, time  = q.popleft()

    if x == K : 
      return time

    for nx in (x-1, x+1, x*2) :
      if 0<= nx <= 100000 and not visited[nx] :
        visited[nx] = True
        q.append((nx, time +1))

print(bfs(N,K))

 

- visited 배열의 크기를 범위에 맞게 만들어야 하는 구나 (여기선 0부터니까 0포함 100001), False로 초기화

- 방향을 반영해서 하나씩 꺼낼 때에 for nx in (n-1, n+1, n*1) 이런식으로 계산식을 만들어서 계산 한 뒤 하나씩 꺼내는 방법이 있군...

- 방문 표시는 큐에 넣을 때에 (방문 -> 인큐) 해야 함.

백준 문제 바로가기

 

2주동안 BFS/DFS 문제를 쉬운 것 부터 풀어보고 실버 -> 골드까지 풀어볼 예정이다.

먼저 해당 유형의 기본 문제를 풀어보자.

문제

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

 

입력

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.

토마토가 하나 이상 있는 경우만 입력으로 주어진다.

 

출력

여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

 

풀이

1. maxDay를 튜플 형태로 좌표와 함께 저장하는 방법

2. maxDay를 좌표값에 그대로 저장해서 넣는 방법

 

간단하게 bfs를 돌려보면 되겠구나 라고 생각했지만 익은 토마토(1)이 두 개 이상 있을 경우엔 어떻게 해야할까 고민됐다.

한 번에 1을 모두 큐에 넣고, 다 넣은 후에 한 번에 큐를 동시적으로 돌리면 될 것 같았다 !

 

처음에는 튜플 형태로 좌표와 함께 day를 저장했는데

다른 풀이를 보니까 메모리를 아낄 겸 좌표 자체에 day를 표시하는 방법도 배웠다.

 

먼저 1번으로 구현했을 때

# 좌표랑 같이 day를 저장함
# 한번에 큐에 넣기: 그리드를 이중 포문으로 돌면서 1인 것들을 다 넣어 , day는 0으로
# 큐 한번에 돌리기
# 팝하고 좌표 이동, 범위 안이고 그리드 좌표값이 0이면 인큐, 방문처리 1 하고, day를 + 1 함
# max_day를 구하는 법: 동시에 큐가 퍼지니까 가장 늦게 도착한 큐를 찾아야 최종적으로 토마토가 다 익은 것임. 그래서 max()사용
# max_day = 0 해놓고, 큐를 pop했을 때 max_day와 현재 팝한 좌표의 day를 비교해서 저장
# 출력에서 다시 이중 포문 돌면서 남은 0이 있나 확인 -> 있으면 -1 프린트, exit(), 포문 안에서는 break안된다
# 0이 없으면 max_day 출력

 

#day를 튜플로 같이 저장하는 방식

from collections import deque
import sys
input = sys.stdin.readline

M, N = map(int, input().split())
grid = []
q = deque()

for _ in range(N):
  grid.append(list(map(int, input().split())))

dir = [ (1,0), (0,1), (-1,0), (0,-1)]

# 처음에 1을 전부 queue에 넣어
for i in range(N) :
  for j in range(M):
    if grid[i][j] == 1:
      q.append((i,j,0))

max_day = 0

#BFS
while q:
  x, y, d = q.popleft()

  max_day = max(max_day, d)

  for ax, ay in dir :
    nx = ax + x
    ny = ay + y

    if 0 <= nx < N and 0 <= ny < M and grid[nx][ny] == 0 :
      q.append((nx, ny, d + 1))
      grid[nx][ny] = 1 #방문 익음 처리

#출력
for row in grid:
  if 0 in row :
    print(-1)
    exit()

print(max_day)

 

 

출력을 이중 포문으로 안 하고 저렇게 검사 형태로 해도 되는구나.. row를 뽑아서 0이 있는지 확인하는 법

 

 

 

2번으로 구현했을 때는 주의해야할 것이 있음.

# 1인 곳은 이미 익음(0일) -> 다음으로 익는 곳은 이전 곳의 + 1 (2일) -> ... 즉, 출력할 때는 일 수를 -1 해주어야 한다

 

# day를 좌표 값으로 입력하는 방법

from collections import deque
import sys
input = sys.stdin.readline

M, N = map(int, input().split())
grid = []
q = deque()

for _ in range(N):
  grid.append(list(map(int, input().split())))

dir = [ (1,0), (0,1), (-1,0), (0,-1)]

for i in range(N) :
  for j in range(M) :
    if grid[i][j] == 1 :
      q.append((i,j))

#bfs
while q:
  x, y = q.popleft()

  for ax, ay in dir :
    nx = ax + x
    ny = ay + y

    if 0 <= nx < N and 0 <= ny < M and grid[nx][ny] == 0 :
      q.append((nx, ny))
      grid[nx][ny] = grid[x][y] + 1

#출력
max_day = 0

for r in range(N) :
  for v in range(M):
    if grid[r][v] == 0 :
      print(-1)
      exit()

    max_day = max(max_day, grid[r][v])
  
print(max_day-1)

 

 

위에것이 2번, 아래것이 1번 방법으로 구현한 것. 메모리에서 조금 차이가 있다.

백준 문제 바로가기

 

2주동안 BFS/DFS 문제를 쉬운 것 부터 풀어보고 실버 -> 골드까지 풀어볼 예정이다.

먼저 해당 유형의 기본 문제를 풀어보자.

문제

N×M크기의 배열로 표현되는 미로가 있다.

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다.

이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오.

한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다.

다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

풀이

#최단거리 - bfs
#시작위치부터 dist 1, 1로만 지나다녀야 하고 상하좌우 움직일 수 있음
#1,1부터 시작해서 (N(세로 y),M(가로 x))에서 break
# 좌표와 거리를 함께 저장하여 넘겨, 좌표 이동할때 거리 + 1

from collections import deque
import sys
input = sys.stdin.readline

N, M = map(int, input().split())

#grid
grid = []

for _ in range(N) :
  grid.append(list(map(int, input().strip()))) #공백없는 입력은 strip

dir = [(1,0), (0,1), (0, -1), (-1, 0)]

def bfs(a, b, dist) :
  q = deque()
  q.append((a,b,dist))
  grid[a][b] = 0

  while q:
    a, b, dist = q.popleft()

    # 도달
    if a == N-1 and b == M-1:
      return dist

    for x, y in dir :
      nx = a + x
      ny = b + y

      if nx >= 0 and nx < N and ny >= 0 and ny < M and grid[nx][ny] == 1:
        q.append((nx, ny, dist + 1))
        grid[nx][ny] = 0

  return dist

result = bfs(0,0,1)
print(result)

 

헷갈리는 것:

입력받을 때 공백이 있는 경우는 split()으로 받고, 없는 경우는 strip()으로 받기

+ Recent posts