LMS 서비스를 운영하던 중 한 가지 문제를 발견했다. 동일한 사용자가 같은 과제에 대해 "제출" 버튼을 빠르게 두 번 누르면, 과제가 두 번 저장되는 현상이 생기는 것이다. 코드를 들여다보니 원인은 단순했다.

@Transactional
public SubmissionResponse submitAssignment(...) {
    // 중복 체크
    validationUtils.validateDuplicateSubmission(userId, planId);

    // 저장
    submissionRepository.save(submission);
}

중복 체크를 통과한 뒤 저장하는 구조 자체는 자연스럽다. 문제는 요청 A와 B가 거의 동시에 들어올 때다. 둘 다 1번을 통과한 뒤 둘 다 2번을 실행한다. 전형적인 race condition이다.

이 글에서는 이 문제를 JPA의 비관적 락으로 해결하는 과정을 정리하고, 같은 종류의 문제를 이전에 Redis 분산 락으로 해결했던 경험과 비교해 두 방식이 언제 어떻게 다른지 분석해본다.

1. Race Condition이란?

경쟁 상태(Race Condition) 란 여러 요청(또는 스레드, 프로세스)이 공유 자원에 거의 동시에 접근할 때, 실행 순서에 따라 결과가 달라지는 현상을 말한다. 이름 그대로 "누가 먼저 도착하느냐의 경주(race)"가 프로그램의 정확성을 좌우하게 되는 상황이다.

핵심은 "검사와 실행 사이의 틈"

race condition이 발생하는 전형적인 패턴은 Check-Then-Act다. 어떤 조건을 검사한 뒤(Check) 그 결과를 바탕으로 동작하는(Act) 구조에서, 검사와 동작 사이에 다른 요청이 끼어들면 검사 결과가 무효가 된다.

과제 제출 코드로 돌아가보자.

validationUtils.validateDuplicateSubmission(userId, planId);  // Check
submissionRepository.save(submission);                          // Act

요청 하나만 있을 때는 아무 문제가 없다. 이미 제출한 사용자가 다시 요청하면 Check 단계에서 예외가 터지고, 처음 제출하는 사용자는 Check를 통과해 Act로 넘어간다.

그런데 요청 A와 B가 거의 동시에 들어오면 이야기가 달라진다. A가 Check를 통과하는 순간, 아직 A의 Act(INSERT)는 실행되기 전이다. 바로 그 찰나에 B도 Check를 실행하면 B 역시 "제출 기록이 없다"는 결과를 받게 된다. 그 뒤 A와 B가 각자의 Act를 실행하면 두 건의 INSERT가 모두 성공한다. 두 요청 모두 자기 기준에서는 올바르게 동작했지만, 결과적으로는 중복 row가 생긴다. 이것이 전형적인 race condition이다.

왜 코드만 봐서는 안 보이는가

race condition의 위험한 점은 단일 스레드로 코드를 읽으면 버그가 전혀 보이지 않는다는 것이다. 위 두 줄은 누가 봐도 "제출 여부를 확인하고 저장한다"는 올바른 로직이다. 문제는 이 두 줄이 원자적으로 실행되지 않는다는 점인데, 이는 코드의 문법이 아니라 실행 모델의 특성이다.

그래서 race condition은 테스트로도 잘 잡히지 않는다. 단위 테스트는 보통 한 스레드로 순차 실행하므로 틈이 생기지 않는다. 실제 운영 환경에서 트래픽이 몰릴 때만 드물게 재현되고, 재현이 어려우니 원인 파악도 까다롭다.

해결의 방향

race condition을 없애는 방법은 크게 세 가지다.

• 공유 자원 자체를 없앤다 — 각 요청이 독립된 자원을 쓰도록 설계를 바꾼다. 가능하면 가장 깔끔하지만, 중복 제출처럼 본질적으로 공유될 수밖에 없는 자원에는 적용할 수 없다.
• 원자적 연산으로 만든다 — Check와 Act를 DB 제약조건(unique index)으로 합치거나, INSERT ... ON DUPLICATE KEY 같은 원자적 구문을 사용한다. 단순한 경우에 효과적이다.
• 검사-실행 구간을 직렬화한다 — Check-Then-Act 구간을 한 번에 한 요청만 들어갈 수 있도록 락으로 감싼다. 비관적 락이 바로 이 방식이다.

이 글에서 다루는 비관적 락은 세 번째 접근이다. "검사와 실행 사이의 틈"을 락으로 메워서, 한 요청이 Check와 Act를 끝낼 때까지 다른 요청이 아예 들어오지 못하게 막는다.

2. 비관적 락이란

낙관적 락과의 대비

동시성 제어는 크게 두 가지 철학으로 나뉜다.

• 낙관적 락(Optimistic Lock): "충돌은 거의 일어나지 않을 것"이라 가정한다. 일단 작업을 진행하고, 커밋 시점에 version 컬럼을 비교해 충돌을 감지한다. 충돌 시 예외를 던지거나 재시도한다.

• 비관적 락(Pessimistic Lock): "충돌이 반드시 일어날 것"이라 가정한다. 데이터를 읽는 순간부터 다른 트랜잭션의 접근을 아예 차단한다.

비관적 락은 물리적으로 동시 접근을 직렬화한다. 줄을 서서 한 명씩 들어가는 것과 같다.

언제 비관적 락을 쓰는가

• 충돌 빈도가 높아서 낙관적 락의 재시도 비용이 커지는 경우
• 중복 제출, 재고 차감, 좌석 예약처럼 "두 번 통과하면 안 되는 불변식" 이 있는 경우
• 짧은 임계구역에서 강한 일관성이 필요할 때

비관적 락의 비용

공짜가 아니다. 락을 잡고 있는 동안 다른 요청은 대기해야 하므로 처리량이 떨어지고, 잘못 설계하면 데드락이 생기며, DB 커넥션을 오래 붙잡고 있어 커넥션 풀을 고갈시킬 수 있다. 그래서 락 점유 시간을 최대한 짧게 유지하는 것이 핵심 원칙이다.

2. JPA 비관적 락으로 해결하기

코드 변경 — Repository

먼저 Plan을 락과 함께 조회하는 메서드를 추가한다.

@Lock(LockModeType.PESSIMISTIC_WRITE)
@Query("SELECT p FROM Plan p WHERE p.planId = :planId")
Optional<Plan> findByIdWithPessimisticLock(@Param("planId") Long planId);

@Lock(LockModeType.PESSIMISTIC_WRITE)는 하이버네이트에게 "이 쿼리를 실행할 때 SQL에 FOR UPDATE를 붙여라"라고 지시한다. 결과적으로 실제 DB에 나가는 SQL은 다음과 같다.

SELECT * FROM plan WHERE plan_id = ? FOR UPDATE

FOR UPDATE가 붙은 순간 해당 Plan row에는 배타 락이 걸린다. 같은 row를 FOR UPDATE로 읽으려는 다른 트랜잭션은 현재 트랜잭션이 커밋되거나 롤백될 때까지 DB 레벨에서 대기한다.

JPA의 락 모드는 세 가지가 있다.

• PESSIMISTIC_READ: SELECT ... FOR SHARE — 읽기는 공유하지만 쓰기는 차단
• PESSIMISTIC_WRITE: SELECT ... FOR UPDATE — 읽기/쓰기 모두 차단
• PESSIMISTIC_FORCE_INCREMENT: 위에 더해 version 컬럼을 강제로 증가

중복 제출 방지에는 배타적 접근이 필요하므로 PESSIMISTIC_WRITE가 적절하다.

코드 변경 — Service

서비스 메서드에서 락 획득을 중복 체크보다 앞에 배치한다.

@Transactional
public SubmissionResponse submitAssignment(Long groupId, Long planId, ...) {
    User user = validationUtils.validateMenteeAccess(groupId, studentNumber);
    Plan plan = validationUtils.validatePlan(planId);

    // Plan 행에 비관적 락 획득 - 동시 제출 요청을 직렬화하여 중복 제출 race condition 방지
    planRepository.findByIdWithPessimisticLock(planId)
            .orElseThrow(() -> new RestApiException(ErrorCode.PLAN_NOT_FOUND));

    // 과제 제출 중복 여부 체크
    validationUtils.validateDuplicateSubmission(user.getUserId(), planId);

    // 저장
    AssignmentSubmission submission = ...;
    return SubmissionResponse.from(submissionRepository.save(submission));
}

이 코드에서 주목해야 할 점이 세 가지 있다.

(1) 락으로 가져온 Plan을 변수에 받지 않는다

findByIdWithPessimisticLock의 반환값을 변수에 담지 않고 .orElseThrow만 호출한 뒤 버린다. 이것은 의도적인 설계다. 이 쿼리의 목적은 Plan의 필드를 읽는 것이 아니라 FOR UPDATE로 락을 거는 부수효과이기 때문이다. Plan의 실제 데이터는 이미 앞 줄의 validatePlan이 가져왔다. 비관적 락 패턴을 처음 보면 어색하게 느껴지는데, "SELECT가 목적이 아니라 락이 목적"이라는 관점에서 보면 자연스럽다.

(2) 왜 Plan에 락을 거는가

중복이 생기는 단위는 "같은 Plan + 같은 User"다. 그런데 락을 AssignmentSubmission에 걸 수는 없다. 아직 존재하지 않는 row이기 때문이다(지금 막 INSERT 하려는 중). 그래서 이미 존재하는 부모 엔티티인 Plan row를 락의 게이트키퍼로 사용한다. 이는 비관적 락 설계의 자주 쓰이는 패턴이다. "새로 만들 자식이 충돌할 수 있다면, 공통된 부모 row를 잠근다."

(3) 순서가 곧 의미다

락 획득 → 중복 체크 → save. 이 순서가 뒤집히면 락의 의미가 사라진다. 만약 중복 체크를 먼저 하면 그건 락 잡기 전의 상태를 읽은 것이라 의미가 없다. 락을 먼저 잡아야 "이 시점 이후로 같은 Plan에 접근하는 모든 요청이 내 뒤에 줄 선다"가 보장되고, 그때부터 하는 중복 체크만 신뢰할 수 있다.

동시 요청 시 실제 흐름

요청 A와 B가 거의 동시에 들어온다고 하자.

1. A가 findByIdWithPessimisticLock(planId) 호출 → Plan row 락 획득
2. B가 같은 메서드 호출 → A의 락 때문에 DB 내부에서 대기
3. A가 중복 체크 통과 → save → 트랜잭션 커밋 → 락 해제
4. B의 SELECT가 그제서야 풀림 → B는 A가 커밋한 데이터까지 본다 → 중복 체크에서 탈락 → 예외

FOR UPDATE는 MVCC 환경에서도 스냅샷이 아닌 최신 커밋 상태를 읽도록 강제하므로, B는 A의 결과를 반드시 본다. 이것이 비관적 락이 만드는 직렬화의 본질이다.

락 해제를 신경 쓰지 않아도 되는 이유

위 코드 어디에도 unlock() 같은 호출이 없다. @Transactional 메서드가 끝나면 정상 커밋이든 예외 롤백이든 DB가 트랜잭션을 종료하면서 잡고 있던 모든 락을 함께 해제한다. 즉 락의 생명주기 = 트랜잭션의 생명주기다. 개발자는 락 해제를 신경 쓸 필요가 없고, 중간에 예외가 터져도 락이 남지 않는다. 이 점은 뒤에서 볼 Redis 분산 락과 가장 크게 대비되는 지점이다.

3. 이중 방어선 — 집계 쿼리도 함께 수정한다

락이 완벽하게 동작해도 과거 데이터에 이미 중복이 쌓여 있을 수 있다. 락은 지금 이후의 중복만 막기 때문이다. 그래서 통계 API도 함께 손봐야 한다.

// Before: 단순 COUNT - 중복 제출이 있으면 한 사람이 여러 번 카운트됨
int submittedCount = submissionRepository
        .countByPlanPlanIdAndStatus(planId, SUBMITTED);

// After: 고유 제출자 수 - 설령 중복이 섞여 있어도 인원 수로 환산됨
int submittedCount = submissionRepository
        .countDistinctSubmittersByPlanIdAndStatus(planId, SUBMITTED);

실제 쿼리는 다음과 같다.

@Query("SELECT COUNT(DISTINCT a.submitter.userId) FROM AssignmentSubmission a " +
       "WHERE a.plan.planId = :planId AND a.status = :status")
int countDistinctSubmittersByPlanIdAndStatus(
        @Param("planId") Long planId,
        @Param("status") SubmissionStatus status);

COUNT(*)을 COUNT(DISTINCT submitter_id)로 바꾸면 row 수가 아니라 사람 수를 센다는 불변식이 생긴다. 한 사람이 두 번 제출했더라도 통계에서는 한 명으로 카운트된다.

미제출자 계산도 함께 정비했다.

@Query("SELECT COUNT(DISTINCT a.submitter.userId) FROM AssignmentSubmission a " +
       "WHERE a.plan.planId = :planId " +
       "AND a.submitter.userId IN (" +
       "  SELECT gm.user.userId FROM GroupMember gm " +
       "  WHERE gm.studyGroup.studyId = :groupId " +
       "  AND gm.role = com.mjsec.lms.studygroup.domain.type.GroupMemberRole.MENTEE" +
       ")")
int countDistinctMenteeSubmittersByPlanIdAndGroupId(...);

notSubmittedCount = totalMentees - submittedMentees로 계산할 때, 제출자 쪽이 "현재 그룹에 속한 멘티"로 한정되지 않으면 탈퇴한 사용자나 역할이 바뀐 사용자 때문에 미제출자 수가 음수로 나올 수도 있다. 그래서 분모(totalMentees)와 분자(submittedMentees)의 기준을 "현재 이 그룹의 멘티" 로 일치시킨 것이다.

정리하면 두 개의 방어선을 깔았다.

• 락: 앞으로 들어올 요청에서 중복이 생기는 것을 차단 (미래 방어)
• 집계 쿼리: 이미 쌓였을 수도 있는 중복이 통계를 왜곡하지 않도록 흡수 (과거 방어)

시간축 양방향으로 방어선을 친 셈이다.

4. 테스트로 못 박은 계약

락을 적용할 때는 테스트로 불변식을 명시해두는 것이 중요하다. 코드만 보고는 "락 획득 → 중복 체크" 순서가 왜 중요한지 알기 어려워서, 리팩토링 중에 순서가 뒤집히는 실수가 일어나기 쉽기 때문이다.

순서 보장 — InOrder 검증

@Test
@DisplayName("비관적 락 획득이 반드시 중복 체크보다 먼저 수행된다")
void lock_acquired_before_duplicate_check() {
    // ... stubbing ...

    service.submitAssignment(GROUP_ID, PLAN_ID, STUDENT_NUMBER, dto, IP_ADDRESS);

    InOrder inOrder = inOrder(planRepository, validationUtils);
    inOrder.verify(planRepository).findByIdWithPessimisticLock(PLAN_ID);
    inOrder.verify(validationUtils).validateDuplicateSubmission(USER_ID, PLAN_ID);
}

Mockito의 InOrder는 "A가 B보다 먼저 호출되었는가"를 검증한다. 이 테스트가 있으면 나중에 누가 코드를 리팩토링하다가 순서를 바꿔도 CI가 막아준다. 일종의 가드레일이다.

실패 전파 — never() 검증

@Test
@DisplayName("락 획득 실패 시 중복 체크와 저장이 수행되지 않는다")
void no_duplicate_check_or_save_when_lock_fails() {
    when(planRepository.findByIdWithPessimisticLock(PLAN_ID))
            .thenReturn(Optional.empty());

    assertThatThrownBy(() -> service.submitAssignment(...))
            .isInstanceOf(RestApiException.class);

    verify(validationUtils, never()).validateDuplicateSubmission(anyLong(), anyLong());
    verify(submissionRepository, never()).save(any());
}

락 획득 단계에서 Plan을 못 찾으면 뒤의 중복 체크와 save가 절대 호출되지 않아야 한다. 트랜잭션 롤백이 어차피 부작용을 되돌리기는 하지만, 서비스 레이어에서 부작용 있는 메서드가 호출되는 것 자체를 막는 더 엄격한 계약이다.

단위 테스트의 한계

이 단위 테스트들은 @Mock으로 Repository를 모킹하므로 실제 DB 락이 걸리는지까지는 검증하지 못한다. "서비스 레이어에서 락 메서드를 올바른 순서로 호출하는가"까지만 확인한다. 실제 락이 DB 수준에서 동작하는지는 별도의 동시성 통합 테스트(AssignmentSubmissionConcurrencyTest)에서 CountDownLatch와 ExecutorService로 5개 요청을 동시에 던져 1개만 성공하는지 검증한다.

단위 테스트는 "계약"을, 동시성 테스트는 "실측"을 담당하는 역할 분담이다.

5. Redis 분산 락과의 비교

예전에 CTF 플랫폼에서는 같은 종류의 중복 제출 문제를 Redis 분산 락으로 해결했다. 두 방식을 비교해보면 비관적 락의 성격이 더 선명해진다.

Redis 분산 락은 보통 Redisson의 RLock 같은 라이브러리로 구현한다. 원리는 SET key value NX PX ttl 같은 원자적 명령으로 "키 선점 = 락 획득"을 구현하고, 여기에 pub/sub 기반 대기, 재진입, watchdog 자동 연장을 얹는 방식이다.

차이점 (1) — 락의 위치와 범위

• JPA 비관적 락: DB row에 직접 건다. 락 대상이 "DB에 존재하는 실제 데이터"여야 한다.
• Redis 분산 락: Redis의 논리적 key에 건다. 락 대상을 자유롭게 정의할 수 있어 DB row가 존재하지 않는 작업(외부 API 호출, 파일 처리 등)에도 락을 걸 수 있다.

차이점 (2) — 트랜잭션과의 결합

• JPA 비관적 락: 트랜잭션에 묶여 있어 자동 해제된다. 락과 데이터 변경이 원자적이다.
• Redis 분산 락: 트랜잭션과 분리되어 있다. 수동으로 unlock() 해야 하고 finally 블록이 필수다. 더 까다로운 문제는 AOP 순서다. 락을 @Transactional 안에서 얻으면 트랜잭션 커밋 전에 락이 풀릴 수 있어, 다음 요청이 아직 커밋되지 않은 상태를 보고 중복 체크를 통과해버릴 수 있다. 그래서 락은 반드시 트랜잭션 바깥에서 감싸야 한다.

차이점 (3) — DB 부하와 확장성

• JPA 비관적 락: DB 커넥션을 락 동안 점유한다. 트래픽이 늘면 커넥션 풀이 고갈될 수 있다. DB가 병목이 된다.
• Redis 분산 락: DB 커넥션은 실제 쿼리 시점에만 사용한다. Redis가 대기열을 흡수하므로 DB 부하가 분산된다. 여러 서비스 / 여러 DB를 넘나드는 MSA 환경에도 적합하다. 대신 Redis 자체의 HA 구성(Redlock 알고리즘, split-brain 문제)이라는 새로운 복잡도가 생긴다.

차이점 (4) — 장애 상황

• JPA 비관적 락: 락 보유 중 애플리케이션이 죽으면 DB 연결이 끊기면서 트랜잭션이 롤백되고 락이 자동 해제된다. 안전하다.
• Redis 분산 락: 애플리케이션이 죽으면 TTL로만 해제된다. TTL이 너무 짧으면 작업 중에 락이 만료되고, 너무 길면 복구가 지연된다. Redisson의 watchdog가 이 문제를 완화하지만 완전히 없애지는 못한다.

차이점 (5) — 운영 복잡도

• JPA 비관적 락: 어노테이션 한 줄. 학습 비용이 낮다.
• Redis 분산 락: 인프라 추가, AOP 순서, TTL 설계, 장애 처리를 모두 고려해야 한다.

6. 그래서 어느 쪽을 언제 쓰는가

두 방식은 우열이 있는 게 아니라 적합한 맥락이 다르다. 판단 기준은 다음 세 가지 정도다.

충돌의 규모와 빈도

• 충돌이 드물고(한 사용자의 더블 클릭 수준) 락 경쟁이 작다면 JPA 비관적 락으로 충분하다. DB 부하가 미미하다.
• 충돌이 극심하다면(수백 명이 동일 리소스에 몰림) DB 락은 커넥션 풀을 금방 고갈시킨다. Redis로 대기열을 흡수해야 한다.

트랜잭션의 길이

• 임계구역의 트랜잭션이 짧으면 JPA 락의 점유 시간이 짧아 무리 없다.
• 트랜잭션이 길면(외부 API 호출, 파일 처리 등이 섞이면) 그 시간만큼 DB 락을 잡고 있게 되어 처리량이 급격히 떨어진다. 이때는 Redis가 유리하다.

분산 환경의 복잡도

• 단일 DB를 공유하는 모놀리스나 단순한 환경에서는 JPA 비관적 락이 가장 단순하고 안전하다.
• MSA로 여러 DB를 넘나드는 상황에서는 애초에 DB 락이 의미가 없으므로 Redis 분산 락이 사실상 유일한 선택지다.

LMS의 과제 제출은 한 사용자가 자신의 과제를 두 번 클릭하는 수준의 충돌이다. 충돌 범위가 매우 좁고(사용자별 Plan 단위) 빈도도 낮다.

반면 CTF 플랫폼은 동일 문제에 수백 명이 동시에 플래그를 제출한다. 충돌이 극심하고 DB 락을 잡으면 커넥션 풀이 터진다. 같은 팀이 두 프로젝트에서 서로 다른 선택을 한 이유가 여기에 있다.

마치며

비관적 락은 개념 자체는 단순하지만, 실제로 적용할 때는 세심하게 고려해야 할 지점이 많다. 락을 어느 엔티티에 걸 것인가, 락과 검증의 순서를 어떻게 할 것인가, 트랜잭션 범위와 어떻게 맞출 것인가, 기존에 쌓인 데이터는 어떻게 보정할 것인가, 그리고 그 계약을 테스트로 어떻게 못 박을 것인가.

락은 단순한 어노테이션 한 줄이지만, 그 한 줄이 제대로 동작하게 하려면 서비스 레이어의 호출 순서, 집계 쿼리의 재설계, 단위 테스트와 동시성 테스트의 역할 분담까지 모두 맞아떨어져야 한다.

Redis 분산 락이 더 "고급"인 것도, JPA 비관적 락이 더 "기본"인 것도 아니다. 해결하려는 문제의 규모, 트랜잭션의 성격, 인프라의 복잡도에 맞춰 가장 단순하게 작동하는 도구를 고르는 것이 가장 좋은 선택이다.

후킹(Hooking)이란 무엇인가?

• 운영체제–응용프로그램, 혹은 모듈/컴포넌트 사이에서 발생하는 호출 흐름(함수/이벤트)을 중간에서 가로채는 동적 계측 기술
  • 그냥 간단하게 내가 원하는 곳으로 경로를 가로채거나 내용을 엿보는 기술

리버싱에서 후킹이 중요한 이유

• 소스코드가 없거나, 수정/재빌드가 불가능한 상황에서 “프로그램이 실제로 어떤 값을 가지고 어떤 경로로 실행되는지”를 보려면 실행 중에 강제로 관찰 지점을 만들어야 한다.

리버싱에서 후킹의 가치가 큰 이유는, 정적 분석만으로는 잘 안 잡히는 것들이 있기 때문이다.

• 실제로 어떤 인자/구조체가 들어오는지
• 어떤 값이 조건 분기를 결정하는지
• 어떤 API가 어떤 순서로 호출되는지(특히 시간·빈도)
• “이 입력/이벤트/상태 변화”가 내부 로직에 어떤 영향을 주는지

후킹은 이런 질문에 답하기 위한 관찰 지점이자, 필요하면 통제 지점이 된다.

용어 정리

• Hook Point: 가로챌 목표 지점 (예: 특정 API 함수, 메시지 큐 등)
• Hook Handler: 흐름을 가로챈 뒤 실행될 '나의 코드' (여기서 로깅, 차단 등을 수행)
• Original Path: 원래 가야 했을 정상적인 실행 경로
• Forward / Block: 내 코드(Handler) 실행 후, 원래 경로로 돌려보낼지(Forward) 여기서 아예 끊어버릴지(Block) 결정

후킹의 전체 프로세스

모든 후킹은 구현 방식이 달라도, 리버싱 관점에서는 다음 4단계의 공통된 프로세스를 거친다. 단, 무작정 코드를 덮어쓰는 것이 아니라 철저한 분석과 복귀 과정이 필수적이다.

1. 타깃 선정(Targeting):

→ “내가 무엇을 관찰/통제할 것인가?” 목표를 먼저 정하고, 그 목표 데이터가 지나가는 경계(레이어) 를 찾는다. 이때 어떤 함수 이름 하나를 고르는 게 아니라, 어느 레벨에서 잡을지를 함께 결정해야 한다. (상위 API는 의미가 명확하지만 우회될 수 있고, 하위 레벨은 포착률이 높지만 의미가 거칠 수 있다.)

• 목표를 ‘관찰 포인트’로 쪼개기:

  예) 파일 접근을 본다 → 파일 열기/읽기/쓰기 경계, 레지스트리면 열기/조회/수정 경계, 네트워크면 연결/송수신 경계처럼 “관찰하고 싶은 행위”를 먼저 적는다.

• 후보 레벨을 2~3개로 잡기(우선순위 포함):

  예) kernel32/user32 같은 상위 API, ntdll 같은 더 하위 레벨(또는 프로그램 내부 함수) 중 어디가 “의미/포착률/우회 가능성” 관점에서 적절한지 결정한다.

• 후킹 난이도 체크:

  호출 빈도(너무 핫하면 로그 폭발), 호출 규약/인자 구조/반환 타입, 스레드 컨텍스트(어느 스레드에서 호출되는지), 예외/에러 경로를 디스어셈블러·디버거로 확인한다.

• 원본 호출 정책까지 같이 정하기:

  원본을 그대로 호출할지(관찰), 조건부로만 호출할지(제한), 아예 대체/차단할지(통제)를 타깃 선정 단계에서 결정해둔다.

1. 실행 컨텍스트 확보 (Execution Context) - *"내 코드는 어디서 실행되는가?"* 흐름을 가로챘다면, 내가 만든 코드(Hook Handler)가 실행될 '메모리상의 자리'가 필요하다.

• 인-프로세스(In-process): 타깃이 내 프로그램 자신이거나, 내가 로드한 모듈 내부일 경우. 이미 같은 메모리 공간이므로 설계가 단순하다.
• 크로스-프로세스(Cross-process): 외부 타깃 프로그램을 후킹할 경우. 내 코드를 타깃의 공간으로 넘기기 위해 인젝션(대표적으로 DLL) 방식을 사용해 타깃 내부에 공간과 실행 권한을 확보하거나, 디버거(Debugger) 형태로 붙어 제어권을 얻어내야 한다.

1. 흐름 가로채기(Interception):

실제로 실행 흐름이 지나가는 “경계”를 내 훅 함수로 우회시키는 단계다. 후킹 방식은 크게 이벤트 경로를 가로채는 방식과 함수 호출 경로를 가로채는 방식(API 후킹) 으로 나뉜다.

• 이벤트/메시지 경로 가로채기(이벤트 후킹):

  키보드/마우스/윈도우 메시지처럼 OS 이벤트가 전달되는 경로에서 핸들러를 먼저 호출되게 만든다.

  → “사용자 행동/입력 흐름”을 관찰하는 데 강함.

• IAT 후킹(주소록 바꿔치기):

  모듈이 외부 함수를 호출할 때 참고하는 IAT 엔트리(함수 포인터)를 내 함수 주소로 교체해 호출이 훅으로 들어오게 만든다.

  → import 경로를 타는 호출에 강하고, 어느 모듈의 IAT를 바꾸는지가 곧 후킹 범위다.

• 인라인 후킹(함수 엔트리 우회 + 트램폴린):

  함수 시작부의 코드 흐름을 우회시키도록 분기(점프)로 변경해, 호출이 무조건 훅으로 들어오게 만든다. 원본 실행을 유지하려면 덮어쓴 원본 앞부분을 트램폴린으로 보존해 원본 경로로 합류한다.

  → IAT를 안 타는 호출/내부 함수까지 포함해 범용성이 높지만, 명령 경계·스레드 타이밍·64비트 제약 등으로 구현 난이도가 높다.

“이벤트 후킹”은 이벤트 흐름을 잡고, “API 후킹(IAT/인라인)”은 함수 호출 경계를 잡는다.

IAT는 모듈 단위로 범위를 좁혀 잡기 좋고, 인라인은 범용적으로 강제 우회가 가능하다.

1. 실행 및 복귀 (Handling & Return): 내 코드(Hook Handler)로 제어권이 넘어와 필요한 작업(인자 로깅, 값 변조, 차단 등)을 수행한다.

• 작업이 끝났다면 프로그램이 크래시(프로그램 종료/예외 발생) 나지 않도록 파괴된 레지스터와 스택을 원상 복구하고, 다시 원본 흐름이나 다음 훅으로 안전하게 돌려보낸다.

후킹 기술의 종류

가로채는 대상과 위치에 따라 후킹 방식은 다양하지만, 리버싱에서 자주 만나는 대표 방식 3개를 먼저 잡고 간다.

• 메시지/이벤트 후킹 (Windows Hooks)
• IAT 후킹
• 인라인 후킹

메시지/이벤트 후킹

→ 메시지/이벤트 후킹은 API 후킹(IAT/인라인)처럼 함수 호출 경계를 낚는 게 아니라, 입력/메시지 같은 이벤트 흐름 자체를 가로채는 방식이다.

• 사용자 입력과 UI 이벤트가 언제/어떤 형태로 들어오는지를 먼저 잡고 싶을 때 유용하다.

[일반적인 경우의 Windows 메시지 흐름에 대한 설명]

윈도우 GUI 프로그램은 기본적으로 메시지 중심으로 동작한다.

1. 키보드 입력이 발생하면 윈도우는 해당 입력을 메시지(WM_KEYDOWN 등) 형태로 만든다.
2. 그 메시지는 먼저 OS가 관리하는 큐에서 분배되고, 최종적으로 해당 스레드의 메시지 큐로 들어간다.
3. 응용 프로그램은 보통 GetMessage/PeekMessage 같은 루프에서 메시지를 꺼내고, DispatchMessage를 통해 윈도우 프로시저(WndProc) 로 전달한다.
4. WndProc 내부에서 메시지 종류(WM_KEYDOWN 등)에 따라 핸들러가 실행된다.

여기서 포인트

메시지/이벤트 후킹은 “WndProc 안으로 들어간 뒤”가 아니라, 그 전에 흐름을 먼저 보는 쪽에 가깝다.

훅 체인(Hook Chain) 감각

윈도우는 입력/메시지 처리 과정에서 훅 체인이라는 중간 경로를 둘 수 있다.

훅 체인에 내 훅 프로시저를 등록하면, 메시지가 응용 프로그램에 도달하기 전에 내 코드가 먼저 호출될 수 있다.

• 훅은 보통 한 개만 존재하는 게 아니라 여러 개가 순서대로 연결될 수 있다.
• 그래서 훅 프로시저는 보통 처리 후 CallNextHookEx로 다음 훅에 넘겨 체인을 유지한다.
  • (체인을 끊으면 예상치 못한 부작용이 생길 수 있다.)

전역 훅(Global) vs 스레드 훅(Thread-specific)

메시지/이벤트 후킹은 범위가 중요하다. 범위를 넓히면 강력해 보이지만, 동시에 리스크도 커진다.

• 스레드 훅(특정 스레드에만 적용)
  • 범위가 제한적이라 안정성이 좋다.
  • “특정 앱/특정 창”만 대상으로 할 때 선호된다.
• 전역 훅(시스템 전반에 적용)
  • 여러 프로세스/스레드 입력을 폭넓게 관찰 가능
  • 대신 제약/충돌 가능성이 높고, 구현 구조도 DLL 형태가 요구되는 경우가 많다.

메시지 후킹으로 뭘 할 수 있나? (관찰/변경/차단)

메시지/이벤트 후킹은 다음 3가지 목적에 쓰인다.

• 관찰(관측)
  • 어떤 입력이 언제 들어오는지(시간 간격, 빈도)
  • 어떤 창/스레드에서 이벤트가 발생했는지
  • 입력 패턴이 사람인지 자동화인지(추정 신호)
• 변경(수정)
  • 특정 메시지의 일부 정보를 변형하는 방식(상황에 따라 가능)
• 차단(전달 중단)
  • 특정 조건에서 메시지가 아래로 더 내려가지 않게 하는 방식(가능은 하지만, 정상 동작을 깨기 쉬워 신중해야 함)

API 후킹과의 관계

• 메시지/이벤트 후킹: 입력/이벤트가 들어오는 흐름(행동)을 잡는다.
  • 예: 키 입력이 발생하는 시점, 입력 속도/빈도, UI 이벤트 패턴
• API 후킹(IAT/인라인): 그 입력이 실제로 어떤 함수 호출/행위로 이어졌는지(결과)를 잡는다.
  • 예: 파일 열기/쓰기, 프로세스 실행, 레지스트리 변경, 네트워크 연결 등

이러한 메시지 훅 기능은 Windows 운영체제에서 제공하는 기본 기능이며, 대표적으로 MS Visual Studio에서 제공되는 SPY++ 가 있다.

예시: Keylogger 후킹 코드 작성해보기

#include <iostream>
#include <windows.h>
#include <string>

// 훅 핸들 보관용 전역 변수
HHOOK _hook;

// Hook Handler (흐름을 가로챈 뒤 실행될 코드)
LRESULT CALLBACK KeyboardHookProc(int nCode, WPARAM wParam, LPARAM lParam) {
    if (nCode >= 0) {
        // 키보드가 눌렸을 때 (WM_KEYDOWN)
        if (wParam == WM_KEYDOWN) {
            KBDLLHOOKSTRUCT* kbdStruct = (KBDLLHOOKSTRUCT*)lParam;
            DWORD vkCode = kbdStruct->vkCode;

            std::string log_message;

            // 조합키(Ctrl, Shift) 상태 확인
            if (GetAsyncKeyState(VK_LCONTROL) & 0x8000 || GetAsyncKeyState(VK_RCONTROL) & 0x8000) {
                log_message += "[Ctrl] + ";
            }
            if (GetAsyncKeyState(VK_LSHIFT) & 0x8000 || GetAsyncKeyState(VK_RSHIFT) & 0x8000) {
                log_message += "[Shift] + ";
            }

            // 일반 키보드 문자 판별
            if (vkCode >= 0x30 && vkCode <= 0x5A) { // 숫자 0-9, 알파벳 A-Z
                log_message += (char)vkCode;
            }
            else if (vkCode == VK_BACK) {
                log_message += "[Backspace]";
            }
            else if (vkCode == VK_RETURN) {
                log_message += "[Enter]";
            }
            else if (vkCode == VK_SPACE) {
                log_message += "[Space]";
            }

            // 가로챈 키보드 입력을 콘솔에 출력
            if (!log_message.empty()) {
                std::cout << "Intercepted Key: " << log_message << std::endl;
            }

            // 만약 특정 키(예: 'A')를 완전히 먹통으로 만들고 싶다면?
            // 여기서 return 1; 을 호출하여 흐름을 끊어버리면(Block) 
            // 원래 응용프로그램에는 'A' 입력이 절대 전달되지 않는다.
        }
    }
    // 처리가 끝났으므로 원래 가야 했을 다음 훅 체인으로 전달 (Forward)
    return CallNextHookEx(_hook, nCode, wParam, lParam);
}

int main() {
    // 타깃 선정 및 실행 컨텍스트 확보
    // OS의 가장 앞단(WH_KEYBOARD_LL)에 나의 훅 프로시저(KeyboardHookProc)를 설치한다.
    _hook = SetWindowsHookEx(WH_KEYBOARD_LL, KeyboardHookProc, NULL, 0);

    if (_hook == NULL) {
        std::cerr << "후킹에 실패했습니다!" << std::endl;
        return 1;
    }

    std::cout << "키보드 훅이 시작되었습니다. (아무 곳에나 타이핑해 보세요!)" << std::endl;

    // 메시지 루프 (훅이 해제되지 않고 계속 대기하도록 유지)
    MSG msg;
    while (GetMessage(&msg, NULL, 0, 0)) {
        TranslateMessage(&msg);
        DispatchMessage(&msg);
    }

    // 프로그램 종료 시 훅 해제 (안전한 복귀)
    UnhookWindowsHookEx(_hook);
    return 0;
}

간단하게 이와 같이 코드를 작성해 키보드 입력을 가져오는 테스트를 할 수도 있다.

IAT 후킹(Import Address Table Hooking)

프로그램이 외부 DLL 함수를 호출할 때 참고하는 ‘수입 주소록(IAT)’의 함수 포인터를 바꿔치기해서, 호출 흐름이 내 훅 함수로 들어오게 만드는 방식이다.

• 작동 원리:

  PE 포맷의 모듈(EXE/DLL)은 자신이 사용할 외부 함수(예: MessageBoxW)를 import로 선언해두고, 로더가 실행 시점에 그 함수들의 실제 주소를 IAT 엔트리(함수 포인터 칸) 에 채워 넣는다.

  프로그램은 해당 API를 호출할 때 (많은 경우) 이 IAT 엔트리를 통해 간접 호출을 수행한다.

  IAT 후킹은 이 엔트리 값을 원본 함수 주소 → 내 훅 함수 주소로 교체하여, 이후 호출이 내 훅으로 먼저 들어오게 만든다.

• 특징 및 한계:

  • 어셈블리 코드를 직접 패치하지 않아도 되는 경우가 많아 개념이 직관적이고 비교적 구현 부담이 적다.
  • 모듈마다 IAT가 따로 존재하므로, “어느 모듈의 IAT를 바꾸는지”가 곧 후킹 범위가 된다.
  • 모든 호출이 IAT를 거치는 것은 아니다. 예를 들어 GetProcAddress 등으로 런타임에 함수 주소를 얻어 함수 포인터로 직접 호출하거나, 한 번 얻은 주소를 다른 곳에 캐싱해서 호출하는 경우에는 IAT 후킹만으로는 빠질 수 있다(범위가 제한될 수 있다).
  • 또한 환경에 따라 IAT 영역이 쓰기 보호되는 경우가 있어, “항상 단순 덮어쓰기만으로 된다”는 전제는 위험하다.

참고

• 그림에서 가운데 IAT 박스의 jmp CreateFile 표기는 IAT를 경유한 간접 호출을 단순화한 표현이다.
  • 실제 IAT 엔트리는 보통 함수 주소(포인터)를 담고 있고, 호출부가 그 포인터를 따라 간접 호출한다.
• 후킹 후(빨간 화살표)는 이 IAT 엔트리가 원본(CreateFile) 대신 훅 함수(그림의 Rootkit code)를 가리키도록 바뀐다.
• 훅 함수는 인자를 로깅/검사한 뒤 원본 CreateFile로 전달하고(Returning control), 결과를 받아 다시 호출자에게 반환한다.
• GetProcAddress는 IAT에 있을 수 있지만, GetProcAddress로 얻은 함수 주소를 직접 호출하는 경로는 IAT 기반 후킹이 빠질 수 있다.

인라인 후킹 (Inline / Detour Hooking)

주소록을 건드리는 대신 메모리에 올라간 타깃 함수의 실제 실행 코드 첫 부분을 강제로 점프(JMP) 명령어로 수정해 버린다.

• 작동 원리: 함수 시작부의 코드 흐름을 우회시키도록 어셈블리 분기(JMP) 명령으로 덮어써서 호출이 무조건 훅으로 들어오게 만든다. 원본 실행을 유지하려면 덮어쓴 원본 앞부분을 트램폴린이라는 공간에 보존해 두었다가, 훅 함수 실행이 끝난 뒤 트램폴린을 거쳐 원본 경로로 합류시킨다.
• 특징 및 한계: IAT를 안 타는 동적 호출이나 프로그램 내부 함수까지 모두 포함해 범용성이 가장 높고 강력하다. 하지만 명령 경계, 스레드 타이밍, 64비트 레지스터 제약 등으로 인해 구현 난이도가 매우 높고 잦은 크래시를 유발할 수 있다.

API 후킹 좀 더 알아보기

이러한 여러 후킹 기법 중에서도, 시스템의 동작 흐름을 완벽하게 꿰뚫어 볼 수 있는 API 후킹(API Hooking)은 윈도우 환경 리버싱의 핵심으로 불린다.

API 후킹 기술 지도 (API Hooking Tech Map)

어떤 대상을 어떻게 후킹할 것인지 한눈에 파악할 수 있는 구조다.

메모리상의 '어느 위치'를 공략하느냐, 그리고 '어떻게 침투'하느냐에 따라 나뉜다.

API 후킹

윈도우 OS에서 어플리케이션은 보안을 위해 메모리나 파일 같은 시스템 자원에 직접 접근할 수 없다. 반드시 OS가 제공하는 Win32 API (kernel32.dll, ntdll.dll 등)를 거쳐 시스템 커널에게 부탁해야만 한다.

API 후킹은 이 필수적인 통로 길목에 갈고리를 걸어 제어권을 완전히 빼앗는 기술이다.

정상적인 API 호출 (https://reversecore.com/54 참고)

• 코드 영역 주소에서 CreateFile() API 호출 (CreateFile은 실제로 CreateFileA/ CreateFileW 로 나뉜다.)
• CreateFile() API는 kernel32.dll 에서 서비스하므로 kernel32.dll 영역의 CreateFile() API가 실행되고 정상적으로 리턴한다.

kernel32 CreateFile()이 후킹된 경우

• 사용자가 DLL injection 기술로 hook.dll을 프로세스 메모리 공간에 침투시킨다.
  • kernel32 CreateFile()을 hook MyCreateFile()로 후킹한다. (이때 후킹 함수 설치 방법은 DLL Injection 말고도 더 있다.)
• 이제부터 해당 프로세스에서 CreateFile() API가 호출 될 때마다 kernel32 CreateFile이 호출되는 게 아닌, hook MyCreateFile()이 호출된다.

API 후킹 예시: 메모장의 파일 열기 (CreateFile)

윈도우 기본 프로그램인 메모장(notepad.exe)이 텍스트 파일을 여는 과정을 API 후킹으로 어떻게 통제하는지 확인한다.

1) 정상적인 실행 흐름 (Original Path)

• 사용자가 메모장에서 c:\abc.txt 파일을 연다.
• 메모장 코드는 내부적으로 파일을 열기 위해 윈도우 API인 kernel32.dll의 CreateFileW() 함수를 호출
• 이 호출은 깊은 단의 ntdll.dll을 거쳐 시스템 커널로 진입하여 정상적으로 파일을 읽어온다.

2) API 후킹이 적용된 실행 흐름 (Hooked Path)

• 리버서가 DLL 인젝션(DLL Injection)을 통해 메모장 프로세스의 메모리 공간에 자신이 만든 hook.dll을 강제로 침투시킨다.
• hook.dll은 실행되자마자, 원본 kernel32.dll 내부의 CreateFileW() 함수의 시작 코드를 조작하여(코드 후킹), 내가 작성한 hook!MyCreateFile() 함수로 향하도록 방향을 꺾어버린다.
• 결과: 이제 메모장이 파일을 열려고 시도할 때마다 무조건 내가 만든 MyCreateFile()이 먼저 실행된다.
  • 할 수 있는 것: 통제권을 쥔 이 MyCreateFile() 함수 내부에서는 인자로 넘어온 파일 경로(c:\abc.txt)를 엿볼 수 있습니다. 만약 열려는 파일 이름이 "기밀문서.txt"라면, 원래 함수로 보내지 않고 강제로 에러를 반환하게 조작하여 메모장이 해당 파일을 절대 열지 못하도록 원천 차단할 수 있다.

출처 및 참고

• https://reversecore.com/54
• https://reversecore.com/55
• https://learn.microsoft.com/en-us/windows/win32/winmsg/about-hooks
• https://github.com/microsoft/detours/wiki/OverviewInterception
• https://wendys.tistory.com/114

CTF(Capture The Flag) 플랫폼을 개발하면서 심각한 버그가 발견됐다. 백엔드 팀에서 테스트한 결과, 50개 팀이 동시에 같은 문제를 제출했을 때, 절반 정도의 팀만 정상적으로 처리되고 나머지는 처리되지 않았다.

예상: 50개 모두 성공
실제: 약 25개만 성공, 나머지는 타임아웃 에러

모든 팀이 첫 번째 문제를 동시에 제출하는 테스트 상황에서, 절반의 팀이 실패하는 것은 치명적인 문제였다. 사용자들은 정답을 제출했음에도 "나중에 다시 시도하세요"라는 메시지를 받게 되는 것이다.

기술 스택

• Backend: Spring Boot, JPA/Hibernate
• Database: MySQL
• Concurrency: Redis, Redisson
• Async: Spring @Async
• Test: Python (동시성 테스트)

원인 분석: Redisson 분산 락 타임아웃

기존 코드 구조

@Transactional
public String submit(String loginId, Long challengeId, String flag, String clientIP) {
    RLock lock = redissonClient.getLock("challengeLock:" + challengeId);

    try {
        // 락 획득 시도: 대기 시간 10초, 점유 시간 10초
        boolean acquired = lock.tryLock(10, 10, TimeUnit.SECONDS);

        if (!acquired) {
            return "Try again later";  // ← 여기서 실패!
        }

        // 1. 플래그 검증 (약 100ms)
        ChallengeEntity challenge = challengeRepository.findById(challengeId)
            .orElseThrow(() -> new RestApiException(ErrorCode.CHALLENGE_NOT_FOUND));

        if (!challenge.getFlag().equals(flag)) {
            return "오답입니다";
        }

        // 2. 히스토리 저장 (약 50ms)
        historyRepository.save(createCorrectAnswerHistory(loginId, challengeId, clientIP));

        // 3. 점수 계산 및 업데이트 (약 3초) ← 병목!
        calculateAndUpdateScores(loginId, challengeId);

        // 4. 팀원들에게 알림 전송 (약 2초) ← 병목!
        sendNotificationToTeamMembers(loginId, challengeId);

        return "정답입니다";

    } catch (InterruptedException e) {
        Thread.currentThread().interrupt();
        throw new RestApiException(ErrorCode.LOCK_ACQUISITION_FAILED);
    } finally {
        if (lock.isHeldByCurrentThread()) {
            lock.unlock();
        }
    }
}

Redisson 락 파라미터 분석

Redisson의 tryLock(waitTime, leaseTime, TimeUnit) 메서드는 세 가지 파라미터를 받는다:

lock.tryLock(10, 10, TimeUnit.SECONDS);
//           ↑   ↑
//           │   └─ leaseTime: 락을 점유할 수 있는 최대 시간 (10초)
//           └───── waitTime: 락 획득을 기다리는 최대 시간 (10초)

waitTime (대기 시간): 다른 스레드가 락을 점유하고 있을 때, 해당 락이 해제되기를 기다리는 최대 시간. 이 시간 내에 락을 획득하지 못하면 false를 반환한다.

leaseTime (점유 시간): 락을 획득한 후 자동으로 해제되기까지의 시간. 이는 데드락을 방지하기 위한 안전장치다.

처리 시간 분석

각 요청당 실제 소요 시간을 측정한 결과:

플래그 검증:        100ms
히스토리 저장:       50ms
점수 계산:        3,000ms  ← 병목 지점
알림 전송:        2,000ms  ← 병목 지점
──────────────────────────
총 처리 시간:     약 5초

점수 계산과 알림 전송이 전체 처리 시간의 대부분(약 5초 중 5초)을 차지했다.

동시성 계산

50개의 요청이 동시에 들어온 경우를 계산해보자:

1개 요청 처리 시간: 약 5초
락 대기 시간(waitTime): 10초
락 점유 시간(leaseTime): 10초

이론적으로 10초 동안 처리 가능한 요청 수:
10초 ÷ 5초 = 약 2개

실제로는 네트워크 지연, 락 경쟁 등으로
10초 동안 약 2~2.5개 정도만 처리됨

50개 요청 ÷ 2개/10초 = 약 250초 필요
→ 10초 대기 시간 내에 락을 획득하지 못한 요청들은 실패!

이것이 바로 약 25개만 성공하고 나머지는 실패하는 이유였다.

왜 Redisson 분산 락을 사용했는가?

이 프로젝트에서 Redisson 분산 락을 사용한 이유는 다음과 같다:

1. 중복 제출 방지: 같은 사용자가 동시에 여러 번 제출하는 것을 막기 위해
2. 순차 처리 보장: 같은 문제에 대한 제출을 순서대로 처리하여 데이터 정합성 확보

하지만 모든 작업을 락 안에서 처리하는 것이 문제였다. 사용자 응답과 관계없는 무거운 작업(점수 계산, 알림 전송)까지 락을 점유한 채로 처리했기 때문에 처리량이 극도로 낮아진 것이다.

해결 방안 검토 With Claude

나 혼자만의 힘으로는 너무나도 어려운 부분이었다. 이럴 때 필요한 게 AI 형님들이다.

고려한 옵션들

옵션 1: 락 타임아웃 늘리기

lock.tryLock(300, 300, TimeUnit.SECONDS);  // 5분으로 증가

• 장점: 간단한 수정
• 단점: 근본적인 해결책이 아니며, 사용자는 여전히 긴 대기 시간 경험

옵션 2: 락 없이 처리

• 장점: 빠른 처리 속도
• 단점: 중복 제출, Race Condition 등 데이터 정합성 문제 발생

옵션 3: 비동기 처리 아키텍처 ⚠️

• 장점: 사용자에게 즉시 응답, 높은 처리량
• 단점: 구현 복잡도 증가, 새로운 Race Condition 발생 가능

첫 번째 시도: 비동기 처리 아키텍처

처음에는 비동기 처리로 문제를 해결하려고 시도했다:

기존: [락 획득] → 모든 작업 수행 → [락 해제] → 응답
시도: [락 획득] → 필수 작업만 수행 → [락 해제] → 응답 → (백그라운드) 무거운 작업

필수 작업 (동기):

• 플래그 검증
• 히스토리 저장
• 중복 제출 체크

백그라운드 작업 (비동기):

• 퍼스트 블러드 판정
• 점수 계산 및 업데이트
• solvers 카운트 증가
• 다이나믹 스코어링
• 팀 점수 재계산
• 알림 전송

이렇게 하면 사용자는 약 150ms만에 응답을 받고, 무거운 작업은 백그라운드에서 처리될 것으로 기대했다.

3단계 비동기 처리 시도와 실패

1. AsyncConfig 설정

Spring의 @Async를 사용하기 위한 스레드 풀 설정:

@Configuration
@EnableAsync
public class AsyncConfig {

    @Bean(name = "submissionAsyncExecutor")
    public Executor submissionAsyncExecutor() {
        ThreadPoolTaskExecutor executor = new ThreadPoolTaskExecutor();
        executor.setCorePoolSize(10);           // 기본 스레드 수
        executor.setMaxPoolSize(20);            // 최대 스레드 수
        executor.setQueueCapacity(100);         // 큐 용량
        executor.setThreadNamePrefix("submission-async-");
        executor.setRejectedExecutionHandler(new ThreadPoolExecutor.CallerRunsPolicy());
        executor.initialize();
        return executor;
    }
}

2. AsyncSubmissionProcessor 첫 번째 버전 (실패)

무거운 작업을 백그라운드에서 처리하는 비동기 프로세서를 구현했다:

@Service
@Slf4j
@RequiredArgsConstructor
public class AsyncSubmissionProcessor {

    private final TeamService teamService;
    private final ChallengeRepository challengeRepository;
    private final UserRepository userRepository;
    private final HistoryRepository historyRepository;
    private final RedissonClient redissonClient;

    @Async("submissionAsyncExecutor")
    @Transactional(propagation = Propagation.REQUIRES_NEW)
    public void processCorrectSubmissionAsync(Long userId, Long challengeId, String loginId) {
        long startTime = System.currentTimeMillis();

        try {
            log.info("[비동기 처리 시작] loginId={}, challengeId={}", loginId, challengeId);

            // 1. 사용자 및 문제 정보 조회
            UserEntity user = userRepository.findById(userId)
                    .orElseThrow(() -> new RuntimeException("User not found"));

            ChallengeEntity challenge = challengeRepository.findById(challengeId)
                    .orElseThrow(() -> new RuntimeException("Challenge not found"));

            boolean isSignature = challenge.getCategory() == ChallengeCategory.SIGNATURE;

            // 2. 퍼스트 블러드 판정 (별도 락 사용)
            boolean isFirstBlood = checkAndProcessFirstBlood(challengeId, user, challenge, isSignature);

            // 3. 팀 점수 및 마일리지 업데이트
            updateTeamScoreAndMileage(user, challenge, isFirstBlood, isSignature, challengeId);

            // 4. 다이나믹 스코어링 적용
            if (!isSignature) {
                updateChallengeScore(challenge);
            }

            // 5. solvers 카운트 증가 ← 여기서 Race Condition 발생!
            challenge.setSolvers(challenge.getSolvers() + 1);
            challengeRepository.save(challenge);

            // 6. 전체 팀 점수 재계산
            updateAllTeamTotalPoints();

            long duration = System.currentTimeMillis() - startTime;
            log.info("[비동기 처리 완료] loginId={}, challengeId={}, duration={}ms",
                    loginId, challengeId, duration);

        } catch (Exception e) {
            log.error("[비동기 처리 실패] loginId={}, challengeId={}, error={}",
                    loginId, challengeId, e.getMessage(), e);
        }
    }

    // ... 기타 메서드들
}

3. ChallengeService 수정 (첫 번째 시도)

@Service
@Slf4j
public class ChallengeService {

    private final ChallengeRepository challengeRepository;
    private final HistoryRepository historyRepository;
    private final AsyncSubmissionProcessor asyncProcessor;
    private final RedissonClient redissonClient;

    @Transactional
    public String submit(String loginId, Long challengeId, String flag, String clientIP) {
        //... 초기 단계 스킵 (기본 유저 검증, 플래그 검증, 문제 검증 등, 오답 처리 등)

        String lockKey = "challengeLock:" + challengeId;
        RLock lock = redissonClient.getLock(lockKey);


        try {
            // 락 획득 (5초 대기, 10초 보유)
            // 기존: tryLock(10, 10) → 변경: tryLock(5, 10)
            // 대기 시간을 줄여서 빠르게 실패하도록 함
            locked = lock.tryLock(5, 10, TimeUnit.SECONDS);

            if (!locked) {
                log.warn("[락 획득 실패] loginId={}, challengeId={}", loginId, challengeId);
                return "Try again later";
            }

            // 락 획득 후 다시 한 번 중복 체크 (동시 요청 방지)
            if (historyRepository.existsByLoginIdAndChallengeId(loginId, challengeId)) {
                return "Submitted";
            }

            // 정답 제출 기록 (공격 감지 방지)
            threatDetectionService.recordFlagAttempt(clientIP, true, challengeId, user.getUserId(), loginId, isInternalIP);

            // HistoryEntity 저장 (가장 중요한 작업만 락 안에서 수행)
            HistoryEntity history = HistoryEntity.builder()
                    .loginId(user.getLoginId())
                    .challengeId(challenge.getChallengeId())
                    .solvedTime(LocalDateTime.now())
                    .univ(user.getUniv())
                    .build();
            historyRepository.save(history);

            // TeamHistory 저장
            if (team.isPresent()) {
                TeamHistoryEntity teamHistory = TeamHistoryEntity.builder()
                        .teamName(team.get().getTeamName())
                        .challengeId(challenge.getChallengeId())
                        .solvedTime(LocalDateTime.now())
                        .build();
                teamHistoryRepository.save(teamHistory);
            }

            // 기존 제출 기록 삭제 (오답 시도 기록)
            Optional<SubmissionEntity> existingOpt =
                    submissionRepository.findByLoginIdAndChallengeId(loginId, challengeId);
            existingOpt.ifPresent(submissionRepository::delete);

            long lockDuration = System.currentTimeMillis() - startTime;
            log.info("[락 내부 처리 완료] loginId={}, challengeId={}, 소요시간={}ms",
                    loginId, challengeId, lockDuration);

        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
            log.error("[제출 처리 중단] loginId={}, challengeId={}, error={}",
                    loginId, challengeId, e.getMessage());
            return "Error while processing";
        } finally {
            // 락 해제
            if (locked && lock.isHeldByCurrentThread()) {
                lock.unlock();
            }
        }

        // 무거운 작업은 비동기로 처리 (락 밖에서 실행)
        try {
            // AsyncSubmissionProcessor를 통해 비동기 처리
            // 이 메서드는 즉시 반환되고, 실제 작업은 백그라운드에서 실행됨
            asyncSubmissionProcessor.processCorrectSubmissionAsync(
                    user.getUserId(),
                    challengeId,
                    loginId
            );
        } catch (Exception e) {
            // 비동기 작업 스케줄링 실패 시 로그만 남기고 계속 진행
            // 사용자에게는 정답 처리된 것으로 표시됨
            log.error("[비동기 작업 스케줄링 실패] loginId={}, challengeId={}, error={}",
                    loginId, challengeId, e.getMessage(), e);
        }

        long totalDuration = System.currentTimeMillis() - startTime;
        log.info("[정답 처리 완료] loginId={}, challengeId={}, 전체소요시간={}ms (비동기 작업 제외)",
                loginId, challengeId, totalDuration);

        // 즉시 정답 응답 반환 (점수 계산 등은 백그라운드에서 처리 중)
        return "Correct";
    }

비동기 처리 첫 번째 시도의 문제점

이렇게 구현하고 테스트를 돌렸더니... 여전히 문제가 발생했다!

문제 1: solvers 카운트 불일치

예상: challenge.solvers = 50
실제: challenge.solvers = 47

비동기 처리로 응답 시간은 개선되었지만, 새로운 Race Condition이 발생했다.

원인: Read-Modify-Write in 비동기 환경

// AsyncSubmissionProcessor에서
challenge.setSolvers(challenge.getSolvers() + 1);  // ← Race Condition!

여러 비동기 스레드가 동시에 같은 Challenge를 읽고 수정하면서 Lost Update 문제 발생:

시간축:

T1: Async Thread A - challenge 조회, solvers = 0 읽기
T2: Async Thread B - challenge 조회, solvers = 0 읽기 ← 동시 읽기!
T3: Thread A - solvers + 1 = 1 계산 후 저장
T4: Thread B - solvers + 1 = 1 계산 후 저장 ← A의 변경 덮어쓰기!

결과: 2번 제출했지만 solvers는 1만 증가

문제 2: 퍼스트 블러드 중복 판정

별도의 락을 사용했지만, 여러 비동기 스레드가 동시에 퍼스트 블러드를 체크하면서 중복 판정이 발생하기도 했다.

문제 3: 점수 계산 불일치

다이나믹 스코어링과 팀 점수 계산에서도 간헐적으로 불일치가 발생했다.

왜 Redis Lock으로 보호되지 않았는가?

"Redisson 분산 락이 있는데 왜 이런 문제가?"라고 의문이 들 수 있다.

하지만 Redis Lock은 메인 트랜잭션(submit 메서드)만 보호한다. 비동기 작업(processCorrectSubmissionAsync)은:

• 별도의 트랜잭션으로 실행 (@Transactional(propagation = REQUIRES_NEW))
• Redis Lock 범위 밖에서 동작
• 여러 비동기 스레드가 동시에 같은 데이터에 접근 가능

Main Thread (Redis Lock으로 보호됨):
  [락 획득] → 히스토리 저장 → 비동기 위임 → [락 해제] → 응답

Async Thread A (보호받지 않음):
  Challenge 읽기 → solvers + 1 → 저장

Async Thread B (보호받지 않음):  
  Challenge 읽기 → solvers + 1 → 저장  ← Race Condition!

비동기 처리의 딜레마

비동기 처리는 성능은 개선하지만, 동시성 제어가 더 복잡해진다:

1. 각 비동기 스레드마다 별도의 락 필요 → 락 관리 복잡도 증가
2. 트랜잭션 경계 관리 어려움 → 데이터 정합성 보장 어려움
3. 에러 처리 복잡 → 실패 시 재시도, 롤백 전략 필요

특히 여러 비동기 작업이 같은 데이터를 수정하는 경우, 락을 아무리 세밀하게 나눠도 Race Condition을 완전히 방지하기 어렵다.

해결책: 핵심 작업은 동기로, 비관적 락 추가 (다른 백엔드가 작업)

역시 팀 협업을 하는 이유는 다 있는거다!

• 비동기 처리로 해결하려던 시도가 실패하자, 백엔드 팀에서 다른 접근 방식을 채택했다.

핵심 아이디어

"비동기로 처리할 수 있는 것과 없는 것을 명확히 구분하자"

데이터 정합성이 중요한 핵심 작업들은:

• 동기 처리로 되돌림 (ChallengeService의 락 안에서 처리)
• 비관적 락 추가로 Race Condition 완전 차단

비동기는:

• 데이터 무결성과 무관한 작업만 담당 (외부 알림 등)

해결 방안: 비관적 락이란?

비관적 락(Pessimistic Lock)은 데이터를 읽는 시점에 데이터베이스 레벨의 Lock을 획득하여, 트랜잭션이 완료될 때까지 다른 트랜잭션의 접근을 차단하는 방식이다.

-- 비관적 락을 사용하면 다음과 같은 SQL이 실행됨
SELECT * FROM challenge WHERE challenge_id = ? FOR UPDATE;

FOR UPDATE 절이 추가되어 해당 행(row)에 배타적 락이 걸린다. 다른 트랜잭션은:

• 이 행을 읽을 수 없음 (SELECT도 대기)
• 이 행을 수정할 수 없음 (UPDATE도 대기)
• 락이 해제될 때까지 대기(blocking)

JPA Lock 모드

JPA는 세 가지 주요 Lock 모드를 제공한다:

이 프로젝트에서는 PESSIMISTIC_WRITE를 사용했다. 배타적 락(Exclusive Lock)을 걸어 다른 트랜잭션이 해당 행을 읽거나 수정하는 것을 완전히 차단한다.

구현 1: ChallengeRepository 수정

@Repository
public interface ChallengeRepository extends JpaRepository<ChallengeEntity, Long> {

    // 일반 조회 (기존)
    Optional<ChallengeEntity> findById(Long challengeId);

    // 비관적 락을 사용한 조회 (추가)
    @Lock(LockModeType.PESSIMISTIC_WRITE)
    @Query("SELECT c FROM ChallengeEntity c WHERE c.challengeId = :challengeId")
    Optional<ChallengeEntity> findByIdWithLock(@Param("challengeId") Long challengeId);
}

구현 2: ChallengeService 수정 (최종 버전)

핵심 작업들을 모두 동기로 처리하고, 비관적 락으로 보호:

@Service
@Slf4j
@RequiredArgsConstructor
public class ChallengeService {

    private final ChallengeRepository challengeRepository;
    private final HistoryRepository historyRepository;
    private final TeamService teamService;
    private final UserRepository userRepository;
    private final AsyncSubmissionProcessor asyncProcessor;
    private final RedissonClient redissonClient;

    @Transactional
    public String submit(String loginId, Long challengeId, String flag, String clientIP) {

        RLock lock = redissonClient.getLock("challengeLock:" + challengeId);
        long startTime = System.currentTimeMillis();

        try {
            // Redis 분산 락 획득
            boolean acquired = lock.tryLock(10, 10, TimeUnit.SECONDS);
            if (!acquired) {
                log.warn("[락 획득 실패] loginId={}, challengeId={}", loginId, challengeId);
                return "Try again later";
            }

            // 1. 비관적 락으로 Challenge 조회 (FOR UPDATE)
            ChallengeEntity challenge = challengeRepository
                .findByIdWithLock(challengeId)  // ← 여기가 핵심!
                .orElseThrow(() -> new RestApiException(ErrorCode.CHALLENGE_NOT_FOUND));

            // 2. 플래그 검증
            if (!challenge.getFlag().equals(flag)) {
                historyRepository.save(createWrongAnswerHistory(loginId, challengeId, clientIP));
                return "오답입니다";
            }

            // 3. 중복 제출 체크
            if (historyRepository.existsByLoginIdAndChallengeId(loginId, challengeId)) {
                throw new RestApiException(ErrorCode.ALREADY_SUBMITTED);
            }

            // 4. 히스토리 저장
            historyRepository.save(createCorrectAnswerHistory(loginId, challengeId, clientIP));

            // 5. 사용자 조회
            UserEntity user = userRepository.findByLoginId(loginId)
                    .orElseThrow(() -> new RestApiException(ErrorCode.USER_NOT_FOUND));

            boolean isSignature = challenge.getCategory() == ChallengeCategory.SIGNATURE;

            // 6. 퍼스트 블러드 판정 (동기 처리)
            boolean isFirstBlood = checkFirstBlood(challengeId);

            // 7. solvers 증가 (비관적 락으로 보호됨)
            challenge.setSolvers(challenge.getSolvers() + 1);
            challengeRepository.save(challenge);

            // 8. 다이나믹 스코어링 (동기 처리)
            int newPoints = challenge.getPoints();
            if (!isSignature) {
                newPoints = calculateDynamicScore(challenge, challenge.getSolvers());
                challenge.setPoints(newPoints);
                challengeRepository.save(challenge);
            }

            // 9. 팀 점수/마일리지 업데이트 (동기 처리)
            if (user.getCurrentTeamId() != null) {
                int baseMileage = challenge.getMileage();
                int fbBonus = (isFirstBlood && baseMileage > 0) 
                    ? (int) Math.ceil(baseMileage * 0.30) : 0;
                int finalMileage = baseMileage + fbBonus;
                int awardedPoints = isSignature ? 0 : newPoints;

                teamService.recordTeamSolution(
                    user.getUserId(),
                    challengeId,
                    awardedPoints,
                    finalMileage
                );
            }

            // 10. 전체 팀 점수 재계산 (동기 처리)
            recalculateTeamsByChallenge(challengeId);

            // 11. 비동기 작업: 퍼스트 블러드 알림만 전송
            asyncProcessor.processCorrectSubmissionAsync(
                user.getUserId(),
                challengeId,
                loginId,
                isFirstBlood,
                newPoints
            );

            long duration = System.currentTimeMillis() - startTime;
            log.info("[제출 처리 완료] loginId={}, challengeId={}, duration={}ms, isFirstBlood={}",
                    loginId, challengeId, duration, isFirstBlood);

            return "정답입니다";

        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
            throw new RestApiException(ErrorCode.LOCK_ACQUISITION_FAILED);
        } finally {
            if (lock.isHeldByCurrentThread()) {
                lock.unlock();
            }
        }
    }

    private boolean checkFirstBlood(Long challengeId) {
        long solvedCount = historyRepository.countDistinctByChallengeId(challengeId);
        return solvedCount == 1;
    }

    private int calculateDynamicScore(ChallengeEntity challenge, int solvers) {
        int initialPoints = challenge.getInitialPoints();
        int minPoints = challenge.getMinPoints();
        int decay = 50;

        double newPoints = (((double)(minPoints - initialPoints) / (decay * decay)) 
            * (solvers * solvers)) + initialPoints;
        newPoints = Math.max(newPoints, minPoints);

        return (int) Math.ceil(newPoints);
    }

    private void recalculateTeamsByChallenge(Long challengeId) {
        // 전체 팀의 점수를 재계산하는 로직
        // 구현 생략
    }
}

구현 3: AsyncSubmissionProcessor 최종 버전 (간소화)

비동기는 외부 알림만 담당하도록 대폭 축소:

@Service
@Slf4j
@RequiredArgsConstructor
public class AsyncSubmissionProcessor {

    private final ChallengeRepository challengeRepository;
    private final UserRepository userRepository;
    private final RedissonClient redissonClient;

    @Value("${api.key}")
    private String apiKey;

    @Value("${api.url}")
    private String apiUrl;

    /**
     * 비동기 처리: 퍼스트 블러드 알림만 전송
     * 
     * 중요: 팀 점수/마일리지/solvers 업데이트는 이미 ChallengeService의 락 안에서 완료됨
     *         비동기에서는 데이터 무결성과 무관한 외부 알림만 전송
     */
    @Async("submissionAsyncExecutor")
    @Transactional(propagation = Propagation.REQUIRES_NEW)
    public void processCorrectSubmissionAsync(Long userId, Long challengeId, String loginId, 
                                             boolean isFirstBlood, int calculatedPoints) {
        long startTime = System.currentTimeMillis();

        try {
            UserEntity user = userRepository.findById(userId)
                    .orElseThrow(() -> new IllegalStateException("User not found: " + userId));

            ChallengeEntity challenge = challengeRepository.findById(challengeId)
                    .orElseThrow(() -> new IllegalStateException("Challenge not found: " + challengeId));

            boolean isSignature = challenge.getCategory() == ChallengeCategory.SIGNATURE;

            // 퍼스트 블러드 알림 전송 (일반 문제만)
            if (isFirstBlood && !isSignature) {
                try {
                    sendFirstBloodNotification(challenge, user);
                    log.info("[퍼블 알림 전송] challengeId={}, by={}", challengeId, user.getLoginId());
                } catch (Exception e) {
                    log.warn("[퍼블 알림 실패] challengeId={}, err={}", challengeId, e.getMessage());
                    // 알림 실패는 전체 프로세스에 영향 없음
                }
            }

            long duration = System.currentTimeMillis() - startTime;
            log.info("[비동기 처리 완료] loginId={}, challengeId={}, duration={}ms, isFB={}",
                    loginId, challengeId, duration, isFirstBlood);

        } catch (Exception e) {
            long duration = System.currentTimeMillis() - startTime;
            log.error("[비동기 처리 실패] challengeId={}, loginId={}, duration={}ms, err={}",
                    challengeId, loginId, duration, e.getMessage(), e);
        }
    }

    private void sendFirstBloodNotification(ChallengeEntity challenge, UserEntity user) {
        try {
            RestTemplate restTemplate = new RestTemplate();
            HttpHeaders headers = new HttpHeaders();
            headers.set("Content-Type", "application/json");
            headers.set("X-API-Key", apiKey);

            Map<String, Object> body = new HashMap<>();
            body.put("first_blood_problem", challenge.getTitle());
            body.put("first_blood_person", user.getLoginId());
            body.put("first_blood_school", user.getUniv());

            HttpEntity<Map<String, Object>> entity = new HttpEntity<>(body, headers);
            ResponseEntity<String> response = restTemplate.exchange(
                apiUrl, HttpMethod.POST, entity, String.class);

            if (response.getStatusCode().is2xxSuccessful()) {
                log.info("[퍼블 알림 성공] challengeId={}, loginId={}", 
                        challenge.getChallengeId(), user.getLoginId());
            } else {
                log.error("[퍼블 알림 실패] challengeId={}, statusCode={}", 
                        challenge.getChallengeId(), response.getStatusCode());
            }
        } catch (Exception e) {
            log.error("[퍼블 알림 오류] challengeId={}, err={}", 
                    challenge.getChallengeId(), e.getMessage());
        }
    }
}

비관적 락 동작 과정

Thread A와 Thread B가 동시에 제출하는 경우:

T1: Thread A - Redis Lock 획득
T2: Thread A - findByIdWithLock() 호출
    → DB에 FOR UPDATE Lock 획득
    → solvers = 0 읽기
T3: Thread B - Redis Lock 대기 중...

T4: Thread A - solvers를 1로 증가
T5: Thread A - 다이나믹 스코어링 계산
T6: Thread A - 팀 점수 업데이트
T7: Thread A - 전체 팀 재계산
T8: Thread A - save() → DB 저장
T9: Thread A - 트랜잭션 커밋 → DB Lock 해제
T10: Thread A - Redis Lock 해제
T11: Thread A - 비동기 알림 위임

T12: Thread B - Redis Lock 획득
T13: Thread B - findByIdWithLock() 호출
     → DB에 FOR UPDATE Lock 획득
     → solvers = 1 읽기 (A의 변경사항 반영!)
T14: Thread B - solvers를 2로 증가
T15: Thread B - 다이나믹 스코어링 계산
T16: Thread B - 팀 점수 업데이트
T17: Thread B - 전체 팀 재계산
T18: Thread B - save() → DB 저장
T19: Thread B - 트랜잭션 커밋 → DB Lock 해제
T20: Thread B - Redis Lock 해제
T21: Thread B - 비동기 알림 위임

결과: solvers = 2 (정확함!)

핵심: Thread B는 Thread A가 커밋한 최신 값(1)을 읽는다. Lost Update 문제가 발생하지 않는다.

왜 이 방식이 효과적인가?

1. Redis Lock + JPA 비관적 락 이중 보호

   • Redis Lock: 분산 환경에서 서버 간 동기화
   • JPA 비관적 락: 데이터베이스 레벨에서 행 단위 보호

2. 모든 핵심 작업을 하나의 트랜잭션 안에서 처리

   • 퍼스트 블러드 판정
   • solvers 증가
   • 다이나믹 스코어링
   • 팀 점수 업데이트
   • 전체 팀 재계산

   → 원자성(Atomicity) 보장

3. 비동기는 부가 기능만

   • 외부 API 알림만 담당
   • 실패해도 핵심 기능에 영향 없음

왜 비동기 처리를 포기했는가?

초기에는 "무거운 작업을 비동기로"라는 아이디어가 매력적이었지만:

문제점:

• 여러 비동기 스레드가 같은 데이터 수정 → Race Condition 불가피
• 각 작업마다 별도 락 필요 → 복잡도 기하급수적 증가
• 트랜잭션 경계 불명확 → 부분 실패 시 롤백 어려움

결론:

• 데이터 정합성이 중요한 작업은 비동기 부적합
• 무거운 작업이어도 동기로 처리하되 락으로 보호하는 것이 더 안전
• 비동기는 데이터 무결성과 무관한 부가 기능에만 사용

왜 비관적 락이 효과적인가?

비동기 처리 환경에서 비관적 락이 효과적인 이유:

1. Read-Modify-Write 패턴 보호: 읽기부터 쓰기까지 원자적으로 보호
2. 자동 대기: 충돌 시 자동으로 대기하므로 재시도 로직 불필요
3. 데이터 정합성 완벽 보장: 동시성 환경에서도 항상 정확한 값 유지

비관적 락의 단점인 "대기 시간"은 이미 비동기 처리로 인해 사용자 응답과 분리되어 있어 문제가 되지 않는다.

왜 낙관적 락을 사용하지 않았는가?

낙관적 락(Optimistic Lock)도 고려했지만 선택하지 않은 이유:

낙관적 락의 동작:

@Version
private Long version;  // Entity에 버전 필드 추가

// 충돌 발생 시 OptimisticLockException 발생
// → 재시도 로직 필요

문제점:

1. 높은 동시성 환경에서 재시도가 과도하게 발생
2. 재시도 로직 구현 복잡도 증가
3. 비동기 환경에서 재시도 실패 시 데이터 손실 가능성

비관적 락은 충돌 시 자동으로 대기하므로 안정성이 높다.

이중 안전장치: 실시간 계산

비관적 락으로 데이터 정합성이 보장되지만, 추가적인 안전장치를 마련했다.

왜 추가 안전장치가 필요한가?

다음과 같은 상황에서 DB의 solvers 값이 부정확할 수 있다:

1. 과거의 버그로 인한 누적 오류
2. 관리자의 직접 수정
3. 데이터 마이그레이션 중 오류
4. 예상치 못한 트랜잭션 롤백

따라서 History 테이블을 Source of Truth로 삼아 실시간으로 계산하는 로직을 추가했다.

구현: 실시간 solvers 계산

@Service
public class ChallengeService {

    private final ChallengeRepository challengeRepository;
    private final HistoryRepository historyRepository;

    public ChallengeDto.Detail getDetailChallenge(Long challengeId) {
        // Challenge 조회
        ChallengeEntity challenge = challengeRepository.findById(challengeId)
                .orElseThrow(() -> new RestApiException(ErrorCode.CHALLENGE_NOT_FOUND));

        // 실시간으로 solvers 카운트 계산
        long actualSolvers = historyRepository.countDistinctSolversByChallengeId(challengeId);

        // DB 값 대신 실시간 계산 값 사용
        challenge.setSolvers((int) actualSolvers);

        return ChallengeDto.Detail.fromEntity(challenge);
    }
}

HistoryRepository에 메서드 추가

@Repository
public interface HistoryRepository extends JpaRepository<HistoryEntity, Long> {

    /**
     * 특정 Challenge를 정답으로 제출한 고유 사용자 수 계산
     */
    @Query("SELECT COUNT(DISTINCT h.loginId) FROM HistoryEntity h " +
           "WHERE h.challengeId = :challengeId AND h.isCorrect = true")
    long countDistinctSolversByChallengeId(@Param("challengeId") Long challengeId);
}

자동 보정 효과

시나리오:
  DB 저장값: challenge.solvers = 47 (비관적 락 적용 전 누적 오류)
  실제 History: 50개 팀이 정답 제출
  조회 결과: 50 반환 (자동 보정!)

이렇게 하면:

• 과거의 데이터 불일치도 자동으로 수정
• DB 값에 관계없이 항상 정확한 값 제공
• History 테이블이 단일 진실 공급원(Single Source of Truth) 역할

성능 고려사항

실시간 계산이 성능에 미치는 영향:

-- 인덱스 추가로 빠른 조회 가능
CREATE INDEX idx_history_challenge_correct 
ON history(challenge_id, is_correct, login_id);

성능 측정 결과:

• 인덱스 없음: 평균 500ms
• 인덱스 있음: 평균 20ms

조회 시 20ms 추가는 충분히 감수할 만한 수준이다.

최종 아키텍처: 다층 방어 체계

최종적으로 세 가지 레벨의 동시성 제어를 갖추게 되었다:

┌─────────────────────────────────────────┐
│  1단계: Redisson 분산 락                  │
│  (애플리케이션 레벨)                       │
│                                          │
│  • 메인 트랜잭션 순차 처리 보장            │
│  • 중복 제출 방지                         │
│  • 분산 환경 대비                         │
└─────────────────────────────────────────┘
              ↓
┌─────────────────────────────────────────┐
│  2단계: JPA 비관적 락                     │
│  (데이터베이스 레벨)                       │
│                                          │
│  • Read-Modify-Write 패턴 보호           │
│  • solvers 카운트 정확성 보장             │
│  • 트랜잭션 내 데이터 무결성 완벽 보장     │
└─────────────────────────────────────────┘
              ↓
┌─────────────────────────────────────────┐
│  3단계: 실시간 계산                       │
│  (검증 레벨)                              │
│                                          │
│  • History 테이블 기반 정확한 값 계산     │
│  • DB 불일치 시 자동 보정                 │
│  • Single Source of Truth 확립          │
└─────────────────────────────────────────┘
              ↓
┌─────────────────────────────────────────┐
│  4단계: 간소화된 비동기 처리               │
│  (부가 기능)                              │
│                                          │
│  • 외부 API 알림만 비동기 처리            │
│  • 핵심 기능과 독립적                     │
│  • 실패해도 전체 프로세스에 영향 없음      │
└─────────────────────────────────────────┘

각 레벨의 역할

1단계 - Redisson 분산 락:

• 같은 Challenge에 대한 제출을 순차적으로 처리
• 여러 서버 인스턴스 간 동기화
• 중복 제출 1차 방어

2단계 - JPA 비관적 락:

• 핵심 해결책: Read-Modify-Write 패턴의 Race Condition 완전 차단
• solvers, points 등 카운터 필드의 정확성 보장
• 데이터베이스 레벨의 확실한 보호

3단계 - 실시간 계산:

• 과거 버그나 예외 상황에 대한 자동 복구
• 데이터 신뢰성 최종 보장
• 모니터링 및 검증 용도

4단계 - 간소화된 비동기 처리:

• 외부 API 알림만 담당 (퍼스트 블러드 알림 등)
• 핵심 데이터 처리와 완전히 분리
• 실패해도 사용자 경험에 영향 없음

핵심 교훈: 무엇을 비동기로 처리할 것인가?

초기에는 "무거운 작업은 모두 비동기로"라는 접근을 시도했지만, 실패했다.

비동기 처리가 적합한 작업:

• 외부 API 호출 (알림, 웹훅 등)
• 로깅, 모니터링
• 캐시 갱신
• 이메일/SMS 전송

비동기 처리가 부적합한 작업:

• 데이터 무결성이 중요한 DB 업데이트
• 다른 작업이 의존하는 계산
• 트랜잭션 롤백이 필요할 수 있는 작업
• 여러 스레드가 같은 데이터를 수정하는 작업

결론: 비동기는 성능을 위한 도구이지만, 데이터 정합성을 희생해서는 안 된다.

성능 비교: 최종 결과

응답 시간

비관적 락 적용으로 25배 개선되었다.

처리량

비관적 락 덕분에 12배 향상되었다.

성공률

최종 버전은 성능과 정합성 모두 달성했다.

배운 교훈

비동기 처리는 만능이 아니다

초기 가정: "무거운 작업을 비동기로 처리하면 모든 문제가 해결될 것이다"

현실: 비동기 처리는 새로운 동시성 문제를 만들었다

• 여러 비동기 스레드가 같은 데이터 수정 → Race Condition
• 트랜잭션 경계 불명확 → 부분 실패 시 롤백 어려움
• 각 작업마다 별도 락 필요 → 복잡도 기하급수적 증가

교훈:

• 데이터 무결성이 중요한 작업은 비동기 부적합
• 비동기는 핵심 로직과 독립적인 부가 기능에만 사용
• 외부 API 호출, 알림, 로깅 등에 적합

비관적 락의 효과

예상: "비관적 락은 느리고 데드락 위험이 있다"

현실: 이 프로젝트에서는 매우 효과적이었다

• Redis Lock과 결합하여 순차 처리 → 데드락 위험 최소화
• FOR UPDATE는 매우 빠름 (수 ms)
• 자동 대기로 재시도 로직 불필요

교훈:

• 비관적 락은 "동시 쓰기가 빈번한" 상황에 적합
• 특히 카운터 증가 같은 Read-Modify-Write 패턴에 효과적
• 락 대기 시간보다 데이터 정합성이 더 중요한 경우 선택

성능과 정합성의 균형

초기 시도: 성능을 위해 모든 것을 비동기로

최종 해결: 핵심 작업은 동기 + 비관적 락, 부가 기능만 비동기

교훈:

• "성능 vs 정합성"은 이분법이 아니다
• 적절한 아키텍처 설계로 둘 다 달성 가능
• 병목을 정확히 파악하여 필요한 부분만 최적화

Read-Modify-Write 패턴을 경계하라

// 위험한 패턴
entity.setValue(entity.getValue() + 1);

이 간단해 보이는 코드가 동시성 환경에서는 치명적인 버그를 만든다.

다음 패턴을 발견하면 항상 동시성 제어를 고려해야 한다:

• 카운터 증가/감소 (solvers, likes, views)
• 재고 수정 (stock -= quantity)
• 잔액 업데이트 (balance += amount)
• 포인트 적립 (points += reward)

해결책:

• JPA 비관적 락
• 원자적 연산 (AtomicInteger 등)
• DB의 UPDATE 쿼리로 직접 증가 (UPDATE ... SET count = count + 1)

동시성 제어는 레이어마다 다르다

애플리케이션 레벨: Redisson 같은 분산 락으로 거시적인 순서 보장 데이터베이스 레벨: JPA 비관적 락으로 미시적인 데이터 정합성 보장 검증 레벨: 실시간 계산으로 최종 안전망 구축

각 레벨마다 적합한 동시성 제어 기법이 다르다.

테스트의 중요성

일반적인 단위 테스트로는 동시성 문제를 발견하기 어렵다.

다음과 같은 전용 테스트가 필수적이다:

• 멀티스레드 환경 시뮬레이션 (Python asyncio)
• 실제 부하 수준의 동시 요청 (50개 팀 동시 제출)
• 성능 지표 측정 (응답 시간, 처리량, P95/P99)
• 데이터 정합성 검증 (solvers 카운트 정확성)

교훈:

• 동시성 버그는 프로덕션에서 발견하기 전에 반드시 테스트로 잡아야 함
• 부하 테스트 도구 투자는 필수

적용 가능한 다른 상황

이 해결 패턴은 다양한 시나리오에 적용할 수 있다:

좋아요/조회수 시스템

// 문제 패턴
post.setLikeCount(post.getLikeCount() + 1);

// 해결책
@Lock(LockModeType.PESSIMISTIC_WRITE)
Optional<Post> findByIdWithLock(Long postId);

재고 관리

// 문제 패턴
product.setStock(product.getStock() - quantity);

// 해결책: 비관적 락 + 비동기 재고 동기화

티켓 예매

// 문제 패턴
seat.setReservedCount(seat.getReservedCount() + 1);

// 해결책: 비관적 락 + 비동기 알림 처리

투표 시스템

// 문제 패턴
poll.setVoteCount(poll.getVoteCount() + 1);

// 해결책: 비관적 락 + 실시간 카운트 계산

공통 패턴: Read-Modify-Write + 무거운 후처리 작업

공통 해결책: 비관적 락 (필수) + 간소화된 비동기 (선택) + 실시간 검증 (권장)

결론

간단해 보이는 카운터 증가 코드(solvers + 1)가 동시성 환경에서 얼마나 복잡한 문제를 일으킬 수 있는지 경험했다.

문제 해결 여정

1. 문제 발견: 50개 중 25개만 성공 → Redisson 타임아웃
2. 첫 번째 시도: 비동기 처리 아키텍처
   • 무거운 작업(점수 계산, 알림)을 백그라운드로 분리
   • 결과: 성능 개선 but 새로운 Race Condition 발생 (solvers 부정확)
3. 문제 재발견: solvers 카운트 불일치 (50 예상 → 47 실제)
4. 최종 해결
   • 핵심 작업은 동기로 되돌림 (ChallengeService의 락 안에서)
   • 비관적 락 추가로 Read-Modify-Write 패턴 보호
   • 비동기는 외부 알림만 담당하도록 축소
   • 결과: 성능 + 정합성 모두 확보

핵심 원칙

1. 비동기는 만능이 아니다: 데이터 무결성이 중요한 작업은 동기로 처리
2. 비관적 락의 재평가: 적절한 상황에서는 매우 효과적
3. Read-Modify-Write는 항상 보호: 카운터 증가는 반드시 락으로 보호
4. 각 레벨에 맞는 동시성 제어: 애플리케이션, DB, 검증 각각 다른 기법
5. 협업의 힘: 서로 다른 관점이 더 나은 해결책을 만듦

최종 교훈

"무거운 작업은 비동기로"라는 단순한 접근은 실패했다.

진짜 중요한 것은:

• 무엇을 비동기로 처리할 것인가? (핵심 vs 부가 기능)
• 데이터 정합성을 어떻게 보장할 것인가? (비관적 락)
• 검증 체계를 어떻게 구축할 것인가? (실시간 계산)

여담으로 함께 작업할 팀이 있다는 건 굉장히 좋은 거 같다.

참고 자료

Spring & JPA 공식 문서

• Spring @Async Documentation
• Spring Data JPA - Locking
• JPA Locking (Jakarta Persistence)
• Controlling Concurrent Access to Entity Data with Locking
• Hibernate User Guide - Locking

Concurrency 관련

• ThreadPoolTaskExecutor JavaDoc

Redis & Redisson

• Redisson Distributed Locks

• Map은 다른 자료구조와는 다르게 Key와 Value를 쌍으로 데이터를 저장하는 자료구조
• Key를 통해 Value에 접근할 수도 있고 Value를 통해 Key를 찾을 수도 있다.
• 또 하나의 정의된 Map에서는 Key의 중복은 불가능 하지만 Value의 중복은 가능하다.
• Key 와 Value는 모두 객체로 구성되어 있다.

Hash 란?

• Hash는 단방향 암호화 기법으로 입력된 값을 출력 데이터의 위치 값으로 변환해준다.
• Hash 함수은 이 Hash 기법을 사용하는 함수로, 입력값과 출력 데이터의 위치값을 연결(매핑, mapping) 해준다.
• Hash 기법은 시간복잡도는 평균적으로 O(1)인 자료구조로 데이터 접근, 검색에 용이하다.
• 다만, 데이터가 순서 없이 저장되므로 정렬이 필요하지 않고, 빠른 검색이 필요한 데이터에 사용한다.

HashMap 이란?

• HashMap 은 Hash 기법을 사용하여 데이터를 보관하는 자료구조
• 이터에 접근하거나 검색할 때 데이터들을 순회하면서 일일이 비교하는 일반적인 자료구조와 다르게 key값을 통해 한 번의 산술연산으로 데이터에 접근할 수 있기 때문에 아주 빠른 접근 속도와 검색 속도가 특징
• 순서를 보장하지 않는다.

Fig1. HashMap, HashTable 구조 (https://medium.com/depayse/kotlin-data-structure-hashtable-ebb9f949e936 의 이미지 참고)

Collision(충돌)

Hash 함수를 거친 HashMap을 보게 되면, 배열로 이루어져 있다.

배열의 원소에는 또 여러 개의 데이터가 들어있다.

이유는 서로 다른 두 입력 값이 Hash function을 거쳐 나온 HashMap의 주소를 가리키는 곳이 같을 수도 있기 때문이다. 이런 경우를 collision(충돌)이라고 한다.

만약 Hash 함수가 여러 입력 값에 대해 같은 결과를 많이 만든다면, collision이 많아질 수 있고, 이렇게 되면 데이터를 찾는데 더 오랜 시간이 걸릴 수 있다. 따라서 Hash function을 잘 설계하는 것도 HashMap의 효율성에 연관된다.

→ Collision이 최대한 안 생기도록 Hash 함수를 설계해야 한다.

Hash function

다음은 Hash function을 구현하는 대표적인 방법들이다.

• Division Method : 나눗셈을 이용하는 방법으로 입력값을 테이블의 크기보다 큰 값으로 나누어 계산한다. 테이블의 크기를 소수로 정하고 2의 제곱수와 먼 값을 사용해야 효과가 좋다고 알려져 있다. h(k) = k % Q (단, Q ≥ table size)
• Digit Folding : Folding이란 key를 동일하게 분할한 후 각 부분을 XOR연산하거나, 더하거나, 또는 key가 문자열일 경우 ASCII 코드로 바꾸고 값을 합하는 등의 연산을 하여 테이블 내의 주소로 사용하는 방법이다.
• Multiplication Method : 숫자로 된 key값 k와 0과 1사이의 실수 A, 보통 2의 제곱수인 m을 사용하여 다음과 같은 계산을 해준다. h(k)=(kA % 1) × m
• Radix Conversion : 진수 변환을 통해 테이블 내의 주소로 사용하는 방법이다.
• Algebraic Coding : key를 이루고 있는 각각의 bit를 다항식의 계수로 이용하여 계산한 값을 테이블 내의 주소로 사용하는 방법이다.
• Univeral Hashing : 다수의 해시함수를 만들어 집합 H에 넣어두고, 무작위로 해시함수를 선택해 해시값을 만드는 기법이다.

Collision resolution(충돌 해결법)

1. Separate chaining

• Fig1과 같이 동일한 Bucket에 여러 개의 데이터를 저장하여 관리하는 방법
• Bucket안의 데이터들을 Linked List를 활용해 Separate chaining을 적용할 경우, N개의 데이터가 같은 Bucket에 저장된다면 최악의 경우 O(N)의 시간복잡도를 가진다.
• Bucket 안의 데이터들을 관리하는 자료구조의 구현을 제외하면 구현이 간단하고, 쉽게 추가하고 삭제할 수 있다는 장점이 있다.
• 하지만 데이터의 수가 많아지면 동일한 버킷에 chaining되는 데이터가 많아져 효율성이 감소한다.

1. Open Addressing

• 추가적인 메모리를 사용하는 Chaining 방식과 다르게 비어있는 해시 테이블의 공간을 활용하는 방법 (대표적으로 3가지 방법이 있다.)
• Linear Probing: 현재의 버킷 index로부터 고정폭 만큼씩 이동하여 차례대로 검색해 비어 있는 버킷에 데이터를 저장한다.
• Quadratic Probing: 해시의 저장순서 폭을 제곱으로 저장하는 방식 (처음 충돌이 발생한 경우에는 1만큼 이동하고 그 다음 계속 충돌이 발생하면 2², 3² 칸씩 옮기는 방식)
• Double Hashing Probing: 해시된 값을 한번 더 해싱하여 해시의 규칙성을 없애버리는 방식 (해시된 값을 한번 더 해싱하여 새로운 주소를 할당하기 때문에 다른 방법들보다 많은 연산을 하게 된다.)

Java의 HashMap

• initial capacity

initial capacity는 처음 HashMap을 생성할 때 배열의 크기

HashMap의 배열 공간의 대부분이 찼을 때 collision이 일어날 확률이 높아지므로, 어느 정도 데이터가 차면 HashMap의 배열의 크기를 늘려줘야 함.

데이터가 어느 정도 찼는지의 정도를 나타내는 것이 load factor 이고, 이 값은 0에서 1사이의 값이 될 수 있다.

• load factor

HashMap을 생성할 때 이 값을 정해주지 않으면 initial capacity는 16, load factor는 0.75로 작동한다.

배열을 확장하는 것은 시간을 소요하는 작업이므로 어느 정도의 데이터를 저장할 것인지에 따라 initial capacity를 정해주는 것이 중요하다.

Java의 HashMap은 separate chaining을 사용하여 Bucket에 Linked List를 사용하거나, java8 이후에는 Red-Black Tree를 사용한다.

참고

• https://medium.com/depayse/kotlin-data-structure-hashtable-ebb9f949e936
• https://huiwoo-devlog.tistory.com/4

초기 구현

import java.util.*;

//HashMap의 key와 value를 구현하기 위한 클래스
class Hash {
    private String key;
    private String value;
    private Hash nextNode;

    public Hash(String key, String value) {
        this.key = key;
        this.value = value;
        this.nextNode = null;
    }

    public Hash(String key, String value, Hash nextNode) {
        this.key = key;
        this.value = value;
        this.nextNode = nextNode;
    }

    // Getters and Setters
    public String getKey() { return key; }
    public String getValue() { return value; }
    public void setValue(String value) { this.value = value; }
    public Hash getNextNode() { return nextNode; }
    public void setNextNode(Hash nextNode) { this.nextNode = nextNode; }
}

//Bucket Size : 초기 버킷 크기(16)
//Separate Chaining으로 충돌 해결
class CustomizedHashMap {
    private Hash[] bucket;
    private int bucketSize;
    private int currentSize;
    // 버킷 크기가 3/4가 넘을 경우 배열 크기 늘리기 위한 변수 (load factor)
    private final double loadFactor = 0.75;

    public CustomizedHashMap() {
        this(16);
    }

    public CustomizedHashMap(int bucketSize) {
        this.bucketSize = bucketSize;
        this.bucket = new Hash[bucketSize];
        this.currentSize = 0;
    }

    //해시 함수 (Digit Folding 방식)
    private int hash(String key) {
        int hashValue = 0;
        int keySegment = 2;

        for (int i = 0; i < key.length(); i += keySegment) {
            int endIndex = Math.min(i + keySegment, key.length());
            String segment = key.substring(i, endIndex);
            for (char c : segment.toCharArray()) {
                hashValue += (int) c;
            }
        }

        return hashValue % bucketSize;
    }

    //크기 2배로 늘리기
    private void resize() {
        Hash[] oldBucket = bucket;
        bucketSize *= 2;
        bucket = new Hash[bucketSize];
        currentSize = 0;

        for (Hash head : oldBucket) {
            Hash current = head;
            while (current != null) {
                put(current.getKey(), current.getValue());
                current = current.getNextNode();
            }
        }
    }

    /*
    put
    - 현재 배열 크기가 3/4을 넘을 경우 크기 2배로 늘리기.
    - 만약 이미 같은 key가 존재한다면, value 바꾸기.
    - 새로운 key라면 맨 뒤에 추가하기.
     */
    public void put(String key, String value) {
        if (currentSize >= loadFactor * bucketSize) {
            resize();
        }

        int index = hash(key);

        if (bucket[index] == null) {
            bucket[index] = new Hash(key, value);
            currentSize++;
            return;
        }

        Hash current = bucket[index];
        while (current != null) {
            if (current.getKey().equals(key)) {
                current.setValue(value);
                return;
            }
            current = current.getNextNode();
        }

        Hash newNode = new Hash(key, value);
        newNode.setNextNode(bucket[index]);
        bucket[index] = newNode;
        currentSize++;
    }

    //Bucket 배열 비우기 + 현재 크기 0
    public void clear() {
        bucket = new Hash[bucketSize];
        currentSize = 0;
    }

    //Linked list 형식으로 앞으로 가며 탐색하기
    public String get(String key) {
        int index = hash(key);
        Hash current = bucket[index];

        while (current != null) {
            if (current.getKey().equals(key)) {
                return current.getValue();
            }
            current = current.getNextNode();
        }
        return null;
    }

    //현재 크기 반환
    public int size() {
        return currentSize;
    }

    //같은 키가 존재한다면 true 없으면 false
    public boolean containsKey(String key) {
        int index = hash(key);
        Hash current = bucket[index];

        while (current != null) {
            if (current.getKey().equals(key)) {
                return true;
            }
            current = current.getNextNode();
        }
        return false;
    }

    //현재 크기가 0인지 확인
    public boolean isEmpty() {
        return currentSize == 0;
    }

    /*
    remove
    - 삭제할 키가 맨 앞인 경우
    - 삭제할 키가 맨 앞이 아닌 경우 (탐색하며 찾아 삭제)
     */
    public boolean remove(String key) {
        int index = hash(key);
        Hash current = bucket[index];

        if (current == null) return false;

        if (current.getKey().equals(key)) {
            bucket[index] = current.getNextNode();
            currentSize--;
            return true;
        }

        while (current.getNextNode() != null) {
            if (current.getNextNode().getKey().equals(key)) {
                current.setNextNode(current.getNextNode().getNextNode());
                currentSize--;
                return true;
            }
            current = current.getNextNode();
        }

        return false;
    }

    //전체 키 리스트 반환
    public List<String> keys() {
        List<String> allKeys = new ArrayList<>();
        for (int i = 0; i < bucket.length; i++) {
            Hash current = bucket[i];
            while (current != null) {
                allKeys.add(current.getKey());
                current = current.getNextNode();
            }
        }
        return allKeys;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        CustomizedHashMap customizedHashMap = new CustomizedHashMap();

        while (true) {
            System.out.print("하고 싶은 동작을 입력해주세요!(put, get, clear, size, containsKey, isEmpty, remove, keys, exit) : ");
            String order = scanner.nextLine().trim().toLowerCase();

            switch (order) {
                case "put":
                    System.out.print("키를 입력하세요: ");
                    String key = scanner.nextLine();
                    System.out.print("값을 입력하세요: ");
                    String value = scanner.nextLine();
                    customizedHashMap.put(key, value);
                    System.out.println("추가 완료: (" + key + ", " + value + ")");
                    break;

                case "get":
                    System.out.print("찾을 키를 입력하세요: ");
                    String getKey = scanner.nextLine();
                    String result = customizedHashMap.get(getKey);
                    if (result != null) {
                        System.out.println("값: " + result);
                    } else {
                        System.out.println("키 '" + getKey + "'를 찾을 수 없습니다.");
                    }
                    break;

                case "clear":
                    customizedHashMap.clear();
                    System.out.println("모든 데이터가 삭제되었습니다.");
                    break;

                case "size":
                    System.out.println("현재 크기: " + customizedHashMap.size());
                    break;

                case "containskey":
                    System.out.print("확인할 키를 입력하세요: ");
                    String containsKey = scanner.nextLine();
                    boolean exists = customizedHashMap.containsKey(containsKey);
                    System.out.println("키 '" + containsKey + "' 존재 여부: " + exists);
                    break;

                case "isempty":
                    boolean empty = customizedHashMap.isEmpty();
                    System.out.println("비어있는지 여부: " + empty);
                    break;

                case "remove":
                    System.out.print("삭제할 키를 입력하세요: ");
                    String removeKey = scanner.nextLine();
                    customizedHashMap.remove(removeKey);
                    System.out.println("키 '" + removeKey + "' 삭제 완료");
                    break;

                case "keys":
                    List<Integer> allKeys = customizedHashMap.keys();
                    if (!allKeys.isEmpty()) {
                        System.out.println("모든 키: " + allKeys.toString().replaceAll("[\\[\\]]", ""));
                    } else {
                        System.out.println("저장된 키가 없습니다.");
                    }
                    break;

                case "exit":
                    System.out.println("프로그램을 종료합니다.");
                    scanner.close();
                    return;

                default:
                    System.out.println("잘못된 명령입니다. 다시 입력해주세요.");
            }
        }
    }
}

• Hash 클래스: 키-값 쌍을 저장하는 노드, 다음 노드 참조로 연결리스트 구성
  • key , value , Linked list를 위한 nextNode를 가짐.
• bucket 배열: 각 인덱스가 연결리스트의 헤드를 가리키는 해시 테이블
• loadFactor( 0.75): 버킷의 75%가 차면 자동으로 크기 2배 확장

해시 함수 (Digit Folding)

• 문자열을 2글자씩 나누어 각 문자의 ASCII 값을 합산
• 최종 합을 버킷 크기로 나머지 연산하여 인덱스 생성

충돌 해결 (Separate Chaining)

• 같은 버킷에 여러 데이터가 오면 Linked list로 연결
• 새 노드는 버킷의 맨 앞에 추가 (O(1) 삽입)
• 검색/삭제 시 nextNode을 따라가며 순차 탐색

시간 복잡도

• 평균 경우: 모든 연산이 O(1)
• 최악 경우: 모든 키가 같은 버킷에 몰리면 O(n)
• 리사이징: O(n) - 모든 데이터 재배치 필요

추가 요구 사항

해시맵 키 값이 문자열이 아니라 다른 타입이라면 어떤 부분이 어떻게 바뀌는지 살펴본다.

→ Generic 타입을 사용해 코드를 변경한다.

제네릭 변환 단계별 과정

1.데이터 클래스 변경

// 기존: String 전용
class Hash {
    private String key;
    private String value;
    private Hash nextNode;
}

// 변경: 제네릭 적용
class Hash<K, V> {
    private K key;
    private V value;
    private Hash<K, V> nextNode;
}

클래스 시그니처 변경

// 기존
class CustomizedHashMap {
    public CustomizedHashMap(int bucketSize)
}

// 변경
class CustomizedHashMap<K, V> {
    public CustomizedHashMap(int bucketSize)
}

모든 함수 시그니처 업데이트

// 기존
public void put(String key, String value)
public String get(String key)

// 변경
public void put(K key, V value)
public V get(K key)

2. 해시 함수 변경 이유

기존 Digit Folding 방식은 String에만 특화된 방법이었음.

// 기존: String 전용 Digit Folding
private int hash(String key) {
    int hashValue = 0;
    int keySegment = 2;

    for (int i = 0; i < key.length(); i += keySegment) {
        int endIndex = Math.min(i + keySegment, key.length());
        String segment = key.substring(i, endIndex);
        for (char c : segment.toCharArray()) {
            hashValue += (int) c;  // String에만 있는 속성
        }
    }
    return hashValue % bucketSize;
}

문제점:

• key.length(), key.substring() → String 전용 메서드
• char 타입 → String 문자 전용 속성
• Integer, Double, Custom 객체 등 다른 타입에서는 사용 불가

해결책: 범용 hashCode() 사용

• 모든 Java 객체가 가진 hashCode() 메서드 활용
• 각 타입에 최적화된 해시 알고리즘 자동 적용

해시 함수 변경시 나온 오류

data class 와 함수들을 generic 타입으로 변경하고 그에 맞춰 해시 함수를 변경함.

private int hash(K key) {
    int hashValue = key != null ? key.hashCode() : 0;
    return hashValue % bucketSize;
}

돌렸더니 오류가 나왔다.

하고 싶은 동작을 입력해주세요!(put, get, clear, size, containsKey, isEmpty, remove, keys, exit) : put
키를 입력하세요: boostCamp
값을 입력하세요: naver
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index -12 out of bounds for length 16

이유는 "boostCamp".hashCode() = -2023192380 음수가 나왔기 때문이다.

(-2023192380) % 16 = -12 로 여전히 음수다.

String hashCode 알고리즘:

// Java String.hashCode() 공식
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

"boostCamp" 계산:

b(98) * 31^8 + o(111) * 31^7 + o(111) * 31^6 + s(115) * 31^5 +
t(116) * 31^4 + C(67) * 31^3 + a(97) * 31^2 + m(109) * 31^1 + p(112)

이 계산 결과가 32비트 정수 범위를 초과하면서 오버플로우가 발생하기 때문에 Math.abs 함수를 통해 이를 막아줘야 한다.

전체 코드

import java.util.*;

//HashMap의 key와 value를 구현하기 위한 클래스
class Hash<K, V> {
    private K key;
    private V value;
    private Hash<K, V> nextNode;

    public Hash(K key, V value) {
        this.key = key;
        this.value = value;
        this.nextNode = null;
    }

    public Hash(K key, V value, Hash<K, V> nextNode) {
        this.key = key;
        this.value = value;
        this.nextNode = nextNode;
    }

    // Getters and Setters
    public K getKey() { return key; }
    public V getValue() { return value; }
    public void setValue(V value) { this.value = value; }
    public Hash<K, V> getNextNode() { return nextNode; }
    public void setNextNode(Hash<K, V> nextNode) { this.nextNode = nextNode; }
}

//Bucket Size : 초기 버킷 크기(16)
//Separate Chaining으로 충돌 해결
class CustomizedHashMap<K, V> {
    private Hash<K, V>[] bucket;
    private int bucketSize;
    private int currentSize;
    // 버킷 크기가 3/4가 넘을 경우 배열 크기 늘리기 위한 변수 (load factor)
    private final double loadFactor = 0.75;

    @SuppressWarnings("unchecked")
    public CustomizedHashMap() {
        this(16);
    }

    @SuppressWarnings("unchecked")
    public CustomizedHashMap(int bucketSize) {
        this.bucketSize = bucketSize;
        this.bucket = (Hash<K, V>[]) new Hash[bucketSize];
        this.currentSize = 0;
    }

    //해시 함수
    private int hash(K key) {
        int hashValue = key != null ? key.hashCode() : 0;
        return Math.abs(hashValue) % bucketSize;
    }

    //크기 2배로 늘리기
    @SuppressWarnings("unchecked")
    private void resize() {
        Hash<K, V>[] oldBucket = bucket;
        bucketSize *= 2;
        bucket = (Hash<K, V>[]) new Hash[bucketSize];
        currentSize = 0;

        for (Hash<K, V> head : oldBucket) {
            Hash<K, V> current = head;
            while (current != null) {
                put(current.getKey(), current.getValue());
                current = current.getNextNode();
            }
        }
    }

    /*
    put
    - 현재 배열 크기가 3/4을 넘을 경우 크기 2배로 늘리기.
    - 만약 이미 같은 key가 존재한다면, value 바꾸기.
    - 새로운 key라면 맨 뒤에 추가하기.
     */
    public void put(K key, V value) {
        if (currentSize >= loadFactor * bucketSize) {
            resize();
        }

        int index = hash(key);

        if (bucket[index] == null) {
            bucket[index] = new Hash<>(key, value);
            currentSize++;
            return;
        }

        Hash<K, V> current = bucket[index];
        while (current != null) {
            if (Objects.equals(current.getKey(), key)) {
                current.setValue(value);
                return;
            }
            current = current.getNextNode();
        }

        Hash<K, V> newNode = new Hash<>(key, value);
        newNode.setNextNode(bucket[index]);
        bucket[index] = newNode;
        currentSize++;
    }

    //Bucket 배열 비우기 + 현재 크기 0
    @SuppressWarnings("unchecked")
    public void clear() {
        bucket = (Hash<K, V>[]) new Hash[bucketSize];
        currentSize = 0;
    }

    //Linked list 형식으로 앞으로 가며 탐색하기
    public V get(K key) {
        int index = hash(key);
        Hash<K, V> current = bucket[index];

        while (current != null) {
            if (Objects.equals(current.getKey(), key)) {
                return current.getValue();
            }
            current = current.getNextNode();
        }
        return null;
    }

    //현재 크기 반환
    public int size() {
        return currentSize;
    }

    //같은 키가 존재한다면 true 없으면 false
    public boolean containsKey(K key) {
        int index = hash(key);
        Hash<K, V> current = bucket[index];

        while (current != null) {
            if (Objects.equals(current.getKey(), key)) {
                return true;
            }
            current = current.getNextNode();
        }
        return false;
    }

    //현재 크기가 0인지 확인
    public boolean isEmpty() {
        return currentSize == 0;
    }

    /*
    remove
    - 삭제할 키가 맨 앞인 경우
    - 삭제할 키가 맨 앞이 아닌 경우 (탐색하며 찾아 삭제)
     */
    public boolean remove(K key) {
        int index = hash(key);
        Hash<K, V> current = bucket[index];

        if (current == null) return false;

        if (Objects.equals(current.getKey(), key)) {
            bucket[index] = current.getNextNode();
            currentSize--;
            return true;
        }

        while (current.getNextNode() != null) {
            if (Objects.equals(current.getNextNode().getKey(), key)) {
                current.setNextNode(current.getNextNode().getNextNode());
                currentSize--;
                return true;
            }
            current = current.getNextNode();
        }

        return false;
    }

    //전체 키 리스트 반환
    public List<K> keys() {
        List<K> allKeys = new ArrayList<>();
        for (int i = 0; i < bucket.length; i++) {
            Hash<K, V> current = bucket[i];
            while (current != null) {
                allKeys.add(current.getKey());
                current = current.getNextNode();
            }
        }
        return allKeys;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        CustomizedHashMap<Integer, String> customizedHashMap = new CustomizedHashMap<>();

        while (true) {
            System.out.print("하고 싶은 동작을 입력해주세요!(put, get, clear, size, containsKey, isEmpty, remove, keys, exit) : ");
            String order = scanner.nextLine().trim().toLowerCase();

            switch (order) {
                case "put":
                    System.out.print("키를 입력하세요: ");
                    int key = scanner.nextInt();
                    scanner.nextLine(); // consume newline
                    System.out.print("값을 입력하세요: ");
                    String value = scanner.nextLine();
                    customizedHashMap.put(key, value);
                    System.out.println("추가 완료: (" + key + ", " + value + ")");
                    break;

                case "get":
                    System.out.print("찾을 키를 입력하세요: ");
                    int getKey = scanner.nextInt();
                    scanner.nextLine();
                    String result = customizedHashMap.get(getKey);
                    if (result != null) {
                        System.out.println("값: " + result);
                    } else {
                        System.out.println("키 '" + getKey + "'를 찾을 수 없습니다.");
                    }
                    break;

                case "clear":
                    customizedHashMap.clear();
                    System.out.println("모든 데이터가 삭제되었습니다.");
                    break;

                case "size":
                    System.out.println("현재 크기: " + customizedHashMap.size());
                    break;

                case "containskey":
                    System.out.print("확인할 키를 입력하세요: ");
                    int containsKey = scanner.nextInt();
                    scanner.nextLine();
                    boolean exists = customizedHashMap.containsKey(containsKey);
                    System.out.println("키 '" + containsKey + "' 존재 여부: " + exists);
                    break;

                case "isempty":
                    boolean empty = customizedHashMap.isEmpty();
                    System.out.println("비어있는지 여부: " + empty);
                    break;

                case "remove":
                    System.out.print("삭제할 키를 입력하세요: ");
                    int removeKey = scanner.nextInt();
                    scanner.nextLine();
                    customizedHashMap.remove(removeKey);
                    System.out.println("키 '" + removeKey + "' 삭제 완료");
                    break;

                case "keys":
                    List<String> allKeys = customizedHashMap.keys();
                    if (!allKeys.isEmpty()) {
                        System.out.println("모든 키: " + String.join(", ", allKeys));
                    } else {
                        System.out.println("저장된 키가 없습니다.");
                    }
                    break;

                case "exit":
                    System.out.println("프로그램을 종료합니다.");
                    scanner.close();
                    return;

                default:
                    System.out.println("잘못된 명령입니다. 다시 입력해주세요.");
            }
        }
    }
}

실행 결과

하고 싶은 동작을 입력해주세요!(put, get, clear, size, containsKey, isEmpty, remove, keys, exit) : put
키를 입력하세요: boostCamp
값을 입력하세요: naver
추가 완료: (boostCamp, naver)
하고 싶은 동작을 입력해주세요!(put, get, clear, size, containsKey, isEmpty, remove, keys, exit) : put
키를 입력하세요: boost
값을 입력하세요: java
추가 완료: (boost, java)
하고 싶은 동작을 입력해주세요!(put, get, clear, size, containsKey, isEmpty, remove, keys, exit) : size
현재 크기: 2
하고 싶은 동작을 입력해주세요!(put, get, clear, size, containsKey, isEmpty, remove, keys, exit) : containsKey
확인할 키를 입력하세요: boost
키 'boost' 존재 여부: true
하고 싶은 동작을 입력해주세요!(put, get, clear, size, containsKey, isEmpty, remove, keys, exit) : get
찾을 키를 입력하세요: boost
값: java
하고 싶은 동작을 입력해주세요!(put, get, clear, size, containsKey, isEmpty, remove, keys, exit) : put
키를 입력하세요: boostCamp
값을 입력하세요: mobileApp
추가 완료: (boostCamp, mobileApp)
하고 싶은 동작을 입력해주세요!(put, get, clear, size, containsKey, isEmpty, remove, keys, exit) : get
찾을 키를 입력하세요: boostCamp
값: mobileApp
하고 싶은 동작을 입력해주세요!(put, get, clear, size, containsKey, isEmpty, remove, keys, exit) : isEmpty
비어있는지 여부: false
하고 싶은 동작을 입력해주세요!(put, get, clear, size, containsKey, isEmpty, remove, keys, exit) : remove
삭제할 키를 입력하세요: boostCamp
키 'boostCamp' 삭제 완료
하고 싶은 동작을 입력해주세요!(put, get, clear, size, containsKey, isEmpty, remove, keys, exit) : get
찾을 키를 입력하세요: boost
값: java
하고 싶은 동작을 입력해주세요!(put, get, clear, size, containsKey, isEmpty, remove, keys, exit) : size
현재 크기: 1
하고 싶은 동작을 입력해주세요!(put, get, clear, size, containsKey, isEmpty, remove, keys, exit) : clear
모든 데이터가 삭제되었습니다.
하고 싶은 동작을 입력해주세요!(put, get, clear, size, containsKey, isEmpty, remove, keys, exit) : isEmpty
비어있는지 여부: true
하고 싶은 동작을 입력해주세요!(put, get, clear, size, containsKey, isEmpty, remove, keys, exit) : size
현재 크기: 0
하고 싶은 동작을 입력해주세요!(put, get, clear, size, containsKey, isEmpty, remove, keys, exit) : exit
프로그램을 종료합니다.

성능 요약

메모리: 15832 KB, 시간: 120 ms

분류

구현, 시뮬레이션

제출 일자

2025년 7월 21일 11:22:47

어떻게 풀 수 있을까?

해당 문제 로직은 크게 두 가지로 나뉜다.

첫번째는 남학생.

“스위치 번호가 자기가 받은 수의 배수이면, 그 스위치의 상태를 바꾼다. 즉, 스위치가 켜져 있으면 끄고, 꺼져 있으면 켠다. <그림 1>과 같은 상태에서 남학생이 3을 받았다면, 이 학생은 <그림 2>와 같이 3번, 6번 스위치의 상태를 바꾼다.”

→ 스위치 번호를 입력 받아 해당 스위치 번호를 따로 저장한 후, while문을 통해 스위치 번호에 해당하는 값을 조건문을 통해 바꾼 후 따로 저장한 스위치 번호 값을 + 해주는 방식으로 스위치 번호 수의 배수를 변경해나가면 된다.

두번째는 여학생.

”여학생은 자기가 받은 수와 같은 번호가 붙은 스위치를 중심으로 좌우가 대칭이면서 가장 많은 스위치를 포함하는 구간을 찾아서, 그 구간에 속한 스위치의 상태를 모두 바꾼다. 이때 구간에 속한 스위치 개수는 항상 홀수가 된다.”

→ 처음엔 count 라는 변수를 1로 지정해놓고, 스위치 번호 - count 와 스위치 번호 + count 를 비교해 같으면 count의 값에 + 1을 한 후 비교하는 것을 반복하도록 설정했으나, 런타임 에러(배열 인덱스 길이 초과)가 나옴.

→ 해당 값들을 비교할 수 있는 ‘범위’를 지정해두고, 그 범위 내에서 값들을 비교하도록 변경하면 런타임 에러에서 안전하게 비교할 수 있음!

*그리고 *

“스위치의 상태를 1번 스위치에서 시작하여 마지막 스위치까지 한 줄에 20개씩 출력한다. 예를 들어 21번 스위치가 있다면 이 스위치의 상태는 둘째 줄 맨 앞에 출력한다. 켜진 스위치는 1, 꺼진 스위치는 0으로 표시하고, 스위치 상태 사이에 빈칸을 하나씩 둔다.”

→ 출력에 주의하자! count 변수를 지정해 if 조건문으로 처리함.

처음 짠 코드 (런타임 에러)

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

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

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

        num = new int[n+1];
        num[0] = Integer.MAX_VALUE;
        st = new StringTokenizer(br.readLine());
        for(int i = 1; i <= n; i++){
            num[i] = Integer.parseInt(st.nextToken());
        }

        k = Integer.parseInt(br.readLine());
        for(int i=0; i<k; i++){
            st = new StringTokenizer(br.readLine());
            int gender = Integer.parseInt(st.nextToken());
            int switchNum = Integer.parseInt(st.nextToken());
            if(gender == 1){ //남자
                int count = switchNum;
                while(switchNum <= n){
                    num[switchNum] = num[switchNum] == 0 ? 1 : 0; //스위치 상태가 0이면 1로, 1이면 0 으로
                    switchNum += count;
                }
            }
            else{ //여자
                int count = 1;
                while(true){
                    if(switchNum - count < 1 || switchNum + count > n){
                        break;
                    }
                    if(num[switchNum - count] == num[switchNum + count]){
                        count++;
                    }
                    else{
                        count--;
                        break;
                    }
                }

                for(int j=switchNum-count; j<=switchNum + count; j++){
                    num[j] = num[j] == 0 ? 1 : 0;
                }
            }
        }

        int count = 0;
        for(int i=1; i<=n; i++){
            if(count >= 20){
                count = 0;
                sb.append("\n");
            }
            sb.append(num[i] + " ");
            count++;
        }

        System.out.println(sb.toString());
    }
}

왜 실패했는가?

여학생 로직의 경우에서 문제가 됐다.

int count = 1;
while(true){
    if(switchNum - count < 1 || switchNum + count > n){
        break;
    }
    if(num[switchNum - count] == num[switchNum + count]){
        count++;
    }
    else{
        count--;
        break;
    }
}

for(int j=switchNum-count; j<=switchNum + count; j++){
    num[j] = num[j] == 0 ? 1 : 0;
}

예를 들어

2
1 1
3
1 1
2 1
2 2

와 같은 입력이 주어졌다고 해보자.

문제가 될 수 있는 부분인 2 2 이다.

이 경우,학생은 여자이며 switchNum이 2라는 값을 받게 된다.

그렇다면 while문 안에 들어감과 동시에

if(switchNum - count < 1 || switchNum + count > n){
    break;
}

이 if문 조건에서 걸려 break 문으로 빠져나오게 되고, count는 그대로 1이 된다.

배열 인덱스의 범위는 2까지인데, switchNum은 2, count는 1인 상황이므로

for(int j=switchNum-count; j<=switchNum + count; j++){
    num[j] = num[j] == 0 ? 1 : 0;
}

해당 로직에서 인덱스 범위를 벗어난 3까지 for문을 돌리게 된다.

즉 런타임 에러가 나오게 된다.

코드 수정 + 코드 리팩토링 (통과 코드)

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

public class Main {
    static int n,k; //스위치 개수 , 학생 수
    static int[] num; //스위치 상태 표시 배열
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {

       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        num = new int[n+1];
        num[0] = Integer.MAX_VALUE; //스위치 상태 0번은 사용 X

        //스위치 상태 넣어주기.
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 1; i <= n; i++){
            num[i] = Integer.parseInt(st.nextToken());
        }

        //학생 수 입력 받기
        k = Integer.parseInt(br.readLine());
        for(int i=0; i<k; i++){
            st = new StringTokenizer(br.readLine());

            //각각 성별, 스위치 번호 입력 받기
            int gender = Integer.parseInt(st.nextToken());
            int switchNum = Integer.parseInt(st.nextToken());

            if(gender == 1){ //남자
                studentMan(switchNum);
            }
            else{ //여자
                studentWoman(switchNum);
            }
        }

        printSwitches();
    }
    public static void printSwitches(){

        int count = 0;
        for(int i=1; i<=n; i++){
            if(count >= 20){
                count = 0;
                sb.append("\n");
            }
            sb.append(num[i] + " ");
            count++;
        }

        System.out.println(sb.toString());
    }

    public static void studentWoman(int switchNum){

        /*
        최대 범위를 설정함. 
        예: 만약 switchNum이 3이고, n이 8이라면 최대로 비교할 수 있는 범위는 2임.
        즉 3을 기준으로 1,5번 2,4번 인덱스를 비교하는 것이 최대라고 설정해두면 런타임 에러(배열 인덱스 값 넘어섬)를 벗어날 수 있음.
         */
        int range = Math.min(switchNum - 1, n - switchNum);
        int count = 0;

        for(int j = 0; j<=range; j++){
            if(num[switchNum-j] == num[switchNum+j]){
                count = j;
            }
            else{
                break;
            }
        }

        for(int j = switchNum - count; j <= switchNum + count; j++){
            num[j] = num[j] == 0 ? 1 : 0;
        }
    }

    public static void studentMan(int switchNum){

        int count = switchNum;
        while(switchNum <= n){
            num[switchNum] = num[switchNum] == 0 ? 1 : 0; //스위치 상태가 0이면 1로, 1이면 0 으로
            switchNum += count;
        }
    }
}

개념

• 동적 계획법은 작은 부분 문제의 답을 저장하고 재활용하여 전체 문제를 해결하는 기법입니다
• 일반적으로 중복되는 하위 문제(overlapping subproblems)와 최적 부분 구조(optimal substructure)를 가지는 문제에서 사용됩니다.
• 대표적인 예제로는 피보나치 수열, 배낭 문제(Knapsack Problem), 최단 경로 문제 등이 있습니다

동적 계획법을 사용할 수 있는 가정

1. 큰 문제를 작은 문제로 나눌 수 있어야 한다.
   • 마치 피보나치 수열처럼.
   • 큰 문제들은 작은 문제들로 이루어진다. 작은 문제들로 분할이 가능.
   • 단, 큰 문제와 작은 문제의 관계에서 사이클이 발생해선 안된다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
   • 즉, 점화식을 세울 수 있어야 한다.

DP의 두 가지 방식

1. 탑다운 방식 (Top-down, Memoization)

• 재귀를 이용하여 큰 문제를 작은 문제로 나누어 해결하는 방식이다.
• 이미 계산한 값은 저장하여 중복 계산을 피한다.
• 깊은 재귀 호출이 발생할 수 있으므로 스택 오버플로우 방지에 주의해야 한다.

2. 바텀업 방식 (Bottom-up, Tabulation)

• 작은 문제부터 해결하며 점진적으로 큰 문제를 해결하는 방식이다.
• 반복문을 사용하여 결과를 테이블에 저장하고 참조한다.
• 재귀 호출이 없으므로 스택 오버플로우 문제를 방지할 수 있다.

피보나치 수열을 탑다운과 바텀업으로 한번 구현해봤습니다.

피보나치 수열은 대부분이 익숙할 내용이니 그림으로 설명하겠습니다.

딱 보시면 감이 오실 거라 생각합니다. 자신과 자신의 순서 -1 의 수를 더해 자신의 다음 순서에 저장하는 것을 반복합니다.

즉

위와 같은 형태를 띄게 됩니다.

예제 1: 피보나치 수열 (Top-down, Memoization)

#include <iostream>
#include <vector>
using namespace std;

vector<long long> dp(100, -1);

long long fibonacci(int n) {
    if (n <= 1) return n;
    if (dp[n] != -1) return dp[n];
    return dp[n] = fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n;
    cin >> n;
    cout << "Fibonacci(" << n << ") = " << fibonacci(n) << "\n";
    return 0;
}

예제 2: 피보나치 수열 (Bottom-up, Tabulation)

#include <iostream>
#include <vector>
using namespace std;

long long fibonacci(int n) {
    vector<long long> dp(n + 1, 0);
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n;
    cin >> n;
    cout << "Fibonacci(" << n << ") = " << fibonacci(n) << "\n";
    return 0;
}

0/1 배낭 문제(Knapsack Problem)

문제 설명

• 배낭 문제는 한정된 무게(capacity) 내에서 가장 높은 가치를 얻는 방법을 찾는 문제이다.
• n개의 아이템이 주어지며, 각 아이템은 무게(weight)와 가치(value)를 가진다.
• 아이템을 한 번만 선택할 수 있으며(0/1 선택), 무게 한도를 초과할 수 없다.

해결 방법

• dp[i][w]는 i번째 아이템까지 고려했을 때, 무게 w 이하에서의 최대 가치를 저장하는 2차원 배열이다.
• 점화식:
  • 만약 현재 아이템의 무게가 w보다 작다면, 해당 아이템을 선택할 수 있음.
  • dp[i][w] = max(dp[i-1][w], values[i-1] + dp[i-1][w-weights[i-1]])
  • 그렇지 않다면, 해당 아이템을 선택하지 않음.
  • dp[i][w] = dp[i-1][w]

코드 구현 (Bottom-up Approach)

#include <iostream>
#include <vector>
using namespace std;

int knapsack(int W, vector<int>& weights, vector<int>& values, int n) {
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            if (weights[i - 1] <= w)
                dp[i][w] = max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]]);
            else
                dp[i][w] = dp[i - 1][w];
        }
    }
    return dp[n][W];
}

이제 백준 문제를 통해 배낭 문제를 알아보고자 합니다. (https://www.acmicpc.net/problem/12865)

(https://sectumsempra.tistory.com/103) 를 참고해 작성된 예시입니다. 설명을 너무 잘 해주셔서 가져왔습니다.

해당 문제를 요약하자면

짐 4개가 다음과 같이 있을 때, 7kg까지 넣을 수 있는 가방에 넣을 수 있는 짐의 가치의 최대합은 얼마인가?

해결 방법 (아이디어)

1. [짐의 수+1][무게+1] 크기의 배열을 생성합니다. 위 문제의 경우 짐이 4개이고 가방에 7kg까지 담을 수 있으니 아래와 같이 표를 생성합니다.

2. 칸을 채워나간다. 우선 첫 번째 행의 경우는 가방에 무게6, 가치 13의 짐을 넣으려 하는 경우인데, 1~5kg까지 담을 수 있다고 가정하면 이 짐은 넣을 수 없고, 6,7kg까지 담을 수 있다고 하는 경우에만 짐을 넣을 수 있습니다.

즉 담을 수 없는 경우엔 0 이라는 값을 넣어줍니다.

최대 7kg까지 담을 수 있다고 했기 때문에 두 번째 짐도 넣어보면

여기서 주목할 점은 배열[2][6] , 배열[2][7]입니다. 가치 8짜리 짐을 넣는 것 보다 13짜리 짐을 넣는 것이 이득이기 때문에 바로 윗칸의 값, 즉 배열[1][6], 배열 [1][7]부분을 각각 가져오고 있습니다.

이제 3,6짜리 짐을 넣는다고 하면 여기서는 배열[3][7]부분에 주목해야 합니다. 단순히 윗칸의 값을 가져오는 것보다 가치 8짜리 짐(2번 짐)과 가치 6인 짐(3번짐)을 넣는 것이 이득이기 때문에 값 14가 들어갑니다. 

이를 알고리즘의 점화식으로 표현한다면!

현재 짐을 넣을 수 있다.

    짐을 넣는다.
    -> 배열[i-1][W-현재 짐의 무게] + 현재 짐의 가치 값을 넣는다.

    짐을 넣지 않는다.
    -> 윗 칸의 값을 가져온다.

현재 짐을 넣을 수 없다.

    짐을 넣지 않는다.
    -> 윗 칸의 값을 가져온다.

이런 식으로 정리할 수 있겠죠 ?

짐을 넣는 경우는 바로 위의 경우를 보면 됩니당. 3번째 짐을 넣을지 말지 검토할 때 무게 7까지 넣을 수 있다면, 2번 짐(무게 4, 가치 8)의 짐을 넣고 3번 짐을 넣습니다. 즉 배열[3][7]에 배열[2][7-3번짐의 무게(3)]+3번 짐의 가치(6) 값을 넣습니다.

우리는 7kg까지 담을 수 있을 때의 최대 가치를 알고싶으니 배열[4][7]이 답이다. 즉 14가 답이 된다.

이를 C++ 코드로 작성하면! (블로그내 c++ 코드입니당)

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define P pair<int,int>
using namespace std;
//[물품 수][무게]
int arr[101][100001];
int allweight[101];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, k, w, v;
    cin >> n >> k;
    //(무게,가치)의 쌍을 담는 벡터 vv
    vector<P> vv;
    for (int i = 0; i < n; i++) {
        cin >> w >> v;
        vv.push_back(P(w, v));
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            int curweight = vv[i-1].first;
            int curval = vv[i-1].second;
            //현재 검토중인 짐을 담을 수 있는 경우(두 경우 중 최적의 경우 선정->max함수 사용)
            //1. 현재 짐을 넣지 않는다(바로 윗 칸의 값을 가져온다.) arr[i-1][j]
            //2. 현재 짐을 넣는다.arr[i-1][j-curweight]+curval
            if (curweight <= j) {
                arr[i][j] = max(arr[i - 1][j - curweight] + curval, arr[i - 1][j]);
            }
            //현재 검토중인 짐을 담을 수 없는 경우
            //바로 윗 칸의 값을 가져온다. arr[i-1][j]
            else {
                arr[i][j] = arr[i - 1][j];
            }
        }
    }
    cout << arr[n][k];

}

2. 그리디 알고리즘(Greedy Algorithm)

개념

• 그리디 알고리즘은 매 순간 최적이라고 생각되는 선택을 하면서 전체 해를 구하는 방법이다.
• 항상 최적해를 보장하지는 않지만, 특정 조건에서 최적해를 보장하는 문제들이 존재한다.
• 대표적인 예제로는 거스름돈 문제, 활동 선택 문제(Activity Selection), 크루스칼 알고리즘 등이 있다.

그리디 알고리즘 단계

💡 그리디 알고리즘의 단계는 매 단계마다 최적이라고 생각되는 선택을 하면서 최종적으로 전체적으로 최적인 해답을 찾아내는 과정을 의미합니다.

💡 그리디 알고리즘의 단계

1. 문제의 최적해 구조를 결정합니다.

2. 문제의 구조에 맞게 선택 절차를 정의합니다 : 선택 절차(Selection Procedure)

- 이 단계에서는 ‘현재 상태’에서 ‘최적인 선택’을 합니다. 이 선택은 이후에는 바뀌지 않습니다.

3. 선택 절차에 따라 선택을 수행합니다.

4. 선택된 해가 문제의 조건을 만족하는지 검사합니다 : 적절성 검사(Feasibility Check)

- 이 단계에서는 선택한 항목이 ‘문제의 조건’을 만족시키는지 확인합니다. 조건을 만족시키지 않으면 해당 항목은 제외됩니다.

5. 조건을 만족하지 않으면 해당 해를 제외합니다.

6. 모든 선택이 완료되면 해답을 검사합니다 : 해답 검사(Solution Check)

- 이 단계에서는 모든 선택이 완료되면, ‘최종 선택’이 ‘문제의 조건을 만족’시키는지 확인합니다. 조건을 만족시키면 해답으로 인정됩니다.

7. 조건을 만족하지 않으면 해답으로 인정되지 않습니다.

예제 1: 거스름돈 문제

문제 설명

• 거스름돈 문제는 가장 적은 수의 동전으로 특정 금액을 거슬러 주는 문제이다.
• 다양한 동전 단위가 주어질 때, 최소 개수의 동전을 사용하여 거스름돈을 만드는 방법을 찾는다.
• 탐욕적 기법을 사용할 수 있는 경우는 큰 단위의 동전이 작은 단위의 동전의 배수인 경우이다. 그렇지 않은 경우 최적해를 보장하지 못할 수도 있다.

해결 방법

• 가장 큰 단위의 동전부터 최대한 사용하면서 남은 금액을 처리한다.
• 해당 단위를 사용한 후, 남은 금액을 더 작은 단위의 동전으로 반복하여 처리한다.

#include <iostream>
#include <vector>
using namespace std;

int minCoins(int amount, vector<int>& coins) {
    int count = 0;
    for (int coin : coins) {
        count += amount / coin;
        amount %= coin;
    }
    return count;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int amount;
    cin >> amount;
    vector<int> coins = {500, 100, 50, 10};
    cout << "Minimum coins needed: " << minCoins(amount, coins) << "\n";
    return 0;
}

예제 2: 회의실 배정 문제(Activity Selection)

문제 설명

• 활동 선택 문제는 한 사람이 여러 개의 활동 중에서 최대한 많은 활동을 선택할 수 있도록 하는 문제이다.
• 각 활동은 시작 시간과 종료 시간이 있으며, 겹치지 않도록 선택해야 한다.
• 탐욕적 기법을 사용할 수 있는 경우는 빨리 끝나는 활동을 먼저 선택하는 방식을 따를 때이다.

해결 방법

• 종료 시간이 가장 빠른 활동을 먼저 선택한다.
• 그 이후 선택한 활동과 겹치지 않는 활동 중에서 다시 종료 시간이 가장 빠른 것을 선택하는 방식으로 진행한다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Meeting {
    int start, end;
};

bool compare(Meeting a, Meeting b) {
    return a.end < b.end;
}

int maxMeetings(vector<Meeting>& meetings) {
    sort(meetings.begin(), meetings.end(), compare);
    int count = 0, lastEnd = 0;
    for (auto& meeting : meetings) {
        if (meeting.start >= lastEnd) {
            count++;
            lastEnd = meeting.end;
        }
    }
    return count;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n;
    cin >> n;
    vector<Meeting> meetings(n);
    for (int i = 0; i < n; i++) {
        cin >> meetings[i].start >> meetings[i].end;
    }
    cout << "Maximum number of meetings: " << maxMeetings(meetings) << "\n";
    return 0;
}

3) 그리디 알고리즘과 DP

💡 비슷한 방법으로 해결이 되는 동적 계획법과 비교를 해봅니다.

DP는 큰 문제를 작은 문제로 나누어 해결, 그리디는 각 단계에서 최적 선택을 한다는 차이가 있습니다. 상황에 따라 적절한 알고리즘을 선택하는 것이 중요합니다.

이번 주차는 코딩테스트의 꽃, 백트래킹과 DFS 그리고 BFS에 대해 학습해보려고 합니다!

그만큼 코딩테스트에 단골 문제로 DFS 혹은 BFS가 나옵니다.

기본적인 문제들도 백준 티어가 최소 실버3? 혹은 실버2부터 시작합니다. 본격적으로 난이도가 올라가는 만큼 이 강의 노트에 만족하지 않고, 구글링을 통해 찾아보는 것도 많은 도움이 될 것 같습니다!

백트래킹

백트래킹은 모든 가능한 경우의 수를 탐색하는 알고리즘 기법으로, 유망하지 않은 경로는 더 이상 탐색하지 않고 되돌아갑니다. 이를 통해 불필요한 탐색을 줄이고 효율적으로 문제를 해결할 수 있습니다.

재귀적으로 문제를 해결하되 현재 재귀를 통해 확인 중인 상태가 제한 조건에 위배가 되는지 판단하고, 해당 상태가 위배되는 경우 해당 상태를 제외하고 다음 단계로 넘어가는 방식입니다.

여기서 “확인 중인 상태가 제한 조건에 위배가 되는지 판단하고, 해당 상태가 위배되는 경우 **해당 상태를 제외”** 한다는 의미로 이를 가지치기라고도 합니다.

주로 모든 경우의 수를 탐색하므로 DFS를 사용해 모든 경우의 수를 탐색하는 과정에서, 조건문 등을 통해 답이 될 수 없는 상황을 정의하고, 이런 상황일 경우엔 탐색을 중지하고 그 이전으로 돌아가 다시 다른 경우를 탐색하도록 만듭니다.

그래프 탐색 (DFS & BFS)

그래프 탐색은 그래프에서 특정 노드를 방문하거나, 특정 조건을 만족하는 노드를 찾는 것을 의미합니다.

이를 위해 사용되는 DFS(깊이 우선 탐색) 과 BFS(너비 우선 탐색)에 대해 설명하겠습니다.

DFS와 BFS의 차이

예시를 위해 가져온 DFS와 BFS 작동 방식입니다.

즉 어떤 노드를 기준으로 깊이(자식)을 먼저 탐색하는가? 혹은 너비(형제)를 먼저 탐색하는가에 차이입니다.

DFS (Depth First Search)

(https://gongbu-ing.tistory.com/58 블로그를 참고했습니다.)

DFS의 진행 방식입니다.

시작 정점을 기준으로 한 노드를 선택해 우선적으로 끝까지 탐색한 후 다른 인접한 노드로 방문할 수 있습니다.

→ DFS는 그래프의 모든 노드를 방문하고자 할 경우 유용합니다.

코드 구현 방식은 재귀 혹은 Stack 을 사용합니다. 기본적으로 저는 Stack을 사용해서 푼 기억은 많이 없습니다 ㅎ…

그렇기에 이 또한 위 블로그 예시로 대체합니다.

void dfs(int depth, int before) {
  if(depth == n) return;

  for (int i = 0; i < n; i++) {
    if(linked[before-1][i] && !visit[i]) {
      visit[i] = true;
      dfs(depth + 1, i + 1);
    }
  }
}

이는 한 곳을 지정한 후 그 노드을 쭉 탐색하는 방식입니다.

BFS (Breadth First Search)

DFS와 달리 시작 노드에서 인접한 노드들을 차례대로 방문하는 것을 볼 수 있습니다.

BFS는 DFS와 달리 Queue를 주로 사용하고 재귀 방식은 사용하지 않습니다.

0. 시작 노드만 저장된 큐를 준비한다.

1. 시작 노드에 방문한다. (방문 여부 체크)

2. 큐에서 노드를 꺼낸다.

3. 꺼낸 노드에 방문한다. (방문 여부 체크)

4. 큐에 인접한 노드들을 추가한다. 

    ※ 단, 방문 여부를 판단하여 방문한 적 있는 노드는 추가를 하지 않는다. 이를 어기면 무한 루프에 빠지게 된다.

5. 큐에 저장된 노드가 없을 때까지 2 ~ 4번을 반복한다.

예시 코드입니다.

void bfs() {
  Queue<Integer> qu = new ArrayDeque<Integer>();
  qu.add(v);  // 시작할 정점 대기열에 추가

  while(!qu.isEmpty()) { // 큐가 완전히 비어있을 때까지 루프
    int el = qu.poll();  // 큐의 맨앞 요소를 꺼낸다.

    for (int i = 0; i < n; i++) {
      if(linked[el-1][i] && !visit[i]) {    // 노드가 서로 연결되있고 방문한 적 없다면?
        visit[i] = true;  // 방문여부 추가!
        qu.add(i+1);  // 방문한 적 없는 노드의 이웃을 전부 큐에 추가
      }
    }
  }
}

예시 문제

바이러스 (https://www.acmicpc.net/problem/2606)

DFS와 BFS를 알아볼 수 있는 간단한 문제입니다.

1번 풀이 (DFS)

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool visited[101]; //방문 여부 확인용
vector<int> graph[101]; //그래프 (인접 리스트 방식)
int cnt = 0;  //감염된 컴퓨터 수를 세는 변수

void dfs(int x)
{
    visited[x] = true;
    for (int i = 0; i < graph[x].size(); i++) // 인접한 노드 사이즈만큼 탐색
    {
        int y = graph[x][i];
        if (!visited[y]) { 
        // 방문하지 않았으면 즉 visited가 False일 때 not을 해주면 True가 되므로 
        //아래 dfs 실행
            dfs(y); // 재귀적으로 방문
            cnt++;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N,computer;
    // N은 컴퓨터 수, E는 연결된 쌍의 수
    cin >> N >> E;
    int x, y;

    for (int i = 0; i < E; i++) {
        cin >> x >> y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }

    dfs(1); // 1번 컴퓨터에서 시작

    cout << cnt << "\n";
    return 0;
}

2번 풀이(BFS)

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

bool visited[101]; // 방문 여부 확인용
vector<int> graph[101]; // 그래프 (인접 리스트 방식)
int cnt = 0; // 감염된 컴퓨터 수를 세는 변수
queue<int> q;

void bfs(int start) {
    visited[start] = true;
    q.push(start);

    while (!q.empty()) {
        int x = q.front();
        q.pop();

        for (int i = 0; i < graph[x].size(); i++) { // 인접 노드 탐색
            int y = graph[x][i];
            if (!visited[y]) { // 방문하지 않은 노드만 탐색
                visited[y] = true;
                q.push(y);
                cnt++; // 감염된 컴퓨터 수 증가
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, E; // N은 컴퓨터 수, E는 연결된 쌍의 수
    cin >> N >> E;

    for (int i = 0; i < E; i++) {
        int x, y;
        cin >> x >> y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }

    bfs(1); // 1번 컴퓨터에서 시작

    cout << cnt << "\n";
    return 0;
}

2번째 예시 문제입니다.

유기농 배추(https://www.acmicpc.net/problem/1012)

주로 이런 류의 문제를 많이 보게 될 것입니다. 즉 어떠한 범위가 있고, 그 범위 안에서의 특정 조건을 만족시키는 값을 찾으라는 방식입니다.

저는 해당 문제를 DFS를 통해 해결했습니다.

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int MAX = 50; // 최대 가로, 세로 크기
int map[MAX][MAX]; // 배추밭 지도
bool visited[MAX][MAX]; // 방문 여부
int dy[] = {0, 0, -1, 1}; // 상하좌우
int dx[] = {-1, 1, 0, 0};
int M, N, K; // 가로, 세로, 배추 개수
int ans;

void dfs(int x, int y) {
    visited[x][y] = true;

    for (int i = 0; i < 4; i++) {
        int temp_x = x + dx[i];
        int temp_y = y + dy[i];

        if (temp_x >= 0 && temp_y >= 0 && temp_x < M && temp_y < N) {
            if (map[temp_x][temp_y] == 1 && !visited[temp_x][temp_y]) {
                dfs(temp_x, temp_y);
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int T; // 테스트 케이스 수
    cin >> T;

    while (T--) {
        cin >> M >> N >> K;

        // 초기화
        memset(map, 0, sizeof(map));
        memset(visited, false, sizeof(visited));
        ans = 0; //배추흰지렁이 마리 수

        for (int i = 0; i < K; i++) {
            int x, y;
            cin >> x >> y;
            map[x][y] = 1; // 배추 위치 설정
        }

        for (int j = 0; j < M; j++) {
            for (int k = 0; k < N; k++) {
                if (map[j][k] == 1 && !visited[j][k]) {
                    dfs(j, k); // 새로운 영역 탐색
                    ans++;
                }
            }
        }

        cout << ans << "\n";
    }

    return 0;
}

문제 풀이 순서

1. 각각의 테스트 케이스 수를 입력 받는다.

2. map 크기 즉, 배추 밭 크기와 방문 여부를 초기화한다.

3. 각각의 입력을 받는다. (배추 위치 1로 설정)

4. 2중 for문을 통해 해당 위치에 배추가 있고, 방문하지 않은 곳을 탐색한다.

5. 해당 위치에서 DFS 알고리즘을 실행한 후 배추흰지렁이 마리 수를 추가한다.

DFS 알고리즘
1. 해당 위치를 방문 처리한다.

2. 해당 위치에서 동서남북으로 이동했을 경우를 따진다.

3. 해당 위치가 배추 밭 안에 있는 지 확인한다. (배열 기준으로 0보다는 크고 M과 N보다는 작은 지 확인)

4. 만약 동서남북으로 이동한 위치에 배추가 있다면, 재귀 방식으로 해당 위치에서 DFS를 실행한다.

문제 푸는데 도움이 됐으면 좋겠습니다! 감사합니다!

쇠막대기 (https://www.acmicpc.net/problem/10799)

문제를 읽어보시면 숨이 턱 막히며 어렵다 라고 생각하실 수 있습니다!! 하지만 처음엔 누구나 다 어렵고 힘듭니다. 걱정하지 마세요 정상입니다 :)

이번에도 똑같이 문제 설명을 한번 읽어보시고

레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 ‘( ) ’ 으로 표현된다. 또한, 모든 ‘( ) ’는 반드시 레이저를 표현한다.
쇠막대기의 왼쪽 끝은 여는 괄호 ‘ ( ’ 로, 오른쪽 끝은 닫힌 괄호 ‘) ’ 로 표현된다.

이 내용이 중요해보입니다.

이 문제의 핵심은 사실 () 안에 얼마나 많은 ‘(’ 그리고 ‘)’가 있는가? 입니다.

해당 문제 이미지입니다.

한번 세볼까요?

정말 17개네요!

그리고 각 괄호는 이렇게 대응이 되고 있습니다.

여기서

이 부분을 한번 볼까요? 레이저 양 옆에 괄호가 둘러싸여있습니다.
그리고 레이저가 반으로 자르니까 2개의 조각이 나오게 됩니다. 이걸 코드로 구현하면 어떻게 해야 할까요?
제 생각엔 레이저를 만나기 전까지 ‘(’ 의 개수와 마지막 닫는 ‘)’ 의 개수를 더해줄 것 같습니다. 그러면 딱 2개가 나오니깐요. 이 원리로 하나하나 접근해봅시다.
첫번째 레이저는 스킵하겠습니다 (지워지는 조각이 없습니다.)

두번째 레이저입니다.

‘(((’ 괄호가 3개가 있네요 + 3개 카운트해주겠습니다.

세번째 레이저입니다.

똑같이 닫는 ‘)’가 없으므로 3개 더 카운트해주면 됩니다 (총 6개)

그 후 닫히는 괄호 하나 해서 + 1

네번째 레이저입니다.

그리고 ‘((’ + ‘(’ 으로 + 3개 ( 10개)

여기서도 괄호가 하나 더 닫히므로 + 1 해주겠습니다.

다섯번째 레이저입니다.

닫히는 괄호를 제외하면 맨 앞 ‘((’ 두 개만 있습니다 + 2개 해주겠습니다. (총 13개)

그리고 닫히는 괄호 2개 해서 + 2개 해주겠습니다. (총 15개)

그리고 마지막으로 여섯번째 레이저는 조각 2개

총 17개가 됩니다!

이를 문제 코드로 볼까요?

문제 코드

#include <iostream>
#include <stack>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    stack<char> bracket_stack;  // 괄호를 저장하는 스택
    int total_pieces = 0;       // 총 잘려진 쇠막대기의 조각 수
    string input;               // 입력 문자열

    cin >> input;

    for (int i = 0; i < input.length(); i++) {
        if (input[i] == '(') {
            bracket_stack.push(input[i]);  // 여는 괄호를 스택에 추가
        } else { // input[i] == ')'
            if (input[i - 1] == '(') {
                // 레이저인 경우
                bracket_stack.pop();      // 레이저의 여는 괄호 제거
                total_pieces += bracket_stack.size();  // 현재 스택 크기만큼 조각 추가
            } else {
                // 쇠막대기의 끝인 경우
                bracket_stack.pop();      // 쇠막대기의 끝을 처리
                total_pieces++;           // 하나의 조각 추가
            }
        }
    }

    cout << total_pieces << "\n";

    return 0;
}

문제 코드에서 주석을 통해 설명을 보충했습니다.

해당 문제는 O(N)으로 해결할 수 있겠죠? 감사합니다!

queuestack 문제 (https://www.acmicpc.net/problem/24511)

문제를 처음 읽을 경우 “?” 라는 생각이 들 수 있습니다. 제가 그랬거든요 ㅎ;

문제 설명을 다시 한번 차근차근 읽어보시고 와주세요!

예제 1을 통해 어떻게 동작하는지 한번 확인해보겠습니다.

4
0 1 1 0
1 2 3 4
3
2 4 7

기본적인 입력입니다.

자료구조의 개수 N= 4이고

두번째 줄엔 i번 자료구조가 큐인지 스택인지 써있습니다. 즉

이런 식으로 구성이 될겁니다.

그 후 삽입할 수열의 길이 M = 3이고

2 4 7 이 들어오게 됩니다.

즉 먼저 0번 자료구조(큐) 에 2라는 값이 PUSH될겁니다. 그리고는 pop됩니다.

이런 식으로 바뀌겠죠? (큐는 선입선출: 먼저 들어온 값이 먼저 나간다)

그리고 1번 자료구조인 스택에 1이라는 값이 push되어 넘어가게 될겁니다.

하지만 여기서 중요한 점은 스택은 선입후출 즉 먼저 들어온 값이 나중에 나가게 됩니다.

그 말은 즉 스택은 기존의 값 변화 없이 새로 들어온 값이 2번 자료 구조 스택으로 pop된다는 겁니다.

그렇기에 1이라는 값이 빠져나가게 됩니다.

2번도 스택이므로 똑같이?

새로 들어왔던 값이 또 빠이빠이 하고 나가게 됩니다.

이제 3번에서는 자료구조가 큐이므로 어떤 값이 빠져나가나요?

바로 먼저 들어왔던 4라는 값이 나가게 됩니다.

그렇기에 예제 출력 1에서

4 1 2

첫번째 값이 4가 되는 것입니다!

이런 식으로 쭉쭉 이어나가게 되는 과정이라고 설명드릴 수 있을 거 같습니다!

여기서 이상한 점을 느끼시면 좋을 거 같습니다.

막말로 스택은 하는 일이 없습니다!

이 말이 바로 문제의 핵심입니다.

다시 문제를 한번 볼까요?

시간제한은 1초입니다.

그리고 우리가 넣을 수 있는 최대 자료구조의 개수 N은?

10만개까지입니다.

이 말이 의미하는 바가 뭔가요? 라고 한다면

100000 X 100000 은 10000000000 즉 10억입니다.

제가 ppt에서 간단하게 코멘트로 적어두긴 했지만 다시 한번 말씀드리자면

대략 컴퓨터가 1억 번의 연산을 하기 위해서는 1초 정도의 시간이 필요합니다.

고로 적어도 우리는 O(N^2)이 되선 안됩니다.

이걸 생각하고 스택이 필요없다 라는 걸 인지하신다면 풀이가 좀 간소화되고, 그만큼의 시간복잡도가 줄어들게 됩니다.

여기서 말하는 스택이 필요없다 라는 말을 조금 디테일하게 설명드리는 겸 문제 풀이를 먼저 올려드리겠습니다.

문제 코드

#include <iostream>
#include <queue>

using namespace std;

queue<int> queue_storage;      // 큐 역할을 하는 변수
bool is_stack[100000];         // 데이터가 스택에 들어가야 하는지 여부를 나타내는 배열

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;                     // 기존 데이터의 개수
    int m;                     // 새로 삽입할 데이터의 개수
    int value[100001] = {};                 // 입력값
    cin >> n;

    // 데이터가 스택에 들어가야 하는지 여부 입력
    for (int i = 0; i < n; i++) {
        cin >> is_stack[i];
    }

    // 기존 데이터 입력
    for (int i = 0; i < n; i++) {
        cin >> value[i];
    }

    //데이터 처리
    for (int i = n-1; i >= 0; i--) { //역순으로 입력받은 데이터를 처리해야 함!!
        if (!is_stack[i]) {  // 0이라면 값 넣어주기 
            queue_storage.push(value[i]);
        }
    }

    // 새 데이터 입력 +  결과 출력
    int num;
    cin >> m;

    for (int i = 0; i < m; i++) {
        cin >> num;
        queue_storage.push(num);
        cout << queue_storage.front() << " ";
        queue_storage.pop();
    }

    return 0;
}

해당 풀이에서는 Stack 을 사용하지 않습니다.

먼저 기본적인 데이터 입력을 실행합니다.

그 후

    //데이터 처리
    for (int i = n-1; i >= 0; i--) { //역순으로 입력받은 데이터를 처리해야 함!!
        if (!is_stack[i]) {  // 0이라면 값 넣어주기 
            queue_storage.push(value[i]);
        }
    }

이 부분이 사실상 메인이라고 보시면 됩니다.

is_stack 배열은 0 1 1 0 즉 자료구조가 스택인지 큐인지 확인하는 boolean 형 배열입니다.

즉 0 (큐일 경우)엔 선언한 queue에 값을 넣어주죠.

하지만 for문을 역순으로 처리했습니다. 이는 위 과정에서

결과적으로 뭐가 먼저 빠져나왔는지를 생각하시면 편합니다.

어떤 값을 넣든, 맨 마지막 큐의 처음 들어간 값이 먼저 출력됩니다.

그렇게 설계를 하려면

위와 같이 설계가 되야 합니다. (top이 아니라 front인데 죄송합니다 ;;)

그렇기에 for문을 역으로 설계해 풀이했습니다.

그 밑은 입력과 출력이므로 어렵지 않을 것이라 생각합니다.

성능 요약

메모리: 86944 KB, 시간: 220 ms

분류

0-1 너비 우선 탐색, 너비 우선 탐색, 데이크스트라, 그래프 이론, 그래프 탐색, 최단 경로

제출 일자

2024년 9월 18일 21:31:26

문제 설명

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

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

입력

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

출력

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

풀이(BFS)

여러 블로그를 참고해 해결했다...

각각의 경우(순간이동, +1, -1)를 따져가며 최소를 구한다는 쉬운 풀이임에도 틀렸습니다. 가 나올 수 있는 문제이다.

못 푼 이유

내게 특히 문제가 됐던 반례는

입력: 4 6
출력: 1

위 케이스이다.

답은 분명 1이지만, 방문 여부를 어떻게 처리하느냐에 따라 코드 출력이 2가 나온다.

먼저 답이 1이 나오는 경우는 4 -> 3 -> 6 이 경우이다. 하지만 필자의 코드에서는 자꾸 출력이 2가 나왔는데, 이는 while문에서 4 -> 5 -> 6을 먼저 처리하고 4 -> 3 -> 6를 나중에 처리했기 때문이다.

4 -> 5 -> 6 을 먼저 처리하면 방문 여부 확인 배열에서는 6이 방문했다고 바뀌게 될 것이다. 그 후로 어떤 답이 들어오든 6은 이미 방문했다고 나오므로 최소 시간은 바뀌지 않게 되는 것이다.

위 문제를 해결하지 못해 다른 블로그를 참고했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Node{
    int x;
    int time;

    public Node(int x,int time) {
        this.x=x;
        this.time=time;
    }
}

public class Main {
    //bfs 풀이
    static int n;
    static int k;
    static boolean[] check = new boolean[100001];
    static int min_num = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st =new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        if(n>=k) { //n이 더 크거나 같으면 비교 의미 X
            System.out.println(n-k);
        }
        else {
            bfs(n);
            System.out.println(min_num);
        }
    }

    public static void bfs(int num) {
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(new Node(num,0));
        while(!queue.isEmpty()) {
            Node node=queue.poll();
            check[node.x]=true;

            if(node.x==k) { //최소 시간 찾기
                min_num = Math.min(node.time,min_num);
            }

            //순간이동 가능할 경우 (시간 0초 소요)
            if(node.x *2 <= 100000 && check[node.x*2]==false) {
                queue.add(new Node(node.x*2,node.time));
            }

            //+1 가능할 경우 (시간 1초 소요)
            if(node.x +1<=100000 && check[node.x+1]==false) {
                queue.add(new Node(node.x+1,node.time+1));
            }

            //-1 가능할 경우 (시간 1초 소요)
            if(node.x-1>=0 && check[node.x-1]==false) {
                queue.add(new Node(node.x-1,node.time+1));
            }
        }
    }
}

위 풀이의 경우, 변경한 위치가 k와 같다면 방문 여부를 먼저 확인하지 않고 최소인지 먼저 확인하므로 가능한 풀이이다.

성능 요약

메모리: 120624 KB, 시간: 2820 ms

분류

깊이 우선 탐색, 그래프 이론, 그래프 탐색, 트리

제출 일자

2024년 9월 13일 20:48:53

문제 설명

트리(tree)는 사이클이 없는 무방향 그래프이다. 트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다. 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다.

이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다. 정확히 정의하자면 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이를 말한다.

입력으로 루트가 있는 트리를 가중치가 있는 간선들로 줄 때, 트리의 지름을 구해서 출력하는 프로그램을 작성하시오. 아래와 같은 트리가 주어진다면 트리의 지름은 45가 된다.

트리의 노드는 1부터 n까지 번호가 매겨져 있다.

입력

파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연결하는 두 노드 중 부모 노드의 번호를 나타내고, 두 번째 정수는 자식 노드를, 세 번째 정수는 간선의 가중치를 나타낸다. 간선에 대한 정보는 부모 노드의 번호가 작은 것이 먼저 입력되고, 부모 노드의 번호가 같으면 자식 노드의 번호가 작은 것이 먼저 입력된다. 루트 노드의 번호는 항상 1이라고 가정하며, 간선의 가중치는 100보다 크지 않은 양의 정수이다.

출력

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

풀이 (DFS)

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

class Node {
    int index;
    int cost;

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

public class Main {
    //DFS 문제
    static ArrayList<Node>[] list; //간선과 가중치를 가짐
    static boolean[] visited;
    static int result=0; //결과 (최댓값)

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int n = Integer.parseInt(br.readLine());
        list = new ArrayList[n+1];

        for(int i=1; i<=n; i++) {
            list[i] = new ArrayList<Node>();
        }

        for(int i=0; i<n-1; i++) {
            st = new StringTokenizer(br.readLine());
            int one = Integer.parseInt(st.nextToken());
            int two = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            //양방향이므로 둘 다 add해준다.
            list[one].add(new Node(two,cost));
            list[two].add(new Node(one,cost));
        }

        for(int i=1; i<=n; i++) {
            visited = new boolean[n+1];
            dfs(i,0);
        }

        System.out.println(result);
    }
    public static void dfs(int node, int cost) { //DFS 실행
        if(result < cost) {
            result = cost;
        }
        visited[node]=true;

        for(int i=0; i<list[node].size(); i++) {
            Node n = list[node].get(i);
            if(!visited[n.index]) {
                dfs(n.index,cost+n.cost);
                visited[n.index]=true;
            }
        }
    }
}

성능 요약

메모리: 14192 KB, 시간: 100 ms

분류

그리디 알고리즘, 정렬, 문자열

제출 일자

2024년 9월 12일 17:08:09

문제 설명

접두사X 집합이란 집합의 어떤 한 단어가, 다른 단어의 접두어가 되지 않는 집합이다. 예를 들어, {hello}, {hello, goodbye, giant, hi}, 비어있는 집합은 모두 접두사X 집합이다. 하지만, {hello, hell}, {giant, gig, g}는 접두사X 집합이 아니다.

단어 N개로 이루어진 집합이 주어질 때, 접두사X 집합인 부분집합의 최대 크기를 출력하시오.

입력

첫째 줄에 단어의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 단어가 주어진다. 단어는 알파벳 소문자로만 이루어져 있고, 길이는 최대 50이다. 집합에는 같은 단어가 두 번 이상 있을 수 있다.

출력

첫째 줄에 문제의 정답을 출력한다.

풀이(그리디 알고리즘)

문제 해결 방식은 어렵지 않게 알 수 있었다.

1. 문자열을 정렬한다. (크기가 제각각으로 입력되기 때문에) 2. 문자열을 서로 비교해 큰 문자열에 작은 문자열이 부분문자열이면서 첫 문자열에 나오는지 확인한다. 3. 맞다면 원래 단어 N개에서 하나를 줄이며, for문을 통해 계속 탐색한다.

이를 위해 우리는 문자열 정렬 (길이를 기준으로)과 문자열 함수인 startsWith 혹은 indexOf를 써야한다.

혹시 잘 모르겠다면 참고하자.

• [문자열 길이 기준으로 정렬]
• [startsWith , indexOf]

그런데 처음 풀이가 바로 틀렸습니다 가 나온 문제이다...

첫번째 풀이로도 충분히 가능할 것이라고 생각했는데 당황했다.

첫번째 풀이 (실패)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Set;

public class Main {
    //그리디 알고리즘 문제
    static Set<String> banWord = new HashSet<>();

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

        String[] words = new String[N];

        for(int i=0; i<N; i++) {
            words[i] = br.readLine();
        }

        //문자열 내림차순 정렬하기
        Arrays.sort(words,new Comparator<String>() {
            @Override
            public int compare(String str1, String str2) {
                return str2.length()-str1.length();
            }
        });

        int result=N;

        for(int i=0; i<N; i++) {
            for(int j=i+1; j<N; j++) {
                System.out.println("순서: "+words[i]+" "+words[j]);
                //문자열 비교하기 -> 부분 문자열인지 확인 && 문자열내 첫 문자열이 겹치는지 확인
                if(words[i].contains(words[j])) {
                    if(words[i].startsWith(words[j])) {
                        if(banWord.contains(words[j])) {
                            //이미 집합에 넣지 않을 문자라면 고려 X
                            continue;
                        }
                        else {
                            //집합에 넣지 않을 문자열 추가
                            banWord.add(words[j]);
                            result--;
                        }
                    }
                }
            }
        }

        //최대 집합 크기
        System.out.println(result);
    }
}

먼저 위 풀이에서 실수한 점은 바로 contains와 startsWith를 같이 썼다는 점이다.

startsWith는 부분문자열이 첫 시작 문자열에 나오는 지 확인하는데, contains는 부분문자열이 문자열에 포함되는 지만 확인하는 함수다.

즉 startsWith를 쓰면 굳이 contains를 쓸 필요가 없다.

하지만 그렇다고 해서 문제가 될 이유는 없다. 포함하는 지 확인한 후, 첫 문자열에 해당하는 지 확인한다고 해서 크게 문제가 될 것은 없다고 생각한다.

중복 처리 관련 문제인가 싶었지만, Set을 통해 안되는 문자열을 지워나갔기에 이 또한 아니라고 본다.

아직 어디서 틀린건지 정확히 모르겠어서 이 부분은 더 공부가 필요할듯하다...

혹시나 어느 부분에서 잘못됐는 지 알겠다면 댓글 부탁드립니다

두번째 풀이 (성공)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Set;

public class Main {
    //그리디 알고리즘 문제

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

        String[] words = new String[N];

        for(int i=0; i<N; i++) {
            words[i] = br.readLine();
        }

        //문자열 내림차순 정렬하기
        Arrays.sort(words,new Comparator<String>() {
            @Override
            public int compare(String str1, String str2) {
                return str1.length()-str2.length();
            }
        });

        int result=N;

        //만약 문자열이 접두사형태면 하나씩 지워간다.
        for(int i=0; i<N; i++) {
            for(int j=i+1; j<N; j++) {
                if(words[j].startsWith(words[i])) {
                    result--;
                    break;
                }
            }
        }

        //최대 접두사 X 집합 크기
        System.out.println(result);
    }    
}

결국 다른 블로그 풀이를 참고했다. 내가 처음 짰던 풀이와 어느 정도 비슷해 이해하고 적용하기 어렵지 않아 채택했다. [해당 블로그]

코드잇 부스트 1기 프로젝트 조각집 - 백엔드 부분 담당 정유찬입니다!

조각집이라는 이름으로 기억(추억) 저장 및 공유 서비스를 위한 웹 프로젝트입니다.

[Zogakzip Github]

⏲개발 기간

2024.08.08 ~ 2024.09.07

멤버 구성 (개발)

• 정유찬(백엔드) : 그룹 API 내용 구현 , 배지 API 내용 구현, 이미지 URL 변경 로직 담당
• 오세리(백엔드) : 게시글 API 내용 구현 , 댓글 API 내용 구현 담당
• 곽서하(프론트엔드) : 그룹 / 게시글 / 댓글 / 배지 등 전반적인 프론트엔드 담당

역할 분담

• 정유찬 : 자료 조사, Notion 팀 페이지 개설
• 오세리 : 발표
• 곽서하 : PPT, 자료 조사

🚀 Stacks

백엔드

• Node.js
• Express.js

프론트엔드

• HTML + CSS + JavaScript
• React

데이터베이스

• postgreSQL

협업용 Tools

• Notion
• GitHub
• Discord

🛠구현 내용

그룹

그룹 등록

• 그룹명, 대표 이미지, 그룹 소개, 그룹 공개 여부, 비밀번호를 입력하여 그룹을 등록합니다.

그룹 수정

• 비밀번호를 입력하여 그룹 등록 시 입력했던 비밀번호와 일치할 경우 그룹 정보 수정이 가능합니다.

그룹 삭제

• 비밀번호를 입력하여 그룹 등록 시 입력했던 비밀번호와 일치할 경우 그룹 삭제가 가능합니다.

그룹 목록 조회

• 등록된 그룹 목록을 조회할 수 있습니다.
• 각 그룹의 이미지(한 장), 그룹명, 그룹 소개, 그룹 공개 여부, 디데이(생성 후 지난 일수), 획득 배지수, 추억수, 그룹 공감수가 표시됩니다.
• 공개 그룹 목록과 비공개 그룹 목록을 구분하여 조회합니다.
• 최신순, 게시글 많은순, 공감순, 획득 배지순으로 정렬 가능합니다.
• 그룹명으로 검색 가능합니다.

그룹 상세 조회

• 그룹 목록 페이지에서 그룹을 클릭할 경우 그룹 상세 조회가 가능합니다.
• 비공개 그룹의 경우 비밀번호를 입력하여 그룹 등록시 입력한 비밀번호와 일치할 경우 조회 가능합니다.
• 각 그룹의 대표 이미지, 그룹명, 그룹 소개, 그룹 공개 여부, 디데이(생성 후 지난 일수), 획득 배지 목록, 추억수, 그룹 공감수가 표시됩니다.
• 공감 보내기 버튼을 클릭할 경우 그룹의 공감수를 높일 수 있으며, 공감은 클릭할 때마다 중복해서 보낼 수 있습니다.
• 해당 그룹의 추억 목록이 표시됩니다.

게시글(추억)

게시글 등록

• 닉네임, 제목, 이미지(한 장), 본문, 태그, 장소, 추억의 순간, 추억 공개 여부, 비밀번호를 입력하여 추억 등록이 가능합니다.

게시글 수정

• 비밀번호를 입력하여 추억 등록 시 입력했던 비밀번호와 일치할 경우 추억 수정이 가능합니다.

게시글 삭제

• 비밀번호를 입력하여 추억 등록 시 입력했던 비밀번호와 일치할 경우 추억 삭제가 가능합니다.

게시글 목록 조회

• 그룹 상세 조회를 할 경우 그 그룹에 해당되는 추억 목록이 같이 조회됩니다.
• 각 추억의 닉네임, 추억 공개 여부, 제목, 이미지, 태그, 장소, 추억의 순간, 추억 공감수, 댓글수가 표시됩니다.
• 공개 추억 목록과 비공개 추억 목록을 구분하여 조회합니다.
• 최신순, 댓글순, 공감순으로 정렬 가능합니다.
• 제목, 태그로 검색 가능합니다.

게시글 상세 조회

• 추억 목록에서 추억을 클릭할 경우 추억 상세 조회가 가능합니다.
• 닉네임, 제목, 이미지(한 장), 본문, 태그, 장소, 추억의 순간, 추억 공개 여부, 추억 공감수, 댓글수가 표시됩니다.
• 공감 보내기 버튼을 클릭할 경우 그룹의 공감수를 높일 수 있으며, 공감은 클릭할 때마다 중복해서 보낼 수 있습니다.
• 해당 추억의 댓글 목록이 조회됩니다.

댓글

댓글 등록

• 닉네임, 댓글 내용, 비밀번호를 입력하여 댓글 등록이 가능합니다.

댓글 수정

• 비밀번호를 입력하여 댓글 등록 시 입력했던 비밀번호와 일치할 경우 댓글 수정이 가능합니다.

댓글 삭제

• 비밀번호를 입력하여 댓글 등록 시 입력했던 비밀번호와 일치할 경우 댓글 삭제가 가능합니다.

댓글 목록 조회

• 추억을 조회할 경우 그 추억에 해당되는 댓글 목록이 조회됩니다.
• 닉네임, 댓글 생성 날짜, 댓글 내용이 표시됩니다.

배지

• 그룹은 일정 조건을 달성하면 자동으로 배지를 획득합니다.
• 배지의 종류
  • 7일 연속 추억 등록
  • 추억 수 20개 이상 등록
  • 그룹 생성 후 1년 달성
  • 그룹 공간 1만 개 이상 받기
  • 추억 공감 1만 개 이상 받기
    • 공감 1만 개 이상의 추억이 하나라도 있으면 획득

📖배운 점

첫 프로젝트로 기본적인 Node.js와 Express.js를 통한 백엔드 구현과 같은 기능적인 부분뿐만 아닌, 협업 능력에 대해서도 배울 수 있었다.

협업 능력

!주기적인 회의는 필수 + 백엔드 혼자 개발하는 것이 아니다!

• 단순히 나 혼자 짜는 것이 아니기에 코드 주석, 코드 컨벤션처럼 서로에게 있어 익숙해질 수 있도록 노력해야함을 느낄 수 있었다.

• 일정 조율, 진행 상황 공유 등을 통한 서로간의 이해, 현재 상황을 통한 앞으로의 진행 상황 예상 등 협업하면서 생길 수 있는 여러 가지 상황을 대비할 수 있어야 한다.

• 개발하면서도 필요하다면 중간중간 프론트와 충분한 소통으로 서로에게 맞춰 개발해 가야한다.

기술적 능력

!기본적인 개발 실력을 늘리고 Error에 대해 유연하게 대처하자!

• 기본적인 API를 코드잇 부스트 측에서 제공해주는 방식이었기에 조금 쉽게 개발할 수 있었지만, 앞으로의 프로젝트엔 이런 API를 직접 세팅해야 하므로 개발자로서 더 성장해야 한다.

• Error가 발생한 경우에는, 당황하지 말고 Error 코드를 구글링하거나 공식 문서를 통해 쉽게 찾을 수 있음을 기억하자.

• 한 기능을 코드로 구현한 후에는 테스트 코드를 많이 만들어 예상치 못한 Error를 대비하자.

그 외 능력

!설계를 튼튼하게!

• 이번 첫 프로젝트에서 설계를 튼튼하게 하지 못한 점이 너무 뼈아팠다. Data Schema 등 설계해야 할 부분을 조금 더 꼼꼼히 해 중간에 오류가 발생하지 않도록 해야한다.

💬아쉬운 점

• AWS S3로 배포한 프론트엔드와 Render로 배포한 백엔드를 합치는 과정에서 오류가 발생했었다.
  • 내 코드에서 에러가 발생한건지, 프론트측 코드에서 에러가 발생한건지 확인하지 못했고, 정확히 로직이 잘 돌아가는지 확인하지 못한 채 끝이 났다.
• 앞으로의 프로젝트에서는 끝까지 완성하는 것을 목표로 하여금 계속해서 나아갈 것이다.

• 배포 작업에 대한 이해가 조금 부족했던 거 같다.
  • 코드잇 강의를 통해서 배포하는 방법에 대해 익히긴 했지만, 다른 배포 방식 등 모르는 부분이 아직 많은 거 같아 AWS부터 차근차근 학습해 나갈 예정이다.

그 외...

더 자세한 코드를 확인하고 싶다면 맨 위 Github 주소를 확인하면 된다. [Zogakzip Github]

+ 끝까지 고생해준 팀원분들에겐 너무 감사한 마음이 크다.

+ 이런 프로젝트를 만들 수 있는 경험을 준 코드잇에게도 감사한 마음을 전한다.

성능 요약

메모리: 315256 KB, 시간: 1048 ms

분류

그리디 알고리즘

제출 일자

2024년 9월 10일 15:09:59

문제 설명

홍준이는 요즘 주식에 빠져있다. 그는 미래를 내다보는 눈이 뛰어나, 날 별로 주가를 예상하고 언제나 그게 맞아떨어진다. 매일 그는 아래 세 가지 중 한 행동을 한다.

1. 주식 하나를 산다.
2. 원하는 만큼 가지고 있는 주식을 판다.
3. 아무것도 안한다.

홍준이는 미래를 예상하는 뛰어난 안목을 가졌지만, 어떻게 해야 자신이 최대 이익을 얻을 수 있는지 모른다. 따라서 당신에게 날 별로 주식의 가격을 알려주었을 때, 최대 이익이 얼마나 되는지 계산을 해달라고 부탁했다.

예를 들어 날 수가 3일이고 날 별로 주가가 10, 7, 6일 때, 주가가 계속 감소하므로 최대 이익은 0이 된다. 그러나 만약 날 별로 주가가 3, 5, 9일 때는 처음 두 날에 주식을 하나씩 사고, 마지막날 다 팔아 버리면 이익이 10이 된다.

입력

입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타내는 N개의 자연수들이 공백으로 구분되어 순서대로 주어진다. 날 별 주가는 10,000이하다.

출력

각 테스트케이스 별로 최대 이익을 나타내는 정수 하나를 출력한다. 답은 부호있는 64bit 정수형으로 표현 가능하다.

풀이 (그리디 알고리즘)

그리디 알고리즘 특성상, 풀고 나면 쉽지만... 풀기 전까지는 조금 고민해야 하는 경우가 많다.

풀이 자체는 간단한 편이다.

• 배열을 거꾸로 순회한다.

• 순회하면서 더 큰 수가 나오면 바꾸고, 아니면 최대 수 - 현재 수 를 계산해 결과값에 추가한다.

위 두 가지만 따르면 충분히 해결할 수 있는 문제이다.

주의사항

"각 테스트케이스 별로 최대 이익을 나타내는 정수 하나를 출력한다. 답은 부호있는 64bit 정수형으로 표현 가능하다."

64bit 정수형은 자바 기준 long 타입임을 명심해야 한다.

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

public class Main {
    //그리디 알고리즘 문제

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

        int T = Integer.parseInt(br.readLine()); //테스트 케이스
        for(int i=0; i<T; i++) {
            int N = Integer.parseInt(br.readLine());//배열 수

            int[] num = new int[N];
            st = new StringTokenizer(br.readLine());

            for(int j=0; j<N; j++) {//입력 받기
                num[j] = Integer.parseInt(st.nextToken());
            }

            int max_num = num[N-1]; //최대 이익 수
            long result = 0;

            //만약 이익이 생길 수 있다면 이익 구하기 아니면 최대 이익 수 갱신
            for(int j = N-2; j>=0; j--) {
                if(max_num < num[j]) {
                    max_num = num[j];
                }
                else {
                    result += max_num - num[j];
                }
            }

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

        System.out.println(sb.toString());
    }
}

성능 요약

메모리: 20160 KB, 시간: 236 ms

분류

문자열

제출 일자

2024년 8월 31일 21:27:21

문제 설명

N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 P_N이라고 한다.

• P₁ IOI
• P₂ IOIOI
• P₃ IOIOIOI
• P_N IOIOI...OI (O가 N개)

I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 P_N이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다.

출력

S에 P_N이 몇 군데 포함되어 있는지 출력한다.

풀이

조금 디테일하게 생각해야 하는 문제이다.

필자같은 경우엔 런타임 에러 (StringIndexOutOfBounds) 가 많이 나와 당황했던 문제이기도 하다.

위 에러처럼 문자열 범위를 넘어가지 않도록 하는 것이 중요한 문제이다.

로직 자체는 if문으로 IOI를 찾아나간다고 보면 된다. IOI를 하나 찾을 때마다 카운트해주며 P_N이 되면 정답 +1 을 해주고 카운트에서 1을 빼주면 된다.

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

public class Main {
    //문자열 문제
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        String str = br.readLine();

        int ans=0;
        int count=0;

        for(int i=1; i<m-1; i++) {
            if(str.charAt(i-1)=='I' && str.charAt(i)=='O' && str.charAt(i+1)=='I') {
                count++;

                if(count == n) {
                    count--;
                    ans++;
                }
                i++;
            }
            else {
                count=0;
            }
        }

        System.out.println(ans);
    }
}

성능 요약

메모리: 15032 KB, 시간: 128 ms

분류

임의 정밀도 / 큰 수 연산, 다이나믹 프로그래밍

제출 일자

2024년 8월 30일 15:47:19

문제 설명

2×n 직사각형을 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 정수 n이 주어진다.

출력

입력으로 주어지는 각각의 n마다, 2×n 직사각형을 채우는 방법의 수를 출력한다.

풀이 (DP + BigInteger)

먼저 dp 배열의 점화식을 세워야하는 문제이다.

우리가 사용할 수 있는 도형은 2X1 , 2X2 도형 두 가지뿐이다.

고로 위 3개의 도형을 사용해 점화식을 이끌어야 한다.

예를 들어 DP의 i번째를 끝으로 하는 2 x i 벽을 전부 타일로 채우는 경우를 생각해보자.

이때 가능한 경우는 2가지이다. 1. i-1번째 까진 다 채워진 상황에서 남은 한 열을 채워야 하는 경우 2. i-2번째 까지 다 채운 후 남은 두 열을 채워야 하는 경우

상황 1.

이 경우엔 2X1 블럭 하나를 이용해 채우는 방법밖에 없다.

상황 2.

놀랍게도 2X2 블럭이랑 2X1 블럭 사용한거다. 그냥 그렇게 봐주세요.

아무튼 2X2 블럭 하나를 사용하는 경우 1개, 2X1 블럭 2개를 사용하는 경우 1개. 총 2개의 경우의 수가 있다.

i-3의 경우엔 위 i-1과 중복된 상황이 나오므로 우리는 i-1과 i-2의 상황만 가지고 점화식을 세우면 된다.

즉, 식으로 바꾸면 이렇게 된다.

DP[i] = DP[i-1] + DP[i-2]*2;

이와 함께 큰 수를 다루기 위해 BigInteger를 사용할 것이다.

혹여나 BigInteger에 대해 까먹었을 경우 BigInteger에 대해 설명해주신 [블로그]를 링크로 남긴다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;

public class Main {
    //dp + 큰 수 다루기(BigInteger)
    static BigInteger[] dp = new BigInteger[251];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        calculate(); //dp 배열 값 넣어주기

        String input; //입력 없을 때까지 계속 입력받기 위한 용도.
        while((input = br.readLine())!=null) {
            int n = Integer.parseInt(input);
            System.out.println(dp[n]);
        }
    }

    public static void calculate() {
        dp[0] = new BigInteger("1"); dp[1]= new BigInteger("1"); dp[2]= new BigInteger("3");
        for(int i=3; i<=250; i++) {
            BigInteger two = new BigInteger("2");
            BigInteger addNum = dp[i-1].add(dp[i-2].multiply(two));

            dp[i] = addNum;
        }
    }
}

성능 요약

메모리: 22800 KB, 시간: 160 ms

분류

브루트포스 알고리즘, 깊이 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2024년 8월 29일 13:07:47

문제 설명

5×5 크기의 숫자판이 있다. 각각의 칸에는 숫자(digit, 0부터 9까지)가 적혀 있다. 이 숫자판의 임의의 위치에서 시작해서, 인접해 있는 네 방향으로 다섯 번 이동하면서, 각 칸에 적혀있는 숫자를 차례로 붙이면 6자리의 수가 된다. 이동을 할 때에는 한 번 거쳤던 칸을 다시 거쳐도 되며, 0으로 시작하는 000123과 같은 수로 만들 수 있다.

숫자판이 주어졌을 때, 만들 수 있는 서로 다른 여섯 자리의 수들의 개수를 구하는 프로그램을 작성하시오.

입력

다섯 개의 줄에 다섯 개의 정수로 숫자판이 주어진다.

출력

첫째 줄에 만들 수 있는 수들의 개수를 출력한다.

풀이 (DFS)

DFS로 전체 경로를 모두 검사하고, Set을 통해 중복을 제거한 후 size()를 출력했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
    //DFS 문제
    static int[][] arr = new int[6][6];
    static Set<String> sets = new HashSet<String>();
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};

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

        for(int i=1; i<=5; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=5; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i=1; i<=5; i++) {
            for(int j=1; j<=5; j++) {
                DFS(i,j,"");
            }
        }

        System.out.println(sets.size());
    }

    public static void DFS(int x,int y,String num) {
        if(num.length()==6) {
            sets.add(num);
            return;
        }

        for(int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx >5 || nx<1 || ny>5 || ny<1) {
                continue;
            }

            DFS(nx,ny,num+Integer.toString(arr[nx][ny]));
        }
    }
}

성능 요약

메모리: 15000 KB, 시간: 116 ms

분류

다이나믹 프로그래밍

제출 일자

2024년 8월 28일 19:55:07

문제 설명

BOJ 거리는 보도블록 N개가 일렬로 놓여진 형태의 도로이다. 도로의 보도블록은 1번부터 N번까지 번호가 매겨져 있다.

스타트의 집은 1번에 있고, 링크의 집은 N번에 있다. 스타트는 링크를 만나기 위해서 점프해가려고 한다.

BOJ거리의 각 보도블록에는 B, O, J 중에 하나가 쓰여 있다. 1번은 반드시 B이다.

스타트는 점프를 통해서 다른 보도블록으로 이동할 수 있다. 이때, 항상 번호가 증가하는 방향으로 점프를 해야 한다. 만약, 스타트가 현재 있는 곳이 i번이라면, i+1번부터 N번까지로 점프를 할 수 있다. 한 번 k칸 만큼 점프를 하는데 필요한 에너지의 양은 k*k이다.

스타트는 BOJ를 외치면서 링크를 만나러 가려고 한다. 따라서, 스타트는 B, O, J, B, O, J, B, O, J, ... 순서로 보도블록을 밟으면서 점프를 할 것이다.

스타트가 링크를 만나는데 필요한 에너지 양의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 1 ≤ N ≤ 1,000이 주어진다.

둘째 줄에는 보도블록에 쓰여 있는 글자가 1번부터 순서대로 주어진다.

출력

스타트가 링크를 만나는데 필요한 에너지 양의 최솟값을 출력한다. 만약, 스타트가 링크를 만날 수 없는 경우에는 -1을 출력한다.

풀이 (DP)

처음엔 Stack에 마지막 문자를 저장하는 방식으로, Stack의 FILO 구조를 이용한 풀이를 짰었는데... 예제 6번에서 막혀서 코드를 다시 짰다...

예제 6번 입력

15
BJBOJOJOOJOBOOO

출력

52

내가 Stack으로 짤 때 실수했던 부분은 문자상의 거리를 기준으로 최대한 짧은 문자를 Stack에 저장해가며 B -> O -> J 순서를 고집했다. 그래서 예제 6번에서 마지막 BOOO를 처리할 때 B와 만나는 가장 첫번째 O를 처리하고 마지막 n까지 도달하지 못해 -1를 출력시켰었다.

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


public class Main {
    //dp 문제
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        char[] BOJ = new char[n]; //BOJ 문자 배열
        BOJ = br.readLine().toCharArray();

        long[] dp = new long[n];
        Arrays.fill(dp, Integer.MAX_VALUE);

        dp[0]=0;

        for(int i=0; i<n-1; i++) { // B -> 0 -> J 순으로 탐색
            char word = BOJ[i];
            if(word=='B') {
                for(int j=i+1; j<n; j++) {
                    char next_word = BOJ[j];
                    if(next_word=='O') {
                        dp[j] = (long) Math.min(dp[j], (dp[i]+ Math.pow(i-j, 2)));
                    }
                }
            }
            else if(word=='O') {
                for(int j=i+1; j<n; j++) {
                    char next_word = BOJ[j];
                    if(next_word=='J') {
                        dp[j] = (long) Math.min(dp[j], (dp[i]+ Math.pow(i-j, 2)));
                    }
                }
            }
            else {
                for(int j=i+1; j<n; j++) {
                    char next_word = BOJ[j];
                    if(next_word=='B') {
                        dp[j] = (long) Math.min(dp[j], (dp[i]+ Math.pow(i-j, 2)));
                    }
                }
            }
        }

        if(dp[n-1]==Integer.MAX_VALUE) {
            System.out.println(-1);
        }
        else {
            System.out.println(dp[n-1]);
        }
    }
}

성능 요약

메모리: 14964 KB, 시간: 836 ms

분류

조합론, 다이나믹 프로그래밍, 수학

제출 일자

2024년 8월 27일 19:00:38

문제 설명

행의 수가 N이고 열의 수가 M인 격자의 각 칸에 1부터 N×M까지의 번호가 첫 행부터 시작하여 차례로 부여되어 있다. 격자의 어떤 칸은 ○ 표시가 되어 있다. (단, 1번 칸과 N × M번 칸은 ○ 표시가 되어 있지 않다. 또한, ○ 표시가 되어 있는 칸은 최대 한 개이다. 즉, ○ 표시가 된 칸이 없을 수도 있다.)

행의 수가 3이고 열의 수가 5인 격자에서 각 칸에 번호가 1부터 차례대로 부여된 예가 아래에 있다. 이 격자에서는 8번 칸에 ○ 표시가 되어 있다.

격자의 1번 칸에서 출발한 어떤 로봇이 아래의 두 조건을 만족하면서 N×M번 칸으로 가고자 한다.

• 조건 1: 로봇은 한 번에 오른쪽에 인접한 칸 또는 아래에 인접한 칸으로만 이동할 수 있다. (즉, 대각선 방향으로는 이동할 수 없다.)
• 조건 2: 격자에 ○로 표시된 칸이 있는 경우엔 로봇은 그 칸을 반드시 지나가야 한다.

위에서 보인 것과 같은 격자가 주어질 때, 로봇이 이동할 수 있는 서로 다른 경로의 두 가지 예가 아래에 있다.

• 1 → 2 → 3 → 8 → 9 → 10 → 15
• 1 → 2 → 3 → 8 → 13 → 14 → 15

격자에 관한 정보가 주어질 때 로봇이 앞에서 설명한 두 조건을 만족하면서 이동할 수 있는 서로 다른 경로가 총 몇 개나 되는지 찾는 프로그램을 작성하라.

입력

입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으로 구분된다. K의 값이 0인 경우도 있는데, 이는 ○로 표시된 칸이 없음을 의미한다. N과 M이 동시에 1인 경우는 없다.

출력

주어진 격자의 정보를 이용하여 설명한 조건을 만족하는 서로 다른 경로의 수를 계산하여 출력해야 한다.

풀이 (DFS)

특이하게도 DP 문제지만, DFS로 접근해 풀었다...

DP 풀이가 궁금해서 따로 구글링을 통해 여러 블로그들을 찾아봤고, [DP 풀이] 위 풀이를 찾아냈다.

DFS로는 K 값이 0인 경우, 0이 아닌 경우로 나눠 DFS를 실행해 해결했다.

K 값이 0인 경우

• 위 경우는 그냥 1,1을 기준으로 N,M까지 DFS를 실행해주고 N,M에 도달한 경우에 + 1을 하며 늘려줬다.

K 값이 0이 아닌 경우

위 경우가 이제 문제가 될 수 있는데, 처음엔 따로 boolean 변수를 만들어서 DFS 함수가 해당 K 좌표를 무조건 지나는 경우만 체크할까 고민했었다.

하지만 이 멍청한 어린 양은 백준 질문란에서 힌트를 얻었고,

(1,1)부터 (K의 X좌표, K의 Y좌표)까지 DFS를 진행하는 것 하나. (K의 X좌표, K의 Y좌표)부터 (N,M)까지 DFS를 진행하는 것 하나.

총 두 갈래로 나눠 DFS를 실행하면 된다는 것을 깨달았다. 사실 이 내용은 고등학교 수학 1학년?때 확률과 통계에서 배웠다. 다만 내 뇌는 그걸 기억할 정도로 똑똑하지 않아서 문제가 됐던 것 뿐 ㅎㅎ;;

정보) 이 내용은 진짜 수학임. 이와 관련된 문제를 푸는 [최단 거리 문제 풀이]를 가져왔다.

아무튼 그래서 즉, ((1,1)부터 (K의 X좌표, K의 Y좌표)까지 DFS) * ((K의 X좌표, K의 Y좌표)부터 (N,M)까지 DFS) 를 계산해준다면, 답을 구할 수 있다는 것이다!

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

public class Main {
    //dfs로 해결한 문제
    static int N,M,K;
    static int[][] map;
    static int[] dx = {1,0}; //오른쪽 , 아래
    static int[] dy = {0,1};
    static boolean[][] visited; //방문 여부 확인용
    static int ans=0; //경로 구하기 답

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

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

        map= new int[N+1][M+1]; 
        visited = new boolean[N+1][M+1];

        int X=0; int Y=0;

        int distance =0; //배열 번호 매기기
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                distance++;
                map[i][j] = distance;
                if (distance == K) {
                    X = i;
                    Y = j;
                }
            }
        }

        if(K==0) { //반드시 지나야하는 구간 없다면 그냥 DFS
            dfs(1,1,N,M);
            System.out.println(ans);
        }
        else { //반드시 지나야하는 구간을 기준으로 나누기.
            dfs(1,1,X,Y);
            int first_ans = ans; //처음 1,1부터 k좌표까지 DFS
            ans=0;

            dfs(X,Y,N,M);
            int second_ans =ans; //k좌표부터 N,M까지 DFS
            System.out.println(first_ans * second_ans); //두 값 곱하면 답
        }
    }

    public static void dfs(int x,int y, int end_x, int end_y) {
        visited[x][y]=true;
        if(x==end_x && y==end_y) {
            ans++;
            return;
        }

        for(int i=0; i<2; i++) {
            int nx = x+dx[i];
            int ny = y+dy[i];

            if(nx> N || nx<=0 || ny>M || ny<=0) {
                continue;
            }
            if(visited[nx][ny]) {
                continue;
            }

            visited[nx][ny]=true;
            dfs(nx,ny,end_x,end_y);
            visited[nx][ny]=false;
        }
    }
}

성능 요약

메모리: 14340 KB, 시간: 100 ms

분류

브루트포스 알고리즘, 다이나믹 프로그래밍, 배낭 문제

제출 일자

2024년 8월 27일 11:24:49

문제 설명

세준이는 성형수술을 한 후에 병원에 너무 오래 입원해 있었다. 이제 세준이가 병원에 입원한 동안 자기를 생각해준 사람들에게 감사하다고 말할 차례이다.

세준이를 생각해준 사람은 총 N명이 있다. 사람의 번호는 1번부터 N번까지 있다. 세준이가 i번 사람에게 인사를 하면 L[i]만큼의 체력을 잃고, J[i]만큼의 기쁨을 얻는다. 세준이는 각각의 사람에게 최대 1번만 말할 수 있다.

세준이의 목표는 주어진 체력내에서 최대한의 기쁨을 느끼는 것이다. 세준이의 체력은 100이고, 기쁨은 0이다. 만약 세준이의 체력이 0이나 음수가 되면, 죽어서 아무런 기쁨을 못 느낀 것이 된다. 세준이가 얻을 수 있는 최대 기쁨을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N(≤ 20)이 들어온다. 둘째 줄에는 각각의 사람에게 인사를 할 때, 잃는 체력이 1번 사람부터 순서대로 들어오고, 셋째 줄에는 각각의 사람에게 인사를 할 때, 얻는 기쁨이 1번 사람부터 순서대로 들어온다. 체력과 기쁨은 100보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 세준이가 얻을 수 있는 최대 기쁨을 출력한다.

풀이 (DP 배낭)

배낭 문제와 흡사한 문제이다.

//무게가 최대 배낭 무게를 초과할 경우
dp[N][W] = dp[N-1][W];

//무게를 초과하지 않을 경우
dp[N][M] = Math.max(dp[N-1][M],dp[N-1][M - 물건무게] + 물건 가치);

위 규칙을 따라가기에, 배낭 문제처럼 풀면 된다.

필자는 dp배열을 [n 값(사람 수][체력] 로 설정했는데, 이때 주의할 점은 체력 최대가 100이 아닌 99까지라는 것이다.

이는 백준 예제 입력 2번에서 어느 정도 힌트를 준 셈인데,

1
100
20

를 입력해주면,

0

0이 나오는 것을 확인할 수 있다. 이는 본문에서 "만약 세준이의 체력이 0이나 음수가 되면, 죽어서 아무런 기쁨을 못 느낀 것이 된다." 라는 내용을 확인한 예제인데, 만약 배열내 최대 체력이 100이었다면, 체력이 0이 되도 괜찮게 된다.

그러므로 체력을 k라는 변수에 99라는 값을 넣어줬다. 그 외엔 특히 주의해야 할 사항은 없다.

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

public class Main {
    //dp 문제
    static int k=99;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[] hp = new int[n+1]; //체력
        int[] happy = new int[n+1]; //기쁨
        int[][] dp = new int[n+1][k+1]; //체력 99까지 [사람 수][체력]

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=1; i<=n; i++) {
            hp[i] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        for(int i=1; i<=n; i++) {
            happy[i] = Integer.parseInt(st.nextToken());
        }

        for(int i=1; i<=n; i++) {
            for(int j=1; j<=k; j++) {
                if(hp[i] > j) {
                    dp[i][j] = dp[i-1][j];
                }
                else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-hp[i]]+happy[i]);
                }
            }
        }

        System.out.println(dp[n][k]);
    }
}