2022년에 React 컴포넌트 라이브러리 만들기

@solved-ac/ui-react를 만들기 위한 여정

TL;DR:

  • create-react-library는 쓰지 마세요.
  • peerDependencies에 추가하는 라이브러리는 devDependencies에도 추가하세요.
  • styled-components 기반 라이브러리에서 SSR 이슈가 발생한다면 이 글을 참고하세요.

저는 다음 달이면 3년차가 되는 프론트엔드 개발자입니다. 하나 고백하자면, 안타깝게도 저에게는 프론트엔드 사수가 있었던 적이 없습니다. 여태까지 독학한 React 지식으로 얼렁뚱땅 일해왔다고 할 수 있습니다. 여태까지는 잘 먹혔습니다.

근데 이제 파트장입니다. 야 이거 큰일 났다. 면접도 내가 봐야 되고 신규입사자 교육도 내가 해야 되는데 나는 아는 게 하나도 없네…

그래서 인터넷의 힘을 빌리기로 합니다.

작성했던 코드를 잘 짰던 못 짰던 일단 올리고 보는 겁니다. 이렇게 하면 사수 분들이 마구마구 생기겠지? 회사 코드를 올릴 수는 없고, 마침 개인적으로 컴포넌트 재사용에 대한 니즈가 있던 solved.ac 코드를 정리해서 올려보기로 합니다.

첫 삽 뜨기

모르는 게 있을 때 취해야 하는 참된 개발자의 자세, 바로 구글 켜기입니다.

구글에 creating a react component library를 검색한 결과

1시간 정도 구글링해본 결과 아래 옵션들로 정리할 수 있었습니다.

Bit은 좋아 보이지만 나중에 뭔가 하려면 돈을 내야 될 것 같은 분위기를 느껴서 제외했습니다. 그냥 rollup을 직접 쓰는 것과 create-react-library의 도움을 받는 것 중에서 고민하다가 create-react-library를 골랐습니다. 간단해 보여서였습니다.

프로젝트를 만들고 기존에 쓰던 테마 정의와 함께 Button 컴포넌트를 옮겨왔습니다.

어 그런데 뭔가 이상합니다.

이 왜 any?

분명히 테마도 타입 정의가 잘 되어 있고 styled-components도 잘 임포트되어 있는데 테마 속성들이 전부 any로 뜹니다. 심지어는 styled component prop도 any가 뜹니다. 타입 추론이 없는데 어떻게 개발을 합니까? 이건 천재지변입니다.

styled-componentspeerDependencies에만 있고 devDependencies에는 없었음을 확인하고 고치는 데는 의외로 많은 시간이 걸렸습니다.

dependencies, devDependencies, peerDependencies

TL;DR: 라이브러리를 개발할 때 peerDependencies에 뭔가를 추가하려면 devDependencies에도 똑같은 패키지를 추가해야 합니다.

너무 기니까 dependencies를 줄여서 deps라고 부르도록 합시다.

depsdevDeps는 패키지를 빌드했을 때 프로덕션 번들에 포함되는지 아닌지의 차이가 있습니다. devDeps에는 주로 @types/*라던가 Prettier, Babel 플러그인과 같이 개발 과정이나 빌드 등을 도와주는 패키지들이 들어갑니다. 이미 완성된 코드에다 ESLint를 돌릴 이유는 없으니까요.

하지만 depsdevDeps는 사실 일반적인 프론트엔드 프로젝트에서는 별 상관이 없습니다. 이는 webpack의 번들 방식 때문인데, webpack은 entryPoint부터 시작해서 import들을 따라가면서 패키지들을 필요에 따라 넣기 때문입니다. create-react-app@types/* 같은 의존 패키지들을 전부 devDeps가 아니라 deps에 때려박아도 별 일 없는 이유이기도 합니다. 개인적으로는 싫지만…

peerDependencies

라이브러리를 만들면 아무도 의존하지 않는 패키지 – 예를 들면 프론트엔드 앱 – 를 만들 때는 볼 수 없었던 peerDeps와 마주하게 됩니다. peerDeps에 의존성을 추가하면 내 패키지에서 의존성을 관리하는 대신 내 패키지를 의존하는 패키지에서 의존성을 대신 관리하게 됩니다.

말이 조금 헷갈리는데, 예를 들어 내 프로젝트가 라이브러리 A, B, C를 쓰는데, 세 라이브러리 모두가 D라는 패키지에 의존한다고 합시다.

  • 세 라이브러리에서 D를 deps로 두는 경우에는 node_modules에 A > D, B > D, C > D 모두가 들어가게 됩니다.
  • D를 peerDeps로 두는 경우에는 node_modules에 A, B, C, D가 따로따로 들어가고, 내 프로젝트 단에서 A, B, C 각각이 내 프로젝트에서 직접 가져온 D에 의존할 수 있도록 해 줍니다.

요약하면, peerDeps는 의존성 트리 최적화를 위해 내 패키지를 쓸 패키지들에게 ‘이거 대신 설치해 주세요’라고 설명하는 것과 같습니다. 이건 ‘내 패키지 자체에서는 이 의존성을 굳이 쓰지 않겠어요’라는 말과 같은 말입니다. 다 좋은데 그러면 내가 내 패키지는 어떻게 개발하죠?

빌드된 모습

결과적으로는 peerDepsdevDeps 모두에 의존성이 들어가야 합니다. 이렇게 하면 빌드된 index.js에서 peerDepsrequire를 사용하도록 바뀌고 나머지는 잘 번들됩니다. 이 require는 로컬 환경에서는 devDeps에 의해 설치된 패키지를, 피의존 환경에서는 이 패키지의 peerDeps에 의해 설치된 패키지를 활용할 것입니다.

알고 나면 어렵지 않은 이유지만, 라이브러리를 만드는 입장에서 peerDeps를 설명해 둔 리소스가 현저히 적어서 알기까지 너무 오래 걸렸습니다. 이건 험난한 여정의 시작일 뿐이라는 걸 당시의 저는 몰랐습니다.

인터넷에 올리기 부끄럽지 않은 코드 짜기

const ButtonContainer = styled.button<ButtonContainerProps>`
  display: inline-block;
  vertical-align: middle;
  text-align: center;
  background: ${({ backgroundColor }) => backgroundColor}; // XXX
  /* ... */
`

이건 안 좋은 코드의 예입니다. solved.ac에서는 버튼에 색상을 그렇게 많이 집어넣거나 색상에 애니메이션을 줄 일이 없었기 때문에 기존에는 이렇게 구현했지만, styled-components는 모든 경우의 수마다 CSS 클래스를 하나씩 만들 거고 자칫 다이나믹할 수 있는 값을 이런 식으로 구현하면 퍼포먼스 이슈가 생길 것은 안 봐도 비디오, 웰 노운 팩트입니다.

따라서 CSS 변수를 사용하기로 합니다. 스타일드 컴포넌트 안에서는 색상 등을 var(--solvedac-button-background-color) 등으로 정의하고, 컴포넌트에 인라인 스타일로 --solvedac-button-background-color: #17ce3a와 같은 식으로 넣어주면 됩니다. 이걸 잘 쓰기 위해 타입스크립트의 도움을 받고 싶습니다. 예를 들어 아래와 같은 코드를 작성하면…

const [vars, v] = cssVariables(
  [
    'backgroundColor',
    'hoverBackgroundColor',
    'textColor',
    'hoverTextColor',
    'hoverShadow',
    'activeShadow',
  ],
  'button'
)

…스타일드 컴포넌트에서는 이렇게 가져다 쓰고…

const ButtonContainer = styled.button<ButtonContainerProps>`
  display: inline-block;
  vertical-align: middle;
  text-align: center;
  background: ${v.backgroundColor}; // Does not trigger class name generation which is good
  /* ... */
`

…인라인 스타일은 이렇게 넣을 수 있게 말이죠.

<ButtonContainer
  disabled={disabled}
  circle={circle}
  fullWidth={fullWidth}
  style={{
    [vars.backgroundColor]: computedBackgroundColor,
    [vars.hoverBackgroundColor]: computedHoverColor,
    [vars.textColor]:
      computedBackgroundColor &&
      readableColor(computedBackgroundColor, solvedTheme),
    /* ... */
    ...style,
  }}
  {...rest}
>
  {children}
</ButtonContainer>

이게 전부 타입 추론이 되게 하기 위해서 열심히 타입스크립트 매드무비를 찍습니다. readonly를 사용하면 string 배열을 tuple 취급하게 할 수 있습니다. 여기서 [...T]는 TS 4.0 기능입니다.

export const cssVariables = <T extends Array<string>>(
  names: readonly [...T],
  prefix: string
): [
  { [key in T[number]]: `--solvedac-${string}` },
  { [key in T[number]]: `var(--solvedac-${string})` }
] => {
  const vars = Object.fromEntries(
    names.map((name) => [
      name,
      `--solvedac-${prefix}-${name
        .replace(/[A-Z]/g, (m) => `-${m.toLowerCase()}`)
        .replace(/^-/, '')}`,
    ])
  ) as { [key in T[number]]: `--solvedac-${string}` }

  const v = Object.fromEntries(
    Object.entries(vars).map(([k, v]) => [k, `var(${v})`])
  ) as { [key in T[number]]: `var(--solvedac-${string})` }

  return [vars, v]
}

이렇게 하면 에디터가 타입 추론을 잘 해 줍니다. 그런데 갑자기 빌드가 되지 않습니다. 이번엔 왜일까요?

CSSProperties와 다시 만나는 declaration merging

리액트는 기본적으로 인라인 스타일에 --solvedac-button-background-color 같은 걸 허용하지 않습니다. CSSProperties의 키가 아니기 때문입니다. 리액트의 index.d.ts에는 이런 주석이 달려 있습니다.

export interface CSSProperties extends CSS.Properties<string | number> {
    /**
     * The index signature was removed to enable closed typing for style
     * using CSSType. You're able to use type assertion or module augmentation
     * to add properties or an index signature of your own.
     *
     * For examples and more information, visit:
     * https://github.com/frenic/csstype#what-should-i-do-when-i-get-type-errors
     */
}

직접 인덱스 시그니쳐를 만들고 싶으면 type assert를 하거나 module augmentation을 하라고 합니다.

Type assert는 웬만해서는 쓰기 싫기 때문에 declaration merging을 했습니다. 예전에 테마 타입 정의하는 데 고생한 적이 있어서 비교적 쉽게 해결했습니다. 이렇게 하면 됩니다.

type CustomProp = { [key in `--${string}`]: string }
declare module 'react' {
  // eslint-disable-next-line @typescript-eslint/no-empty-interface
  export interface CSSProperties extends CustomProp {}
}

오래된 react-scripts, 관리가 중단된 microbundle-crl

리액트 프로젝트에서 타입스크립트 관련해서 뭔가 안 된다 싶으면 이 친구입니다. react-scripts는 자기만의 webpack 설정 등을 쓰기로 유명합니다.

create-react-libraryreact-scripts@3.4.1을 설치해 줍니다. TS 4.0을 지원하지 않는 버전입니다. yarn add react-scripts@latest -D로 해결해 줍니다.

이외에도 microbundle-crl은 예전 버전의 Babel을 사용하고 있으며, 2년 전 microbundle 소스의 포크입니다. Unfork 해 줍니다.

Zero configuration을 표방하는 패키지를 종종 보게 되는데, 일반적인 경우에는 좋지만 일반적이지 않은 경우에는 꽤 골치아파지게 됩니다. 여담으로 react-scripts를 쓰면서 webpack 구성을 바꿔야 하는 경우가 있다면, eject하는 대신 react-app-rewired를 사용해 보시기 바랍니다.

이제 모든 게 다 잘 됩니다. 슬슬 solved.ac에 적용해 볼까요?

이상해요

뭔가 이상한 솔브드

사이트에 새 컴포넌트들을 적용하고 띄워 보니 패딩이 사라져 있습니다. 그럴 리가 없는데… 링크를 타고 다른 페이지들을 로드해 보면 정상적으로 보입니다. Prop `className` did not match와 같은 증상이 또 나타났습니다! 이번엔 테마 정의도 declaration merging으로 해 줬고 babel-plugin-styled-components도 잘 설정해 줬는데 대체 왜?

SSR의 악몽

생성되어 있는 componentId

dist/index.js를 확인해 봤을 때 컴포넌트 ID는 빌드 시점에 생성되는 것을 알 수 있습니다. Babel 플러그인이 잘 동작했다는 뜻입니다.

그러면 의심이 가는 부분은 solved.ac 프론트엔드 프로젝트에서 ServerStyleSheetcollectStyles 해 주는 부분입니다. 이 방향으로 검색해 봤더니 FAQ가 하나 나옵니다. yarn link에 대한 내용이지만 이 라이브러리에도 적용할 수 있을 것 같습니다.

styled-components는 싱글톤이고, 각자의 스코프에서 렌더할 컴포넌트들을 전부 관리합니다. 따라서 solved.ac 프론트엔드 프로젝트와 방금 만든 UI 라이브러리에 있는 styled-components는 다른 styled-components라는 뜻입니다. 이걸 강제로 같게 만들어서 한 쪽의 styled-components가 프론트엔드 프로젝트와 UI 라이브러리 모두의 컴포넌트를 관리하게 해 줘야 합니다.

모든 require('styled-components')가 특정 경로의 모듈로 resolve 되도록 모듈 alias를 해 주면 되는데 Next.js + Typescript 환경에서는 비교적 간단하게 해결할 수 있었습니다.

{
  "compilerOptions": {
    "paths": {
      "styled-components": ["./node_modules/styled-components"]
    }
  }
}

이렇게 해 주면 SSR도 잘 적용되는 것을 확인할 수 있습니다.

Update: @solved-ac/ui-react는 이제 emotion을 사용하고 있습니다. emotion은 일부 셀렉터를 제외하고는 SSR 환경에서 별도의 설정 없이 사용할 수 있습니다. (2022/06/20)

사수 무제한 제공 거짓말 사건

컴포넌트를 라이브러리화하고 정상적으로 렌더하기 위한 과정들이었습니다. 모르면 맞아야 하는 도메인 지식들이 너무 많은데, 컴포넌트 라이브러리를 만드는 사람이 많지 않은지 리소스도 상당히 적었고 그로 인해 너무 고생을 많이 했습니다. 나는 있는 코드를 그대로 올리면 누군가 코드 리뷰를 해 주지 않을까 싶었던 것뿐인데!

그래도 이제 잘 동작하니까 계속 여러 컴포넌트들을 정리해서 올려봐야겠어요. 가뜩이나 리소스 없는 분야인 것 같은데 이 글이라도 여러분의 쓸데없는 삽질 예방에 도움이 되었으면 좋겠습니다.

조율자의 손길: 한별포스 이벤트를 돌아보며

solved.ac를 운영하면서 다양한 채널에서 사이트에 대한 의견들을 모으는 편입니다. 특히 그 중에서도 트위터 맞팔 분들께서는 저에게 창의적인 기능 아이디어들을 추천해 주고 계신데요, 몇 개만 봅시다.

솔브드 테라버닝
솔브드 1주년 코인샵
솔브드 스타포스

그래서 직접 만들어 봤습니다.

한별포스

2022년 4월 1일 정오부터 만우절 대회인 진짜 최종 구데기컵 2 2가 끝날 때까지 프로필 닉네임 위에 별을 25개 띄워봤습니다. 이게 대략 무슨 뜻인지 아시는 메이플 유저 분들께서는 대체 이게 왜 여깄지 하면서 당황하셨을 것 같습니다. 모르시더라도 마우스를 올리면 밑줄이 떠서 되게 클릭하고 싶게 만들었기 때문에 한번쯤은 클릭해보셨을 것 같아요. 이걸 클릭하면 한별포스 이벤트 페이지로 갑니다.

한별이

‘스타포스’라는 이름을 그대로 쓸 수는 없고…, solved.ac 길라잡이에 등장할 캐릭터 ‘한별이’의 이름을 빌려왔습니다. 귀엽지 않나요? 카카오 이모티콘으로 쓸 수 있어요.

여하튼 한별포스는 메이플스토리의 스타포스를 거의 그대로 가져온 이벤트였습니다. 프로필을 강화할 수 있습니다. 강화하면 프로필 위에 뜨는 별의 갯수가 변하는 것 이외엔 아무 일도 일어나지 않습니다.

스타포스?

스타포스 강화가 어떻게 돌아가는지를 요약해보면 이렇습니다.

  • 강화에 성공하면 별이 하나 늘어납니다.
  • 실패에는 세 가지 경우가 있습니다.
    • 별 개수가 유지됩니다. 10성까지에서 강화 시도에 실패한 경우 무조건 유지되며, 15성과 20성에서 실패한 경우에도 파괴되지 않았다면 무조건 유지됩니다.
    • 별이 하나 줄어듭니다. 10성까지 그리고 15성과 20성에서 강화 시도에 실패하는 경우에는 일어나지 않습니다.
    • 장비가 파괴됩니다. 12성 이상에서 강화를 시도하는 경우 드문 확률로 일어납니다. 이후 같은 장비를 준비해 장비를 복구할 수 있으며, 12성부터 다시 시작합니다.
  • ‘스타캐치’라는 미니게임을 통해 성공 확률을 1.05배로 올릴 수 있습니다.
  • 확률은 여기에서 참고할 수 있습니다.

스타캐치를 제외한 모든 요소를 그대로 가져와봤습니다. 스타캐치를 가져오지 않은 이유는 스타캐치에 성공했는지 아닌지를 서버에서 검증하기가 어렵기 때문인데, 대신 한별이가 그려진 배경을 프로필 배경으로 설정하면 같은 효과의 ‘한별캐치’를 적용해 줍니다.

이벤트 가격과 보상 설정

30일동안 매일 1문제씩을 푼다면 적당히 하루 75조각, 한 달 2,250조각을 얻는다고 봅니다(10일동안 매일 5문제 + 5기여를 해도 이 정도를 벌 수 있습니다). 그래서 일단 이런 유저가 22성까지 달성할 수 있는 것을 목표로 비용을 설정합니다.

이렇게 하려면 1번 강화 당 비용을 현저히 낮게 잡아야 합니다. 프로필 파괴 시 복구 비용도 없앴습니다. 기댓값을 보면서 강화 비용을 미세하게 조정했고, 정확한 비용은 아래와 같습니다.

  • 10성 이하를 목표로 강화: 별조각 1개
  • 15성 이하를 목표로 강화: 별조각 2개
  • 20성 이하를 목표로 강화: 별조각 3개
  • 25성 이하를 목표로 강화: 별조각 4개

이 때의 기댓값은 이렇습니다. 이 블로그에서 기댓값 계산 매드무비를 찍고 싶었지만 이미 다른 분께서 작성해 주신 다른 매드무비가 있어서 생략합니다. 요약하면 이렇습니다. (한별캐치 없음 / 한별캐치 있음)

  • 0성 → 10성: 18조각 / 17조각
  • 0성 → 15성: 138조각 / 117조각
  • 0성 → 17성: 215조각 / 181조각
  • 0성 → 20성: 1,143조각 / 851조각
  • 0성 → 21성: 1,417조각 / 1,043조각
  • 0성 → 22성: 2,330조각 / 1,654조각
  • 0성 → 23성: 36,569조각 / 23,955조각

주의해야 할 점은 스타포스 기댓값은 편차가 굉장히 크다는 점이고, 여기는 알고리즘 문제해결을 공부하는 곳이고, 참가자들이 이벤트 시작 후 1시간 안으로 기댓값 테이블을 전부 계산해버릴 것이라는 점입니다. 메이플스토리 같은 경우에는 상위 95% 유저는 상위 50% 유저보다 2.5배 많은 재화를 소모해야 한다는 시뮬레이션이 있을 정도입니다. 만우절 이벤트인데 너무 스트레스를 받지는 않았으면 해서, 많은 유저들이 얻도록 하려는 22성 보상까지에 대해서는 기댓값의 2배에서 3배쯤이 되도록 설정했습니다.

1등 보상을 따로 둔 것은 나름의 실험 같은 거였는데, 기댓값에 따르면 21성까지는 성공 확률이 최소 30%여서 할 만 하고, 잔고가 3조각이어도 강화 버튼을 누르는 게 이득입니다. 하지만 22성에서 성공 확률 3%의 강화 버튼을 누르는 건 일반적으로 손해입니다. 1등이 22성으로 모두가 행복하게 별조각을 5,000개씩 더 받고 끝날지, 아니면 남들이 별조각 5,000개를 더 받는 걸 막기 위해 22성에서 버튼을 누를지 궁금했습니다.

23명의 23성

결과적으로 solvedac 계정을 제외하고 23성을 달성한 유저는 22명이었네요. 23성에서 강화 버튼을 눌러서 터진 분들도 계십니다. 무섭습니다…. 개인적으로는 23성이 나온다면 24성이 한 명 이하로 나온다고 예상했는데 24성은 나오지 않았네요.

얼마나 썼을까

CSV 덤프

통계를 따로 계산하지 않아서 로그를 CSV 덤프로 까봤습니다. 3,519명의 유저가 총 1,636,385번 강화를 시도했고, 4,762,579개의 별조각을 소모했습니다.

각 단계별 강화 시도 횟수는 이렇습니다.

n성에서 버튼을 누른 횟수
  • 0성에서는 3,677번의 강화 시도가 있었습니다. $\frac{3\,519}{3\,677}\approx 0.957$이므로, 한별캐치를 고려하면 대략 맞습니다.
  • 9성 이하에서는 모든 단계에서 7,000번 이하의 강화 시도가 있었고, 10성에서는 149,682번의 강화 시도가 있었습니다. 9성 이하로는 돌아올 수 없기 때문에 강화 시도가 적습니다.
  • 15성에서의 강화 시도가 가장 많습니다(340,776번). 15성과 20성 완충 구간의 경우 그래프가 폭 튀어나와 있습니다.
  • 20성에서의 강화 시도는 24,071번, 21성에서는 9,927번입니다.
  • 22성에서의 강화 시도는 2,040번이며 이 중 23성으로의 강화를 성공한 경우는 70번이었습니다.
  • 23성에서의 강화 시도는 37번이며 이 중 24성으로의 강화를 성공한 경우는 없었습니다.

이 이벤트에서 별조각을 가장 많이 쓰신 분은 별조각을 28,396개 소모하셨으며, 7,882번의 강화 시도를 했습니다. 이 분께서는 22성에서 강화 버튼을 16번 누르셨지만 23성에 도달하지 못하시고 17성으로 마감하셨습니다.

뼈아픈 기록

최종 22성 유저 중 가장 적은 별조각을 소모한 경우 겨우 64개를, 가장 많은 별조각을 소모한 경우 무려 21,364개를 소모하셨습니다. 물론 가장 많은 별조각을 소모한 경우는 22성에서 프로필이 파괴된 후 다시 돌아온 경우이긴 합니다. 17성의 경우는 최소 44개, 최대 28,396개였습니다.

마지막으로 22성에 주차한 저는 2,264개의 별조각을 소모했습니다. 기댓값을 약간 상회합니다.

이모저모

솔브드가 메이플 인벤에 소개되는 신기한 경험을 했습니다. 댓글에 22성 인증이 꽤 올라오던데 알고리즘 문제 푸시는 분들과 메이플스토리 유저 간의 교집합이 어느 정도 되는 것 같습니다. 저도 그렇구요.

저희 학회에서도 문제는 안 풀고 한별포스하는 데 심취해 계셨다고 하고 들리는 소문으로는 SSAFY에서도 한별포스 강화전을 했다고 하네요.

백준님께서는 매크로를 짜서 강화를 시도하셨고…, 별조각을 15,630개 소모해 소모량 7위에 랭크되셨습니다. 안타까워요.

주절주절

작년엔 대규모 리팩터링을 하느라 만우절 이벤트를 못 했는데 올해는 뭔가 보여드릴 수 있었습니다. 재밌게 즐겨 주셨나요? 스타포스 추가해 달라는 걸 진짜 들어줄 줄은 몰랐나요? 솔브드는 알고리즘 문제해결을 재밌게 배울 수 있게 하자는 사명 아래 어떻게 하면 사이트를 좀 더 재밌게 만들 수 있을까 고민하다 보니 게임을 기획하듯이 기획하고 있습니다. 재밌게 즐겨주셨다면 다행입니다!

그치만 이번엔 너무 게임밖에 없었을지도 모르겠네요. 문제를 푸는 것과 연계해서 별조각을 더 다양한 방법으로 주고, 별조각을 사용할 만한 곳들이 많아졌으면 좋겠다는 생각을 하게 만들었던 이벤트였습니다. 앞으로 이런 방향으로 컨텐츠 업데이트를 해보고 싶어요.

이번 이벤트 참가해 주신 많은 분들께 정말 감사드립니다!

왜 AC RATING인가요?

solved.ac의 근간이 되는 두 가지 중요한 기능은 다음과 같습니다.

  • Baekjoon Online Judge 문제들에 난이도와 태그를 매겨서, BOJ에 있는 방대한 문제들 중 어떤 문제를 풀면 좋을지 훨씬 쉽게 고를 수 있는 수단을 제공합니다.
  • 푼 문제 수가 아닌, 푼 문제들의 난이도의 구성을 바탕으로 한 실력 지표와 이를 기반으로 한 순위 등을 제공해, 알고리즘 문제해결 학습자들에게 더 흥미로운 문제를 해결할 동기를 부여합니다.

실력 지표의 경우, 기존에는 문제를 해결할 때마다 경험치가 쌓이고, 푼 문제들의 경험치의 총 합을 기준으로 실력 지표인 티어를 결정했습니다. 이 방식은 solved.ac가 처음 만들어진 2019년 6월 6일부터 2년 가까히 이어져왔습니다만, 오는 1일부터는 새로운 실력 지표인 AC RATING으로 티어를 결정하게 됩니다. AC RATING은 아래의 합으로 결정되며, 이론적으로 3,450 이하의 정수 값입니다.

  • 푼 문제들을 난이도 순으로 내림차순 정렬했을 때, 상위 100개 문제의 난이도 값의 합 (최대 3,000)
  • CLASS에 따른 보너스 (최대 250)
  • 푼 문제 수에 따른 보너스 (최대 175)
  • 기여 수에 따른 보너스 (최대 25)

아니 잘 쓰던 경험치 냅두고 왜 이제 와서 이상한 조건의 레이팅을?이라고 생각하실까봐 레이팅제가 어떤 과정을 거쳐 탄생했는지에 대해 소개합니다.

경험치제의 문제점

기존의 경험치제를 간략하게 요약하면 이렇습니다.

  • 브론즈 5 문제를 해결하면 320점을 주도록 합니다. 어떤 문제보다 1티어 높은 문제의 경우 약 1.5배의 경험치를 주도록 합니다.
  • 브론즈 4 티어가 되려면, 브론즈 5 티어를 달성한 이후 브론즈 4 문제를 20문제 더 해결해야 하도록 합니다. 티어 $x$가 되려면, 티어 $x-1$을 달성한 후 난이도 $x$의 문제를 $n_x$개 더 해결해야 하도록 합니다.
  • 기여 한 건마다 경험치 10,000을 줍니다.

이는 여러분께서 자신의 티어와 비슷한 난이도의 문제를 해결할 것으로 기대하고 기획한 것이었습니다. 하지만 여러 부작용이 있었습니다.

단적인 예로 아무것도 해결하지 않은 사람이 루비 1 문제 하나를 풀면 그 한 문제 덕분에 바로 다이아몬드 5가 됩니다. 알고리즘 실력을 키우고 싶은지 아닌지는 제쳐두고, 티어를 올리고 싶다면 힘들게 브론즈 실버를 캐면서 차근차근 올라갈 필요 없이 어려운 문제 하나만 풀면 되는 것입니다.

보통 그런 ‘어려운 문제’는 혼자 힘으로 해결하기 상당히 어렵기 때문에 인터넷을 참고해 해결하는 경우가 많고, 해결하는 순간 경험치 구성의 대부분을 차지해 버리게 됩니다. 이제 본인 실력의 문제를 해결하는 것으로는 경험치가 1%도 오르지 않습니다.

루비 V 한 문제가 경험치의 93.4%를 차지하는 극단적인 사례.

위 유저가 해결한 문제 중 가장 어려운 문제는 루비 V이고, 그 다음은 골드 II 한 문제, 골드 III 두 문제, 골드 V 열한 문제입니다.

기존 경험치제에서 이 유저의 티어는 플래티넘 V인데, 플래티넘 V 유저가 골드 V 한 문제를 풀어서 얻을 수 있는 경험치량은 0.411%입니다.

루비 V 한 문제를 풀지 않았다면? 이 유저의 티어는 실버 I이었을 것이며, 이 경우 골드 V 한 문제는 무려 6.02%의 경험치를 줍니다. 그러면 현재 루비 V 문제 하나를 해결한 상황에서 골드 V 문제를 푸는 게 과연 매력이 있을까요? 그렇다고 플래티넘 문제들을 푸는데 많은 시간을 소비할까요?

대부분의 경우, 의욕을 잃거나 새로운 어려운 문제를 찾아 떠나게 됩니다. 이런 점을 노린 코드 카피 어뷰징이 solved.ac가 등장한 이후 상당히 빈번하게 발생했습니다. solved.ac는 알고리즘 문제해결 학습자들의 학습 동기 증진을 목적으로 하는 사이트인데, 기존 경험치제가 학습자를 다소 좋지 않은 학습 방향으로 유도한다는 생각이 들었습니다.

또한 한 문제를 풀면 경험치를 얼마나 주는지, 다음 티어로 올라가기 위해서는 총 경험치가 얼마쯤 되어야 하는지 혹은 어떤 문제를 얼마나 해결해야 하는지 알기가 어려웠다는 사소한 문제도 있었습니다. 더구나 현재 1위의 총 경험치의 자릿수는 11자리나 되어 상당히 비직관적입니다.

레이팅제의 목표

기존의 제도에는 이런 문제점들이 있었고, 이를 어느 정도 해결하기 위해 많은 고민 끝에 새로 레이팅 제도를 만들었습니다. 새 레이팅 제도의 목표는 아래와 같았습니다.

  • 실력을 정확히 측정하는 것과 동기를 불러일으키는 것 사이 어딘가에서 적당히 줄다리기합니다. 둘 다 완벽하게 되면 더 좋고요.
  • 낮은 티어의 유저들이 새롭고 다양한 알고리즘 분야를 접하는 것을 장려합니다.
  • 푼 문제가 현저히 많다고 레이팅이 현저히 높아지거나, 어려운 문제 하나가 레이팅의 대부분을 차지하게 되는 현상을 최대한 완화합니다.
  • 직관적인 값으로 보여지도록 합니다.
  • 서버가 빠르게 계산할 수 있도록 합니다.

실력 측정 vs 동기 부여

기존의 경험치제나, 새로 도입하게 되는 레이팅제나 사용자의 정확한 실력을 반영해 주기 원하시는 분들이 많았습니다. 결론부터 말하자면 정확한 실력을 가늠하는 건 불가능했기 때문에, 레이팅과 실력과의 상관관계를 높이는 것은 목표로 하지 않았고, 기존과 같이 약한 상관관계를 보이게 하는 것으로 만족했습니다.

정확한 실력을 가늠하는 것이 불가능한 이유는 BOJ가 OJ이기 때문입니다. OJ에 등록된 문제들은 이미 어딘가에서 출제되었던 문제들이고, 많은 경우 쉽게 해설을 찾아볼 수 있습니다. 반면 대회 플랫폼의 경우 매번 새로운 문제들을 주고 틀린 횟수와 해결 시간을 바탕으로 실력을 계산합니다.

따라서 OJ 쪽은 대회 플랫폼에 비해 유저의 실력을 계산하기 위해 사용할 수 있는 정보와 그 정보의 신뢰도 모두가 현저히 떨어집니다. 심지어 대회 플랫폼의 레이팅도 정확한 실력을 반영한다고는 할 수 없습니다. 대회는 실력을 샘플링하는 것에 지나지 않기 때문입니다. 수능 모의고사에서 1등급을 받은 학생이 수능에서도 같은 등급을 받을 것이라는 보장이 없듯이요…

이런 이유로 레이팅과 실력과의 대략적인 상관관계는 기존 수준으로 유지하되 새 레이팅 제도가 목표로 하는 동기 부여적 측면을 더 부각시킬 수 있는 쪽으로 기획 방향을 정했습니다.

레이팅의 뼈대

무작정 높은 난이도의 문제를 푸려고 하게 되는 이유는, 높은 난이도의 문제가 푸는 데 오랜 시간이 걸림에도 불구하고 티어 상승이라는 측면에서 상당히 매력적으로 보이기 때문입니다.

기존 경험치제에서 루비 I 문제 하나를 푸는 것은 브론즈 V 문제 약 30만개를 푸는 것과 비슷한 경험치를 줬고, 이는 문제해결에 쏟는 시간 대비 엄청난 가성비를 보여줍니다. 모든 티어에서 상당히 매력적으로 보이는 게 당연합니다. 따라서 매력을 너프하기 위해서는, 일단 문제 해결로 얻는 경험치가 난이도에 따라 기하급수적으로 올라가는 식이 아니어야 합니다.

하지만 그렇게 되면 난이도에 관계없이 문제를 많이 해결한 사람이 무조건 유리해집니다. 레이팅이 적용된 다른 OJ들이나 비슷한 구조의 게임들이 이를 막는 방법은 크게 두 가지가 있습니다.

  • 반영되는 문제 수에 제한을 둡니다. $n$문제를 반영한다면, 어떤 사용자가 난이도 $x$까지의 문제를 해결할 수 있을 때 이론적으로 받을 수 있는 최대치는 $nx$입니다.
  • 모든 문제를 반영하되 적당한 상수 $0<r<1$을 정해서 첫 문제에는 $1$을, 두 번째 문제에는 $r$을, 세 번째 문제에는 $r^2$를 곱해나가는 식으로 합니다. 어떤 사용자가 난이도 $x$까지의 문제를 해결할 수 있을 때 이론적으로 받을 수 있는 최대치는 $\frac{x}{1-r}$입니다.

두 방법은 사실상 같습니다만 첫 번째 방법은 서버가 계산하기 쉬운 대신 특정 난이도 이상의 문제를 풀지 않으면 아무리 문제를 풀어도 레이팅이 아예 오르지 않는다는 단점이 있고, 두 번째 방법은 문제를 풀면 레이팅이 계속 오르겠다는 믿음을 주는 대신(실제로는 1점 올리기는 상당히 어렵습니다) 서버가 레이팅을 계산하는 코스트가 조금 더 든다는 단점이 있습니다.

그래서 문제를 풀면 레이팅이 오르겠다는 믿음은 다른 방법으로 주기로 하고 첫 번째 방법을 택했습니다. 100문제를 해결하면 레이팅이 수렴했다고 보고, 푼 문제들을 난이도 순으로 정렬해 상위 100개 문제의 난이도 값의 단순합을 레이팅의 가장 많은 부분을 차지하도록 했습니다. 공교롭게도 solved.ac의 문제 난이도는 0부터 30까지라서 이렇게 하면 총 3,000점이 되고, 다른 대회 플랫폼들의 4자리수 레이팅과 비슷한 값이 되어 직관적이게 됩니다.

상위 100문제의 난이도 합으로 결정

여기에 문제 해결 수에 따른 보너스 레이팅을 $\left\lfloor 175\left( 1-0.995^n \right) \right\rceil$만큼 주어 약 1,200문제를 해결할 때까지 어느 문제나 해결해도 레이팅이 오른다는 믿음을 주도록 유도했습니다. 다만 실제로 믿으실지는 모르겠습니다. 믿어 주세요.

기존 기획은 이 100문제를 (5년간 출제된 OI/ICPC 문제) 50개와 나머지 문제 50개를 반영하려 했으나, 그렇게 할 근거가 부족하여 100문제를 합하는 것으로 선회했습니다.

새롭고 다양한 알고리즘 문제해결 장려

이미지
CLASS

solved.ac에는 티어 외에도 CLASS라는 실력 지표가 있습니다. 실력대별로 미리 정해진 48문제 중 20문제 이상을 해결하면 얻을 수 있습니다.

CLASS 문제들은 수준에 따라 교육적인 목적을 갖고 정해져 있습니다. 예를 들어,

  • CLASS 1는 프로그래밍 혹은 알고리즘 문제해결 입문자가 풀어보면 좋을 만한 문제들로 구성했습니다.
  • CLASS 2는 코딩 테스트나 프로그래밍 대회 등에서 자주 등장하는 주제들 중 초심자가 이해하고 구현하기 쉬운 주제들로 구성했습니다. (브루트포싱, 기초 수학, 정렬, 큐, 스택, 덱)
  • CLASS 3은 CLASS 2에서 등장한 주제들을 전부 이해하고 나서 시도하면 좋을 만한 주제들로 구성했습니다. (그래프, 그래프 탐색, 힙, 우선순위 큐, 다이나믹 프로그래밍 등)
  • CLASS 4는 CLASS 3과 비슷하지만 더 어렵다고 느껴지는 주제들을 담았습니다. (백트래킹, 최단 경로 문제, 어려운 구현, 어려운 다이나믹 프로그래밍, 어려운 그래프 문제 등)

낮은 CLASS 문제들은 ‘단계별로 풀어보기’와 비슷한 구성으로 초심자가 가면 좋을 만한 길을 추천해 주는 것을 목표로 했습니다. 이를 더더욱 권장하기 위해 레이팅에 CLASS 보너스를 추가했습니다. 다만, 새 레이팅과 실력과의 괴리가 생길 것을 감안해 낮은 티어에서는 CLASS 보너스가 매력적으로 보이지만 높은 티어에서는 CLASS 보너스의 유무가 랭킹에 큰 차이를 주지 않도록 다음과 같이 정했습니다.

  • CLASS 1, 2: +25점
  • CLASS 3, 4, 5: +50점
  • CLASS 6~: +10점

CLASS 6부터는 주로 프로그래밍 대회에만 등장하는 어려운 주제들을 다루고 있습니다. 또한 CLASS 6 이상을 취득할 수 있는 실력의 사람이라면 CLASS 5 정도는 쉽게 취득할 수 있고, 굳이 CLASS 문제를 해결하지 않더라도 실력을 늘릴 방법을 많이 알고 있을 것이라고 생각했기 때문에 CLASS 6 이상에서의 레이팅 보상은 랭킹에 크게 영향을 미치지 않는 방향으로 결정했습니다.

레이팅 컷

레이팅에 따른 티어는 크게 두 가지 요소를 고려해 정했습니다.

  • 티어 $x$의 유저 입장에서 티어 $x+1$로 가기 위한 과정에서의 경험은 적절한가
  • 티어에 따른 유저 비율이 어떻게 변화할 것인가

특히 새로운 레이팅 제도에서는 상위 100문제를 반영하고 있는데, 알고리즘 공부를 막 시작한 입장에서는 100문제를 해결하는 것부터 버거울 수 있겠습니다. 따라서 ‘몇 CLASS이길 기대하는가?’와 더불어 낮은 티어의 경우 ‘몇 문제를 해결하는 것을 기대하는가?’를 고려했습니다. 예를 들자면

  • 기존 경험치제의 브론즈 구간에서는 실력에 맞는 문제를 약 30문제 정도를 해결하는 것을 기대했습니다. 새로운 레이팅제에서는 CLASS 1~2를 해결하는 여정을 고려하여 레이팅 컷을 정했습니다.
  • 골드 구간부터는 100문제 이상 해결을 기대하고, 상위 100문제에서 기대하는 난이도 평균을 고려했습니다. 예컨대 골드 III 유저는 평균적으로 클래스 2~3에 실버 II에서 골드 V 수준의 문제를 쉽게 해결할 수 있을 것으로 생각했습니다. 클래스 5를 달아 레이팅 100~150을 챙기고, 클래스 5를 풀면서 골드 상위~플레 하위 문제들에 익숙해져 상위 100문제를 그렇게 구성한다면 어느새 플래티넘이 되어 있을 것입니다.
  • 이론적인 레이팅 만점은 3450이지만 루비 구간의 문제들이 부족하고 상위 100문제가 이미 다이아몬드와 루비로 꽉 차 있는 상황에서 더 어려운 루비 문제를 해결하는 것 자체가 상당히 어려운 과정임을 감안해 루비 구간은 촘촘하게 나눴습니다.

그렇게 하면서도 레이팅 컷이 직관적인 수가 되도록 했습니다 – 브론즈 30, 실버 200, 골드 800, 플래티넘 1600, 다이아몬드 2200, 루비 2700. 이렇게 각각의 티어에서 많은 고민 끝에 레이팅 컷을 정했습니다.

새 레이팅 컷

플래티넘, 골드, 실버, 브론즈가 각각 상위 10%, 33%, 67%, 100%가 되는 것이 이상적이라고 생각하고 있습니다만, 당시 레이팅 공식이 공개되지 않았음을 고려해 기존보다 약간 더 어렵게 설정했습니다. 레이팅 공식이 공개되는 것이 유저 비율에 영향을 미칠 수 있어서입니다.

레이팅 vs 기존 실력 지표

(왼쪽) 새 티어와 코드포스 레이팅의 상관관계, (오른쪽) 기존 티어와 코드포스 레이팅의 상관관계

신규 레이팅제에서, 코드포스 아이디가 존재하는 상위 569명을 대상으로 코드포스 레이팅과 새 티어를 비교한 결과 기존 티어에 비해 상관관계가 약해졌습니다만, 기존과 같이 어느 정도의 상관관계는 유지하는 양상을 보였습니다. Inversion count도 기존 148,135회에서 161,462로 증가했습니다. 기존 경험치제의 문제점을 해결하기 위해 실력과의 상관관계를 다소 희생했으나, 여전히 어느 정도 유의미한 상관관계를 가진다고 해석했습니다.

극복해야 할 과제

새로운 레이팅제도 완벽하진 않습니다. 대표적으로 1,200문제를 해결해 문제 수 보너스 175점을 모두 받은 유저의 경우, 새 레이팅제에서는 상위 100문제보다 낮은 난이도의 문제를 해결하는 것의 의미가 없어집니다. 충분히 흥미로운 문제가 있을 수도 있지만요. 또한 CLASS 보너스 레이팅을 산입하는 것이 좋은 선택인가에 대한 논의도 있었습니다.

이런 부분들에 대해서는 레이팅제로 운영해보면서 어떻게 개선할 수 있을지에 대해 고민해 보기로 했습니다. 길라잡이 컨텐츠를 잘 만드는 것 등 레이팅 공식 외적으로도 개선할 수 있는 부분이 있을지도 모르겠습니다.

티어를 어떻게 결정할지를 정하는 것은 solved.ac 전체를 통틀어 가장 어려운 기획입니다. 그만큼 수많은 고민 끝에 만들어진 기획인데, 고민한 만큼 긍정적으로 정착하면 좋겠습니다.


이후 계획

제가 직장인이 되었고 또 여러가지 일들로 바빠지다 보니 solved.ac에 새로운 컨텐츠를 만들 시간이 상대적으로 부족해졌습니다. 현재 계획하고 있는 것들은 이렇습니다.

  • 백엔드 리팩터링(~6월). 프론트엔드에 이어 백엔드입니다. 현재 백엔드는 PHP인데, 유지보수가 너무 어려운 상황이라 Express로 다시 짜고 있습니다. solved.ac를 처음 만들 시절엔 이렇게 커질 줄 몰랐으니까 어쩔 수 없는 것 같습니다. 프로젝트를 시작할 때부터 기반을 잘 닦읍시다.
  • 길라잡이(~9월).
  • 투표 개편(~9월).

앞으로도 많은 관심과 기대 부탁드리겠습니다!

solved.ac 개발기 2: 더 많은 사람이 쓸 수 있게 해 보기

이 글은 solved.ac 개발기 1: 학회에서 사용할 서비스 만들기에서 이어집니다.

학회에서 사용할 수 있을 만한 서비스가 드디어 완성되었습니다. 하지만 안타깝게도 서강대학교에는 PS를 잘하는 사람이 그렇게 많지 않습니다.

Theorem 1. 서강대학교 구성원만으로 BOJ 문제들에 난이도를 일관되게 많이 달기는 힘들다.

Lemma 1. 서강대학교에는 PS를 잘하는 사람이 그렇게 많지 않다.

Proof of lemma. 애초에 시프트부터가 PS를 못한다. ∎

Proof of theorem. By Lemma 1, it’s trivial. ∎

집단지성으로 난이도를 붙이려는 시도는 이렇게 무너지고 마나요? 아니죠, 집단이 충분히 커지면 괜찮아요.

기존에 짜여 있었던 갱신 로직은 단체 랭킹 페이지를 긁어와서 갱신하기 쉽도록 되어 있었고, 더구나 전체 유저를 스크레이핑할 경우 서비스 자체가 차단될 수도 있겠다고 생각했기에, 일단은 랭킹 페이지가 있는 단체들에 제공하면 좋겠다고 생각했습니다. 다른 많은 학교들과 함께 기여해 나가면 됩니다.

집단지성

다만, 학회에서 쓸 거라고 생각했기에 신경쓰지 않은 부분이 많았습니다. 일단 전 포스트에서 언급했듯이 푼 문제 정보를 업데이트하는 속도가 초당 150문제밖에 되지 않았습니다.

오늘 기준으로 서강대학교 학생들이 맞은 문제 수를 전부 합히면 80,989문제입니다. 초당 150문제라면, 9분만에 처리할 수 있는 수준입니다. 갱신 주기가 1시간이라면 봐줄 수 있는 갱신 시간이죠.

서울의 대학교 지도

하지만 여기에 맞은 문제 132,249개의 서울대학교가 추가된다면 어떨까요? 거기에 더해 다른 학교가 열 곳, 스무 곳 이상씩 추가된다면? 아마 업데이트 시간으로 1시간은 턱없이 부족할 겁니다. 분명히 갱신 시간을 더 줄일 수 있을 텐데, 줄일 구석은 어디에 있을까요?

갱신 시간

갱신 작업은 여러 개의 작은 작업들로 나눌 수 있습니다.

문제 리스트 스크레이핑해서 문제 목록 받아오기
→ 단체 랭킹 리스트 스크레이핑해서 유저 목록 받아오기
→ 유저 페이지 스크레이핑해서 맞은 문제 목록 받아오기
→ 맞은 문제 정보를 토대로 경험치 계산
→ 맞은 문제 정보를 solved.ac 서버로 전송

줄일 구간이 어떤 게 있을까 하고 각각 단계별로 걸리는 시간을 계산해봤습니다.

  • 스크레이핑은 단체 랭킹이나 유저 페이지나, 1페이지당 1초를 넘기지 않았습니다(300ms~700ms). 다만 한 단체를 400명이라고 했을 때 단체 내의 모든 유저 페이지를 스크레이핑하는 건 약 3.6분 가량이 걸렸습니다.
  • 특히 문제 목록 스크레이핑은 전체 문제 페이지가 160페이지 가량이다 보니, 전부 스크레이핑하는 데 약 1~2분 정도가 걸렸습니다.
  • 경험치 계산도 오래 걸리지 않았습니다. 전체 문제 목록을 스크레이핑할 때 문제 난이도 정보도 solved.ac에서 가져왔기 때문입니다. 전체 문제 m개의 목록과 유저가 맞은 문제 n개의 목록은 모두 정렬된 상태였기 때문에, O(m)만에, 그리고 n이 충분히 작다면 O(n log m)만에 경험치를 계산할 수 있습니다. 2,000문제 가량을 맞은 제 유저 페이지를 기준으로, 경험치를 계산하는 데 겨우 13ms 가량이 걸렸습니다.
  • 맞은 문제 정보 갱신은 생각보다 오래 걸렸습니다. 위에서 언급했듯이 초당 150문제를 처리할 수 있는데, 제 페이지의 경우 1350ms 가량이 걸렸습니다.

결국 한 번 업데이트하는 데 맞은 문제 정보 갱신유저 페이지 스크레이핑, 그리고 문제 목록 스크레이핑 순서로 많은 시간을 쓰고 있음을 알 수 있었습니다. 경험치를 계산하는 로직에서는 더 줄일 수 있는 게 딱히 보이지 않았습니다. 이걸 어떻게 줄일 수 있을까요?

문제 목록 스크레이핑

‘이건 줄일 수 있겠다!’고 생각한 것 중 가장 먼저 생각난 것은 문제 목록 스크레이핑이었습니다. BOJ에는 1만 6천개 가량으로 많은 문제들이 있지만, 그렇다고 해도 문제가 1시간 단위로 추가되거나 하지는 않기 때문이죠.

그래서 다소 시간이 걸리는 문제 스크레이핑은 사용자 수가 가장 적을 매일 오전 6시에만 하도록 했습니다.

-reload 플래그가 있으면 문제 목록을 업데이트하게 했습니다

이를 통해 일단 2분 가량을 아낄 수 있었습니다.

유저 페이지 스크레이핑

지난 1시간 동안 푼 문제가 없는데도 업데이트를 해야 할까요? 푼 문제가 없다면 업데이트하지 않아도 되지 않을까요?

유저 페이지 스크레이핑 시간을 줄이려면 유저 페이지 자체를 들어가지 않아야 합니다. 다행히도 유저 페이지를 들어가지 않고도 푼 문제 수가 변했는지 확인할 수 있습니다. 애초에 랭킹 페이지를 스크레이핑해 오기 때문인데요,

학교 랭킹 페이지

랭킹 페이지에는 다행히도 맞은 문제 수와 제출 수가 있습니다. 이를 서버에 캐싱해 두고, 변동이 있을 경우에만 유저 페이지에 직접 들어가서 스크레이핑합니다. 참고로 재채점 등으로 인해 맞은 문제 수가 줄어들 수도 있으므로 맞은 문제 수와 제출 수를 동시에 확인해야 해요.

BOJ가 가장 활성화되는 시간인 오후 12시~1시 사이에도, 서강대학교에서는 8% 이하의 유저만이 맞은 문제 수 또는 제출 수에 변화가 있었습니다. 이런 식으로 모든 유저가 항상 BOJ를 붙들고(?) 있진 않기 때문에, 이 방법을 적용하고 스크레이핑 시간을 현저히 줄일 수 있었습니다. 학교 당 12배 정도였습니다. 게다가 BOJ 서버에 전송하는 리퀘스트 수도 획기적으로 줄이는 효과를 누렸습니다.

맞은 문제 정보 갱신

가장 많은 시간이 걸렸던 맞은 문제 정보 갱신 로직도 시간을 줄일 수 있었습니다. DB에 수많은 레코드들을 업데이트하는 건 시간이 꽤 걸리므로, solved.ac에 저장된 맞은 문제 정보와 스크레이핑해온 맞은 문제 정보를 가져와서, 차이가 있는 것들만 DB에 넣어주도록 바꿨습니다.

예를 들어 이런 경우라면 1004번과 8481번만 DB에 업데이트해 주면 됩니다.

유저 정보를 처음 가져올 때는 여전히 많은 시간이 걸렸지만, 한 명이 한 시간에 몇백 개의 문제를 풀 리가 없으므로 (과연?) 처음 유저 정보를 가져온 이후에는 푼 문제 수에 비해 엄청나게 적은 레코드를 업데이트하게 되어 갱신 시간이 상당히 줄어들게 되었습니다.

이 세 가지 방법을 적용했더니, 결과적으로 390명을 9분만에 처리하는 수준에서 8,000명을 평균적으로 5분만에 처리하는 수준까지 개선할 수 있었습니다. 처리 속도가 약 37배 빨라진 셈입니다. 이 방법을 적용하고 나서, 홍익대학교, 서울대학교, KAIST 등의 순서로 차례차례 학교를 등록해 나갔고 지금 현재 37개의 단체가 별 무리없이 갱신되고 있습니다.

하지만 현재 업데이트되는 사용자 규모는 10,000명 정도에 불과하고, BOJ 전체 유저는 16만 명 정도이므로 전체 사용자를 대상으로 갱신한다면 아마 이걸로도 부족할 것입니다. BOJ에 리퀘스트를 날리면서, 동시에 맞은 문제 차이를 계산하고, 동시에 solved.ac 서버에 업데이트하도록 백엔드를 파이프라인화시키는 것도 고려하고 있으나 애초에 서버의 vCPU 수가 2개밖에 안 되는지라 효과적일지는 모르겠네요..

여담으로, solved.ac 한 달 광고 수익은 제가 2,500원짜리 학식 라면을 꼭 5번 먹을 수 있을 정도에 불과해요. 저도 중학생 때 캐놓은 비트코인 같은 거라도 있었더라면 좋았겠네요 ㅠ


고려하지 못했던 것

그렇게 많은 학교를 추가하고 한동안 여러 기능들을 추가하면서 평화롭게(?) 지냈습니다. 모든 기능이 문제없이 잘 돌아가고 있었습니다. 근데 원래 모든 게 잘 돌아가면 어딘가 불안해집니다. 저만 그런가요?

아무튼 그렇게 매일 새벽까지 개발하고 늦잠 자고 아침강의도 없겠다 늦게 일어나고 하는 평화로운 나날을 보내고 있었습니다. 이런 메시지를 받기 전까지는요.

아니 대체 왜?

갑자기 로그인이 안 될 이유가 딱히 없는데 로그인이 안 된다고 합니다. 음 뭐지?

No space left on device라고 합니다. df 명령어로 남은 공간을 확인해봤는데 공간은 아직 많이 남아 있습니다. 진짜 뭐지??

구글링 끝에 알게 되었습니다. ext4 파일시스템에는 파일의 메타데이터를 저장하는 inode가 있는데, 이 수에 제한이 있다고 합니다. df -hi로 inode 사용량을 분석할 수 있습니다.

역시 inode 사용량이 가득 찼던 거였습니다. Inode가 가득 찼다는 건 파일을 엄청 많이 만들었다는 뜻이 될 거 같은데, 파일을 그렇게 많이 만든 적이 없었던 거 같은데 대체 어느 부분에서 이렇게 되었을까요?

바로 세션 정보들이었습니다. 세로로 긴 이미지 하나 보고 갑시다.

많이 삭제한 게 이 정도입니다.’

세션 파일이 몇백만 개나 있었습니다. 이 세션 파일들이 inode 개수를 다 잡아먹고 있었습니다.

커스텀 세션 핸들러

불행 중 다행으로 PHP는 세션 핸들러를 직접 만드는 게 가능했습니다. 기존 세션 파일들을 전부 삭제하고, MySQL을 사용하는 세션 핸들러를 만들어 교체해 줬더니 세션들이 전부 DB에 저장되었고, inode 폭발 현상이 다시 일어나는 일은 없었습니다.


다음에 한가할 때는 프론트엔드를 짜면서 했던 고민들에 대해 이야기해 보고자 합니다. 최근 solved.ac에 제출된 난이도 의견 수가 12,000건을 넘겼습니다. 학회에서만 사용하려고 했는데 어쩌다 보니 여기까지 올 수 있게 되었습니다. 사이트에 관심 가져 주셔서 정말로 감사하고, 알고리즘 문제해결을 공부하는 사람들의 길잡이가 될 수 있는 좋은 커뮤니티 프로젝트가 되도록 노력을 아끼지 않겠습니다.

감사합니다!

solved.ac 개발기 1: 학회에서 사용할 서비스 만들기

병역특례 인원이 축소된다는 분위기입니다. 알 수 없는 위기감이 맴돕니다. Sogang ICPC Team에서 (학회장 한다는 사람이 없으면) 제가 졸업할 때까지 학회장을 하려고 했는데, 지금 병역 문제를 해결하지 않으면 졸업한 후에 어떻게 될 지 모르기 때문에 이번 학기를 마치고 산업기능요원으로 가기로 결심했습니다. 누가 뽑아줘야 가겠지만..,

여하튼 학회장으로 있으면서 해 보고 싶은 일은 많았는데, 당장 이번 학기가 끝나고 제가 사라지게 되어서 가장 해 보고 싶었던 일을 해 보리라 마음먹었습니다.

TMI가 많습니다(이거 동어반복인가요?). 각오하시고 읽어 주세요!

acm이 icpc와 관련 없는 단체가 되어서 지금은 학회 이름이 ‘Sogang ICPC Team’이 되었습니다.

Sogang ICPC Team은 서강대학교 컴퓨터공학과의 알고리즘 문제해결 소학회입니다. 알고리즘 문제해결 학회라면 목적에 맞게 알고리즘 문제들을 해결해야겠죠? 우리 학회는 Baekjoon Online Judge(BOJ)라는 플랫폼을 문제은행으로 쓰고 있습니다.

문제는 BOJ가 다 좋은데 ‘문제 난이도’라는 지표가 없다는 것입니다. 애초에 BOJ에는 여러 대회들에서 가져온 14,000개가 넘는 문제들이 등록되어 있고, 이 수많은 문제들에 일관된 난이도 기준으로 난이도를 매기는 건 상당히 어렵기 때문일 것입니다.

하지만 ‘문제 난이도’라는 정보가 없어서 처음 시작한 학회원들이 공부를 시작하기가 어려웠습니다. 물론 jh05013님의 단계별로 풀어보기도 있지만 단계별로 문제가 그렇게 많진 않아서 충분히 연습하기는 곤란했습니다. 대신 문제집을 만들 수는 있어서, 지금까지 우리 학회는 수많은 문제들을 대략적인 난이도 그룹으로 나누고 문제집을 많이 만들어 이런 식으로 관리하고 있었습니다.

네 저 그리디 못해요

이 방법은 처음엔 좋았으나 문제집이 추가될수록 여러가지 문제가 생겼습니다.

  • 문제집이 너무 많아졌습니다. 지금 학회 그룹에 등록된 문제집 수는 64개입니다.
  • 한 문제집에는 문제를 100개까지밖에 못 넣습니다. BOJ에는 다이나믹 프로그래밍 문제만 500개가 넘게 있습니다.
  • 문제를 푼 직후 문제집에 문제 하나를 추가하려면 적어도 다섯 번은 클릭해야 합니다.(‘그룹’ – ‘ICPC Team’ – ‘문제집’ – ‘수정’ – ‘확인’) 생각보다 상당히 번거로운 작업입니다.

결국 문제 하나하나에 난이도를 매길 수 있는 크롬 확장 프로그램을 만들자는 결론에 다다랐습니다. 더 나아가서 푼 문제들의 난이도에 따라 개개인마다 레벨을 부여한다면 문제를 풀 동기도 마련해 줄 수 있겠다는 생각이 들었습니다. 당장 착수했습니다.

첫 버전

시험기간 버프로 이틀만에 첫 버전이 나왔습니다. PHP로 간단하게 백엔드를 만들었습니다. 크롬 플러그인은 예전에 만들어 본 적 있어서 어렵지 않게 새로 만들 수 있었습니다.

문제 목록. 지금 쓰는 난이도 아이콘이 없었고, 전부 텍스트였습니다.

난이도 투표 스크린입니다. 역시 디자인은 신경쓰지 않았습니다.

작년(2018년)에 숭실대학교 최고의 동아리 SCCC가 우리에게 시비를 걸었던 적이 있는데, 그냥 두고 볼 수 없었던 저는 서강대학교가 아직 못 푼 문제들을 정리해 두는 서비스를 간단히 만들었습니다. 그 때 만들어 두었던 문제 데이터베이스를 수정해 ‘문제 난이도’라는 칼럼을 하나 만들고, 투표하면 값을 넣는 식으로 구현했습니다. 당연히 한 명만 투표가 가능했습니다.

하지만 제가 어렵다고 생각한 문제를 최고의 임원 raararaara 선배께서는 쉽다고 생각하실지도 모르는 일입니다. 한 명만 투표할 수 있는 건 뭔가 아닌 거 같습니다. 여러 명이 투표할 수 있게 하되 최종 문제 난이도는 여러 명의 투표값의 평균으로 하기로 계획했습니다. 이를 구현하려면 생각해야 될 사항들은 아래와 같습니다.

  • 투표를 저장하는 데이터베이스 구조는 어떻게 해야 할까? 기존 투표도 수정할 수 있어야 하고…
  • 내가 투표했다고 치면, 투표한 사람이 진짜 shiftpsh인지 아닌지는 어떻게 검증할 수 있을까? 클라이언트는 절대 믿으면 안 되니까 페이지에서 유저네임을 그냥 뽑아오는 방법은 안 될 텐데… (실제로 개발자 도구를 열어 HTML을 조작한다면 이 방법은 정말 쉽게 파훼가 가능합니다)

데이터베이스 구조는 그다지 어렵지 않았습니다. 유저와 문제 번호마다 하나의 난이도 값이 있는 테이블을 새로 만들었습니다. 투표한 사람을 검증하는 일은 생각을 해 봐야 했습니다. 당시에는 임원들만 난이도 투표를 하게 할 생각이었어서 큰 고민은 아니었습니다. 후술하겠습니다.

티어 계산

[속보] ICPC Team 학회장 임원 디스코드 유출
 

임원 분들과 열심히 난이도를 매긴 결과 600문제 정도에 난이도가 붙게 되었습니다. 전체 문제의 4%밖에 안 되지만 다들 많이 푸신 문제들 위주로 매겼다보니 이 정도면 티어 계산을 해도 되겠다는 생각이 들었습니다.

티어를 계산하려면 고려해야 될 것들에는 이런 것들이 있습니다.

  • 경험치 테이블. 레벨 업 기준들과 문제당 경험치. 문제 난이도와 티어는 각각 30단계씩이 있습니다. 어려울수록 경험치를 많이 주고 싶지만 한 티어 높은 문제를 풀었다고 보상을 엄청 많이 주긴 좀 그렇고, 그렇다고 브론즈 5 문제만 엄청 풀어서 플래티넘 가게 하고 싶진 않았습니다.
  • 사용자가 푼 문제 정보 가져오기: 한 단어로 크롤링입니다. BOJ는 사이트에 부담이 가는 크롤링을 허용하지 않고 있습니다. 지금은 백준님께서도 이 사이트의 존재를 알고 계시지만 당시에는 비밀스럽게 진행했던 프로젝트였어서 BOJ에 최대한 요청을 적게 보내면서 크롤링을 해야 했습니다.
  • 사용자가 푼 문제들의 정보를 저장하는 데이터베이스의 구조도 생각해야 했습니다.

초기에는 난이도가 한 단계 올라가면 받는 경험치가 1.4배가 되도록 테이블을 설정했습니다. 레벨 업 조건은 총 경험치가 (전 티어 경험치) + (현 티어와 같은 난이도의 문제를 풀면 주는 경험치) * (상수)로 정했습니다. 현재는 조금 다르게 정해져 있습니다.

문제 난이도가 내려가지 않는 한 티어가 떨어질 일도 없습니다. 티어가 떨어질 일이 별로 없다는 것은 어려운 문제에 많이 도전할 충분한 동기 부여가 됩니다.

서강대학교 랭킹

테이블은 잘 정했지만 크롤링이 문제였습니다. 일단 BOJ에 등록되어 있는 서강대학교 구성원은 당시 약 390명이었습니다.

코틀린으로 짠 크롤링 프로그램은 문제 리스트 전체(약 160페이지)와 서강대학교 구성원 전체를 파싱합니다. 한 번 실행에 총 550번의 리퀘스트를 보내는 셈입니다. 실시간성을 위해 1분에 1번 업데이트한다고 생각하면 하루에 BOJ 서버에 792,000개의 리퀘스트를 날린다는 계산이 나왔습니다. 이건 밴 당할 게 분명합니다.

그래서 일단 실시간성을 포기하고 1시간에 1번 업데이트하는 것으로 정했습니다. 하루 13,200개의 리퀘스트는 여전히 많지만, 79만 개보단 훨씬 적기 때문에 ‘음.. 문제 열심히 푸는 사람이라면 하루에 리퀘스트 1만 개 정도는 보낼 수 있지 않을까?'(불가능합니다) 같은 막연한 생각으로 cron 태스크를 만들었습니다. 1시간에 1번씩 잘 돌아갔습니다.

어떻게 이걸 효율을 높일 수 있지

그런데 예상하지 못한 문제가 또 있었습니다. 파싱은 잘 됐는데, 데이터베이스에 푼 문제들을 등록하는 게 너무 오래 걸렸습니다. 문제를 많이 푼 순으로 위에서 15명이 푼 문제 정보를 데이터베이스에 등록하는 데 무려 12분이 걸렸습니다. 54문제를 등록하는 데 1초 걸린 셈입니다. 뭔가 방법이 잘못되었다는 걸 직감했습니다.

트위터 찬스를 썼습니다.

무려 새벽 1시 반에 트윗을 남겼음에도 불구하고 트위터에 인생을 파신 개발자 분께서 바로 대답해 주셨습니다.

하지만 A는 문자열이었습니다. 저는 문자열이 primary key가 될 리가 없다고 생각하고 ‘A가 스트링이죠’라고 답글을 보냈습니다. primary key와 인덱스가 여러 칼럼에 걸릴 수 있다는 것도 몰랐습니다. 답글로 얻어맞게 됩니다.

그냥 제가 SQL을 모르는 거였습니다. 당장 유저명과 문제 번호에 primary key, unique, index를 걸었고 쿼리 속도가 초당 150문제 정도로 개선되었습니다.

쿼리 속도가 세 배 개선되었습니다

PK를 적용하고 나니 서강대학교 전체를 업데이트하는 데엔 6분 가량이 걸리게 되었습니다. 여전히 조금 느렸지만, 서강대학교만 쓰던 당시로서는 만족할 수 있었던 성능이었기에 나중에 생각하기로 했습니다.

푼 문제들을 파싱했으니 난이도 순으로 정렬된 유저 페이지를 만들 수 있을 거 같아서 이것도 만들었습니다. CSS는 ask.shiftp.sh의 것을 가져와서 개조했기 때문에 만드는 데 오래 걸리진 않았습니다. 이거 발전시키면 개인적으로 프레임워크같이 쓸 수 있을 거 같다는 생각도 하는 중입니다.

초기 푼 문제 목록 페이지

이 날 랭킹 페이지도 새로 만들었습니다.

본인 확인

앞에서 난이도 투표를 한 사람이 누군지 검증할 수 없는 문제가 있었다고 언급했습니다. 이를 해결하기 위해 일단 solved.ac에 따로 회원가입 시스템을 만들었습니다.

플러그인에서 로그인하면 서버에서 토큰을 발급해 주고, 이를 로컬에 저장해 뒀다가 문제 난이도를 매길 때 인증 정보로서 서버에 다시 보내는 식으로 구현하는 것으로 해결했습니다.

문제는 solved.ac에 가입하는 사람이 BOJ의 그 사람이 맞는지 아닌지 검증하기가 곤란하다는 건데, 디스코드에 있는 외국 알고리즘 문제해결 커뮤니티 CP Community의 한 봇에서 영감을 얻을 수 있었습니다.

CP Community는 러시아의 Codeforces 플랫폼을 기반으로 활동하는데, 이 디스코드 서버는 특정 문제에 컴파일 에러가 나는 코드를 제출하게 해서 본인임을 확인합니다.

초기 본인 인증

BOJ에는 소스를 공개적으로 공유할 수 있는 기능이 있습니다. 이 기능을 이용해 공유된 소스는 문제를 풀지 않았거나 심지어 로그인하지 않았더라도 누구나 열람할 수 있습니다.

따라서 틀려도 부담되지 않을 만한 문제를 골라 서버에서 랜덤하게 생성한 문자열을 입력하고, 그 소스를 공유해 소스 주소를 서버에 보내면 서버가 이를 검증하는 방식으로 본인인지 아닌지는 확인할 수 있습니다. 이를 통해 투표하는 사람이 누구인지에 대한 걱정도 해결했습니다.

이렇게 학회 내부에서 사용할 서비스가 완성되었습니다.

한계

이 서비스는 분명한 한계가 있었습니다. 기술적인 한계는 아닙니다. 서강대학교는 사람이 적어서 많은 사람들이 학교 리스트에 등록될 리 없기 때문입니다. 다만 사람이 적기 때문에 난이도 의견 자체가 적었습니다. 활발하게 난이도를 매기는 사람들은 저를 포함한 임원들이나 문제를 많이 풀어본 사람들 뿐이었고, 그분들마저도 일정 수준 이상의 문제에 난이도를 매기는 건 역부족이었습니다.

해결방법은 서강대 밖의 많은 고수들을 끌어모으는 것이었습니다. 하지만 많아봐야 고작 100명 정도의 학회원들이 사용하는 서비스를 수천 명이 사용하는 서비스로 개조하기 위해서는 생각을 많이 해야 했습니다.

이번 포스트에서는 ‘제가 SQL을 정말 몰랐네요’, ‘본인확인 이렇게 하는데 어때요 멋지죠?’ 말고 별다른 기술적인 내용을 다루지 않아 결국 일상 포스팅 같은 게 되었지만, 다음 포스트에서는 solved.ac를 수천 명이 사용하는 서비스로 개조하면서 한 생각들을 다뤄볼 생각입니다.