Server: Spring Boot · Client: React + Next.js (BFF) 작성 목적: 리뷰용 설계 문서

1. 목적

1. 현재 레거시 플랫폼은 front-end와 back-end가 긴밀하게 종속(tightly coupled)되어 있어, 책임 경계가 모호하고 독립적인 변경·배포가 어렵다.
2. SSR(Server-Side Rendering)을 유지하여 SEO·초기 로딩 이점을 지키면서, 클라이언트 인터랙션(상태/DOM 동기화)을 강화해 사용자 UX를 개선한다.
   • 주의: "전부 SPA로 전환"이 아니다. 순수 SPA(CSR)는 SEO에 불리하므로, Next.js로 부분 SSR/RSC를 유지한 채 인터랙션만 더한다.
3. 중복 기능을 제거하고, 일부 기능의 버전 관리·현행화를 수행한다.

--

전환 이유 (4축)

1. 책임 분리 (Client / Server)
   • front/back의 책임 소재를 명확히 분리, 독립 배포 가능.
   • Trade-off: 운영 대상이 2배(Spring + Node 런타임), API 계약·빌드 파이프라인 추가. → 운영 복잡도 증가를 감수.
2. 보안 (공격 표면 축소)
   • Spring API를 내부망(private network)에 격리 → 외부에서 직접 노출되지 않음.
   • 서버 컴포넌트(RSC, React Server Components)에서 민감 로직·데이터 접근을 처리하면 해당 코드가 브라우저로 전송되지 않음.
3. 개발 생산성 (상태/DOM 동기화)
   • React의 선언적 렌더링으로 상태(state)와 DOM 동기화를 자동화 → 인터랙션 개발 생산성 향상.
4. SEO (부분 SSR)
   • Next.js로 SEO가 필요한 영역에 SSR/RSC를 적용.

2. 현재 구조 (As-Is)

• MPA(Multi-Page Application) + SSR 방식.
• 페이지 이동마다 서버가 완성된 HTML을 렌더링해 전달.
• 장점: 초기 로딩이 빠르고 SEO에 유리 → 이벤트 페이지에서 가장 중요한 요구사항.
• 단점: front/back 종속, 인터랙션 한계.

3. 전환 결론 (To-Be)

4. 구조: BFF (Backend For Frontend)

Next.js가 브라우저와 Spring API 사이의 단일 진입점(BFF) 역할을 한다.

[브라우저]
   │  httpOnly 쿠키 (User JWT) 자동 첨부 + CSRF 토큰
   ▼  외부 (HTTPS)
[Next.js 서버 = BFF]   ← 외부에 노출되는 유일한 진입점
   │  쿠키에서 토큰 추출 → Authorization 헤더로 부착
   ▼  내부망 (server-to-server)
[Spring API]           ← 외부에서 직접 접근 불가
   ▼
[DB]

4.1 핵심 원칙

• User JWT: httpOnly 쿠키에 저장 (브라우저 JS 접근 차단).
• 브라우저 호출 방식: 모든 데이터 요청은 BFF의 /api/proxy를 경유한다. 브라우저가 Spring API를 직접 호출하지 않는다(same-origin 강제). → 서버 컴포넌트든 클라이언트 컴포넌트든 동일하게 적용.
• 토큰 헤더 부착: 토큰을 요청 헤더에 싣는 작업은 서버 프록시(BFF)에서 수행. 브라우저는 토큰 값을 직접 다루지 않는다.
• 쿠키 기반 인증 교환: POST /api/auth/login (BFF 라우트, fetch) → 내부에서 백엔드 /auth/cookie-login 호출.

5. 인증 / 세션 처리

5.1 토큰 발급·검증의 책임 분담

심층 방어(defense in depth): BFF가 검증했더라도 Spring은 자기에게 도착한 토큰을 독립적으로 다시 검증한다. BFF 우회 호출 시에도 데이터가 보호되도록, 데이터를 내주는 Spring이 최종 방어선을 갖는다.

5.2 토큰 저장 위치

• 토큰은 브라우저 JS가 읽을 수 있는 곳(localStorage)이 아니라 JS 접근이 차단된 httpOnly 쿠키에 보관한다.
• 쿠키는 브라우저에 저장되지만 JS 접근이 차단되며, 읽고 검증하는 주체는 Next.js 서버(BFF)다.
• 대비 축은 "브라우저 vs 서버"가 아니라 "JS가 읽을 수 있는가(localStorage) vs 없는가(httpOnly)"이다.

5.3 토큰 클레임(claim) 원칙

• JWT payload는 암호화가 아니라 base64 인코딩이므로, 누구나 디코딩하면 내용을 읽을 수 있다(서명은 위조만 막을 뿐 열람은 못 막는다).
• 따라서 토큰에는 개인정보를 넣지 않는다.
  • 담는 것: 내부 식별자(sub = USER_ID 등), 권한(role/scope), 메타데이터(iat, exp, iss).
  • 절대 넣지 않는 것: 비밀번호, 주민번호, 카드번호, 이름·이메일·전화번호 등 직접 식별 가능한 개인정보.
• 실제 개인정보(USERNAME 등)는 토큰에서 꺼내지 않고, 토큰의 ID로 Spring이 DB를 조회하여 제공한다.

5.4 키 관리 전략 (다중 서버 대응)

• stateless 토큰은 키만 있으면 어느 서버든 독립 검증 가능 → 스케일아웃에 강함.
• 단, 서버마다 키가 다르면 검증이 실패하므로 키 일관성이 필수.
• 비대칭키(RS256) 권장: Spring(인증 서버)이 private key로 발급, BFF·여러 Spring 인스턴스는 public key로 검증만. 공개키는 노출돼도 위조 불가.
• 키 교체(rotation) 시 무중단을 위해 옛 키·새 키를 일정 기간 동시 인정(또는 JWKS 엔드포인트로 공개키 동적 배포).

5.5 로그인 흐름

신규 플랫폼의 accessToken 유효성에 따라 분기한다. (단순 "유/무"가 아니라 서명·만료 검증 통과 여부로 판단)

1. 유효한 accessToken이 없는 경우 (없거나 검증 실패)
   • POST /api/auth/login → 내부 /auth/cookie-login 호출하여 accessToken 발급·수신.
2. 유효한 accessToken이 있는 경우
   • /api/proxy/auth/profile 호출 → 로그인 정보(USER_ID, USERNAME 등)를 서버 조회로 획득.

5.6 토큰 만료·갱신

• accessToken 만료 시간: 15분.
• API 호출 시마다 토큰의 서명·만료를 검증.
• 토큰이 만료/부재면 refreshToken으로 재발급 요청.
• refreshToken으로도 재발급에 실패하면 최종 실패 → 세션 종료 후 로그인 페이지로 리다이렉트.

6. CSRF 방어

httpOnly 쿠키는 XSS(토큰 탈취)는 막지만, 쿠키 자동 첨부 성질 때문에 CSRF(cross-site request forgery)에 노출된다. XSS와 CSRF는 별개의 공격이므로 둘 다 방어해야 한다.

• SameSite: 쿠키에 SameSite=Lax(현대 브라우저 기본·권장) 설정 → cross-site 요청의 쿠키 자동 첨부 차단.
• CSRF 토큰: 상태 변경 요청(POST/PUT/DELETE)에 예측 불가능한 토큰을 요구. 외부 사이트는 same-origin 정책상 이 값을 읽을 수 없어 위조 요청이 걸러짐.
• BFF 구조에서는 브라우저 ↔ Next.js 구간에 방어를 건다(Next.js ↔ Spring은 내부망 통신이라 무관).
• 쿠키 설정 시 httpOnly + secure(HTTPS 전용) + sameSite를 한 세트로 적용.

cookies().set('token', jwt, {
  httpOnly: true,   // XSS 방어 (JS 접근 차단)
  secure: true,     // HTTPS에서만 전송
  sameSite: 'lax',  // CSRF 방어 (cross-site 자동첨부 차단)
  path: '/',
});

7. Data Fetching

• 경로: 브라우저 → Next.js 서버(BFF) → Spring API.
• 클라이언트 컴포넌트의 모든 데이터 요청은 Next.js Route Handler(/api/proxy)를 경유하며, 브라우저에서 Spring API를 직접 호출하지 않는다(same-origin 강제). → CORS 문제 회피, 토큰을 브라우저가 만지지 않음.
• 서버 컴포넌트(RSC)는 Next.js 서버에서 직접 Spring을 호출(내부망). 민감 데이터는 RSC에서 처리해 클라이언트 번들로 나가지 않게 한다.

8. 하이드레이션 불일치 (Hydration Mismatch) 대응

• 하이드레이션: SSR이 보낸 정적 HTML에 JS로 이벤트·상태를 부착해 인터랙티브하게 만드는 과정.
• 불일치: 서버가 그린 HTML과 브라우저가 재계산한 HTML이 다를 때 발생. SSR을 쓰는 이상 반드시 고려해야 함.
• 원인: 시간(new Date()), 랜덤 값(Math.random()), 타임존·로케일 차이, 브라우저 전용 API(window, localStorage).
• 대응: 환경에 따라 달라지는 값은 첫 렌더에서 제외하고, useEffect로 하이드레이션 후 채우거나 클라이언트 전용 렌더로 격리한다.
  • 서버에서는 useEffect가 실행되지 않으므로, 첫 렌더 결과가 서버·클라이언트 동일해져 불일치가 방지됨.
• 이벤트 페이지 대표 사례: 카운트다운 타이머, "마감까지 D-3" 같은 시간 의존 표시.

function Countdown() {
  const [remaining, setRemaining] = useState(null); // 첫 렌더: 서버·클라 모두 null
  useEffect(() => {
    setRemaining(calcRemaining()); // 하이드레이션 후 채움
  }, []);
  return <span>{remaining ?? "로딩 중"}</span>;
}

9. 마이그레이션 전략

• 점진 전환(strangler fig 패턴): 기존 MPA를 한 번에 갈아엎지 않는다.
• 신규 이벤트 도메인부터 적용 → 새로 생성되는 이벤트부터 신규 구조(React + Next.js)로 점차 확대.
• 기존 안정 페이지는 그대로 두어 마이그레이션 위험을 최소화.

10. 운영 고려사항

• Node 런타임 운영: Spring 외에 Next.js(Node) 프로세스의 모니터링·패치·스케일링·배포 주체를 정의해야 함.
• 세션 전략: stateless(서명된 토큰) 방식 채택 → 서버 메모리 세션 불필요, 수평 확장 용이. (refresh 토큰 관리에서 일부 상태가 필요할 수 있음.)
• BFF 자체 보안: 외부 노출 진입점이므로 Next.js 서버의 의존성 취약점·SSRF 등을 관리.
• HTTPS 적용: 개인정보가 지나가는 브라우저 ↔ BFF 구간 암호화 필수. 로그에 개인정보·토큰을 남기지 않도록 주의.

11. 책임 분담 요약

부록: 용어

• BFF (Backend For Frontend): 프론트엔드 전용 백엔드. 여기서는 Next.js 서버가 브라우저와 Spring 사이의 중계·보안 계층 역할.
• RSC (React Server Components): 서버에서만 실행되어 클라이언트로 JS를 전송하지 않는 컴포넌트.
• stateless 토큰: 서버가 세션을 저장하지 않고, 토큰 자체에 정보를 담아 검증하는 방식(JWT).
• 하이드레이션(hydration): SSR HTML에 클라이언트 JS로 동작을 부착하는 과정.

문제

카약과 강풍

풀이

이 문제는 카약이 부서진 팀과 카약을 하나 더 가져온 팀이 동일할 수 있다는 개념을 알고 하면 된다 하나 더 가져오면 부서져도 대체가 가능하기 때문이다. 어려운 문제는 아닌데 그래서 이부분을 모르면 무조건 한번은 틀린다. 나는 더 틀렸는데 그 이유는 마지막에 -1을 샐때 n번째를 포함하지 않고 샜기 때문에 틀렷다... 또 바보짓함;;

일단 나는 전체 카약이 부서진 배의 인덱스를 -1으로 해주었고 카약을 하나 더 가져왔으면 1을 셋팅해주었다

여기서 중요한점은 부서진 배를 가지고 있는 값이 -1 인경우 배열을 다시 0으로 저장하는 작업이다

...
for (int i = 0; i < s; i++) {
    arr[Integer.parseInt(st.nextToken())] = -1;
}
st = new StringTokenizer(br.readLine());
for (int i = 0; i < r; i++) {
    int k = Integer.parseInt(st.nextToken());
    if (arr[k] == -1) {
        arr[k] = 0;
    } else {
        arr[k] = 1;
    }
}
...

전체 코드

전체 코드

후위 표기식2

풀이

표기식에 관한 문제라면 역시 스택이지! 이 문제는 스택에는 문자를 넣어주지 않고 현재의 값을 넣어주는데에 있다 시나리오는 대충 이렇다 A에 해당하는 배열을 스택에 문자이면 넣는다.(Character.isLetter()) 스택에 넣는값은 알파벳에 해당하는 숫자를 넣으면 된다 만약 문자가 아니라면 연산을 해줄 값을 스택에서 꺼내서 연산하면 된다. 후위표기식이기 때문에 2개를 연속해서 꺼내야한다 나중에 꺼낸것이 연산에 앞에 오는 것이므로 주의해야한다.!

전체 코드

전체코드

걸그룹 마스터 준석이

풀이

해시맵 두개를 가지고 하나는 그룹명을 키로두고 값은 배열로 둔 것으로 문제에서 요구하는 전체 멤버의 이름을 출력하기 위해저장하는 것 하나와 나머지 하나는 키가 이름이고 값은 그룹 명으로 저장해서 바로 불러올수 있게 저장하였다.

전체 코드

전체 코드

좋은 단어

풀이

이 문제는 처음에는 replace로 하려고 했다 좋은 단어의 조건은 인접한 것끼리 묶어서 단어에서 제외해주면 되기 때문에 replace('AA','').replace('BB','') 를 해주면 되지 않을까 그런 다음 남아있는 값이 아무것도 없다면 그것은 좋은 단어 일 것 이다.

하지만 이 문제는 스택이기 때문에 스택의 아이디어로 푼다면 처음에 스택이 비어있을때는 현재 값을 무조건 스택에 값을 넣어주고 스택에 값이 존재 한다면 스택에 가장상위에 있는 값과 비교해서 같으면 스택에 있는 값을 빼주고, 다르면 스택에 현재 값을 넣어준다. 그런다음 스택에 남아있는 값이 없다면 그것은 좋은 단어라는 것이다.

Stack<Character> stack = new Stack();

while (n-- > 0) {
    String s = br.readLine();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        // 값이 존재 하지 않으면 비교해줄 대상을 늘려준다
           if (stack.isEmpty()) {
            stack.push(c);
        } else {
            if (stack.peek() == c) { // 인접한 단어가 현재 단어와 일치한다
                stack.pop();
            } else {
                stack.push(c);
            }
        }

        if (stack.isEmpty()) {
            answer++;
        }
    }
}

전체 코드

전체 코드

두 수의 합

풀이

이 문제는 마이너스 인덱스를 비교 하게 되어서 indexoutofBound 가 계속 났다. 알고리즘 자체는 문제가 없었는데 배열을 두개로 두고 한개는 주어지는 배열을 저장할 용도 이고 나머지 하나는 값이 존재하는지만 볼거라 boolean 배열을 선언해주면 된다

그래서 이문제에서 가장 중요한 점은 x값보다 작은 값들로만 더해져야 하기 때문에 값이 존재하는 지 알아보기 전에 x값보다 작은 값인지를 먼저 비교해야 한다

for (int i = 0; i < n; i++) {
    if (arr[i] < x) { // x보다 작은 값이어야 a + b를 할수 있습니다.
        if (arr1[x - arr[i]]) {
            answer++;
        }
    }
}

전체 코드

전체 코드

문제

Project Teams

풀이

뭐지 이문제는 ? 정답률 보면 날먹문제 같다..

가장 평균의 가깝게 짝지어 주기 위해서는 정렬을 하고 가장 작은 수와 가장 큰 수끼리 짝을 지어주면 됩니다.

오늘도 스트릭 호로록 합니다..

전체 코드

전체 코드

가운데를 말해요

풀이

중간값을 뽑을때는 자료구조를 두개 두고 작은 값이 나오면 상대적으로 작은 값을 앞으로 보내주는 작업을 하면 된다

이 문제에서 주어지는 내용중에 작은 값을 출력하라고 되어있으므로 상대적으로 작은 값을 가지는 우선순위 큐 보다 상대적으로 큰 값을 가지는 우선순위 큐의 양이 많아지면 큰 값을 가지는 우선순위 큐에서 앞에 있는 값을 하나빼줘서 반대 큐에 옮겨 담는다

참고로 큰 값을 가지는 우선순위 큐는 정렬 순서를 반대로 고정하여 오름차순으로 만들어주는 것이 이문제에서 가장 중요한 부분이다

PriorityQueue<Integer> minpq = new PriorityQueue<>();
PriorityQueue<Integer> maxpq = new PriorityQueue<>(Collections.reverseOrder());

minpq.add(Integer.parseInt(br.readLine());

for (int i = 1; i < n; i++) {
    int k = Integer.parseInt(br.readLine());


    if (minpq.size() < maxpq.size()) {
           minpq.add(k);
     } else { 
        maxpq.add(k); 
    }

    int min = minpq.peek();
    int max = maxpq.peek();

     if (min < max) {
           minpq.poll(); maxpq.poll();
           minpq.add(max);
        maxpq.add(min);
     }
    sb.append(max.peek()).append("\n");
}

전체 코드

전체 코드

문제

N과 M (11)

풀이

이번엔 같은 수를 여러번 출력할 수 있는 대신에 중복된 순서로 출력되는 라인만 제거하면 된다 이전에 9번문제에서 영감을 주신 그분 덕택에 이 문제를 풀 수 있다. 10 번 문제도 이런식으로 풀었다

이제 n과 m문제를 졸업할 시간이 다가온다. 아쉽다. (이젠 너무 익숙해져서 스트릭 날먹하고있었는데... )

전체 코드

전체 코드

문제

N과 M (9)

풀이

백트래킹에 대한 내용은 이전이랑 너무 비슷해서 생략하고, 중복된 순서대로 나오면 안되서 뭘쓸까하다가..그냥만만한 hashset을 사용했다 근데 생각해보니 적재순서를 보장해줘야 해서 LinkedHashSet을 사용해서 풀었다.

메모리 공간이 너무 많이 차지하려나? 했는데 맞았다. 그리고 지금보니까 vistied 배열도 공간을 줄이면 메모리도 더줄일수 있을거같고

자료 구조를 이용한 것도 괜찮긴한데...

이런풀이말고 다른게 더 괜찮을거 같아서 다른 분들 풀이 보니까 visited 체크와 동시에 backtracking 안에서 변수를 선언해서 이전에 들어간 값이랑 겹치지 않는 값을 선택하기 위해 이전값을 저장하고 있다가 비교를 하고있었다. 자바코드는 아니지만 너무 좋자나

void func(int cnt) {
    if (cnt == m) {
        for (int i = 0; i < m; i++)
            printf("%d ", res[i]);
        printf("\n");
        return;
    }
    int xx = 0;
    for (int i = 0; i < n; i++) {
        if (!chk[i] && arr[i] != xx) {
            res[cnt] = arr[i];
            xx = res[cnt];
            chk[i] = true;
            func(cnt + 1);
            chk[i] = false;
        }
    }
}

출처 나중에 보고 배껴야지~

이제보니까 hash사용한 풀이들도 많구나 휴 다행이다,

전체 코드

전체 코드

문제

N과 M (7)

풀이

이제 이쯤됬으면 백트래킹에 대해서 그냥 출퇴근 시간에 무심결에 생각하게 됬다. 이문제는 이전에 6번문제,, 포스팅을 안했지만 그문제 보다 더 쉽다,

private static void backtracking(int depth) {
    // 멈추는 조건
    if (depth == m) {
        ..
        return;
    }

    // 반복조건
    for (int i = 0; i < n; i++) {
        ..
        backtracking(depth + 1);
    }
}

일단 멈추는 조건은 m번째에 멈추면 되고 반복조건은 중복이 가능하기 때문에 visited 체크는 하지않아도 되고, 멈추는 조건에서 출력할 데이터를 저장할 곳에 입력으로 받은 데이터를 i부터 n번째 까지 순서대로넣어주면 됩니다. 처음에는 백트래킹이 정말 어려운거같은데, 손으로 스택을 그려가면서 하면 정말 쉽게 이해가 가능합니다

전체 코드

전체 코드

문제

N과 M (3)

풀이

1-n가지의 자연수를 m개씩 뽑는 경우의 수를 전부 출력하면 된다 백트래킹 문제중에선 굉장히 유명하고 연습하기 좋은 문제같다.

백트래킹은 반복문과 멈추는 조건을 정의를 먼저 해야한다. 멈추는 조건은 3개까지 모두 뽑혔을때 멈추면 된다. 그리고 1-n의 숫자를 사용하는 경우의 수기 때문에 1-n까지 반복해야한다.

private static int dfs(int depth, int m) {
    // m개를 모두 고름
    if (depth == m) {
        for (int x : arr) {
            sb.append(x).append(" ");
        }
        sb.append("\n");
        return;
    }

    // 1- N 의 숫자를 모두 쓰는 경우의 수
    for (int i = 1; i <= n; i++) {
        arr[depth] = i;
        dfs(depth + 1, m);
    }
}

전체 코드

전체 코드

문제

카드놀이

풀이

마지막에 이긴 사람을 저장하는 String변수를 만들고 마지막에 한번더 sumA와 sumB를 비교를 해줘야 한다. 마지막에 이겼다고 모든 카드 놀이에서 이긴것이 아니기 때문에 마지막에 비교하는 문장이 없으면 틀린다. 실제로 이런 문제에서 코테에서 당황해버린 경우가 많았던것같다.

전체 코드

전체 코드

문제

팩토리얼 2

풀이

팩토리얼은 너무 많이 쓰던거라 익숙하다. 재귀형으로 쓰면 라인 하나만써도 뚝딱 .. 다만 이 문제는 long 형으로 리턴 받아야한다.

    private static long factorial(int n) {
        if (n == 1 || n == 0) return 1;
        return n * factorial(n - 1);
    }

전체 코드

전체 코드

문제

수강신청

풀이

linkedlist 를 했는데도 시간초과가 납니다.. 왜ㅈ ... ㅣ... contains도 안썼는데...

이유가 너무 궁금해서 찾아보니 linkedhashset은 add 및 remove의 속도가 O(1) 이고 linkedlist는 O(n) 이기 때문입니다 그래서 시간초과 인것이에용..[참고]

전체 코드

전체 코드

문제

숫자

풀이

a > b일수도 있고 b > a 일수도 있고 a = b 일수도 있기 때문에 케이스를 나누어서 작성해주어야 했다.

전체 코드

전체 코드

문제

ROT13

풀이

문제 자체에서 원하는것은 ascii코드에서 + 13을 하는것인데 char의 자료형이 취급하는 숫자는 -128부터 127 입니다. char에서 +13을 했울경우 (만약 주어진 문제에서 소문자 z가 주어졌을 경우) 이 범위를 초과할 수 있습니다. 이걸 의도하고 만들어진 문제같습니다

저의 경우에는 공백이 중복으로 계속 주어진 경우에 대해서 예외처리가 되지 않아서 몇번씩 틀렸던 문제였습니다

전체 코드

전체 코드

문제

토마토

풀이

이 문젠 솔직히 bfs의 전형적인 문제라 알고리즘을 틀렸다기 보다는 3차원 배열을 정의하는데 있어서 시간을 좀 더 많이 들였던것 같습니다. 저는 개인적으로 3차원 배열을 다를 수 있는 기회가 실제 프로젝트에서 있지는 않아서.. 아마 게임개발쪽이시면 그냥 푸실거같으네요.

BFS하면 큐겠죠. 큐를 정의하는데 저는 배열로 넣고 빼겠습니다.

Queue<int[]> q = new LinkedList<>();
// 높이
for (int i = 0; i < h; i++) {
    // 세로
    for (int j = 0; j < n; j++) {
        st = new StringTokenizer(br.readLine());
        // 가로
        for (int k = 0; k < m; k++) {
            box[i][j][k] = Integer.parseInt(st.nextToken());
            if (box[i][j][k] == 1) {
                q.add(new int[] {i, j, k});
            }
        }
    }
}

높이(h) 세로(y) 가로(x) 순으로 for문을 돌리고 높이, 세로, 가로 순으로 큐에 넣습니다. 큐에 넣는 이유는 1인 것부터 차례대로 BFS 큐에넣고 0인것을 바꿔주기 위해서 입니다.

    static int[] dx = {0, 0, -1, 1, 0, 0};
    static int[] dy = {-1, 1, 0, 0, 0, 0};
    static int[] dz = {0, 0, 0, 0, -1, 1};

이거는 그냥 문제에서 주어지는 대로 움직이는 범위를 정의한 배열입니다. 6개의 방향이있기때문에 정의해주는것입니다.

while (!q.isEmpty()) {
    int[] xy = q.poll();
    int z = xy[0];
    int x = xy[1];
    int y = xy[2];

    for (int i = 0; i < dx.length; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        int nz = z + dz[i];
        if (nx >= 0 && ny >= 0 && nz >= 0
                && nx < n && ny < m && nz < h) {
            if (box[nz][nx][ny] == 0) {
                box[nz][nx][ny] = box[z][x][y] + 1;
                q.add(new int[] {nz, nx, ny});
            }
        }
    }
}

본격적인 bfs 입니다. box배열에는 몇번째로 접근이 되는지를 depth + 1을 해주는 것입니다. 0인경우에만 접근해주면 되기 때문에 넘나 쉬움..

private static int validate() {
    int result = 0;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < m; k++) {
                if (box[i][j][k] == 0) {
                    return -1;
                }
                result = Math.max(result, box[i][j][k]);
            }
        }
    }
    return result - 1;
}

그런다음에 배열이 모두 접근하였는지를 비교하겠습니다. depth는 앞서서 box배열에 넣어놨기 때문에 가장 큰 값으로 넣어주면 그 값이 문제어서 원하는 최소 일수가 됩니다. -1을 해주는 이유는 처음부터 배열에 1부터 정의되었기 때문에 이값을 없에주기 위함입니다.

전체 코드

전체 코드

문제

동전 1

풀이

dp배열은 n개를 만드는데 경우의 수를 값으로 넣습니다. 그래서 n개를 만들때 경우의수 k는 dp[n] = k 로 나타내기로 합니다 다이나믹 프로그래밍의 경우에는 규칙성을 파악해보기로 하는데 예시에서 주어진 1, 2, 5를 가지고 문제를 풀어볼수있는데요

dp[0] = 1; // 1개
dp[1] = 1; // 1 => 1개
dp[2] = 2; // 1,1 / 2 => 2개
dp[3] = 2; // 1,1,1 / 2,1 => 2개
dp[4] = 3; // 1,1,1,1 / 2,1,1 / 2,2 => 3개
dp[5] = 4; // 1,1,1,1,1 / 2,1,1,1 / 2,2,1 / 5 => 4개
...

이렇게 경우의 수를 나열하다 보면 규칙성이 존재함을 알수 있습니다. 바로 dp[n]은 이전의 dp[n]의 값에 영향을 받는 다는 것입니다.

일단 모든 n은 1로만 이루어질 수 있기에 모든 경우에 수(dp[n])에 +1를 기본적으로 해줍니다 또 2를 포함한 경우의 수는 dp[n] n은 2보다 큰 경우의 수 전부에 포함될것입니다. 그렇기 때문에 2이상인 경우 +1를 반복적으로 해주는 작업이 필요합니다.

또 dp[4] 의 경우인 4의 경우에는 2로만 이루어진 경우에 수가 딱하나더 추가가 될것입니다. 이 경우의 수를 나열하면서 규칙을 찾아보면 다음과같습니다.

dp[n] = dp[n] + dp[n - arr[i]];

더해지는 dp[n]은 이전의 dp[n]의 값을 말합니다. 그래서 이전의 값에 해당하는 것을 가져와서 dp[n - arr[i]] 을 더하면 이것이 바로 n이 가지는 값이겠습니다.

이 수식을 가지고 전개합니다. 잘 이해했다면 정말 쉬운문제였겠지만 저는 이부분에 도달하는데도 오래걸렸기 때문에 ㅠㅠ

// 동전 n개를 차례대로 넣습니다.
for (int i = 0; i < n; i++) {
    // 가치 k가될때까지 경우의 수를 계속 더해줍니다.
    for (int j = arr[i] ; j <= k; j++) {
        dp[j] += dp[j - arr[i]];
    }
}

전체 코드

전체 코드

문제

이항 계수 2

풀이

이항계수는 수학 공식이 따로 있어서 거기에 대입해도 되는데요. 공식에서는 팩토리얼을 구현해야하는데.. 자바 내장함수에는 팩토리얼이 없어서 구현을 해야하는디, 팩토리얼 구현하면 스택 오버 플로우 일것입니다.

대부분은 파스칼의 삼각형을 가지고 구현하는 것이 나은가봅니다. 파스칼의 삼각형은... 베스트셀러 수학귀신에 나오는 내용입니다

1
11
121
1331
14641
...
...

여기에서 배열 arr[a][b] 를 구하면 그것이 이항계수입니다.

for (int i = 0; i <= a; i++) {
    for (int j = 0; j <= i; j++) {
        if (i == 0 || j == 0) arr[i][j] = 1;
        else arr[i][j] = (arr[i - 1][j - 1] + arr[i - 1][j]) % 10007;
    }
}

전체 코드

전체 코드