UX/UI, BackEnd와 진행하는 협업 프로젝트에서 프로젝트 리더를 맡아 “모임”이라는 주제를 바탕으로 프로젝트를 진행하게 되었습니다. 이번 포스트에서는 WEGO를 개발하게 된 배경과 팀구성, 프로젝트 구조까지 WEGO를 개발하면서 진행된 프로세스들을 자세하게 풀어보겠습니다.

▪︎ 프로젝트 개요

▫︎ 팀 구성

UX / UI : 1명

FrontEnd : 3명

BackEnd : 2명

▫︎ 사용 기술

Typescript, Next.js, Tailwind CSS, Zustand, Tanstack Query, MSW, Jest, Storybook

▫︎ MVP 개발 기간

2024.11.25 - 2025.01.06

▪︎ 프로젝트 배경

▫︎ 프로젝트의 시작

우선 “모임”이라는 주제를 구체화 했습니다. 기존에 사람들이 가지고 있던 에로사항이나 있었으면 하는 기능들을 서비스로 만들고 싶었습니다. 다양한 키워드를 모임에 대입해가며 고민한 결과, 사람들이 여행을 시작하는데 있어서 어려움을 겪고 있다는 점을 파악했습니다. 지인들을 통한 QA를 바탕으로 페르소나와 키피쳐를 정의하고 서비스 제작을 시작했습니다.

QA의 공통적인 사항들을 정리해보았을 때, 아래와 같은 에로사항이 있다는 것을 확인했습니다. 문제에 대해 서비스 기능을 이용하여 해결할 수 있도록 기획의 방향을 잡았습니다.

▫︎ 주제 선정

위와 같은 QA 결과를 바탕으로 저희는 “여행 동행 모집을 위한 플랫폼”이라는 주제로 개발을 시작하였습니다. 정리한 문제 상황들에 대한 해결 방법을 기능으로 정의하였습니다.

1. 여행 리뷰와 여행 일정의 공유를 통해 여행지 정보 습득의 어려움이 있는 유저들의 불편을 해소하고자 하였고,
2. 계획한 여행 일정 공유와 동행모집, 또 여행 일정 참가 기능을 통해 여행 동반인을 모으기 힘들어하는 유저들의 에로사항을 해결하고자 했습니다.
3. 여행에 대한 이야기를 하기 위해 외부 채널들을 사용해야하는 번거로움을 해소하기 위해 플랫폼 내 채팅 기능을 도입했습니다.

WEGO는 여행 일정 공유와 참여, 동행모집 그리고 채팅방 참여를 통한 일행들과의 대화를 통해 여행 시작에 소요되는 시간을 획기적으로 단축시킬 수 있는 플랫폼으로 기획되었습니다. 추가로 여행 일정을 제시한 사람에 대한 신뢰도를 제공하기 위하여 각 여행에 대한 리뷰 기능또한 포함하게 되었습니다.

▪︎ 개발 프로세스

▫︎ 문서화

각 팀원들이 개발 진행 사항 및 개발에 관련한 컨벤션 등의 정보를 쉽게 파악할 수 있도록 노션을 통해 개발 과정을 문서화했습니다. API 명세서를 통해 구현 API에 대한 정보를 확인하고 백엔드와 댓글 기능을 통해 소통할 수 있도록 했으며, 타입,커밋,코드 등의 컨벤션을 정의하여 프로젝트 전체적으로 일관된 코드 스타일로 개발을 진행할 수 있도록 하였습니다.

▫︎ 와이어프레임 작성

기획한 내용을 바탕으로 UX/UI 팀원의 빠른 진행을 위해 각 페이지에 필요한 정보들을 전달하기 위한 와이어 프레임을 작성하였습니다. 최대한 러프하게 구성하여 디자인의 자유도는 올리면서도 필수적으로 들어가야하는 정보들을 최대한 정리하고 깔끔하게 구성하여 디자인 팀에게 전달했습니다.

▫︎ 디자인 작업 & API 명세서 작성

전달받은 와이어프레임을 바탕으로 디자인 팀에서는 디자인 시스템과 반응형 화면 등의 작업을 시작했으며, 디자인 작업과 동시에 디자인과 와이어프레임을 바탕으로 프론트엔드와 백엔드 팀에서는 필요한 API에 대해 고민하고 명세를 작성하였습니다.

▫︎ CI/CD 파이프라인 구축

Git Hooks를 통한 로컬 환경 품질 관리

Husky를 활용하여 Git Hooks를 설정하였습니다.

1
2
3
4
5
6
7
8
9

# .husky/pre-commit
npx lint-staged  # 커밋 전 린트 검사

# .husky/commit-msg
requiredPattern="^(feat|fix|design|docs|style|refactor|test|conf|rename|remove):.*$"
# 커밋 메시지 컨벤션 검사

# .husky/pre-push
npm run test  # 푸시 전 테스트 실행

커밋 이전에는 코드 스타일 검사, 탕입스크립트 타입 체크, 린트 규칙 준수 여부를 확인하였고, 커밋 메시지 컨벤션을 검사하였으며, 푸시 전에는 단위 테스트를 실행하고 통합 테스트를 검증하여 빌드의 오류를 사전 방지했습니다.

Github Actions를 활용한 CI 파이프라인

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# .github/workflows/git-pr.yml
name: Test code on pull request

jobs:
  test:
    steps:
      - name: Check TypeScript
        run: npm run type-check

      - name: Run ESLint
        run: npm run lint

      - name: Build Project
        run: npm run build

      - name: Run Tests
        run: npm test

1. PR 생성 시 자동화 검증을 통해 빌드 오류를 차단했습니다. 다음 작업들이 PR 생성 시 자동으로 실행됩니다.
   • 타입스크립트 타입 검사
   • ESLint를 통한 코드 품질 검사
   • 프로젝트 빌드 테스트
   • 테스트 코드 실행

1
2
3
4
5
6
7
8

# .github/workflows/storybook.yml
name: Storybook Preview

jobs:
  storybook-preview:
    steps:
      - name: Chromatic에 게시
        uses: chromaui/action@v1

1. 추가로 Storybook의 변경사항을 자동으로 Chromatic에 배포하고 PR 코멘트로 프리뷰 URL을 제공하도록 하였습니다.

CD 파이프라인 구성

1
2
3
4
5
6
7
8

# .github/workflows/git-push.yml
name: git push into another repo to deploy to vercel

jobs:
  build:
    steps:
      - name: Pushes to another repository
        uses: cpina/github-action-push-to-another-repository@main

메인 브랜치 푸시 시 자동으로 배포할 수 있도록 설정했습니다. 배포용 저장소로 코드를 동기화하여 Vercel 플랫폼을 통해 자동으로 배포될 수 있도록 하였습니다.

결과

CI/CD 파이프라인 구축을 통해 자동화된 코드 검사와 일관된 코드 스타일을 유지함으로써 코드의 품질을 향상시켰고, 반복 작업을 자동화함으로써 개발 생산성을 증가시켰습니다. 또한 표준화된 작업 프로세스로 협업 효율성 또한 개선되었습니다.

▫︎ 개발 업무 분배

개발 업무 분배는 초기에 나누어 진행하기 보다는 초기 개발 환경 설정 이후에 서비스 구성에 필요한 페이지, 기능들을 깃헙 이슈에 정리해두고 자신이 맡은 기능을 완료한 팀원이 asign 해가면서 아직 할당되지 않은 기능들을 팀원들이 가져가서 개발하는 방식으로 진행되었습니다.

이를 통해 전체적인 개발의 진행이 빠르게 이루어졌고, 정해진 개발 기간 동안 정의한 기능들을 모두 개발 완료할 수 있었습니다.

▫︎ 개발 진행

디자인이 완성되는 대로 프론트엔드와 백엔드 팀에서는 개발을 동시에 진행했는데요, 처음에는 Bottom Up 방식으로 진행하는 것을 의도했지만 짧은 MVP 개발 기간동안 디자인 작업과 개발이 함께 이루어진다는점, 빈번한 기획 수정이 예상된다는 점으로 인해 완전한 아토믹한 요소들을 바탕으로 컴포넌트들을 쌓아올려가며 개발하는 방식을 적용하는 것이 어렵다는 결론에 도달하였습니다.

따라서 코드의 작성 또한 디자인과 기획의 변경에 대응하기 위해 확장성있고 유연한 방식으로 할 수 있도록 노력했습니다. 공통 컴포넌트들에 추가적인 ClassName과 ClassNameCondition이라는 Prop을 받아 사용하는 쪽에서 디자인의 변화를 대응할 수 있게 하였으며, 우선적으로 모든 기능을 개발하고 이후 리팩토링 과정에서 정돈하는 것으로 방향을 잡았습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

const Button = forwardRef<HTMLButtonElement, Props>(
  (
    {
      fill,
      size,
      font,
      label,
      type,
      hover,
      hoverBorder,
      disabled,
      children,
      className,
      classNameCondition,
      handler,
      showSpinner,
    },
    ref
  ) => {
    return (
      <button
        ref={ref}
        type={type === "submit" ? "submit" : "button"}
        disabled={disabled}
        className={cn(ButtonVariants({ fill, size, font, hover, hoverBorder }), className, classNameCondition)}
        onClick={handler}
      >
        {label && (showSpinner ? <SpinnerButtonIcon className="animate-spin" /> : label)}
        {children && children}
      </button>
    );
  }
);

템플릿 코드 작성

짧은 개발 기간을 효율적으로 사용하고 개발 생산성을 올리기 위해 많은 고민을 했습니다. 팀원들에 경우 결정된 기술을 사용해보지 못한 팀원들도 있었고, 있다 하더라도 이해도가 차이가 났습니다. 또한 각 기술들을 통해 작성하는 코드들이 일관되지 못할 것이라는 걱정도 있었습니다.

이를 해결하기 위해 미팅 때 기술에 대한 전체적인 이해도를 맞추기 위한 기술 발표를 진행했고, 템플릿 코드를 개발 이전 우선적으로 작성하여 코드 작성에 대한 가이드라인을 제시했습니다.

모킹 API 활용

프론트엔드와 백엔드가 동시에 개발을 진행하는 경우 백엔드 개발 완료 이전 프론트엔드에서 API 관련 코드를 작성할 수 없다는 딜레마가 생겼습니다. 이를 해결하기위해 MSW의 API 모킹 기능을 활용하여 API 명세서를 바탕으로 API 관련 코드 작성을 진행했습니다.

프론트엔드에서는 모킹 API를 활용한 개발 환경과 실제 개발 완료된 API를 활용한 개발 환경을 나누어 테스트 할 수 있도록 세팅했고, 이를 통해 개발 생산성을 높일 수 있었으며, 백엔드 개발이 완료된 이후에도 브라우저에서 에러 상황을 연출할 필요 없이 모킹된 API를 통해 다양한 에러 상황들에 대해 테스트 해볼 수 있었습니다.

프론트 - 백 소통

프론트엔드와 백엔드 간의 소통은 Trello를 사용하여 이루어졌습니다. 각 카드들을 통해 현재 진행중인 개발 상황들에 대해 공유할 수 있도록 하였으며, 개발된 내용과 관련된 이슈들이나 추가 요구 사항들을 REQUEST 카드를 생성하여 전달하고 메시지를 주고 받았습니다.

▫︎ 구현 사항 및 이슈 공유

개발 구현 사항 및 이슈등을 노션에 문서화하여 공유했습니다. 이를 통해 팀원과 구현 사항에 대한 의견을 주고 받을 수 있었으며, 자신이 맡은 업무 뿐만아니라 다른 팀원의 기능들까지 함께 고민하고 이해할 수 있는 계기가 되었습니다.

이슈 공유 시 정리된 문서를 통해 담당자가 직접 겪었던 경험들을 미리 확인하고 대안을 함께 고민할 수 있었으며, 각자의 구현 사항에 대해 복습할 수 있는 레퍼런스를 확보할 수 있었습니다.

▪︎ 프론트엔드 프로젝트 구조

1
2
3
4
5
6
7
8
9
10
11
12
13
14

src/
├── @types/          # 타입스크립트 타입 정의
├── api/             # API 통신 관련 로직
├── app/             # Next.js 13+ 앱 라우팅
├── components/      # 리액트 컴포넌트
├── constants/       # 상수 정의
├── hooks/           # 커스텀 훅
├── mocks/           # MSW 모킹 관련
├── providers/       # 리액트 컨텍스트 프로바이더
├── queries/         # React-Query 관련 로직
├── store/           # Zustand 상태 관리
├── styles/          # 전역 스타일 및 폰트
├── utils/           # 유틸리티 함수
└── middleware.ts    # Next.js 미들웨어

관심사의 분리와 모듈화를 통해 코드의 재사용성과 유지보수성을 높이는데 중점을 두고 구조를 설정했습니다. 특히 도메인별로 관련 코드들을 그룹화하여 확장성과 가독성을 높였습니다.

1. app/
   • app 폴더의 경우 next.js 앱라우터를 이용할 때 정말 routable한 파일들만을 관리하는 것이 더 명시적인 구조라고 생각했습니다. 따라서 실제 라우팅되는 페이지들을 분리하여 관리했고, 하위에 구성되는 컴포넌트들은 components 폴더에서 관리했습니다.
2. api/ - queries/
   • 관심사를 분리하기 위해 api 폴더와 queries 폴더를 분리하였습니다. HTTP 요청의 기본 구조 정의, 엔드포인트 URL 관리, 요청/응답 타입 정의, HTTP method 정의와 같은 순수한 API 통신 로직은 api 폴더에서 관리하고 캐싱 전략, 에러처리 및 재시도 로직, 데이터 동기화 등 데이터 상태 로직에 대해서는 queries 폴더에서 Tanstack Query를 활용하여 관리했습니다.
3. constants/
   • 쿼리키, 인증관련 스키마와 같은 상수들을 따로 분리하여 관리함으로써 프로젝트의 확장성과 유지보수성을 향상시켰으며 팀 단위 개발에서 일관성있는 코드 작성이 가능했습니다.
4. utils/
   • 유틸리티 함수들 또한 분리하여 관리하여 컴포넌트 내에서의 함수 정의를 지양했습니다. 기능을 나타낼 수 있는 확실한 함수 네이밍을 통해 컴포넌트 내에서의 코드의 양을 줄이고 가독성을 향상시켰습니다.

▪︎ 마치며

이번 프로젝트에서는 MSW를 활용한 API 모킹과 체계적인 폴더 구조화를 통해 효율적인 개발 환경을 구축할 수 있었습니다. 특히 백엔드와의 의존성을 줄이고 병렬 개발을 가능하게 한 것이 가장 큰 성과였습니다.

또한 constants, queries, api 등의 폴더 구조화를 통해 코드의 역할과 책임을 명확히 분리함으로써, 유지보수성과 확장성을 크게 향상시켰습니다. 이러한 구조는 팀 단위의 개발에서 일관성 있는 코드 작성을 가능하게 했습니다.

앞으로도 지속적인 개선을 통해 더 나은 개발 경험을 만들어나갈 예정이며, 이러한 경험이 다른 프로젝트에도 좋은 참고가 되길 바랍니다.

▪︎ API 모킹 도입의 배경

프론트엔드와 백엔드가 동시에 개발을 시작하는 프로젝트에서는 항상 한 가지 딜레마가 존재합니다. 프론트엔드 개발자는 백엔드 API가 완성되기 전까지 실제 데이터를 다루는 코드를 작성하기 어렵다는 점입니다.

우리 프로젝트는 짧은 MVP 개발 기간이라는 제약 조건 속에서 이 문제를 해결해야 했습니다. 이를 위해 다음과 같은 접근 방식을 채택했습니다.

▫︎ 선행 API 명세 작성

• 디자인 시안 분석을 통한 필요 API 도출
• 데이터 구조 및 엔드포인트 사전 정의
• 팀 간 API 명세서 공유 및 합의

▫︎ 병렬 개발 전략

• 백엔드: API 명세에 따른 실제 구현
• 프론트엔드: 모킹된 API를 통한 선행 개발

우선 디자인 시안을 분석하여 우리 앱 개발에 필요한 API들을 분석하고 정리하여 API 명세서를 작성했습니다. 해당 문서를 통해 프론트엔드 - 백엔드 간 소통을 진행하였으며 이를 바탕으로 모킹된 API를 작성, API 관련 개발을 초기부터 진행할 수 있었습니다.

▪︎ MSW란?

MSW는 서비스 워커를 활용하여 네트워크 수준에서 API 요청을 가로채고 모의 응답을 제공하는 API 모킹 라이브러리입니다.

출처: https://www.codit.eu/blog/how-to-mock-api-requests-in-front-end-development/

1. 브라우저에 Service Worker가 구성되어 있고, 실제 요청(Request)이 발생하면 Service Worker가 이를 가로챕니다.
2. Service Worker는 가로챈 요청(Request)을 복사하여 MSW로 전달합니다.
3. MSW는 가로챈 요청을 미리 정의된 모의 응답(Mock Response)과 매칭하는 작업을 수행합니다.
4. MSW는 모의 응답을 Service Worker에 전달합니다.
5. Service Worker는 모의 응답을 브라우저에 전달합니다.

▫︎ MSW의 주요 특징

1. 네트워크 레벨 모킹
   • 실제 네트워크 요청을 가로채서 처리
   • 브라우저 네트워크 탭에서 요청 확인 가능
   • 실제 API와 동일한 동작 방식
2. 개발 환경 통합
   • 별도의 서버 없이 모킹 환경 구축
   • 실제 API로의 전환이 용이
   • 테스트 코드와의 높은 호환성

▪︎ MSW를 활용한 API 모킹

우리 프로젝트에 MSW를 적용하여 백엔드 개발 이전 모킹된 API를 통한 관련 코드 작성이 가능했습니다. 뿐만아니라 테스트 코드에서도 MSW를 활용하여 API 통신과 관련된 테스트도 진행하여 보다 안정된 코드 작성이 가능했습니다.

이는 프론트엔드 개발 생산성을 크게 증대시켰습니다. 실제 API와 모킹 API 연결 간 코드의 수정이 필요가 없었기 때문에 명세서 대로 작성하고 백엔드 개발 완료 이후에는 정상적으로 동작하는지 확인만 해주면 되었습니다.

▫︎ 핸들러 구현 예시 (Auth)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

export const signup = [
  /* -------------------------------- 인증 이메일 전송 ------------------------------- */
  http.post<MailSendRequestBody, PathParams>(
    `${process.env.NEXT_PUBLIC_BASE_URL}/auth/sign-up/emails`,
    async ({ request }) => {
      const { email } = await request.json();

      // 이메일 중복 체크 실패 (이미 가입된 이메일)
      if (email === FAKE_USER_EMAIL) {
        return HttpResponse.json(
          { message: 'Email already exists' },
          { status: 400 },
        );
      }

      // 이메일 중복 체크 성공
      return HttpResponse.json(
        {
          message: 'Email sent',
        },
        { status: 200 },
      );
    },
  ),

  /* ------------------------------- 이메일 인증코드 확인 ------------------------------ */
  http.post<VerifyRequestBody, PathParams>(
    `${process.env.NEXT_PUBLIC_BASE_URL}/auth/emails/verify`,
    async ({ request }) => {
      const { verifyNumber } = await request.json();

      // 이메일 인증코드 확인 실패
      if (Number(verifyNumber) !== FAKE_EMAIL_CODE) {
        return HttpResponse.json(
          {
            message: 'Invalid email code',
          },
          {
            status: 400,
          },
        );
      }

      // 이메일 인증코드 확인 성공
      return HttpResponse.json(
        {
          message: 'Email code verified',
          verifiedToken: FAKE_VERIFIED_TOKEN,
        },
        { status: 200 },
      );
    },
  ),

  /* -------------------------------- 회원 가입 요청 -------------------------------- */
  http.post<SignupRequestBody, PathParams>(
    `${process.env.NEXT_PUBLIC_BASE_URL}/auth/sign-up`,
    async ({ request }) => {
      const {
        email,
        password,
        name,
        nickname,
        birthDate,
        contact,
        verifiedToken,
      } = await request.json();

      // 회원 가입 성공
      if (
        email &&
        password &&
        name &&
        nickname &&
        birthDate &&
        contact &&
        verifiedToken
      ) {
        return HttpResponse.json(
          {
            message: 'Sign up successful',
          },
          {
            status: 200,
            headers: {
              'Set-Cookie': 'accessToken=msw-access, refreshToken=msw-refresh',
            },
          },
        );
      }
      return HttpResponse.json({ message: 'Sign up failed' }, { status: 400 });
    },
  ),

1. 실제 API 스펙 반영
   • 동일한 엔드포인트 사용
   • 일치하는 요청/응답 구조
   • 에러 케이스 시뮬레이션
2. 상태 관리
   • 모의 데이터베이스 구현
   • 상태 변경 추적
   • 실제 서버와 유사한 동작

▪︎ 개발 환경 분리

1
2
3
4
5
6
7

// package.json
{
  "scripts": {
    "dev": "cross-env NEXT_PUBLIC_MODE=production next dev -H front.we-go.world --experimental-https",
    "dev-mock": "cross-env NEXT_PUBLIC_MODE=mock next dev"
  }
}

개발을 진행하며 모킹된 API를 적용한 환경과 실제 API를 적용한 환경을 구별하여 개발 편의성을 늘렸습니다. npm dev-mock 명령어를 통해 우리가 작성한 모킹 API를 기반으로 한 테스트를 진행하고, 이후 npm run dev 명령어를 통해 실제 API 환경에서도 작성된 코드가 잘 동작하는지를 확인할 수 있었습니다.

백엔드 개발이 완료된다 하더라도 모킹 환경은 큰 이점이 있었습니다. 에러 케이스들을 확인해야 할 때 특히 유용하게 사용되었는데, 에러 상황을 띄우기 위해 브라우저에서 다른 동작을 해주지 않고 간단한 코드 수정만으로 해당 상황을 연출할 수 있었기 때문입니다.

▫︎ 환경별 동작 방식

1. 실제 API 환경 (npm run dev)
   • 실제 백엔드 서버로 요청
   • 프로덕션과 동일한 동작
   • 실제 데이터로 테스트
2. 모킹 환경 (npm run dev-mock)
   • MSW가 요청 가로챔
   • 모의 응답 반환
   • 빠른 개발 반복 가능

▫︎ 환경 분리의 이점

1. 개발 생산성 향상
   • 백엔드 의존성 제거
   • 빠른 프로토타이핑
   • 병렬 개발 가능
2. 코드 재사용성
   • API 관련 코드의 재사용
   • 환경 전환 시 코드 수정 최소화
   • 일관된 인터페이스 유지
3. 유지보수 용이성
   • API 스펙 변경 시 한 곳만 수정
   • 테스트 환경 구축 용이
   • 디버깅 효율성 증가

▫︎ 실제 적용 효과

1. 개발 프로세스 개선
   • API 명세 기반 선행 개발 가능
   • 백엔드 개발 완료 전 기능 구현
   • 빠른 피드백 루프 형성
2. 코드 품질 향상
   • 일관된 API 인터페이스 유지
   • 엣지 케이스 테스트 용이
   • 안정적인 개발 환경 제공
3. 팀 협업 효율화
   • 명확한 API 계약 정의
   • 의사소통 비용 감소
   • 병렬 작업 가능

▪︎ 마치며

MSW를 활용한 API 모킹과 개발 환경 분리는 현대적인 웹 개발 프로세스에서 매우 효과적인 전략입니다. 특히 짧은 개발 기간 내에 프론트엔드와 백엔드가 동시에 개발을 진행해야 하는 상황에서, 이 접근 방식은 개발 생산성을 크게 향상시키고 코드 품질을 유지하는 데 도움이 되었습니다.

이러한 방식은 단순히 개발 편의성을 넘어서, 더 나은 소프트웨어 아키텍처와 개발 프로세스를 구축하는 데 기여했습니다. API 명세를 중심으로 한 개발 방식은 프론트엔드와 백엔드 간의 명확한 계약을 형성하며, 이는 장기적으로 프로젝트의 유지보수성과 확장성을 높이는 결과로 이어진다고 생각합니다.

Next.js 프론트엔드 개발 중 백엔드와의 쿠키 공유 이슈를 해결하기 위해 HTTPS 를 설정하게 되었습니다. SameSite=None, Secure 설정이 된 쿠키를 저장하기 위해서는 HTTPS 를 사용해야합니다.

▪︎ Window 에서 localhost를 HTTPS 로 설정하는 방법

1️⃣ Chocolatey 설치

PowerShell을 관리자 권한으로 실행하여 다음 명령어를 입력합니다.

1

Set-ExecutionPolicy Bypass -Scope Process -Force; [System.Net.ServicePointManager]::SecurityProtocol = [System.Net.ServicePointManager]::SecurityProtocol -bor 3072; iex ((New-Object System.Net.WebClient).DownloadString('https://community.chocolatey.org/install.ps1'))

2️⃣ mkcert 설치

1

choco install mkcert

3️⃣ Local CA 설치

1

mkcert -install

4️⃣ localhost 인증서 생성

프로젝트 루트로 이동하여 다음 명령어를 입력합니다.

1

mkcert localhost

위 단계를 정상적으로 마쳤다면 localhost.pem 과 localhost-key.pem 파일이 생성됩니다.

여기서 생성된 인증서의 개인키는 절대 공유되어서는 안되며 프로젝트의 모든 팀원들이 각자의 시스템에 개별적으로 설치하여야 합니다.

5️⃣ Github 에 공유되는 것을 막기 위해 .gitignore 파일에 다음 텍스트를 추가

1
2
3
4
5

# SSL Certificate
*.pem
*.key
*.crt
*.cert

6️⃣ package.json 의 script에 개발 환경 테스트 명령어를 수정

1
2

"scripts": {
  "dev": "next dev -H [개발 도메인 주소] --experimental-https",

▪︎ 호스트에 Custom Domain을 설정하는 방법

호스트 파일을 수정하여 Custom Domain을 설정하면 개발 환경에서 localhost 대신 지정한 도메인을 사용하여 애플리케이션에 접근할 수 있습니다. 이를 통해 프론트엔드와 백엔드가 동일한 베이스 도메인 하에서 동작하게 되어 쿠키 설정 시 도메인 불일치 문제를 해결할 수 있습니다.

1️⃣ /etc/hosts 파일을 수정

호스트 파일을 수정함으로써 특정 도메인을 localhost (127.0.0.1)로 매핑할 수 있습니다.

1. vscode와 같은 에디터를 관리자 권한으로 실행합니다.
2. open file 클릭 후 ****C:\Windows\System32\drivers\etc ****경로에서 hosts 파일을 실행합니다.
3. 코드 맨 아래에 127.0.0.1 front.we-go.world 를 추가합니다.

2️⃣ package.json 파일의 script의 dev 명령어에서 도메인을 수정

1
2

"scripts": {
  "dev": "next dev -H front.we-go.world --experimental-https",

확인

실행 시 다음과 같이 설정한 도메인의 개발 환경에서 테스트를 할 수 있다.

▪︎ 백엔드 서버와의 쿠키 공유

▫︎ 개발 환경에서 Set-Cookie로 받은 쿠키가 사라진다?

우리 프로젝트에서는 로그인을 하면 서버에서 Set-Cookie를 통해 인증 토큰을 심어주고, 이후 인증이 필요한 요청 (로그인이 필요한 요청) 시 서버에서 프론트 요청의 쿠키를 읽어 인증 여부를 검증하고 그에 따른 응답을 반환하도록 설계되어있다.

배포 환경에서는 해당 로직이 잘 동작하였으나 개발 환경에서 받아온 쿠키가 계속해서 사라지는 현상이 일어났다.

▫︎ 문제 찾아보기

1️⃣ cors 설정이 제대로 안되어있는 것은 아닐까?

우선 백엔드 측에 cors 설정이 되어있는지를 확인해보았다. 백엔드 측에서는 개발환경과 배포환경에 대해 조건부로 잘 설정해주었다고 답변받았다. 혹시 실수가 있었던 것은 아닐까? next.js 의 rewrites 기능을 이용하여 프록시를 통해 cors를 우회하여 테스트를 해보았다.

1
2
3
4
5
6
7
8
9

// next.config.ts
  rewrites: async () => {
    return [
      {
        source: '/api/:path*',
        destination: `${process.env.NEXT_PUBLIC_BASE_URL}/:path*`,
      },
    ];
  },

$ 여전히 쿠키는 사라진다. cors 문제는 아니다.

2️⃣ SameSite 를 None 으로 설정하면 해결되지 않을까? ( + Secure )

크로스 사이트 요청 시 쿠키 전송을 허가하는 설정인 SameSite=None 을 쿠키에 설정해주면 어떨까? 우선 SameSite를 설정하기 위해서는 Secure 설정또한 추가로 해줘야 한다.

$ 해당 설정을 해주어도 동일한 현상이 일어났다.

3️⃣ HTTP 의 문제

문제 해결을 위해 쿠키의 각 속성에 대한 정보를 찾아보았다. Secure 설정을 위해서는 반드시 HTTPS 요청이 필요하다. HTTP와 HTTPS 간의 scheme 차이 때문에 발생하는 문제였다는 것을 찾아냈다.

정리해보자면 SameSite=None을 사용하기 위해서는 반드시 Secure 플래그가 필요하고, 이를 위해서는 다시 HTTPS가 필요하다.

mkcert 로 로컬 인증서를 생성하고 pakage.json의 script에서 “dev” 명령어에 —experimental-https 옵션을 사용하여 https://localhost:3000 에서 요청을 보내보았다.

1
2
3
4

// package.json
"scripts": {
    "dev": "next dev -H localhost --experimental-https",
...

$ https 설정을 하여 SameSite=None, Secure 설정을 해줘도 쿠키는 사라졌다.

4️⃣ 크로스 도메인 문제인 것 같다. 쿠키를 구워줄 때, 개발환경에서의 요청이라면 Domain 값을

    **localhost로 설정하면 되지 않을까?**

마지막으로 살펴볼만한 문제는 쿠키의 Domain 속성이다. 쿠키의 도메인은 .we-go.world 로 되어있다. 배포 주소가 we-go.world 이기 때문에 배포 사이트에서는 정상적으로 동작하고, localhost 인 개발환경에서는 정상적으로 동작하지 않는 것이 아닐까?

백엔드와 상황을 공유하니 백엔드에서 요청한 클라이언트의 Origin을 읽어 그에 따라 조건부로 Domain을 설정해주기로 했다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

@Component
public class CookieProvider {
    @Value("${cookie.domain}")
    private String domain;

    @Value("${security.jwt.token.expire-length}")
    private String accessTokenExpire;

    public ResponseCookie accessTokenCookie(String accessToken, HttpServletRequest request) {
        String origin = request.getHeader("Origin");
        String referer = request.getHeader("Referer");

        boolean isLocalhost = (origin != null && (origin.contains("localhost") || origin.contains("127.0.0.1")))
            || (referer != null && (referer.contains("localhost") || referer.contains("127.0.0.1")));

        ResponseCookie.ResponseCookieBuilder cookieBuilder = ResponseCookie.from("accessToken", accessToken)
            .httpOnly(true)
            .secure(true)
            .path("/")
            .maxAge(Duration.ofSeconds(Long.parseLong(accessTokenExpire)))
            .sameSite("None");

        if (!isLocalhost) {
            cookieBuilder.domain(domain);
        }

        return cookieBuilder.build();
    }
}

그러나 동일하게 쿠키의 Domain 부분에는 .we-go.world 가 설정되어있다.

5️⃣ 서버는 자신의 도메인이 아닌 다른 도메인에 쿠키를 설정할 수 없다.

api 요청 시 백엔드도 localhost 에서 실행되었을 때에는 쿠키가 정상적으로 설정되었겠지만, 우리는 지금 배포된 백엔드에 테스트를 하려고 했다. 그래서 Domain이 우리가 의도한 대로 설정되지 않았다.

6️⃣ 로컬 호스트 환경에서도 도메인 일치를 위해 Custom Domain을 설정하자.

프론트의 로컬 호스트 환경에서 Custom Domain을 설정하여 프론트와 백엔드가 동일한 베이스 도메인 하에서 테스트할 수 있다면 해결되지 않을까?

/etc/hosts 파일을 수정하여 localhost 도메인을 front.we-go.world로 설정하고, 추가로 개발 모드 실행에서 도메인을 명시해주었다.

1
2
3
4
5

// package.json
...
"scripts": {
  "dev": "next dev -H front.we-go.world --experimental-https",
...

▪︎ 정리

프론트와 백엔드 간의 쿠키 공유를 위해서는 서로의 베이스 도메인을 일치시켜야한다. 또한 서로가 동일한 도메인이 아닌 경우, 쿠키의 SameSite=None 과 Secure 설정이 필요하며 이를 위해서는 프론트의 개발 환경에서 HTTPS 를 사용해야만 한다.

포스팅: 개발 환경에 HTTPS 및 Custom Domain 설정하기

부분문자열 찾기

위 이미지와 같은 문제에서 어떠한 문자열 내에서 특정한 다른 문자열을 찾을 때 가장 단순한 방법은 두 문자열의 각 문자들을 비교하는 것입니다. 그러나 이 경우 각 문자열의 모든 문자들을 매칭하여 탐색해야하기 때문에 효율성이 낮습니다. 따라서 대상 문자열의 크기가 크거나 효율성을 높이고 싶다면 KMP 알고리즘을 고려해볼 수 있습니다. 위 사진을 예시로하여 문자열을 찾는 두가지 방법에 대해 밑에서 알아보겠습니다.

▪︎ 두 문자열의 각 문자 비교

str을 기준으로 각 문자를 순회하되 해당 문자가 subStr의 첫 문자와 같다면 그 다음 문자들을 비교하는 방식으로 이루어집니다. 이 경우 str을 순회하는 start 포인터와 str과 subStr의 일치여부 확인을 위한 위치 포인터가 필요하기 때문에 O(NM)의 시간복잡도를 가집니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

const str = "ABCABCABBD";
const subStr = "ABCABB";
const answerIdx = [];

for (let i = 0; i < str.length; i++) {
  let isMatched = true;

  for (let j = 0; j < subStr.length; j++) {
    if (str[i + j] !== subStr[j]) {
      isMatched = false;
      break;
    }
  }

  if (isMatched) answerIdx.push(i + 1);
}

console.log(answerIdx); // output: [4] 4번째 문자로 시작하는 하나의 같은 문자열이 존재

▪︎ KMP 알고리즘

위 방법을 개선하여 효율성 높게 문자열을 찾는 방법이 KMP 알고리즘입니다. KMP 알고리즘은 무려 O(N+M)의 시간복잡도로 해결이 가능합니다. 어떻게 그것이 가능할까요? 문자열들의 각 문자들을 비교하는 방법에서는 버려지는 정보들을 활용하기 때문입니다. 위의 예시를 다시 가져와보겠습니다.

두 문자열을 비교하던 중 매칭이되지 않은 문자들을 만났습니다. 이 때 우리는 ABCABC가 ABCABB가 아니라는 것을 확인함과 동시에 ABCABB의 앞쪽 문자들과 매칭되는 부분(index 3 ~ 4)이 있다는 정보를 얻게되었습니다. 이 정보를 활용하면 str문자열의 각 문자를 시작으로 하는 문자열을 전부 확인하는 것이 아니라 subStr의 앞쪽 부분과 매칭되는 index 3에서부터 다시 비교를 시작할 수 있습니다.

이 원리를 이용하면 str을 이중 순회하는 것이 아닌 한번의 순회만으로 문자열을 찾아낼 수 있습니다. subStr을 문자열의 접두사이면서 접미사인 부분 문자열들에 대한 정보와 매칭하고 그 정보를 이용하여 str의 문자를 순회하는 동안 subStr의 포인터를 이동시켜 같은 문자열인지를 판단합니다.

KMP 알고리즘은 다음 단계를 통해 구현할 수 있습니다.

1. subStr의 접두사,접미사 관련 정보를 담은 pi를 생성합니다.
2. str을 순회하며 각 문자열의 pointer 이동합니다.
3. subStr의 포인터가 끝으로 이동했을 때에 문자끼리 같다면 동일 문자열입니다.

▫︎ failure 함수를 통해 pi 배열 생성

pi 배열은 subStr의 접두사와 접미사를 확인하여 같은 길이를 값으로 가지는 배열입니다. pi의 index 0은 0으로 시작하며 이후부터는 해당 인덱스까지의 부분문자열의 접두사와 접미사가 같은 길이를 값으로 가집니다. pi 배열은 failure함수를 통해 만들 수 있습니다.

“ABCA”의 경우 앞 뒤 “A”가 같기 때문에 1을 값으로 가집니다.

“ABCAB”의 경우 앞 뒤 “AB”가 같기 때문에 2를 값으로 가집니다.

failure 함수의 동작

1. 첫 인덱스 값을 0으로하는 subStr 길이와 같은 배열을 생성합니다.
2. 새로운 포인터 k를 선언하고 subStr을 순회하면서 다음 동작을 반복합니다.
   • subStr[k]와 subStr[i]가 같은 경우 pi[i]에 k+1을 저장하고 k와 i 인덱스를 모두 증가시킵니다.
   • 다를경우 k에 pi[k-1] 위치에 있는 값을 재할당합니다. (이 동작을 subStr[k]와 subStr[i]가 같아지거나 k가 0이 될 때까지 반복합니다) 이후 i 인덱스만 증가시킵니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

const subStr = "ABCABB";
const pi = Array(subStr.length).fill(0);

let k = 0;
for (let i = 1; i < subStr.length; i++) {
  while (k > 0 && subStr[k] !== subStr[i]) {
    k = pi[k - 1];
  }

  if (subStr[k] === subStr[i]) {
    pi[i] = k + 1;
    k++;
  }
}

console.log(pi); // [0,0,0,1,2,0]

▫︎ pi배열과 두 문자열을 이용해 문자열 찾기

이제 pi 배열을 이용해서 문자열을 찾아보겠습니다. str과 subStr의 각 포인터들을 이동시키면서 str을 순회합니다. 아래 그림과 같은 방식으로 동작합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

const str = "ABCABCABBD";
const subStr = "ABCABB";
const pi = Array(subStr.length).fill(0);

// failure 함수를 통해 pi 배열 설정
let k = 0;
for (let i = 1; i < subStr.length; i++) {
  while (k > 0 && subStr[k] !== subStr[i]) {
    k = pi[k - 1];
  }

  if (subStr[k] === subStr[i]) {
    pi[i] = k + 1;
    k++;
  }
}

// pi 배열을 이용해 문자열 찾기
let j = 0;
const answerIdx = [];
for (let i = 0; i < str.length; i++) {
  while (j > 0 && subStr[j] !== str[i]) {
    j = pi[j - 1];
  }

  if (subStr[j] === str[i]) {
    if (j === subStr.length - 1) {
      answerIdx.push(i - subStr.length + 2);
      j = pi[j];
    } else {
      j++;
    }
  }
}

console.log(answerIdx); // output: [4] 4번째 문자로 시작하는 하나의 같은 문자열이 존재

▪︎ 에라토스테네스의 체

에라토스테네스의 체는 빠르게 범위 내 소수들을 찾는 방법입니다. 하나의 수에 대해 소수인지 아닌지를 판별하는 것은 O(N)으로 해결이 가능하지만 범위 내에서 소수들을 찾기 위해서는 추가로 범위 내에 존재하는 K개의 수가 곱해진 O(N*K)의 시간복잡도를 가질 것입니다. 그러나 에라토스테네스의 체를 이용하면 O(N * log logN)의 시간복잡도로 이를 해결할 수 있습니다.

▫︎ 에라토스테네스의 체 원리

• _출처 : https://ko.wikipedia.org/wiki/에라토스테네스의_체_

step 1) 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.

step 2) 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)

step 3) 자기 자신을 제외한 2의 배수를 모두 지운다.

step 4) 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)

step 5) 자기 자신을 제외한 3의 배수를 모두 지운다.

step 6) 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)

step 7) 자기 자신을 제외한 5의 배수를 모두 지운다.

step 8) 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)

step 9) 자기 자신을 제외한 7의 배수를 모두 지운다.

step 10) 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다. (보라색)

범위 최대값의 제곱근보다 작거나 같은 자연수의 배수들만 지우면 된다. 위 예시의 경우 10까지만 배수들을 지워주는 동작을 시행한다.

▫︎ 에라토스테네스의 체 구현

1. 2부터 소수를 구하고자하는 구간의 모든 수를 배열의 인덱스를 key로 삼아 0과 1을 제외하고 모두 true로 초기화합니다.
2. 생성한 배열을 순회하면서 value가 false인 경우 스킵하고, true인 경우 배열 내 해당 index의 배수에 위치하는 모든 값들을 false로 재할당합니다.
3. 초기 생성한 배열에서 true를 값으로 가진 인덱스들이 소수입니다.

▪︎ Example of Apply

▫︎ 100보다 작은 소수 찾기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

// 소수 체크 테이블
const check = Array(Math.floor(101)).fill(true).fill(false, 0, 2);

// 100의 제곱근인 10보다 작은 자연수의 배수들만 지우기
for (let i = 2; i <= 10; i++) {
  if (!check[i]) continue;

  for (let j = i * 2; j <= 100; j += i) {
    check[j] = false;
  }
}

// 소수 배열
const prime = [];

// 체크 테이블의 값이 true인 index가 소수
check.forEach((el, idx) => {
  if (el) prime.push(idx);
});

console.log(prime);

코딩테스트에서 2차원 배열을 데이터로 주고 그 안에서 포인터를 이동시키는 문제 유형에서 유용하게 사용할 수 있는 방법입니다.

▪︎ dxdy 테크닉

dxdy 테크닉은 2차원 배열에서 어느 한지점의 포인터를 상하좌우로 간편하게 이동할 수 있는 방법입니다. x방향과 y방향의 direction 정보를 저장한 배열을 생성하고 순서대로 각 데이터를 참조하면서 현재 포인터 기준 4방향의 인덱스를 탐색할 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

const arr = [
  [1, 2, 3],
  [10, 20, 30],
  [100, 200, 300],
];
const dx = [0, 0, -1, 1];
const dy = [-1, 1, 0, 0];

// 현재 위치를 (1,1) 이라고 할 때, pointer 위치의 값은 20
const cx = 1;
const cy = 1;

for (let i = 0; i < 4; i++) {
  console.log(arr[cy + dy[i]][cx + dx[i]]);
}

// output :
// 2 (pointer 기준 '상')
// 200 (pointer 기준 '하')
// 10 (pointer 기준 '좌')
// 30 (pointer 기준 '우')

▪︎ Example of Apply

• https://www.acmicpc.net/problem/1987

이 문제는 (0,0) 위치에서부터 4방향을 움직이되 움직인 위치의 값이 이전에 지나온 값이라면 갈 수 없습니다. 따라서 dxdy 테크닉을 통해 2차원 배열을 재귀로 움직이면서 현재 위치의 값을 visited 변수에 저장하고 이동하면서 참조한 뒤, visited 값이 true라면 재귀를 멈추면 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

const fs = require("fs");

const input = fs.readFileSync("dev/stdin").toString().trim().split("\n");
const arr = input.slice(1).map((el) => el.trim().split(""));

const dx = [0, 0, 1, -1];
const dy = [1, -1, 0, 0];
const visited = Array(26).fill(false);
let answer = 0;

const dfs = (depth, x, y) => {
  answer = answer < depth ? depth : answer;

  for (let i = 0; i < 4; i++) {
    const nx = x + dx[i];
    const ny = y + dy[i];

    // 이동할 좌표가 없을 경우 continue
    if (nx < 0 || nx >= arr[0].length || ny < 0 || ny >= arr.length) continue;
    // 이동한 좌표의 알파벳의 아스키코드가 true면 이미 지나온 블록. continue
    if (visited[arr[ny][nx].charCodeAt() - 65]) continue;

    visited[arr[ny][nx].charCodeAt() - 65] = true;
    dfs(depth + 1, nx, ny);
    visited[arr[ny][nx].charCodeAt() - 65] = false;
  }
};

visited[arr[0][0].charCodeAt() - 65] = true;
dfs(1, 0, 0);

console.log(answer);

코딩테스트에서 그래프와 관련된 문제를 만났을 때, 해당 그래프를 순회하고 조작할 수 있는 정제된 형태의 데이터로 만들 필요가 있습니다. 이번 포스트에서는 여러 그래프의 종료들의 분석하는 방법과 함께 그래프 정보를 인접행렬 / 인접리스트 데이터로 정제하는 방법에 대해 다뤄보겠습니다.

▪︎ 무방향 그래프

무방향 그래프는 노드가 서로 양방향으로 연결되어있는 형태로 방향에 상관없이 연결된 노드에 접근이 가능한 구조입니다. 행을 타겟 노드로, 열을 접근할 노드로 하는 인접행렬 데이터를 배열로 만들어 순회할 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

// 무방향 그래프
const N = 5;
const input = [
  [1, 2],
  [1, 3],
  [2, 4],
  [2, 5],
  [3, 4],
];
const graph = Array.from(Array(N + 1), () => Array(N + 1).fill(0));

input.forEach((array) => {
  graph[array[0]][array[1]] = 1;
  graph[array[1]][array[0]] = 1;
});

console.log(graph);

▪︎ 방향 그래프

방향 그래프는 노드가 단방향으로 연결되어있는 형태로 한쪽 방향으로만 연결된 노드에 접근할 수 있습니다. 입력된 그래프 데이터에서 노드가 가리키는 다른 노드의 위치에 대한 정보만을 인접행렬에 저장합니다. (입력 데이터 각 배열의 인덱스의 값의 순서가 의미를 가집니다.)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

// 방향 그래프
const N = 5;
const input = [
  [1, 2],
  [1, 3],
  [3, 4],
  [4, 2],
  [2, 5],
];
const graph = Array.from(Array(N + 1), () => Array(N + 1).fill(0));

input.forEach((array) => {
  graph[array[0]][array[1]] = 1;
});

console.log(graph);

▪︎ 가중치 그래프

가중치 그래프는 노드끼리에 연결에 가중치가 붙어있는 구조입니다. 입력 데이터에 [1, 3, 3]과 같이 가중치에 대한 정보가 추가로 들어있습니다. 구현 방법은 위와 같으며 연결된 노드에 1이 아닌 가중치를 저장해주면 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

// 가중치 무방향 그래프
const N = 5;
const input1 = [
  [1, 2, 2],
  [1, 3, 4],
  [2, 4, 2],
  [2, 5, 5],
  [3, 4, 5],
];
const graph1 = Array.from(Array(N + 1), () => Array(N + 1).fill(0));

input1.forEach((array) => {
  graph1[array[0]][array[1]] = array[2];
  graph1[array[1]][array[0]] = array[2];
});

console.log(graph1);

/* --------------------------------------------------------------------- */

// 가중치 방향 그래프
const input2 = [
  [1, 2, 2],
  [1, 3, 4],
  [3, 4, 5],
  [4, 2, 2],
  [2, 5, 5],
];
const graph2 = Array.from(Array(N + 1), () => Array(N + 1).fill(0));

input2.forEach((array) => {
  graph2[array[0]][array[1]] = array[2];
});

console.log(graph2);

▪︎ 노드 개수가 많을 때

노드의 개수가 적을 때에는 인접 행렬 데이터로 변환하여 문제를 풀 수 있지만, 노드의 개수가 많아질수록 그래프 크기가 커져 재귀의 동작이 많아져 문제를 푸는데 어려움이 생깁니다. 이럴 때는 인접행렬 대신 인접리스트를 사용하여 문제를 풀 수 있습니다.

인접리스트에서는 graph의 행의 인덱스 만이 노드를 키값으로 의미를 지니게 되고, 열의 인덱스는 인접행렬과 달리 의미를 지니지 않습니다. 각 노드 행에 연결된 노드에 대한 정보를 push해주면 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

// 인접리스트
const N = 5;
const input = [
  [1, 2],
  [1, 3],
  [1, 4],
  [2, 1],
  [2, 3],
  [2, 5],
  [3, 4],
  [4, 2],
  [4, 5],
];
const graph = Array.from(Array(N + 1), () => Array(0));

input.forEach((el) => {
  graph[el[0]].push(el[1]);
});

console.log(graph);

▪︎ 재귀 함수

재귀 함수란 자기 자신을 호출하는 함수를 말합니다. 종료 조건이 충족될 때까지 반복적으로 자신을 호출하면서 주어진 동작을 수행합니다. 재귀 함수는 순회할 대상의 상태를 변경하면서 각 대상마다 비슷한 동작을 수행해야 할 때 효율적으로 사용할 수 있습니다.

[1, 2, 3, 4, 5, 6] 이라는 배열안의 모든 숫자의 합을 구하는 코드를 작성한다고 해보겠습니다. 이 경우 간단하게 배열을 for문으로 순회하는 것으로 풀이가 가능합니다.

[1, 2, 3, [1, 2, [4, 5], 3], 5, 6] 이러한 형태의 배열은 어떨까요? 3중 for문으로 배열들을 순회하면 가능할 것입니다. 그러나 문제에서 주어지는 입력값이 계속 바뀔 수 있고, 어느정도 중첩될지 예측할 수 없는 상황이라면 기존처럼 코드를 구현하기에는 한계가 있을 것입니다. 이 때 재귀함수를 사용하면 효율적이고 가독성있는 코드 작성이 가능합니다.

▫︎ 재귀 함수의 구성

재귀 함수는 크게 종료 조건과 실행할 동작으로 나누어 구성할 수 있습니다. 실행할 동작에서 주어진 데이터들을 가공하고 동작을 수행하면서 자기 자신을 계속 호출하다가 정해놓은 종료 조건에 다달았을 때 함수를 return하게 하는 것입니다.

1
2
3
4
5
6
7
8
9
10

const recursive = (depth, ...) => {
  if( 종료 조건 ) return;

//-------------------------------

  // depth별 실행할 동작
  recursive(depth+1, ...)
};

recursive(1, ...)

▫︎ 재귀 함수의 depth

재귀 함수를 자바스크립트 코드로 처음 구현할 때, 코드의 동작을 따라가며 이해하는 것이 어렵습니다. 그러나 depth 개념을 적용하여 코드를 구현한다면 원활한 이해가 가능합니다. depth는 재귀 함수가 호출된 깊이, 즉 자신을 몇번째 호출했는지에 대한 데이터입니다.

순열과 조합을 예시로 지금까지의 내용들을 적용하여 재귀함수를 이해해보겠습니다.

▪︎ 카드를 뽑아보자

▫︎ 순열

순열은 순서를 고려하여 카드들을 뽑는 방법입니다. 카드를 하나씩 뽑되, 뽑은 카드는 제외하고 남은 카드들 중에서 하나씩 뽑는 것을 반복하면 됩니다. 그러다가 원하는 개수의 카드를 뽑았을 때 동작을 멈추면 됩니다. 재귀를 사용하면 효율적인 이유는 카드를 뽑는 동작들이 모두 ‘주어진 배열들을 순회하며 하나를 선택한다’라는 같은 동작을 하기 때문입니다. 각 카드를 뽑는 동작, 몇 번째 카드를 뽑는 상황인지에 따라 depth가 부여됩니다. (첫 번째 카드를 뽑으면 depth 1 …)

이제 우리는 재귀 함수를 구현하기 위해 세가지만 고려하면 됩니다.

1. 종료 조건
2. 시행할 동작
3. 필요한 데이터

1. 종료 조건은 우리가 카드를 3개 다 뽑았을 경우입니다. 따라서 3의 depth까지만 함수를 실행하고 재귀를 멈추면 됩니다.

2. 시행할 동작은 남은 카드들 중 한개를 뽑는 것입니다. 카드 배열들을 for문으로 순회하면서 각 자리에 하나씩 넣어주면 됩니다.

3. 필요한 데이터는 다음 세가지입니다. depth, 남은 카드들의 정보를 담은 배열, 뽑은 카드들의 배열

위 정보를 바탕으로 처음 소개한 재귀 함수와 동일한 구성으로 코드를 구현해보면 다음과 같습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

const cards = [1, 2, 3, 4, 5];

// 순열
const answer = [];
const permutation = (depth, leftCards, arr) => {
  // 종료 조건
  if (depth > 3) {
    answer.push(arr);
    return;
  }

  // depth별 실행할 동작
  for (let i = 0; i < leftCards.length; i++) {
    const cardsArr = leftCards.filter((_, idx) => idx !== i); // 다음에 뽑을 수 있는 카드들의 배열
    permutation(depth + 1, cardsArr, [...arr, leftCards[i]]);
  }
};

permutation(1, cards, []);
console.log(answer);

▫︎ 조합

조합은 순서를 고려하지 않고 카드들을 뽑는 방법입니다. 뽑은 카드를 제외하고 다시 카드를 뽑되, 순서가 달라도 같은 카드들을 뽑으면 안되기 때문에 순회할 때 뽑은 카드 뒤쪽의 카드들만을 대상으로 합니다. 이외에는 순열과 같습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

const cards = [1, 2, 3, 4, 5];

// 조합
const answer = [];
const combination = (depth, leftCards, arr) => {
  // 종료 조건
  if (depth > 3) {
    answer.push(arr);
    return;
  }

  // depth별 실행할 함수
  if (leftCards.length === 0) return;

  for (let i = 0; i < leftCards.length; i++) {
    const cardsArr = leftCards.slice(i + 1); // 다음에 뽑을 수 있는 카드들의 배열
    combination(depth + 1, cardsArr, [...arr, leftCards[i]]);
  }
};

combination(1, cards, []);
console.log(answer);

▪︎ Depth가 유동적이라면?

위에 설명한 depth 데이터는 재귀가 몇번째까지 타고 들어가며 실행되는지를 쉽게 이해하기 위해 추가한 개념입니다. depth 개념으로 순열과 조합을 구현해보면서 재귀의 동작에 대해 기본적인 이해가 생겼다면 depth에 기반한 재귀가 아닌 함수 그 자체가 데이터를 변동하며 스스로를 호출하는 경우를 생각해보겠습니다.

위의 depth를 이용한 재귀 함수의 구현은 모든 상황에서 사용할 수는 없습니다. 예를들어 얼만큼 함수를 다시 호출할지가 정해지지 않은 문제의 경우가 그렇습니다. 위의 예시에서는 ‘5장 중 3장의 카드를 뽑는다’ 였지만, 만약 숫자가 적힌 5장의 카드 중 임의의 수의 카드를 뽑아 손안의 카드와 남은 카드를 비교하는 문제에서는 depth를 기준으로 하여 재귀 함수를 호출할 수 없습니다. 아래 문제를 살펴보겠습니다.

이 문제에서 필요한 정보는 각 부분집합의 경우들과 그와 매치되는 남은 원소들입니다. 위 카드 예시에 대입해보자면 임의의 개수의 카드를 뽑아 순서에 상관하지 않고 뽑는 경우(조합)와 같습니다. 따라서 depth가 아닌 다른 데이터들을 바탕으로 함수를 구성해야 합니다.

임의의 개수의 원소를 뽑는다는 것은 0개 ~ 모든 원소의 개수까지를 뽑아본다는 것입니다. 따라서 조합을 실행하며 선택된 원소의 이전 원소들은 제외하고 남은 원소들의 수가 0이 될 때 함수를 종료하면 될 것 같습니다. 또한 문제를 푸는데 필요한 정보인 각 부분집합, 즉 뽑은 원소들의 배열과 그에 매칭된 남은 원소들이므로 이 둘을 데이터로하여 재귀 함수를 구성하면 문제를 풀 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

const n = 6;
const arr = [1, 3, 5, 6, 7, 10];

let answer = "NO";
let arr1 = [];
let arr2 = [];

const recursive = (leftArr, picks) => {
  if (leftArr.length === 0) return;

  for (let i = 0; i < leftArr.length; i++) {
    const newArr = [...picks, leftArr[i]]; // 전체 배열에서 뽑을 수 있는 (남아있는) 카드들
    recursive(leftArr.slice(i + 1), newArr); // i번째 카드를 뽑았다면 i 이후의 카드들이 남아있게 된다.
    arr1.push(newArr);
    arr2.push(arr.filter((el) => !newArr.includes(el)));
  }
};

recursive(arr, []);

for (let i = 0; i < arr1.length; i++) {
  if (arr1[i].reduce((acc, cur) => acc + cur, 0) === arr2[i].reduce((acc, cur) => acc + cur, 0)) answer = "YES";
}
console.log(answer);

▪︎ 그리디 알고리즘

그리디 알고리즘은 미래를 고려하지 않고, 오직 현재 시점에 가장 좋은 선택을 하는 알고리즘입니다. 현재의 선택이 미래에 어떤 영향을 미칠지는 고려하지 않고, 무조건 현재 가장 빠른 선택, 가장 가치있는 선택을 내리게됩니다. 현실에서는 모든 경우를 고려하면 리소스가 너무 크고, 당장의 최적의 결과만을 쫓는다 하더라도 미래에 (최적의 결과는 아니지만) 어느 정도 보장된 결과를 내고 싶을 때 사용되는 알고리즘입니다.

그러나 코딩테스트에서 우리는 모든 케이스에 적용되는, 항상 최적의 결과가 되는 답을 찾아내야 합니다. 따라서 현재의 최적의 답이 미래의 최적의 답이 되는 상태에서만 적용할 수 있습니다.

▫︎ 그리디 알고리즘을 적용할 수 있는 경우

1. 현재의 선택이 미래의 선택에 영향을 주지 않는다. (탐욕스러운 선택 조건)
2. 부분의 최적해가 모이면 전체의 최적해가 된다.

500원, 100원, 10원 짜리 동전들을 위 그림과 같이 가지고 있다고 할 때, 동전을 가장 적게 사용하면서 2120원을 만드는 방법을 고민해봅시다.

그리디 알고리즘에 따라 동전을 선택한다면 가장 큰 액수의 동전을 선택하는 것이 현재 상황에서 가장 적은 개수로 2120원에 가까워지는 방법입니다. 이 때 (1) 지금 내가 500원을 선택한 것 때문에 미래에 100원 대신 10원을 선택해야만 경우나 10원 대신 100원을 선택해야만 하는 경우는 없습니다. 또한 (2) 각 동전을 선택하는 시점에서, 남은 액수를 넘지 않는 동전 중 가장 큰 액수의 동전을 선택하면 가장 적은 동전의 수로 2120원을 맞출 수 있습니다.

대부분의 코딩테스트 경우에서 그리디 알고리즘의 적용은 주어진 데이터를 “각 판단의 시점마다 동일한 동작으로 최적해를 찾을 수 있도록 설정”하고 “예외 조건을 찾아 처리”해주는 형태로 코드를 작성하게 됩니다. 따라서 대부분의 케이스에서 그리디 문제의 핵심은 데이터의 정렬로 볼 수 있습니다. 주어진 데이터를 정렬할 수 있는 여러 방법들을 우선적으로 고려해봅니다.

▪︎ Example of Apply 1

• https://www.acmicpc.net/problem/1931

위 문제는 겹치지 않고 진행할 수 있는 최대 회의 수를 출력하는 문제입니다. 직관적으로 볼 때 가장 많은 회의를 진행하기 위해서는 가장 빨리 끝나는 회의를 먼저 처리하면 남은 시간이 많아지기 때문에 정답에 가까울 것 같습니다.

1. 데이터 설정) 입력받은 배열 데이터들의 인덱스 1 을 기준으로 오름차순 정렬합니다. 이 때 인덱스 1의 값이 같은 경우 인덱스 0의 값이 더 작은 (빨리 시작하는) 데이터를 우선합니다.
2. 예외 조건 처리) 정렬한 데이터를 순차적으로 순회하며 카운팅하되, 아직 이전 회의가 진행중이라면 카운팅하지 않습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

const fs = require("fs");

const input = fs.readFileSync("dev/stdin").toString().trim().split("\n");
const arr = input.slice(1).map((el) => el.split(" ").map(Number));

arr.sort((a, b) => {
  if (a[1] === b[1]) return a[0] - b[0];
  else return a[1] - b[1];
});

let prev = 0;
let answer = 0;

arr.forEach(([start, end]) => {
  if (prev <= start) {
    answer++;
    prev = end;
  }
});

console.log(answer);

▪︎ Example of Apply 2

• https://www.acmicpc.net/problem/11000

이번 문제는 모든 회의가 가능하도록 하는 강의실의 개수를 출력하는 문제입니다. 현재 진행중인 강의의 개수를 추적하고, 지금까지 동시에 진행된 강의가 가장 많을 때마다 정답을 업데이트해주면 풀 수 있을 것 같습니다. 강의의 개수를 추적하는 방법은 강의가 시작되고 끝나는 시간에 값을 부여하여 시간마다 그 값을 더해주면 됩니다. 그렇게 타임 테이블을 만들고 오름차순 정렬하여 데이터를 순회하면 정답을 도출할 수 있습니다.

타임테이블을 배열로하여 인덱스를 시간으로 추상화하는 방법은 Si, Ti의 최대값이 10^9 이므로 메모리 초과가 뜰 것 같습니다. 따라서 입력받은 데이터들에 저장된 시간들을 O(1)의 시간 복잡도로 조작가능한 Map 함수에서 key : value 형태로 관리하겠습니다. 각 시간에 시작하는 회의가 있을 때 +1, 끝나는 회의가 있을 때 -1을 하면서 시간단위로 강의실 개수를 추적합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

const fs = require("fs");

const input = fs.readFileSync("dev/stdin").toString().trim().split("\n");
const arr = input.slice(1).map((el) => el.split(" ").map(Number));
const timeTable = new Map();

// 타임테이블 생성
for (let i = 0; i < arr.length; i++) {
  timeTable.set(arr[i][0], timeTable.get(arr[i][0]) ? timeTable.get(arr[i][0]) + 1 : 1);
  timeTable.set(arr[i][1], timeTable.get(arr[i][1]) ? timeTable.get(arr[i][1]) - 1 : -1);
}

// 타임테이블 정렬
const answerArr = Array.from(timeTable).sort((a, b) => a[0] - b[0]);
let answer = 0;
let lectures = 0;

// 타임테이블 순회
answerArr.forEach((el) => {
  lectures += el[1];
  if (lectures > answer) answer = lectures;
});

console.log(answer);