인터넷에서 북한 acm-icpc 문제를 찾았습니다

[mathjax]

인터넷에서 acm-icpc 2016 평양 리저널 문제를 찾았습니다. 북한 문제는 어떤 수준인지, 컴퓨터 과학 용어는 우리와 얼마나 많이 차이나는지 궁금해서 저화질의 사진을 보기 쉽게 글로 다시 정리해 보았습니다. 줄바꿈과 일부 기호는 임의로 수정했습니다.

총 12문제로 구성되어 있습니다. 개인적으로는 Mathforces 대회 같은 느낌의 문제들이라고 생각됩니다.

모든 문제는 ICPC Live Archive에서 풀어볼 수 있습니다. 시간제한이 다릅니다.


문제 1. 배렬전도수

  • 시간 제한: 1초
  • 메모리 제한: 64MB

설명

당신들은 모두 배렬1의 전도수에 대하여 알것이다. 배렬 \(\left\{ a_1, a_2, \cdots, a_n \right\} \)의 전도수는 \(i < j\)이고 \(a_i > a_j\)인 \(\left(i, j \right)\)의 쌍의 개수로 정의한다.

한민이는 총명한데 지금 새로운 배렬의 전도수를 생각하고있다.

만일 \(i\) 와 \(j\) 의 짝홀성이 같으면서 \(a_i > a_j\)이면 그는 \(\left(i, j \right)\)를 전도된 쌍으로 생각한다. 한편 짝홀성이 다르면서 \(a_i < a_j\)이면 그는 이런 쌍\(\left(i, j \right)\)도 전도된 쌍으로 생각한다. 다른 말로 말한다면 첨수쌍2 \(\left(i, j \right)\)는 \(i\) 와 \(j\) 의 짝홀성이 같을 때 \(a_i > a_j\)이거나 다를 때 \(a_i < a_j\)이면 전도된 쌍이다.

당신은 한민의 딱친구3이고 배렬의 전도된 쌍의수를 계산할데 대한 부탁을 받았다. 당신은 풀수 있는가?

입력

입력파일의 첫행은 입력자료4개수 \(T \left(1 \leq T \leq 5\right)\)로 되어있다.

매입력자료의 첫행은 한개의 옹근수5 \(N \left(1 \leq N \leq 5000\right)\)을 포함하는데 그것은 배렬의 길이이다.

다음행에 \(N\) 개의 실수가 공백단위로 분리되어 들어온다.

출력

당신은 매 입력자료별로 한행에 전도수를 찍는다.

표준입력

1
5
1 4 3 2 5

표준출력

5

문제 2. \(B_N\)

  • 시간 제한: 1초
  • 메모리 제한: 128MB

설명

총명한 학생 리기웅은 물리를 아주 잘하지만 수학은 잘하지 못한다. 그의 동무 신영진은 반대로 수학을 잘하고 물리를 잘하지 못한다. 그래서 리동무는 신동무의 물리숙제를 도와주고 신동무는 리동무의 수학숙제를 도와준다.

오늘 리동무는 아주 힘든 수학문제를 받아가지고 와서 신동무에게 물어보았다. 그러나 신동무는 아주 바빠서 그는 당신에게 풀어줄것을 부탁하였다. 당신은 신동무의 딱친구이며 반드시 그것을 풀어야 한다. 문제는 다음과 같다.

배렬 \(\left\{ A_1, A_2, \cdots, A_n \right\} \)이 주어졌다. 새로운 배렬 \(\left\{ B_1, B_2, \cdots, B_n \right\} \)은 다음의 공식에 따라 정의된다.

\[ B_N = \left( \sum_{\substack{i_1+i_2+\cdots+i_k=N \\ 1\leq k \leq N}} A_{i_1}A_{i_2}\cdots A_{i_n} \right) \% 1000000007 \]6

물론 \(1 \leq i_1, i_2, \cdots, i_k \leq n\) 이다. \(u \neq v\)에 대하여 \(i_u = i_v\)도 가능하다. 실제로 \(B_3 = A_1 \times A_1 \times A_1 + A_1 \times A_2 + A_2 \times A_1 + A_3\)이다. 당신은 반드시 주어진 \(N\)에 대하여 \(B_N\)을 계산해야 한다.

당신은 그들을 도와줄수 있는가?

입력

입력파일의 첫행은 입력자료개수 \(T\)로 되어있다.

매 자료의 첫행은 두개의 옹근수 \(n\) 과 \(N\)으로 되어있다. \(\left(1 \leq n \leq 100, 1 \leq N \leq 100\right)\)

다음행에는 \(n\) 개의 옹근수가 공백단위로 분리되어 들어온다.

출력

문제의 결과를 출력하시오.

표준입력

1
2 5
3 2

표준출력

495

문제 3. 행렬검사

  • 시간 제한: 1초
  • 메모리 제한: 512MB

설명

정교수는 제 41 차 국제대학생프로그람아시아평양지역경연 문제출제자이다. 그는 100개조의 2016 × 1946 행렬과 1946 × 2016행렬의 곱하기를 끝냈다. 물론 결과는 2016 × 2016행렬식이다. 계산하는데 거의 10일 걸렸다. 결과는 100개조이고 문제 C의 입출력자료로 될것이다.

계산이 끝난 후 정교수는 잠들었고 그의 아들이 결과에 손을 댔다. 그는 어느 한 수의 하나의 자리를 지우고 수자7 1을 써넣었다.

다음날 정교수는 매우 성났다. 그러나 아들애는 겨우 2살이어서 모든것을 기억하지 못한다.

정교수는 그의 아들의 말을 들어보고 세부를 검사한다. 그래서 그는 아들이 매 조의 한수의 하나의 자리수를 변화시켰고 그 수자가 2, 0, 1, 6 중의 하나라는것을 알았다. 그리고 그는 아들이 변화시킨 위치가 행번호와 렬번호가 70 이하라는것을 알았다. 행렬의 왼쪽웃구석의 번호는 (1, 1) 이다. 첫 첨수는 행번호이고 다음번호는 렬번호이다.

그는 입출력을 오늘중으로 전송하여야 한다. 그래서 그는 결과를 검사할 결심을 하였다. 당신은 그의 우수한 학생이다. 정선생을 도우시오.

입력

입력파일은 꼭 100조의 입출력자료로 되어있다. 매 조는 다음과 같이 정의되었다.

첫행은 5개의 옹근수 \(a_1, a_2, a_3, a_4, a_5\)로 되어있다. 당신은 다음과 같이 행렬 \(A\)를 얻을수 있다.

\[A_{ij} = (a_1 \times i^4 + a_2 \times i^3 + a_3 \times j^2 + a_4 \times j + a_5) \% 1946002016\]

다음행은 5개의 옹근수 \(b_1, b_2, b_3, b_4, b_5\)로 되어있다. 당신은 다음과 같이 행렬 \(B\)를 얻을수 있다.

\[B_{ij} = (b_1\times i^4 + b_2\times i^3 + b_3\times j^2 + b_4\times j + b_5) \% 1946002016\]

다음 왼쪽웃구석의 70 × 70 옹근수 행렬이 있다. 당신은 이 행렬식을 검사하여야 한다.8

당신은 두 행렬을 곱할 때 행렬을 반드시 2016011010에 관하여 나머지를 취한다.

출력

당신은 어느 입력조가 아들에 의해 변화되었는가를 출력해야 한다. 입력의 번호는 1부터 100까지 이다. 당신의 출력은 반드시 증가순서로 출력해야 하며 공백단위로 분리되어있어야 한다. 만일 모든 입력조들이 변화되지 않았다면 0을 출력하시오.

입력과 출력의 실례

입력과 출력이 너무 커서 우리는 당신들에게 입력과 출력의 실례를 보여줄수 없다. 당신은 입출력의 형식을 담보해야 한다.


문제 4. 사과나누기

  • 시간 제한: 8초
  • 메모리 제한: 512MB

설명

현일은 도덕있는 학생이다. 그는 항상 그의 학급동무들과 친구들을 자기자신처럼 대해준다. 하루는 그가 맛있고 큰 사과를 가져와 그의 친구들에게 나누어주려고 한다. 흥미있는것은 사과가 타원모양이라는것이다.

그는 항상 두가지 조작을 진행한다.

첫번째는 사과의 \(L\)부터 \(R\)각도사이의 남은 면적을 계산하는것이다.

둘째는 \(L\)부터 \(R\)각도사이의 모든 사과쪼각들을 주는것이다.

현일은 사과를 데카르트자리표계9에 놓았으며 결과 사과는 타원 \(\frac{x^2}{a^2}+\frac{y^2}{b^2}=1\) 에 자리잡고있다.

현일의 형인 당신은 어린 동생의 계산능력을 시험해보려고 하는데 당신은 모든 질문들에 반드시 대답해야 한다.

할수 있는가? 있다.

아, 한가지 조건이 또 있는데⋯ \(prev\)는 마지막으로 출력된 수이며 실제 \(L\)과 \(R\)은 다음의 공식에 의해 계산된다.

\[L_{real} = \left( L_{given} + prev \right) \% 360, R_{real} =\left( R_{given} + prev \right) \% 360\]

만약 \( L_{real} > R_{real} \)이면 당신은 두값을 바꾸어야 한다. 당신은 조작을 \(L_{real}\)과 \(R_{real}\), 두값을 가지고 해야 한다. 처음에 \(prev = 0\)이다.

입력

입력파일의 첫행은 세옹근수를 포함한다. – \(a\) \(b\) \(n\) \(\left( 1 \leq a, b \leq 100, n \leq 300000 \right)\)

\(a\)와 \(b\)는 우에서 설명한 수이고 \(n\)은 조작회수이다.

다음의 \(n\)개 행은 세 수 “\(type\) \(L\) \(R\)”을 포함한다. (\(1 \leq type \leq 2\), \(L\)과 \(R\)은 임의의 실수이다.) \(0 \leq L + prev,0 \leq R + prev\) 라는것은 담보할수 있다.

출력

모든 조작1에 대해서 결과를 계산해야 한다. 소수점아래 5자리에서 반올림하여 출력하시오.

표준입력

10 10 3
1 10.00000 30.00000
2 40.00000 70.00000
1 10.00000 300.00000

표준출력

17.45329
226.89280

주해

문제가 쉬워 지도록 \(L\)과 \(R\)도 소수점아래 5자리로 주어진다. 그리고 \(prev\)는 마지막으로 출력된 첫번째 질문의 값이다. 실례로 \(prev = 17.45329\) 이지만 실제 대답은 \(17.453297519943295769236907684886\cdots\)이다.10


문제 5. 쉬운 기하문제

  • 시간 제한: 1초
  • 메모리 제한: 32MB

설명

\(ABCD\)는 4면체이며 \(\overline{DA} = a\), \(\overline{DB} = b\), \(\overline{DC} = c\), \(\angle BDC = \alpha\), \(\angle ADC = \beta\), \(\angle ADB = \gamma\)로 주어진다. 당신은 \(ABCD\)의 내접원11반경을 계산해야 한다.

입력

첫행은 입력자료개수 \(T (1 \leq T \leq 100000)\)로 되어있다.

매 입력자료는 6개의 수 \(a, b, c, \alpha, \beta, \gamma\) \((1 \leq a, b, c \leq 100, 0 < \alpha, \beta, \gamma < 360)\) 을 포함한다.

출력

내접원의 반경을 소수점아래 6자리에서 반올림하여 출력하시오.

표준입력

1
10 10 10 90 90 90

표준출력

2.113249

문제 6. 가장 좋은 경로찾기

  • 시간 제한: 4초
  • 메모리 제한: 256MB

설명

비트시는 바이트랜드의 수도이다. 비트시에는 현대적인 고속도로체계가 있으며 그 체계는 자주 갱신되는데 고속도로들이 체계에 추가된다. 체계는 교차점들을 연결하는 고속도로들로 이루어져있다.

운수회사 사장인 당신은 어느 한 교차점에서 다른 곳으로 콤퓨터들을 수송하려고 한다. 그런데 바이트랜드에서 휘발유값이 너무 비싸 당신은 한대의 화물자동차로만 나르려고 한다. 당신은 가능한껏 많은 콤퓨터들을 나르려고 하지만 모든 고속도로들은 \(W\)대이상의 콤퓨터들은 나를수 없다는 제한을 가지고있다.

당신은 나를수 있는 콤퓨터의 최대값을 계산해야 한다. 당신의 초기의 고속도로체계상에서 임의의 두 교차점사이로 이동할수 있다. 다시말하여 원래 체계는 연결되었다.12

입력

첫행은 입력자료개수 \(T (1 \leq T \leq 3)\)로 되어있다.

매 입력자료는 교차점과 도로수를 의미하는 두 옹근수 \(N\)과 \(M\)으로 시작된다. \((3 \leq N \leq 70000, N-1 \leq M \leq 150000)\)

다음의 \(M\)개행은 \(a\)와 \(b\)사이에 도로가 있으며 제한은 \(c\)임을 의미하는 세개의 옹근수 \(a\) \(b\) \(c\)를 포함한다. \((1 \leq a, b \leq N, 1 \leq c \leq 10000)\)

다음 행은 질문의 개수를 의미하는 하나의 옹근수 \(Q (1 \leq Q \leq 105000)\)를 포함한다. 모든 질문은 다음의 두 종류중 하나이다.

  1. \(a\) \(b\) \(c\): \(a\)와 \(b\)사이에 도로를 련결하며 제한은 \(c\)이다.
  2. \(a\) \(b\): \(a\)로부터 \(b\)로 나를수 있는 콤퓨터의 최대개수를 계산하시오. \((1 \leq a, b \leq N, 1 \leq c \leq 10000)\)

두 교차점사이에는 둘 혹은 그 이상의 도로가 있을수 있다.

출력

둘째 종류의 매 질문에 대해 나올수 있는 콤퓨터의 최대대수를 출력하시오.

표준입력

1
5 6
1 2 2
1 3 3
2 4 7
2 5 1
3 4 6
3 5 5
4 
2 2 5
1 4 5 8
2 2 5
2 3 4

표준출력

5
7
6

문제 7. 좋은 날들

  • 시간 제한: 1초
  • 메모리 제한: 64MB

설명

당신은 두개의 날자 \(\texttt{y/m/d}\)와 \(\texttt{yy/mm/dd}\)를 입력 받는데 하나는 첫번째 좋은 날이고 하나는 마지막 좋은 날이다. 그것들사이의 모든 날들도 역시 좋은 날이며 다른것들은 그렇지 않다. 당신은 좋은 날자수를 계산해야 한다.

입력

첫행은 입력자료개수 \(T (1 \leq T \leq 10000)\)로 되어있다.

매 입력자료는 6개의 옹근수 \(y\) \(m\) \(d\) \(yy\) \(mm\) \(dd\)로 되어있다. \((1 \leq y, yy \leq 5000)\)

출력

좋은 날자수를 출력하시오.

표준입력

1
2016 11 8 2016 11 11

표준출력

4

문제 8. 효성과 광성

  • 시간 제한: 1초
  • 메모리 제한: 256MB

설명

영어소문자로 이루어진 긴 문자렬 \(S\)가 있다. 두 소년 효성이와 광성이는 재미난 경기를 한다. 경기규칙은 다음과 같다.

초기에 심판원 학명이가 그들에게 비지 않은 \(S\)의 부분문자렬을 준다. (우리는 그것을 \(P\)로 표시하자.) 두명의 경기자는 교대로 뒤에 한개의 문자를 추가하여 새로 생긴 문자렬이 \(S\)의 부분문자렬이 되게 한다. 만일 그들이 문자를 추가하지 못하면 경기는 끝난다.

효성이는 마지막 문자렬이 가능한껏 짧게 하려고 하고 광성이는 문자렬이 가능한껏 길게 하려고 한다. 효성이는 첫 경기자이다. 만일 그들이 최량13으로 경기를 한다면 매 문자렬에 대하여 추가되는 문자의 수를 추측할수 있다. (우리는 그것을 \(f(P)\)로 표시하자.)

부분문자렬 \(A\)는 만일 \(f(A) < f(B)\) 이거나 \(f(A) = f(B)\)이고 \(A\)가 \(B\)보다 사전순으로 앞에 놓이면 부분문자렬 \(B\)보다 작다고 정의한다.

주어진 옹근수 \(K\)에 대하여 문자렬 \(S\)의 \(K\)-번째로 작은 문자렬을 찾으시오. 찾아낼수 있는가?

입력

첫행은 한개의 문자렬로 되어있는데 그것의 길이는 500000 이하이다.

두번째행은 하나의 옹근수 \(K (1 \leq K \leq 1000000000)\)로 되어있다.

출력

결과 문자렬에 대하여 그것에 추가되는 문자의 수와 결과문자렬을 공백단위로 분리하여 출력하시오.

표준입력

aababb
8

표준출력

1 abab

문제 9. 국제망봉사

  • 시간 제한: 1초
  • 메모리 제한: 256MB

설명

지구상에는 수많은 망봉사기14들이 있다. 모든 수 \(i\)에 대하여 \(i\)번째 망봉사기는 “반경” 이라고 불리우는 지수값 \(R_i\)를 가지고있으며 봉사기는 자기로부터 떨어진 거리가 \(R_i\)이하인 모든 점들까지 봉사15할수 있다.

일부 점들은 많은 봉사기들로부터 봉사받을수 있다. 너의 과제는 최대로 많은 개수의 봉사기로부터 봉사받을수 있는 점을 찾는것이다.

지구는 6370의 반경을 가진 완전구로 보며 지구겉면의 구 점사이거리는 유클리드거리가 아니라 겉면상에서의 거리이다.

문제를 쉽게 하기 위해 망봉사기들의 반경을 2012 부터 2016 사이로 한다. (2012와 2016 포함)

입력

첫행은 입력자료개수 \(T (1 \leq T \leq 6)\)로 되어있다.

매 입력자료의 첫행은 봉사기의 대수 \(N (1 \leq N \leq 1000)\)을 포함한다.

다음 \(N\)개 행은 봉사기의 경도와 위도, 반경을 나타내는 세 옹근수를 포함한다. (0 ≤ 경도 < 360, -90 < 위도 < 90)

출력

문제의 답을 출력하시오.16

표준입력

1
2
0 0 2012
0 1 2016

표준출력

2

문제 10. 보석통

  • 시간 제한: 3초
  • 메모리 제한: 256MB

설명

성영은 아무런 수학문제도 아주 빨리 풀수 있다. 그의 형 최광은 비싼 보석들을 보관할수 있는 빈 \(N\)개의 보석통들을 가지고있다.

하루는 최가 보석상점에서 \(N\)개의 보석을 가져왔다. 최는 모든 보석들을 한통에 한개씩 넣을것이다. 다시말하여 그는 매통에 오직 하나의 보석을 보관할것이다.

모든 보석들은 4개의 수를 가지고있는데 보관번호 \(p\), 통에 도착하는 시간 \(t\), 그리고 2가지 값 \(a\)와 \(b\)를 가진다. \((p, t, a, b)\)에대한 설명을 하자.

보석\((p, t, a, b)\)이 도착하면 최는 이미 도착한 보석들가운데서 가장 잘 결합되는 보석을 찾아내야 한다. 가장 잘 결합되는 보석\((p_1, t_1, a_1, b_1)\)은 다음의 조건을 만족시켜야 한다.

  1. 그것은 반드시 새 보석보다 먼저 도착하여야 한다. 다시말하여 \(t_1 < t\).
  2. 그것의 통번호는 \(p\)보다 작아야 한다. 다시말하여 \(p_1 < p\).
  3. 결합효과가 최대로 되어야 한다. 결합효과는 다음과 같이 정의한다. \(a_1 \times a + b_1 \times b\).

그리고 최는 그 통의 뚜껑에 보석들의 결합효과를 써넣으려고 한다. 그래서 최는 성영에게 매통의 뚜껑에 수를 계산하여 써놓을것을 부탁했다. 성영을 도와주자.

입력

첫행은 옹근수 \(N (1 \leq N \leq 100000)\) 을 포함하는데 이것은 보석통의 개수이다.

그리고 다음 \(N\)개의 행이 있다.

\(p\)번째행은 3개의 변수 \(t\) \(a\) \(b\)를 포함한다. – 그곳은 보석 \((p, t, a, b)\)를 의미한다. \((1 \leq t \leq 1000000000, 1 \leq a, b \leq 1000000)\)

어느 두개의 보석도 동시에 도착하지는 않는다.

출력

\(N\)개의 옹근수들을 출력하시오. \(p\)번째수는 \(p\)번째 뚜껑에 써넣을 수이다.

표준입력

3
1 1 1
2 2 2
3 3 3

표준출력

0
4
12

문제 11. K번째 그라프 절단

  • 시간 제한: 3초
  • 메모리 제한: 512MB

설명

지성은 그라프리론17을 배우기 좋아한다. 처음 그는 최소생성나무18에 대하여 배웠다. 다음 그는 최단경로에 대하여 배웠다. 그리고 그는 지금 그라프의 절단문제에 대하여 배우고있다.

무게붙은 방향그라프19(그것은 연결이 아니어도 된다)와 원천과 목적지가 주어진다. 말할 필요는 없지만 원천과 목적지는 그라프의 한개 정점이다.

다음 당신은 그라프에서 원천지와 목적지사이에 아무런 경로도 없게 그라프에서 마디20를 없애야 한다. 그때 제거한 마디들의 무게 합을 “절단” 이라고 부른다.

지성은 이미 일반그라프에서 최소절단이 원천지와 목적지사이의 최대흐름과 같다는것을 알고있다. 그리고 그는 지금 \(K\)째 최소절단에 대해서 알고싶어한다. 그는 \(K\)째 최소생성나무와 \(K\)째 최단경로를 구할수 있지만 \(K\)째 최소절단을 구할수 없다. 그를 도와주자.

입력

첫행은 5개의 옹근수 \(N\) \(M\) \(K\) \(S\) \(T\)를 포함한다.

\(N (1 \leq N \leq 100)\) – 그라프의 정점수를 의미한다.

\(M (1 \leq M \leq 1000)\) – 그라프의 마디수를 의미한다.

\(K (1 \leq K \leq 100)\)

\(S (0 \leq S < N)\) – 원천지의 정점번호.

\(T (0 \leq T < N)\) – 목적지의 정점번호. \((S \neq T)\)

다음 \(M\)개 행은 3개의 옹근수 \(a\) \(b\) \(c\)를 포함한다. – \(a\)와 \(b\)사이의 미디이며 그것의 무게는 \(c\)이다. \((0 \leq a, b < N, a \neq b)\)

문제를 쉽게 하기 위하여 매 \(i (0 \leq i < N, i \neq S, i \neq T)\)에 대하여 \(i\)와 \(T\)사이에 적어도 하나의 마디가 있다.

출력

문제에 대한 답을 출력하시오.

만일 \(K\)째 최소절단이 없다면 -1을 출력하시오.

표준입력

3 3 3 0 2
0 1 1
0 2 3
1 2 2

표준출력

6

문제 12. 긴옹근수 인수분해

  • 시간 제한: 1초
  • 메모리 제한: 256MB

설명

나는 대수를 아주 좋아하는데 특히 인수분해를 좋아한다. 긴옹근수 인수분해는 나에게 즐거움을 주지만 그것은 힘든 문제다.

나의 선생님은 새 인수분해 문제를 주었다. “옹근수 \(N\)이 주어졌을 때 큰 옹근수 \(N^4 + 64\)을 인수분해해야 한다.”

첫단계로 나는 \(N^4 + 64\)을 2개의 옹근수 \(a\) \(b\)의 적21으로 표시하고싶다. 물론 \(1 < a, b < N^4 + 64\)이다.

나는 이것을 할수 있지만 바쁘다. 나를 도울수 있는가?

입력

첫행은 입력자료의 개수 \(T (1 \leq T \leq 10000)\)를 포함한다.

매 입력자료는 한개의 옹근수 \(N (1 \leq N \leq 10000)\)을 포함한다.

출력

\(N^4 + 64 = a \times b\)를 만족하는 \(a\)와 \(b\)를 출력하시오. 만일 여러가지 경우가 있다면 그중 하나를 출력하시오.

표준입력

1
1

표준출력

5 13

2018 서강대학교 프로그래밍 대회에서 우승했습니다

11월 23일에 2018 서강대학교 프로그래밍 대회가 3시간동안 열렸습니다. 매년 서강대학교 학부생을 대상으로 열리는 개인 단위의 ACM-ICPC 스타일 알고리즘 대회입니다. 올해로 14년째입니다. (2016년에 제 12회였으니까 아마 올해가 14번째겠죠 ..? 잘 모르겠지만 그럴거에요)

1~2학년만 참가할 수 있는 Master 디비전과 전학년이 참가할 수 있는 Champion 디비전이 있습니다. 저는 오프라인 대회 경험이 별로 없는 새내기라서 Master 디비전에 참가했습니다. 내년부터 알고리즘 학회장을 하게 되기 때문에 교내 대회를 참가자로서 참여하는 건 이번이 처음이자 마지막일지도 모르겠네요 😄

문제는 디비전마다 6문제, 총 12문제였어요. Baekjoon Online Judge에서 오픈 컨테스트를 풀어볼 수 있어요. Master 디비전에는 오픈 컨테스트의 A, C, D, E, G, I 번 문제가, Champion 디비전에는 B, F, H, J, K, L 번 문제가 출제되었습니다.

ACM-ICPC 스타일 대회에서는 문제를 풀 때마다 푼 문제 색상에 맞는 풍선을 달아주는 문화(?)가 있어요

여름에 2018 전국 대학생 프로그래밍 대회 동아리 연합 대회(UCPC 2018)에서 풍선 스탭으로 일하면서 참가자 분들 책상에 풍선을 달아드렸는데, 이번엔 제 책상에 풍선이 달리는(?) 입장이었어요. 제가 풍선을 달 때는 참가자 분들이 신경쓰이실까봐 다소 걱정도 했지만 문제를 푸는 입장이 되어 보니 생각보다 신경쓰이진 않았어요!

풍선이 많이 달리면 대회장이 예뻐져요. 이런 문화 좋아요!

대회에서 Kotlin을 못 써서 조금 아쉬웠어요. 제 주력 언어는 Kotlin이고, 제가 BOJ에서 푼 문제 중 90% 넘는 문제는 Kotlin으로 풀었거든요. 하지만 학회에서 스터디 하면서 C++에 어느 정도 익숙해져서 딱히 무리는 없었어요. Kotlin은 icpc 월드 파이널 나갈 일이 있다면 거기서 써서 제트브레인의 관심을 한 몸에 받는 거로 만족하고 싶어요. 근데 뭐 일단 월드 파이널을 나갈 수가 있어야..

아무튼 이런 대회가 처음인 새내기의 잡소리는 치워 두고, 문제 이야기를 해 봐요!

문제 이야기

경고: 이 밑에는 솔루션이 있습니다.

솔루션은 제가 문제를 푼 순서입니다.

C. 어려운 소인수분해 / BOJ #16563

A번 풀이가 의외로 곧바로 생각나지 않아서 C부터 풀었습니다. 에라토스테네스의 체는 자신있었거든요.

2와 500만 사이의 자연수가 들어오기 때문에 먼저 $\sqrt{5000000} \approx 2236$까지의 소수를 에라토스테네스의 체로 전처리해 둡니다. 대회에서는 정확하게 500만의 제곱근을 하는 대신 대략 3000으로 잡았습니다. $\pi (2236)=331$이기 때문에, 대략 350개가 안 되는 소수를 얻을 수 있습니다.

어떤 수 n을 입력받습니다. 이제 소수 p에 대해 n이 p로 안 나눠질 때까지 n을 p로 나누고, 동시에 p를 출력합니다. p를 2부터 점점 늘려가다가 n이 $p^2$보다 작아질 경우엔 더 이상 p로 나눠질 리가 없다고 판단하고 루프를 빠져나옵니다. 2236까지의 모든 소수로 나눠봤는데도 n이 1이 아니면, 남아 있는 n 자체가 소수라는 뜻이기 때문에 이 때는 n을 추가로 출력합니다. 이렇게 하면 소인수분해를 해야 되는 수의 개수가 100만 개이더라도 나눗셈을 시도하는 소수 p의 개수가 얼마 안 되기 때문에 큰 걱정이 없습니다. 대회 시작 9분 후 퍼스트 솔브.

A. 3의 배수 / BOJ #16561

의외로 이 문제는 처음에 문제를 잘못 이해해서 고민을 많이 했어요. 자연수 3개로 분할해야 하는데 그걸 놓쳐서 그냥 자연수를 분할하는 갯수로 이해해버렸어요. 아무튼.

문제를 읽어보면 알겠지만 n이 3의 배수인 건 별 의미가 없죠? 사실 $\frac{n}{3}$을 자연수 3개로 분리하는 것과 같습니다. 근데 순서가 상관이 있다고 하네요. 어떻게 분리해야 될까요?

일단 3을 3개로 분리하는 건 1 + 1 + 1 하나밖에 없죠. 4를 3개로 분리하는 건 2 + 1 + 1을 순서를 적절히 바꿔서 3개가 나오고, 5를 3개로 분리하는 건 3 + 1 + 1과 2 + 2 + 1을 순서를 적절히 바꿔서 6개가 나오고… 그러면 이 문제는 공 $\frac{n}{3}$개를 3개의 서로 다른 상자에 각각 1개 이상씩 나눠 담는 경우의 수를 구하는 문제로 생각할 수도 있겠네요! 이건 중복조합 $$\textstyle\left\langle{3\atop {\frac{n}{3}-3}}\right\rangle\left(=_{3}\mathrm{H}_{\frac{n}{3}-3}\right)$$과 같습니다. 계산해 보면 간단히 $$\frac{(\frac{n}{3}-1)(\frac{n}{3}-2)}{2}$$이고, 이렇게 풀면 AC를 받아요!

물론 저는 고등학교 확률과 통계는 잊어버린 지 오래이기 때문에 3, 4, 5, 6을 분할해 보고 각각 1, 3, 6, 10개가 나오는 걸 보고 ‘이건 뭔가 nCr이겠구나!’ 싶어서 바로 그렇게 짰더니 맞았습니다. 대회 시작 14분 후 정답.

B. 친구비 / BOJ #16562

간단한 그래프 문제였어요. 연결 요소들을 찾고, 그 중 최소인 값들만 다 더해주면 됩니다. 연결 요소들은 BFS로 찾든 DFS로 찾든 별 상관은 없고, 모든 노드를 한 번씩만 방문하기 때문에 $O(N)$으로 뚝딱 풀려요. 이 합이 K보다 클 때만 “Oh no”를 출력하면 됩니다. 대회 시작 21분 후 정답.

D. 히오스 프로그래머 / BOJ #16564

팀 목표레벨 T를 0과 $2 \times {10}^{9}$ 사이에서 이진 탐색하는 방식으로 풀었어요. 사실 대회에서는 T의 이론적 최댓값을 신경쓰지 않고 0과 ${10}^{12}$ 사이에서 탐색했어요. 왠진 모르겠지만 범위를 어디까지 잡아야 될지 감이 잘 안 와서..

탐색할 때마다 목표 레벨이 T일 때 올려야 하는 레벨 총합 $\sum \mathrm{max} (0, T-X_i)$를 K와 비교하는 방식이었어요. N이 1백만 이하이고 K가 10억 이하라서 int로 풀면 터지겠죠? 당연히 long long을 썼습니다.

올려야 하는 레벨 총합을 구하는 건 $O(N)$이고 목표 레벨 T를 탐색하는 건 $O\left(\log\left(2\times{10}^{9}\right)\right)$입니다. 따라서 이 문제도 선형 시간 안에 풀립니다. 이진 탐색 범위를 잘못 잡아줘서 한 번 틀리고, 대회 시작 32분 후 퍼스트 솔브.

E. N포커 / BOJ #16565

확률과 통계 문제입니다. 문제지에 숫자를 많이 끄적이게 됐던 거 같아요.

7개를 고를 때를 예로 들어볼게요. 문제의 그림에서 13개의 줄 중 세로줄을 한 개 고르고, 나머지 48장의 카드 중 3장을 고르면 됩니다. 이 때에는 경우의 수가 총 $$\binom{13}{1}\binom{48}{3}$$가지에요.

하지만 11개를 고른다면 어떻게 될까요? 일단 문제의 그림에서 세로줄을 한 개 고르고, 나머지 48장의 카드 중 7개를 고른다고 치면 고른 7장의 카드 중에 또 세로줄을 만드는 경우가 생길 수도 있어요. 이 때엔 세로줄을 두 개 고르고, 나머지 44장의 카드 중에 3장을 고르는 경우를 빼면 됩니다. 경우의 수는 $$\binom{13}{1}\binom{48}{7}-\binom{13}{2}\binom{44}{3}$$가지가 나오겠네요!

15개를 고른다면 어떻게 될까요? 위와 같이 생각한다면 중복을 빼 줄 때 세로줄이 3개 나오는 경우도 빠져버립니다. 따라서 세로줄이 3개 나오는 경우의 수를 다시 더해준다면 $$\binom{13}{1}\binom{48}{11}-\binom{13}{2}\binom{44}{7}+\binom{13}{3}\binom{40}{3}$$가지가 나옵니다.

이쯤 하면 대충 감이 오죠? 일반화할 수 있을 것 같아요. 위의 패턴을 보면 임의의 n에 대해 우리가 구하고자 하는 경우의 수는 $$\sum_{i=1}^{\lfloor n/4 \rfloor} {(-1)}^{i-1} \binom{13}{i}\binom{52 – 4i}{n – 4i}$$가지가 될 것 같고, 실제로도 그래요!

이항 계수를 구하는 게 또 문제인데요, 팩토리얼을 구해 나누는 걸로는 이항 계수를 구할 수가 없어요. long long의 범위는 $2^{63}-1$까지인데, $21! \approx 2^{65.46} $에서 이미 이 범위를 아득히 넘어버리기 때문에 위에 나온 $\binom{48}{7}$을 구하는 건 생각조차 할 수 없을 거에요. long double은 범위는 long long보다 크긴 한데, 엄청 커지면 정확도가 long long보다 못한 것도 있고요. 대신 재귀식 $$\binom nk = \binom{n-1}{k-1} + \binom{n-1}k$$을 쓰면 n ≤ 52, k ≤ 52, k ≤ n에 대해 이항 계수를 다이나믹 프로그래밍으로 전처리해 둘 수 있을 거에요. 숫자가 너무 커질 수도 있간 한데, 어차피 결과는 10,007로 나눈 나머지만 출력하면 되니까 모듈로 연산의 성질을 이용해 전처리할 때 모든 이항 계수는 10,007로 나눈 나머지를 저장하면 돼요.

이렇게 전처리해 둔 이항 계수를 이용하면 n이 얼마가 들어오더라도 최대 13개의 항만 더해서 $O(\lfloor n/4 \rfloor)$에 해결 가능합니다. 식을 잘못 짜서 맞기 전에 3번 틀리고, 대회 시작 1시간 1분 후 퍼스트 솔브.

F. 카드 게임 / BOJ #16566

나중에 알았는데, 이 문제는 원래 Champion 디비전의 F번으로 계획되었다고 합니다. 하지만 이 문제가 더 쉽다고 생각해서 Champion의 F랑 Master의 F를 바꿨다는 것 같습니다. (어쩐지 카드 문제만 연속으로 두 개가 나오더라고요)

여하튼, 처음엔 ‘아 이거 바이너리 서치 트리인가..?’ 하고 한 10분 동안 바이너리 서치 트리를 구현해 보려고 했는데, 트리 연습을 진짜 너무 안 했기 때문에 (게다가 위에서 언급했듯이 Kotlin 하느라 C++에서 struct 짤 일이 별로 없었기 때문에) 포기하고 ‘뭐 어차피 원래 목표는 5등 안에만 드는 거였으니까’ 하고 던지듯이 풀었어요. 근데 맞았습니다!! 이건 데이터가 좀 약했던 것 같아요.

일단 민수가 가져간 카드들을 정렬합니다. 그리고 M의 카드가 쓰였는지 안 쓰였는지 저장하는 플래그 배열을 하나 만듭니다. 이제 철수가 내는 카드의 값을 x라고 할 때, 민수의 카드에서 lower_bound로 x + 1을 찾아봅니다. 이게 아직 안 쓰였다면 바로 출력합니다. 쓰였다면 안 쓰인 카드가 나올 때까지 index를 하나씩 증가시켜 보고, 찾으면 출력합니다.

사실 이 방법은 최악의 경우 $O\left(K^2\log M\right)$이고 TLE가 나도 이상하지 않은 복잡도에요. 그냥 운이 좋았던 것 같아요! 문제를 제대로 풀었다고 말하긴 힘들 거 같지만 여하튼 대회 시작 1시간 47분 후 퍼스트 솔브.

정해는 index sort를 사용하는 것이라고 합니다. M ≤ N ≤ 4,000,000이라서 가능한 것 같은데, 정해로 다시 풀어봐야겠어요.


6문제를 전부 풀어 Master 디비전에서 우승했어요. 참가자로서 아마 처음이자 마지막일 교내대회에서 우승한 것이라 개인적으로도 의미가 큽니다. 참가자, 출제진 모두 수고하셨습니다. 좋은 대회 만들어 주신 운영진 분들께 감사합니다!

코딩하다 중간에 백스페이스가 안 먹어서 고생했지만 (나중에 알고 보니 일부 유학생 분들께서 키보드 언어 설정을 자국 언어로 바꿔 두셔서 그랬다는 것 같습니다) 오랜만의 오프라인 대회 너무 재밌었어요. 내년부터는 출제진이 될 것 같은데, 저도 노력해서 모두 재밌게 즐길 수 있을 만한 대회를 만들어보겠습니다 😊

수고하셨어요! 🎈

Camera2 API, 어떤 점이 다르고 어떻게 사용해야 할까?

이 글은 제가 하이퍼커넥트에서 인턴으로 있으면서 카메라 앱에서 Camera2 API를 활용할 수 있게 구현하고 사내에서 간단히 발표했던 것을 재구성한 포스트입니다. 발표자료는 SlideShare에서 보실 수 있습니다. (공개하기 곤란한 슬라이드들은 삭제되었습니다)

 

스마트폰이 나온 이후 휴대폰 카메라의 존재감은 갈수록 커지고 있습니다. 제조사들도 사용자들의 요구에 맞춰 스마트폰 카메라 성능을 나날히 진화시켜 가고 있습니다. 여행을 갈 때도 요즘은 디지털 카메라를 따로 갖고 가지 않기도 합니다.

하지만 안드로이드는 안드로이드 1.0(API 1; 2008년 9월 23일)에 만들어진 API를 롤리팝 5.0(API 21, 2014년 11월 12일)에서 교체될 때까지 적은 기능만 추가된 채 상당히 오랫동안 써 왔습니다. 사실 Camera API에서 기능이라고 할 만한 게 추가된 건 얼굴 인식 뿐이었습니다.

기존 API는 안드로이드 초기 버전에서 만들어진 만큼 카메라가 지금 이렇게까지 발전할 거라고는 생각하지 않았고, 컴팩트 카메라처럼 간단한 기능들만을 제공했습니다. 이런 점을 상당 부분 개선한 API가 Camera2 API입니다.

혼란을 막기 위해 여기서부터는 예전 카메라 API를 Camera1 API라고 부르겠습니다.

새로운 API

LG V20 카메라의 전문가 모드. 사진 © LGE

Camera2 API는 롤리팝 5.0(API 21)에 등장했습니다. 롤리팝 이후에는 Camera1 API는 deprecate 되지만, 계속 사용할 수는 있습니다.

Camera2는 Camera1이 지원하지 않던 많은 기능들을 새로 지원합니다. 몇 개만 예를 들어 보자면,

  • 3개 이상의 카메라를 쓸 수 있게 됐습니다. 파이 9.0(API 28) 이상에서는 여러 카메라를 동시에 쓸 수도 있습니다.
  • DSLR에서 흔히 볼 수 있는 수동 컨트롤을 지원합니다. Camera1 API는 초점을 맞출 위치만 정해 줄 수 있었지만, Camera2부터는 초점 거리를 정하거나 노출 시간, ISO 등을 API에서 직접 설정해 줄 수 있습니다.
  • 연사, RAW 지원 등이 추가됩니다.
2대의 후면 카메라. Camera1에서는 이 중 한 대는 쓸 수 없습니다. 사진 © LGE

파편화

하지만 새로운 API를 구현하기 전에 항상 생각해야 되는 것이 있습니다. 이게 과연 잘 될까입니다. 결론부터 말하자면 Camera2는 대부분의 경우 잘 되지만, 이상하게 동작하는 경우들이 없진 않습니다.

오픈소스 프로젝트 OpenCamera의 Camera2 관련 소스코드 앞부분. 으악!
심지어 샤오미 폰들 중에는 Camera2를 잘 구현해 놓고 일부러 서드파티 개발자들이 사용할 수 없게 막아둔 것도 있습니다.

그래서 이거 쓸 만 할까요?

  • Camera1이 더 이상 지원이 중단되었기도 하고,
  • Camera2가 지원하는 기능 자체가 너무 강력하며,
  • 후술할 새로운 동작 방식과 HAL(하드웨어 추상화 레이어)의 사용으로 Camera1보다 속도가 개선되었고,
  • 이제는 롤리팝 5.0(API 21) 이상의 점유율이 87%를 넘어가서(2018년 7월 23일까지) 많은 유저들이 Camera2의 프로페셔널한 기능을 사용할 수 있기 때문에

저런 이슈가 있음에도 Camera2를 구현할 만한 가치는 충분히 있습니다. 다만 Camera2를 지원하지 않는 API 21 미만의 기기들이나 Camera2에 버그가 많아 Camera1을 사용해야 하는 기기들을 위해 아직은 2개의 로직을 구현해야 할 것 같습니다.

어떻게 바뀌었나요?

Camera1과 다르게 Camera2 API는 파이프라인 모델으로 만들어져 있습니다.

새 Camera2 API는 파이프라인 모델입니다 © Google

Camera1은 API가 모든 걸 비동기로 처리해서 설정을 변경하거나 명령을 내리면 일부 메서드를 제외하고는 언제 값이 반영되는지, 제대로 반영이 되긴 했는지 알 수 없었습니다. Camera2의 새 구조는 이 점을 상당 부분 개선합니다. 모든 것이 API 내부에서 동기로 처리되어 콜백을 이용해 피드백을 받을 수 있습니다.

Camera2 API의 동작 순서도 © Google

동작 순서도를 보면 역시 Camera1에서는 못 보던 낯선 것들이 등장하는데요, 가장 낯선 부분이 아마 CaptureRequestCameraCaptureSession이 아닐까 싶습니다. 각 요소가 하는 일들은 다음과 같습니다.

CameraManager 시스템 서비스로서, 사용 가능한 카메라와 카메라 기능들을 쿼리할 수 있고 카메라를 열 수 있습니다.
CameraCharacteristics 카메라의 속성들을 담고 있는 객체입니다. (Camera1의 properties와는 다릅니다 – 속성을 가져오는 것만 가능하고, 속성을 정하는 건 다른 방식으로 가능합니다)
CameraDevice 카메라 객체입니다.
CaptureRequest 사진 촬영이나 카메라 미리보기를 요청(request)하는 데 쓰이는 객체입니다. 카메라의 설정을 변경할 때도 관여합니다.
CameraCaptureSession CaptureRequest를 보내고 카메라 하드웨어에서 결과를 받을 수 있는 세션입니다.
CaptureResult CaptureRequest의 결과입니다. 이미지의 메타데이터도 가져올 수 있습니다.
Camera2 API의 동작 순서도 © Google

이렇게 Session에 CaptureRequest를 보내는 것으로 API가 동작합니다. 사진 촬영뿐만 아니라 미리보기(Preview)CaptureRequest를 연속적으로 보내는 식으로 작동합니다. 이 때 Request에 캡쳐 설정을 같이 보내게 됩니다.

위의 그림을 참고하면 여러 개의 Surface로 버퍼를 보내고 있는데, SurfaceView를 사용해 바로 미리보기를 보낼 수도 있고, SurfaceTexture나 RenderScript를 이용해 후처리를 하게 할 수도 있습니다. 특이한 점은 ImageReaderMediaCodec으로 보내는 점인데, Camera2는 사진을 찍으면 바로 ByteArray를 주는 Camera1과는 달리 ImageReader로 Image를 줍니다.

여러 Surface로 보내는 게 가능하기 때문에, Camera1처럼 따로 버퍼의 Preview 크기나 Picture 크기를 정할 필요 없이 Surface의 크기에 맞춰 보냅니다. (다만 아직까지는 모든 Surface들의 크기의 높이 대 너비 비가 같지 않으면 이미지가 이상하게 늘어나는 버그가 많은 기기들에서 관찰됐습니다)

왜 이렇게 바뀌었나요?

카메라 작업들은 보통 꽤 시간이 걸리고, 동기되지 않아서 일어나는 문제들을 해결함과 동시에 속도 측면에서의 이점도 누릴 수 있기 때문입니다. 이미지가 카메라를 거쳐 기기가 사용 가능하도록 디코딩되기까지는 이미지 프로세싱이라는 일련의 과정들을 거칠 필요가 있습니다. 아래 그림을 봅시다.

이미지들이 설정 A로 잘 프로세싱되고 있는 모습을 볼 수 있습니다. 이미지 프로세싱에는 여러 단계가 있어서, 이런 식으로 여러 이미지가 동시에 처리될 수 있습니다.

Camera1은 전역적으로 설정을 적용합니다. 그런데 전역적으로 설정을 적용할 경우 만약 설정을 이미지가 프로세싱되고 있는 도중에 A에서 B로 바꾼다면 결과 이미지에서는 이렇게 A와 B가 섞여버리게 됩니다.

그래서 Camera1은 이렇게 이미지 하나가 전부 프로세싱되고 나서 설정을 새로 적용하고, 새 이미지를 프로세싱하고, 다시 설정을 새로 적용하고, …. 같은 식으로 처리합니다.

하지만 Camera2는 요청 자체에 설정을 첨부해서 보내기 때문에 Camera1과 같이 하나하나 처리할 필요가 없습니다. 각 단계마다 요청에 첨부된 설정을 확인하면 되기 때문입니다. 설정이 섞일 일도 없습니다.

물론 새 버전의 HAL을 활용하는 것도 있지만 이런 방식을 사용해서 Camera2는 Camera1보다 훨씬 빠른 이미지 처리가 가능해졌고, 최고 화질로 초당 30장의 사진을 찍는 연사도 가능하게 되었습니다. 기존에는 초당 1~3장 정도밖에 못 찍었던 것을 생각하면 굉장한 발전입니다.

참고로, Camera2는 많은 동작들에 Handler를 인수로 받아서 그 Handler에서 동기 작업을 합니다. (많은 분들이 Camera1의 작업들이 UI 스레드를 막는다는 걸 모르고 UI 스레드에서 Camera.open() 등의 작업을 하셔서 그런 게 아닐까 싶기도 합니다)

기존 앱에 Camera2 구현하기

일반적인 카메라 앱의 동작 방식

일단 API와 관계없이 앱이 어떻게 동작하는지 단계별로 쪼갠 후, 그에 맞게 기존에 Camera를 핸들하던 클래스를 추상화해서 Camera1과 Camera2 로직을 구현하면 됩니다.

Camera1과 Camera2의 코드 차이는 이 슬라이드쇼의 32쪽부터 47쪽에 걸쳐 확인해 볼 수 있습니다!

하지만 추상화를 잘 하고 API 레벨을 체크해 21 이상이면 Camera2를 쓰게 하더라도 모든 기기가 Camera2를 잘 지원하는 건 아닙니다. 제조사가 HAL을 잘 구현했다면 잘 될 거고, 아니면 안 될 겁니다.

Camera2를 제대로 지원하지 않는 기기에서 사용하려고 하면 끔찍한 크래시가 날 수도 있습니다

그렇다고 그런 소수의 기기들 때문에 Camera2가 제대로 지원되는 기기들이 좋은 기능들을 쓸 수 없게 되는 건 안타까운데요, Camera2의 좋은 기능들을 어떤 방식으로 제공해야 될까요?

일단 기기가 엄청나게 많다면 하나하나 테스트해 볼 수 있습니다. 화이트리스트를 만들어서 잘 되는 기기들을 넣으면 됩니다.

수많은 기기들 © Testmunk

하지만 기기가 그렇게 많지 않거나 저렇게 테스트할 수 있는 환경이 없다면 사용자들에게 잘 되는지 물어보는 방법도 있습니다. 카카오톡의 ‘실험실‘ 기능처럼요.

카카오톡 실험실.

API 21 이상이고 개발자가 테스트하지 않은 기기라면 사용자가 Camera2 기능들을 직접 사용해 볼 수 있도록 실험실에 ‘고급 카메라 기능 사용‘ 등의 항목을 넣어두는 것도 괜찮습니다. 해당 기기에서 많은 오류가 발생한다면 고쳐 보거나 고칠 수 없는 경우 지원을 하지 않으면 되고, 오류가 거의 발생하지 않았다면 화이트리스트에 추가하는 식입니다.

참고하면 좋은 자료

제로부터 시작했던 수험 생활

이 글은 지난 1년간 필자가 집에서 무슨 짓을 하고 살았는지에 대해 기술합니다. 무언가 많이 하긴 했습니다. 글이 상당히 깁니다.

시작

아무리 요즘 고등학교가 4년제라고는 해도 누가 고등학교 3학년 생활을 1년이나 더 하고 싶을까요? 같은 성적에 작년이었다면 분명히 최초합격할 수 있었던 학과였는데 올해 모의지원 결과를 보자니 합격 확률이 나날히 떨어지다가 결국엔 아예 가능성이 없다고 뜰 때의 절망감은 이루 말할 수 없을 정도입니다. 필자도 그랬습니다.

화학은 대체 뭐지…???

그 해 본 평가원 시험 중에서는 가장 잘 본 시험이 수능이었지만, 정작 그 수능 성적이 이랬습니다.

서울 상위권 대학을 목표로 하고 있었습니다만 여러 가지 이유로 높기만 했던 목표에 비해 고등학교 3학년 때 시험을 못 봤으며(후술), 암기로 거의 모든 게 해결되던 내신은 저에게는 정말 맞지 않아서 일반고에서 3등급 초반대를 꾸준히 유지했습니다. 물론 미적분I 같은 주요 과목에 5등급이 껴 있고 일본어나 정보 같이 자신 있던 비주요 과목이 1등급이고 하는 식으로의 3등급 초반대였습니다.

여하튼 필자는 재수를 할 자신이 전혀 없었기에 반수를 결심하고 2학기 휴학이 가능한 국립대에 지원을 합니다. 이 성적에 당연히 서울 상위권은커녕 서울 소재조차 아니었습니다. 그리고 최초합격을 합니다. 그러나..

안타깝게도 답장을 하지 못했습니다.

이 문자를 받고 마시고 취하는 대학 생활에 안주해 그냥 눌러앉아버리는 게 아닐까 – 부터 시작해서 과연 반수 생활을 제대로 할 수 있을지에 대해 여러 고민이 들기 시작했습니다. 결정적으로 친구들이 명문대학에 가는 게 정말 부러웠습니다.

그렇게 입학금을 반환받고, 돌아올 수 없는 재수의 강(재수강 아님)을 우발적으로 건너게 됩니다.

겨울

강대. 아 물론 제가 갔다는 얘기는 아니구요.

서울 지하철 2호선에는 수많은 명문대가 있습니다. 그 중 가장 빨리 졸업할 수 있는 곳이 바로 강대입니다.

물론 필자는 강남 대성학원에 갈 수 있는 성적조차 안 됐을 겁니다. 하지만 재수를 하려는 학생들은 보통 재수종합반이든 독학재수반이든 재수학원에 등록을 하고 1년간 고등학교처럼 다니는 것이 정석이므로 어디든 다니긴 해야 된다고 생각은 했습니다.

그래서 필자도 2월에 목동의 여러 재수학원을 돌아다니면서 설명을 들었습니다. 그러나 집이 그렇게 풍족하지 못한 관계로 집에서 독학을 하다가 나중에 재수학원에 등록하는 것으로 결정이 되었습니다.

언제까지일지 모를 집 독학을 시작하면서 자동적으로 인터넷 강의와 수능기출문제집을 활용한 공부를 시작하게 되었습니다. 그리고 이 때까지만 해도 단과학원을 제외하고는 11월까지 집에서 공부하게 될 줄은 몰랐습니다.

2월 말은 요즘은 절대 봄이라고 할 수 있는 날씨는 아니지만 계절과 플롯의 흐름을 통일시키기 위해 소제목을 그냥 봄이라고 합시다

재수를 시작하기 전, 17수능에서의 패인을 나름대로 구체적으로 분석했습니다. 올해는 어떤 식으로 공부를 해나가야 성적이 오르겠구나 – 라는 갈피를 잡기 위함이었습니다.

국어 과목은 원래부터 4등급 정도 나왔던 과목이기에 11월에 해던 대로만 한다면 2등급은 유지할 수 있을 것이라 생각했고, 화학도 그랬습니다. 영어도 절대평가로 전환되면서 90점이나 100점이나 같은 점수를 받게 되었고 80점대 성적을 받아도 대학에서 실질적으로 ‘까이는’ 점수가 적어서 별로 부담이 없었습니다.

문제는 수학과 생명과학이었는데, 수학은 2016년 모의고사들에서 전반적으로 쉽게 출제가 되어 왔으나 필자가 쉬운 문제에서 실수를 많이 했기에 당해 9월~11월에는 사설 봉투 모의고사를 풀면서 문제를 두 번씩 푸는 것을 연습했던 게 화근이었습니다. 17수능 수학은 절대로 쉽지 않았기에 뒷 문제를 안 보고 이런 식으로 풀어나가다가 18번을 불 때쯤 40분밖에 남지 않았던 것이었습니다. 생명과학은 지엽적인 개념을 숙지하지 않아서였습니다. 그런 이유로 수학은 일단 쉬운 문제를 빠르고 정확히 한 번에 풀 수 있는 기술을 단련해야 했고, 생명과학은 전반적으로 전체 개념을 다시 공부할 필요가 있다고 느꼈습니다.

재수생은 시간이 더럽게 많습니다. …적어도 8월 정도까지는 그렇게 느낍니다.

패인을 분석하고 나서 막상 재수를 시작해 보니 쓸 수 있는 시간이 엄청나게 많았습니다. 노트북과 스마트폰의 유혹에 쉽게 넘어가는 편이고 굳이 없애기도 귀찮아서 하루하루 공부 스케쥴을 짜기로 결심했습니다.

필자는 태어나서부터 열아홉 살때까지 ‘하루 스케쥴’이라는 것을 짜 본 적이 없었습니다. 집 독학을 시작하면서 처음으로 스케쥴을 짜 보게 되었습니다.

벽에 붙여놓고 볼펜으로 쓰기 굉장히 힘들었습니다. 하긴 계획표는 남 보여줄 건 아니니 저만 알아보면 됩니다.

아침에 일어나서 일어난 시간을 기준으로 당일 계획을 30분 단위로 짜고, 그대로 실전했습니다. 못 했을 경우엔 X표를 했고 다음 날에 전날 못 한 공부를 했습니다. 또한 공부하는 과목 순서는 실제 수능에서 응시하는 과목 순서대로 배치했습니다.

계획표를 짜 보고 나니 확실히 계획표를 짜서 공부하는 게, 피곤하거나 놀고 싶어서 계획을 조금만 짜더라도, 안 짜는 것보다 훨씬 효과적이라는 것을 알게 되었습니다.

2월에서 6월까지는 평가원 기출문제를 많이 풀고 개념을 다시 보는 위주의 공부를 했습니다. 굳이 빠르게 보려고 하지 않아도 시간이 엄청나게 많았기에 천천히 전부 두들겨봤습니다. 몰랐던 게 생각보다 엄청나게 많은 느낌이었습니다. 특히 생명과학이 그랬습니다. 개념 강의에서 교과서에 이런 내용이 나오긴 했었나 싶을 정도로 생소한 내용들이 별표와 동그라미로 등장했고, 그런 개념들은 이 때 다시 챙겨갔습니다.

3월, 4월 연합학력평가는 재수생이 고등학교 3학년 수험생(이하 ‘현역’)들과 같이 볼 수 없으니 시험이 치뤄진 다음날에 봤고, 1년 더 공부한 탓인지 한국사를 제외하고는 두 시험 모두 전부 1등급이 나왔습니다.

참고로 6월과 9월에는 학원이나 학교에서 시험을 응시할 수 있는데, 한 달 전쯤에 미리 신청해야 합니다. 응시료도 지불해야 합니다. 재수생이 현역보다 불리한 점은 수시모집을 제외하면 솔직히 이것밖에 없습니다.

여름

이 때 나태해지지 않으면 목표하는 대학은 거의 합격할 수 있을 겁니다.

국어 영역은 기분은 나쁘지만 백분위가 95.5 정도에서 반올림되면 충분히 저럴 수 있습니다.

그리고 6월 모의평가에서 쾌거를 이루게 됩니다. 수학만 빼고요. 수학 볼 때 졸았습니다. 결국 21번 29번 30번은 고사하고 18번 20번 22번(!) 26번 27번을 추가로 틀려버리는 아주 멋진 상황이 발생하게 됩니다.

그러나 ‘졸아서 4등급이었고 안 졸았으면 적어도 2등급이었을 것이다’라는 생각이 들기 시작했고, 7월에는 또 전과목 1등급을 받았습니다. 학력평가(3, 4, 7, 10월) 등급컷이 아무 의미가 없다는 걸 이 때 깨잘았어야 했는데 오히려 이 때부터 본격적으로 게을러지기 시작했습니다. 방이 더운데 에어컨이 없어서 TV가 있는 거실에 나와 공부하기 시작한 것도 한 몫 했고, 결정적으로는 실력을 자만하기 시작한 것입니다.

수험생의 적

재수생들은 다 이쯤에서 의욕을 잃는다는데 필자에게도 안 올 것 같던 시기가 그렇게 찾아왔습니다. 날마다 썼던 계획표가 점점 비었고, 어떤 날은 하루종일 휴대폰과 노트북만 붙잡고 있기도 했습니다. 나는 당장 수능을 보면 정말 잘 볼 텐데- 같은 생각을 하면서.

그래도 9월 모의고사가 다가오고 있는 것은 부정할 수가 없었으므로 슬슬 사설 봉투 모의고사를 풀기 시작했습니다. 8월 말이 되어서요.

이 수험생은 과연 9월에 어떻게 될까요? 스크롤을 내리지 말고 예측해 봅시다.

 

 

 

(미방)

 

 

 

가을

학교에 갈 낯이 없어 성적표조차 가져오지 않았습니다.

전체적으로 17수능보다 못 본 성적이 나왔습니다.

왜일까요? 6월까지 열심히 돌아본 개념이 부족했을까요? 아니면 실력이 부족했을까요?

아니었습니다. 전 과목에서 골고루 정말 말도 안 되는 실수들을 했던 것이었습니다. 틀린 16문제 대부분이 정말 터무니없는 실수들이었습니다. 어느 정도 터무니없는지 하나만 예로 들자면, 화학 I의 3번 문제에서

실선은 공유 결합, 점선은 수소 결합

분명히 실선인 결합 a를…

믿기지 않겠지만 점선으로 봐서 틀렸습니다.

어려운 문제는 다 맞아놓고(수학 21번 제외) 어떻게 남들은 일부러 틀리려고 해도 못 틀릴 문제들을 틀려놨는지 진지하게 고민해 봤고, 결국은 6~8월에 놀아서, 문제풀이에 익숙해지지 않게 되어서로 결론을 내렸습니다.

그러면 어떻게 해야 될까요? 다시 문제를 푸는 데 익숙해져야 할 것입니다. 이 시기부터는 문제 푸는 데 익숙해지기 위해, 그리고 소위 ‘킬러 문항’이라고 하는 어려운 문제들을 시간 안에 풀 수 있는 실력을 훈련하기 위해 봉투모의고사 위주의 공부를 하기 시작했습니다. 기출을 풀면서 킬러 문항도 접해봤겠지만, 그냥 ‘풀 수 있는 것’과 ‘시간 안에 풀 수 있는 것’은 다르다는 것을 느꼈습니다. 결국 수능은 시간 싸움이니까요.

또한 단과학원을 수강하게 되었습니다. 대치동이나 목동, 분당의 단과학원들은 재수학원보다 가격이 쌀 뿐더러 잘만 수강한다면 상당히 양질의 퀄리티의 사설 문제들을 매 주 풀어볼 수 있다는 장점이 있습니다. 재수생 자체가 단과학원에 잘 보이지 않기에 뭔지 모를 이질감이 들 수 있으나 뭐 3달만 다니면 되니까요.

아 수시는 묻지 말아주세요. 6개 모두 논술 썼습니다. 6군데 모두 떨어졌습니다. 감사합니다.

여담으로, 불안감은 사용함에 따라서 장애물이 될 수도 있고, 연료가 될 수도 있습니다. 정확히는 불안감과 확신이 균형잡혀 있을 때 최고의 연료가 됩니다. 당시 9월 모의고사를 보고 과연 수능은 작년보다 잘 보긴 할지 엄청나게 불안했는데요, 불안하기만 했다면 과연 제가 수능에서 긴장하지 않을 수 있었을지 모르겠습니다. 확실한 건 2월~6월에 착실하게 공부했더니 6월 모의고사 성적은 17수능에서 평균 3등급을 받았다고는 믿겨지지 않을 정도로 좋았었다는 것입니다(수학 제외). 하면, 됩니다. 9월은 안 해서 안 된 것이었습니다.

그렇게 수능까지 전력으로 달렸습니다.

수능 연기

연기 발표 당일에는 이 짓을 무려 7일이나 더 해야 된다는 사실에 절망하고 분노했습니다. 하지만 자연재해는 누군가의 탓을 할 수 있는 건 아니기에 화는 나지만 그냥 필자가 지구과학을 선택하지 않은 대가 중 하나라고 생각하고 있습니다.

탐구는 단기간에 성적을 올리기 좋은 과목입니다. 7일 동안엔 탐구 공부에 비중을 뒀습니다.

수능 당일

제가 여기서 본 건 아닙니다.

18수능은 17수능과 같은 시험장에서 보게 되었습니다. 당일 일찍 일어나 아침 5시 반에 출발해 6시에 일찍 도착해서 차에서 조금 졸다가, 7시 반에 교실에 입실했습니다. 아침은 속이 편하면서도 열량 높은 바나나 하나로 해결하고, 막대한 양의 초콜릿을 가져가 한 교시 한 교시 끝날 때마다 먹었습니다.

수능 당일 컨디션과 멘탈 관리는 정말 중요합니다. 당장 1교시 국어 첫 장에 적힌 글이 전혀 눈에 들어오지 않았습니다. 특히 1교시에 다른 수험생들이 1페이지를 다 풀고 나서 종잇장 넘기는 소리는 정말 신경쓰이는데요, 그래서 저는 그냥 2페이지부터 풀고 나서 1페이지를 풀었습니다. 그러면 종잇장 소리에 신경쓸 필요가 없어지니까요.

초콜릿은 살 안 쪄요. 살은 제가 쪄요.

점심은 평소에 먹는 대로, 피곤하지 않을 정도로 조금 적게 먹었습니다. 어차피 초콜릿이 열량을 다 해결해 줍니다. 초콜릿은 맛있습니다. 뭐 그 날 하루 많이 먹는다고 해서 살이 막 몇 kg씩 불어나는 것도 아니고 머리께서 잘 회전하시겠다는데 당연히 먹어줘야죠 어쩔 도리가 있겠습니까.

전체적으로 어렵긴 했지만, 국어 1페이지를 빼놓고는 그렇게 긴장하지 않았던 시험이었던 것 같습니다. 수능 직전까지 실전까지 연습하다 보면 분명히 본수능인데도 모의고사 푸는 느낌이 납니다. 분명히 모의고사 푸는 거 같은데 시험지 표시에 ‘모의고사’라는 글자가 없을 뿐입니다.

한 과목 한 과목 끝나면 과연 내가 맞게 풀었을까 하는 불안감이 들기도 하지만, 어차피 내 버린 OMR 그냥 잊고 편하게 다음 과목 봤습니다. 물론 쉬는 시간엔 굉장히 걱정했습니다.

수험표 뒤에 붙이는 답안지는 최대한 채워 오는 것이 좋습니다. 성적표 나오기 전까지의 정신건강에요.

탐구 영역까지 모든 시험이 끝나고 집에 돌아가는 길은 작년보다 홀가분했습니다.

다시 겨울

집에 돌아와서 떨리는 마음으로 저녁에 가채점을 해 봤습니다. 제 성적이라고는 믿을 수 없는 성적이었습니다. 다행스럽게도 이번엔 좋은 쪽이었습니다.

실감이 잘 나지 않았습니다. 수학에서 OMR 카드를 수정테이프로 몇 번씩 지우고 고치고 했는데 혹시나 테이프가 떨어지지는 않았을까, 잉크가 번지진 않았을까 하는 걱정에 성적발표 전날까지 불안했습니다.

그러나 쓸데없는 걱정이었습니다.

한국사를 제외하고 17수능에 비해 여덟 등급이 올랐습니다.

여름에 해이해지지 않았으면 전부 1등급도 가능하지 않았을까 하는 아쉬움도 남았지만, 그래도 정말 기뻤습니다. ‘재수하길 잘했어’를 되뇌었습니다.

노력해서 무언가 제대로 이루어본 적은 없었기에 의지를 갖고 생각하는 대로만 하면 이루어진다는 것을 배우게 됐다는 점에서 2017년 한 해는 지금까지 살아온 인생 중에서 분명 필자에게 가장 의미있었던 해였습니다.

지금은 정시 원서를 접수하고 결과를 기다리고 있습니다. 잘 될 것 같습니다.

작년엔 이렇게 살았습니다.

모든 캐릭터를 모으기 위해서는 얼마를 써야 하는가

가챠(뽑기)는 나쁜 문명입니다.

뜬금없이 웬 가챠냐고 하면, 요즘 게임을 ‘확률성 아이템’을 빼놓고는 이야기할 수 없을 정도이기 때문입니다. 물론 필자가 하고 있는 게임 대부분에도 확률성 아이템이 들어가 있습니다. 하지만 저는 확률성 아이템의 윤리성 같은 것을 논하는 현명한 소비자와는 꽤 거리가 있으므로, 전혀 반대의 논지, 즉 몇 가지 게임에서 ‘모든 캐릭터를 모으려면 얼마를 써야 할까?’(Shut up and take my money)를 중심으로 이야기해보겠습니다.

확률 계산의 기본

통계학에서 확률을 계산할 때 수학적인 표현을 위해 사용되는 개념들이 있습니다. 확률변수확률질량함수, 기댓값이 그들 중 하나입니다.

확률변수는 값과 확률을 갖는 수입니다. 보통 대문자로 표시합니다. 예를 들어 주사위를 던져서 나오는 수를 확률변수 $X$라고 할 수 있습니다.

확률질량함수는 확률변수와 그 값을 대응시켜 주는 함수입니다. $P\left(X=x\right)$과 같은 방식으로 표기합니다. 쉽게 말하자면, $P\left(X=x\right)$는 $X$가 $x$일 확률을 말합니다. 위에서 언급한 주사위를 던져서 나오는 수를 예로 들면,
\[P\left(X=x\right) = \dfrac{1}{6} \left(x = 1, 2, 3, 4, 5, 6\right)\]
이라고 표시할 수 있겠습니다.

그리고 기댓값은 말 그대로 확률변수에 기대하는 값입니다. 평균이라고도 하는 기댓값은 $E\left(X\right)$로 표기합니다. 주사위의 눈 같은 경우엔 평균 $E\left(X\right) = 3.5$입니다.

조작된 주사위. 거의 매번 7 혹은 11이 나오게 해 줍니다.

그러나 주사위 안쪽에 쇠 같은 걸 붙여 둬서 한 면만 나올 확률이 비정상적으로 높은 주사위가 있다고 생각해 봅시다. 예를 들어, 6은 나올 확률이 $\dfrac{95}{100}$고, 나머지는 나올 확률이 $\dfrac{1}{100}$밖에 안 된다고 생각해 봅시다. 이 때도 주사위를 많이 던졌을 때 평균 $E\left(X\right) = 3.5$라고 생각할 수 있을까요?

아닙니다. 이 때는 거의 6이 나올 것이므로 평균이 6에 가까우면 가까웠지 3.5에 가깝진 않을 겁니다. 그래서 평균, 즉 기댓값을 구할 때는 평균과 확률을 곱해 줘야 합니다. 이 때 기댓값은 이렇게 구할 수 있습니다.

\[E\left(X\right) = 1\times\dfrac{1}{100} + 2\times\dfrac{1}{100} + 3\times\dfrac{1}{100} + 4\times\dfrac{1}{100} + 5\times\dfrac{1}{100} + 6\times\dfrac{95}{100} = 5.85\]

5.85는 3.5보다는 조금 믿을 수 있는 숫자 같네요!

아무튼 이걸 일반화하면, $P\left(X=x_i\right) = p_i \left(i=1, 2, \ldots, n\right)$일 때 아래와 같이 적을 수 있습니다.
\[E\left(X\right) =\sum_{i=1}^{n} {x_i}{p_i}\]
또한 보이다시피 $E\left(X\right)$는 ${x_i}{p_i}$들의 합으로 이루어져 있기 때문에, $E\left(aX+b\right)=aE\left(X\right)+b$, $\sum E\left(X\right)=E\left(\sum_{}^{} X\right)$ 등도 성립합니다.

모든 카드를 얻으려면 – 등급별 가중치가 없을 때

여러 가지 게임들의 예를 들어 보겠습니다만, 일단 ‘사운드 볼텍스’의 예를 들어 보겠습니다. 사운드 볼텍스는 리듬게임이지만 스토리를 진행함에 있어 높은 등급의 카드를 뽑는 것이 거의 필수적입니다. 등급이 나누어져 있긴 하고 실제로 중복 카드를 일부러 더 잘 나오게 설정했다는 게 체감된다고 하지만, 일단은 실제 확률이 고지되어 있지 않으므로 등급별 확률이 정해져 있지 않고 모든 카드가 나올 확률이 같다고 가정하겠습니다.

‘사운드 볼텍스 IV’의 PUR 등급 카드 중 하나의 모습. 필자도 갖고 있습니다.

일단 몇 가지를 가정해 봅시다.

  1. 카드는 한 번 뽑는 데 1,000원입니다.
  2. 카드는 한 장 씩 뽑고, 다음 카드를 뽑기 전에 카드를 확인합니다.
  3. 카드는 전체 $n$종류입니다. 각 카드 종류가 등장할 확률은 $\dfrac{1}{n}$입니다.
  4. $n$종류의 카드를 전부 뽑으면 더 이상 뽑지 않습니다.
  5. 게임에서는 이미 나온 카드를 10번 다시 뽑으면 다음 한 장은 중복이 아님이 보장되지만, 여기서는 무시합니다.

이 때 우리는 평균적으로 카드를 총 몇 장 뽑아야 모든 종류의 카드를 뽑을 수 있을까요? 즉 뽑아야 하는 카드 수를 확률변수 $X$라고 둘 때 $\left(X\right)$는 얼마일까요?

그냥 구하고자 하니 막막합니다. 조금 더 쉬운 방법을 생각해 봅시다. 이미 $i-1$종류의 카드를 모았을 때 새로운 종류의 카드를 모으는 데 뽑는 횟수를 확률변수 $Y_i$라고 두면 $X = Y_1 + Y_2 + Y_3 + \ldots + Y_n$으로 생각할 수 있습니다.

 

 

이렇게 하면 $P\left(Y_i = k\right)$는 $i-1$종류를 뽑은 상황에서 $k$번째에 새로운 종류의 카드를 뽑은 셈이 되므로, $k-1$번은 원래 뽑았던 카드 $i-1$종류 중 하나를, 마지막에는 남은 카드 종류 $n-\left(i-1\right)$개 중 하나를 뽑는 셈이 됩니다. 즉,

\[P\left(Y_i = k\right) = {\left(\dfrac{i-1}{n}\right)}^{k-1}{\left(1-\dfrac{i-1}{n}\right)}\]

가 됩니다. 식이 나왔으니 카드 $i-1$종류가 있을 때 새로운 종류의 카드를 뽑으려면 몇 장을 뽑아야 하는지에 대한 기댓값을 구할 수 있는데요, 이론적으로는 무한 장 뽑아도 새 종류가 안 나올 수도 있으니 $k$에는 사실상 1부터 무한대까지 들어갈 수 있겠습니다. 그러므로,

\[E\left(Y_i\right) =\sum_{k=1}^{\infty} kP\left(Y_i = k\right)\]
\[=\sum_{k=1}^{\infty} k{\left(\dfrac{i-1}{n}\right)}^{k-1}{\left(1-\dfrac{i-1}{n}\right)}\]

식이 복잡하므로 $\dfrac{i-1}{n} = r$으로 치환하고 계속 계산해 보면,

\[=\sum_{k=1}^{\infty} k{r^{k-1}{\left(1-r\right)}}\]
\[=\left(1-r\right)\sum_{k=1}^{\infty} kr^{k-1}\]

여기서 $r$이 1보다 작으므로 위의 멱급수는 무한등비급수의 합을 이용해 계산할 수 있습니다. 항등식 $\sum_{k=1}^{\infty} r^{k} = \dfrac{1}{1-r}$에서 양변을 $r$에 대해 미분하면 $\sum_{k=1}^{\infty} kr^{k-1} = \dfrac{1}{{\left(1-r\right)}^2}$이므로, 이를 이용해서 정리하면

\[E\left(Y_i\right) = \left(1-r\right)\dfrac{1}{{\left(1-r\right)}^2}\]
\[= \dfrac{1}{1-r}\]

라는 꽤 간단한 식이 됩니다. 최종적으로 $r = \dfrac{i-1}{n}$을 다시 대입하고 정리해 주면

\[E\left(Y_i\right) = \dfrac{n}{n-i+1}\]

입니다.

처음에 $X$를 $n$개의 $Y_i$로 쪼갰으니까 $X = \sum_{i=1}^{n} Y_i$라고 쓸 수 있겠습니다. 앞서 언급한 기댓값의 정의에 의해

\[E\left(X\right) = E\left(\sum_{i=1}^{n} Y_i\right) = \sum_{i=1}^{n} E\left(Y_i\right)\]

이므로, $E\left(Y_i\right) = \dfrac{n}{n-i+1}$를 대입하면

\[E\left(X\right) = \sum_{i=1}^{n} \dfrac{n}{n-i+1}\]

입니다. 여기서 $u = n-i+1$, 즉 $i = n-u+1$로 치환해 버린다면 1에서부터 $n$까지의 $i$의 범위는 $n$에서부터 1까지의 $u$의 범위가 되고, 시그마는 범위가 반대여도 결과는 같으므로 식은

\[E\left(X\right) = \sum_{u=n}^{1} \dfrac{n}{u} = n\sum_{u=1}^{n} \dfrac{1}{u}\]

이 나옵니다. $\sum_{u=1}^{n} \dfrac{1}{u}$는 달리 간단히 할 방법이 없으므로 여기서 만족하고 Wolfram|Alpha에 맡기도록 합시다.

적용

이제 식에 대입하는 일만 남았습니다! 만약 카드 한 세트가 총 31장이라고 하고 31장 안에서만 카드가 나온다고 한다면, $n = 31$일 때 $E\left(X\right)$는

\[E\left(X\right) =31\sum_{u=1}^{31} \dfrac{1}{u} \approx 124.84460\]

이므로, 약 124,845원을 넣으면 모든 카드를 수집할 수 있다는 뜻이 되겠습니다! 물론 실제 게임에서는 이미 나온 카드를 10번 다시 뽑으면 다음 한 장은 중복이 아님이 보장되지만 이를 무시하고 계산한 것이기에 숫자가 현저히 크게 나오는 감도 없지 않습니다.

모든 아이돌을 프로듀스하려면 – 등급별 가중치가 있을 때

그러나 많은 게임들은 그렇게 호락호락하지 않습니다. 바로 등급에도 확률을 부여하기 때문입니다.

‘아이돌마스터 신데렐라 걸즈 스타라이트 스테이지’의 SSR 봉투.

대표적으로 ‘아이돌 마스터 신데렐라 걸즈 스타라이트 스테이지’는 노멀, 레어, S레어, SS레어의 4개 등급의 카드를 만들어 놓았습니다. 5명의 아이돌을 유닛으로 편성해 즐기는 리듬게임인데, SS레어 아이돌들이 점수와 직결되는 합계 어필 수치가 현저히 높고 부가 능력치도 훨씬 좋기 때문에 S레어 5인으로 덱을 구성해 게임을 하는 것보다 SS레어 5인으로 구성하는 것이 훨씬 점수가 잘 나와서 높은 점수를 얻으려면 SS레어 아이돌의 존재는 필수적입니다. 결정적으로 일러스트가 상당히 예뻐서 수집욕구를 불러일으키기도 합니다.

하지만 이 게임은 SSR를 얻을 수 있는 확률은 1.5%라고 공지해 두고 있습니다. 결국 98.5%는 S레어 이하의 등급이라는 뜻이죠. 그러면 모든 종류의 SSR 아이돌을 얻기 위해서는 얼마만큼의 돈이 필요할까요?

몇 가지를 가정하겠습니다.

  1. 아이돌은 한 번 스카우트하는 데 스타 쥬얼 250개가 필요합니다. 스타 쥬얼 0.85개는 1엔입니다.
  2. 아이돌은 한 명 씩 스카우트하고, 다음 아이돌을 스카우트하기 전에 아이돌의 이름을 기억해 둡니다.
  3. SS레어 아이돌은 전체 $n$명입니다. 각 아이돌이 등장할 확률은 등급 내에서 $\dfrac{1}{n}$입니다. 한정 아이돌은 한정으로 생각하지 않습니다.
  4. SS레어 아이돌이 등장할 확률은 $p$입니다.
  5. $n$명의 SS레어 아이돌을 전부 스카우트하면 더 이상 스카우트하지 않습니다.

이번에도 사운드 볼텍스에서 계산했던 것과 같이 확률변수 $X$를 $n$개의 $Y_i$로 쪼개서 계산합시다. 하지만 이번에는 SSR가 아닌 아이돌은 고려하지 않습니다. 저번처럼 $P\left(Y_i = k\right)$는 $i-1$명을 스카우트한 상황에서 $k$번째에 새로운 아이돌을 스카우트한 것인데, $k-1$번은 원래 스카우트했던 SSR 아이돌 $i-1$명 중 하나 또는 SR 이하 아이돌을, 마지막에는 SSR 등급에 아직 스카우트하지 못한 아이돌 $n-\left(i-1\right)$명 중 하나를 뽑는 셈이 됩니다.

여기서 SSR 등급에 남은 아이돌 $n-\left(i-1\right)$명 중 한 명을 스카우트하는 확률은 $p\left(1-\dfrac{i-1}{n}\right)$입니다. 원래 스카우트했던 SSR 아이돌 $i-1$명 중 하나 또는 SR 이하 아이돌을 스카우트하는 경우는 전체 카드 중 SSR 등급에 아직 스카우트하지 못한 아이돌 $n-\left(i-1\right)$명 중 한 명을 제외하고 누구를 스카우트하든 상관없는 경우이므로, 확률은 $1 – p\left(1-\dfrac{i-1}{n}\right)$이라고 할 수 있겠습니다. 따라서,

\[P\left(Y_i = k\right) = {\left(1 – p\left(1-\dfrac{i-1}{n}\right)\right)}^{k-1}{\left(p\left(1-\dfrac{i-1}{n}\right)\right)}\]

계산하기 쉽게 $p\left(1-\dfrac{i-1}{n}\right) = s$로 놓으면

\[P\left(Y_i = k\right) = {\left(1 – s\right)}^{k-1}{\left(s\right)}\]

$1-s=r$로 놓으면

\[P\left(Y_i = k\right) = r^{k-1}{\left(1-r\right)}\]

으로 지난번과 똑같은 형태가 됩니다. 다만 $r$ 안의 식이 지난번과 다를 뿐입니다.

역시 이론적으로는 무한 번 뽑아도 안 나올 수 있으므로 지난번과 같은 계산을 하면

\[E\left(Y_i\right) = \dfrac{1}{1-r} = \dfrac{1}{s}\]
\[= \dfrac{n}{p\left(n-i+1\right)}\]

이 됩니다. $E\left(X\right)$도 계산해 보면
\[E\left(X\right) = \sum_{i=1}^{n}\dfrac{n}{p\left(n-i+1\right)}\]
\[= \dfrac{1}{p}n\sum_{i=1}^{n}\dfrac{1}{\left(n-i+1\right)}\]
이므로, 앞서 $\sum_{i=1}^{n}\dfrac{1}{\left(n-i+1\right)} = \sum_{u=1}^{n}\dfrac{1}{u}$로 계산한 것과 같이

\[E\left(X\right) = \dfrac{n}{p}\sum_{u=1}^{n}\dfrac{1}{u}\]

가 됩니다. 따라서 기댓값은 등장 확률에 반비례함을 알 수 있습니다.

적용

데레스테 SSR 소유율이라는 사이트에 의하면 현재(2017년 8월 13일) SSR 아이돌은 총 127명입니다. (통상 70명, 한정 57명) 또한, SSR 확률은 1.5%이므로 $p = \dfrac{3}{200}$입니다.

한정 아이돌을 고려하지 않고 127명이 가챠에서 모두 나올 수 있다고 가정하면, $n = 127$일 때

\[E\left(X\right) = \dfrac{200\times 127}{3}\sum_{u=1}^{127}\dfrac{1}{u}\]

\[\approx\dfrac{200\times 127}{3}\times 5.4253346\approx45934.5\]

이므로, 평균적으로 스타 쥬얼을 11,483,625(1148만 3625)개, 즉 구매량에 따른 효율에 따라 평균적으로 13,353,052엔(1335만 3052엔, $\approx$ 1.35억원)을 과금하면 SSR 아이돌을 전부 모을 수 있습니다.

반면 통상 아이돌 70명만 고려한다면, $n = 70$일 때

\[E\left(X\right) = \dfrac{200\times 70}{3}\sum_{u=1}^{70}\dfrac{1}{u}\]

\[\approx\dfrac{200\times 70}{3}\times 4.8328368\approx22553.2\]

이므로, 이 경우엔 스타 쥬얼 5,638,300개가 필요합니다. 그러므로 평균적으로 6,633,294엔(663만 3294엔, $\approx$ 0.670억원)을 과금하면 통상 SSR 아이돌을 전부 모을 수 있습니다.

신데렐라 페스 한정 아이돌, SSR 마에카와 미쿠. 한 아이돌은 보통 여러 카드에 등장합니다.

6월 말에 신데렐라 페스를 진행했을 때 SSR 확률이 3%로 고정되었습니다. 이 때의 $p = \dfrac{3}{100}$이므로 페스 기간 동안에만 가챠를 돌린다면, 소모되는 비용은 등장 확률에 반비례하기 때문에 현재는 위에 적힌 가격의 반값으로 전부 스카우트하는 것을 기대해 볼 수 있습니다.

스타 쥬얼을 얻을 수 있는 경로가 필요한 스타 쥬얼의 양에 비해 꽤 적은 비율이지만 과금 외에도 존재하므로 이를 고려한다면 위에 적힌 가격보다는 적을 수도 있습니다.

모든 용사를 얻으려면 – 등급별 가중치와 결제 한정 캐릭터를 고려할 때

용사에게 등급이 있지만 4성 이후로는 등급을 올리는 게 가능해 오히려 도감을 채우기 위해 5성 이상보다는 4성이 선호되는 게임 ‘크루세이더 퀘스트’

‘크루세이더 퀘스트’는 특이한 게임입니다. 뽑기로 얻을 수 없는 ‘전설 용사’를 제외하고 1~3성 용사는 ‘일반 용사’, 4~6성은 ‘고급 용사’로 분류됩니다. 용사에 등급이 매겨져 있는 건 다른 게임과 다를 게 없으나, 용사들은 조금의 노력으로 더 높은 단계로 승급할 수 있습니다. 2~4성으로의 승급은 아예 랜덤이지만 5~6성으로의 승급은 고정됩니다. 예를 들어 3성 가챠레인저B는 4성 바이올렛으로 승급이 가능하지만, 4성 바이올렛이 승급하면 5성 인형사 바이올렛, 6성 마법인형사 바이올렛이 고정되는 식입니다.

전설 용사 ‘병아리’. 게임을 시작할 때 바로 얻을 수 있습니다.

하지만 고급 용사는 또 ‘승급 용사’와 ‘계약 전용 용사’로 나뉩니다. 계약 전용 용사는 보석을 5~6개 소모하는 ‘황금 계약서’에서 확률적으로 나옵니다. 그러면 모든 ‘계약 전용 용사’를 얻기 위해서는 얼마가 필요할까요?

이번의 조건은 다음과 같습니다.

  1. 용사는 연속으로 계약한다고 가정합니다. 첫 번째 계약 가격을 무시하고, 한 번 계약하는 데 보석 $5$개를 소모합니다. 보석 1개는 550원입니다.
  2. 용사는 한 명 씩 계약하고, 다음 용사를 계약하기 전에 용사의 이름을 확인합니다.
  3. 4성 이상의 용사는 전체 $n$명입니다. 각 용사가 등장할 확률은 $\dfrac{1}{n}$입니다. 이 중 한정 용사는 $m$명입니다.
  4. $n$종류의 용사와 모두 계약하면 더 이상 계약하지 않습니다.
  5. 게임에서는 10명씩 계약하면 마지막 1명은 4성 이상이 보장되지만, 여기에서는 고려하지 않습니다.
  6. 게임에서는 기간 한정으로 특정 용사의 계약확률이 증가하지만, 여기에서는 고려하지 않습니다.

앞서 확률이 $p$인 등급의 아이돌 $n$명을 전부 스카우트할 때의 기댓값은

\[E\left(X\right) = \dfrac{n}{p}\sum_{u=1}^{n}\dfrac{1}{u}\]

이었습니다. 여기서 ‘모든 계약 전용 용사’를 4~6성 내의 또 하나의 등급으로 생각한다면, 4~6성 내에서 계약 전용 용사와 계약할 확률은 $\dfrac{m}{n}$이므로 더 복잡한 계산을 할 필요 없이 모든 계약 전용 용사와 계약했을 때 계약 횟수에 대한 기댓값은

\[E\left(X\right) = \dfrac{n}{\dfrac{m}{n}p}\sum_{u=1}^{m}\dfrac{1}{u}\]

\[= \dfrac{n^2}{mp}\sum_{u=1}^{m}\dfrac{1}{u}\]

이 됩니다.

적용

황금 계약서에서 4성 이상의 용사가 나올 확률은 19%입니다. 또한 용사등급표에 따르면 현재(2017년 8월 13일) 크루세이더 퀘스트에는 계약서로 획득할 수 없는 이벤트, 전설 용사를 제외하고 승급 용사 43명, 계약 용사 58명이 있으므로 $n = 43 + 58 = 101$, $m = 58$, $p = \dfrac{19}{100}$으로 두면

\[E\left(X\right) = \dfrac{101^2 \times 100}{58 \times 19}\sum_{u=1}^{58}\dfrac{1}{u}\]

\[\approx \dfrac{101^2 \times 100}{58 \times 19} \times 4.646254 \approx 4300.95\]

이므로 평균적으로 보석을 21,505개, 즉 11,827,750원(1182만 7750원)을 과금하면 모든 계약 용사를 얻을 수 있습니다. 물론 이 게임은 보석을 획득할 수 있는 경로가 과금 이외에도 굉장히 다양하고 계약 용사 확정을 고려하지 않았으므로 실제 과금액은 이보다 현저히 적으리라 예상됩니다.

정리

확률형 아이템이 게임을 진행하는 데 중요한 요소가 되는 대표적인 게임 ‘아이돌 마스터 신데렐라 걸즈 스타라이트 스테이지’. 물론 여기다 쓸 돈을 다른 데다 쓰는 게 나을 수도 있겠지만, 적어도 자동차에 쓰면 자동차가 춤추고 노래하진 않을 것 같습니다.

계산하면서 큰 값이 나오리라고는 예상하고 있었지만, 예상을 훨씬 웃도는 숫자들이 나오면서 많이 놀랐습니다.

특히 ‘아이돌 마스터 신데렐라 걸즈 스타라이트 스테이지’의 경우 모든 아이돌을 모으는 데에 평균적으로 몇 천만원대의 과금이 필요하다는 것을 계산하고 나서는 차라리 자동차를 사는 게 낫다고 생각될 수도 있겠지만, 역시 자동차가 춤추고 노래하진 않기에 나름의 의미가 있다고 생각합니다.

마지막으로, 언급된 모든 게임들이 캐릭터를 모두 모으지는 않아도 진행하는 데에 큰 무리는 없으므로, 언급된 가격들은 전부 모으실 게 아니라면 ‘이렇게 큰 숫자가 나오는구나’ 라고 생각해 주시길 부탁드리겠습니다.

기억하기 쉽고 안전한 비밀번호

[latexpage]
‘기억하기 쉽고 안전한’ 비밀번호?

인터넷을 사용하다 보면 어느 서비스든 회원가입을 할 때가 생깁니다. 그리고, 회원가입을 하려면 대부분 비밀번호를 새로 만들어야 합니다. 예전에는 쉽게 만들었던 것 같은데, 대문자 소문자 숫자 특수문자를 다 써서 만들라니 기가 찹니다.

비밀번호 생성기를 켜 봅시다. 인터넷뱅킹에 쓰려고 10자리의 비밀번호를 만들었더니 bet8qU_r#u라는 한 눈에 봐도 강력해 보이는 비밀번호가 나왔습니다. 근데 별로 기억하기는 쉽지 않아 보입니다. 그래도 은행 비밀번호인데 어디다 적어 두자니 남이 볼까 두렵고, 외우자니 시간이 꽤 걸릴 것 같습니다.

‘기억하기 쉬운 비밀번호’와 ‘안전한 비밀번호’는 모순적인 존재들인 것 같습니다. 그런데, 정말 그럴까요?

안전한 비밀번호

  • 이미 비밀번호가 충분히 안전하신 분들께서는 이 부분을 스킵하고 ‘기억하기 쉬운 비밀번호‘부터 보셔도 됩니다!

애초에 ‘안전한 비밀번호’를 왜 만드는 걸까요? 보통은 원하지 않는 사람이 멋대로 내 계정으로 로그인하지 못하게 하기 위함입니다. ‘원하지 않는 사람’이라 함은 비밀번호를 멋대로 알아낼 수 있는 – 일반적으로는 – 해커들이죠.

일단 우리가 가입한 사이트는 비밀번호를 암호화해서 저장한다고 가정합시다. (사실 모든 사이트가 그래야 하지만요. 2017년에 평문으로 비밀번호 저장하는 사이트를 구축하는 웹 개발자는 당장 해고해야 마땅합니다.)

그럼 해커는 어떤 방식으로 비밀번호를 알 수 있을까요? 만약 우리의 암호화된 비밀번호를 입수했다고 해도, 무차별 대입 공격(bruteforcing) 외에는 방법이 없습니다.

암호화는 이런 방식으로 동작합니다. 만약 제가 이 사이트의 관리자 비밀번호를 shift.moe123으로 설정했다고 합시다. 그러면 서버는 (SHA-256 알고리즘을 쓴다면) 비밀번호를 그대로 저장하는 게 아니라, 이런 식으로 저장합니다:

98086156AA56FE8A7D5AC35D4EA21A49A776505B869CC76829CCD93BAC91A3F9

이것을 해시라고 합니다. 해시는 비밀번호마다 다릅니다. 그래서 서버가 맞는 비밀번호인지 체크하려면 사용자가 입력한 비밀번호를 해시로 만들어서 그 값이 똑같은지 체크합니다. 예를 들어 shift.moe123의 해시 값은 항상 위의 해시 값과 같습니다.

그리고 비밀번호가 조금만 바뀌어도 해시 값은 몰라보게 변합니다. 가령 딱 한 글자만 바꾼 shift.moe124의 SHA-256 해시는

66CFE1B558388800107E5E0CE4AADE6866F8FCE147D7D41108D7E930AD923DD5

입니다. 위의 해시와 아래 해시는 전혀 연관이 없어 보입니다.

해시를 통해 원래 비밀번호를 알 수 있는 방법은 … 두 가지가 있습니다. 무작위로 대입해 보는 방법과 암호화 알고리즘을 분석해 알아내는 방법이 있는데요, 후자는 현재로서는 몇십 년동안 천문학적인 액수를 투자해 해시 하나를 풀 수 있습니다. 해커들은 당연히 그럴 만한 가치를 느끼지 못하고 무작위 대입을 시작하는 것입니다.

무작위 대입 전략

해커가 만약 사이트의 모든 유저에 대한 정보 – 비밀번호 해시 값을 포함해서 – 를 담고 있는 데이터베이스를 입수했다고 합시다. 이 때 타겟은 누구일까요? 보통은 어떻게든 해시 값을 생성해서 얻어걸리는 사람의 계정을 탈취해 갈 것입니다. 어떤 계정이든, 로그인만 할 수 있다면 그걸로 카페에 들어가서 게시글을 도배하든 금융거래를 하든 나름대로의 의미가 있을 테니까요.

일단 해커는 먼저 사람들이 가장 자주 사용하는 비밀번호들부터 대입해 볼 것입니다. 1234, 123456, qwerty 같은 비밀번호들이 대표적인 예입니다. 가장 먼저 얻어걸리는 비밀번호들이죠. 위 사이트에 의하면, 아직도 저 리스트에 있는 상위 1,000개의 비밀번호를 전체 91%의 사용자들이 사용하고 있다고 합니다. 보통 SHA-256 키 하나를 대입하는 건 초당 260만번 할 수 있으니 위의 리스트에 있는 비밀번호를 사용 중이라면 고작 0.001초도 안 되어 전부 드러나버릴 수 있습니다.

그런데 요즘은 사이트에서 회원가입을 할 때부터 이런 비밀번호를 못 쓰게 막고 있습니다. 그런 사이트에서는 저런 비밀번호를 사용하는 사람이 애초에 없다는 것일 테고, 해커가 얻어갈 수 있는 이득도 없다는 거나 마찬가지입니다.

그런 해커들이 다음으로 시도해 보는 게 무작위 단어 대입입니다. 사전에 있는 단어들을 조합해서, 처음부터 끝까지 대입해 보는 것이죠. 만약 사전에 있는 단어만으로 만들어진 비밀번호라면 사전에 적혀 있는 단어 수에 따라 다르겠지만, 영어 단어 30만개를 대입한다면 단어 한 개짜리 비밀번호는 대략 0.115초만에, 단어 두 개짜리 비밀번호는 길게는 9시간 35분까지 걸리겠네요. 다시 말하지만 해커는 수많은 정보 중 얻어걸리기만 하면 되기 때문에 9시간 35분은 투자할 가치가 있는, 굉장히 짧은 시간입니다.

무작위 단어 대입을 해도 별 수확을 못 얻었다면 모든 문자를 무작위로 대입하기 시작합니다. 그런데 이건 단점이 조금 있습니다. 비밀번호가 한 자리수 늘어날 때마다 시도해야 되는 가짓수도 배로 늘어난다는 겁니다.

만약 숫자로만 된 비밀번호를 먼저 때려맞추자고 합시다. 숫자는 총 10개가 있으니까 한 자리에 올 수 있는 글자가 10개입니다. 그러니까, 한 자리수 비밀번호를 맞추려면 10번 시도하면 됩니다. 두 자리수는 $10 \times 10 = 100$번 시도하면 되겠군요, $n$자리수의 비밀번호에 대해서는 $10^n$번 시도하면 풀리겠죠?

초당 260만번 대입할 수 있다고 했으니, 4자리 비밀번호는 $\dfrac{10^4}{2,600,000} \approx 0.000385$초, 8자리 비밀번호는  $\dfrac{10^8}{2,600,000} \approx 38.466$초가 걸리겠군요. 한 자리가 늘어날 때마다 걸리는 시간은 10배씩 늘어날 겁니다. 그럼 여기에 알파벳 소문자를 섞으면 어떨까요?

알파벳 소문자는 총 26문자가 있으니까 이걸 숫자와 섞으면 한 자리에 총 36개의 문자가 올 수 있고, $n$자리수의 비밀번호에 대해서는 $36^n$번 시도하면 풀리겠습니다. 4자리 비밀번호는 $\dfrac{36^4}{2,600,000} \approx 0.6460$초, 8자리 비밀번호는  $\dfrac{36^8}{2,600,000} \approx 1,085,042.3$초, 즉 12일 13시간 24분 가량이 걸립니다. 같은 8자리인데, 숫자만 썼을 때는 1분도 안 되던 게 소문자만 섞었는데도 2주가 가까히 걸리게 되었습니다.

그럼, 걸리는 시간을 표로 정리해 보겠습니다.

글자 수 4글자 8글자 10글자 12글자
숫자 10 0초 38초 1시간 4분 4.45일
소문자 26 0초 22시간 18분 1.72년 1,163년
숫자
+ 소문자
36 1초 12.56일 44.59년 5.78만 년
숫자
+ 소문자
+ 특수문자(8)
44 1초 62.54일 331.7년 64.2만 년
숫자
+ 소문자
+ 대문자
62 6초 2.66년 1.02만 년 3935만 년
숫자
+ 소문자
+ 대문자 +
특수문자(8)
70 9초 7.03년 3.45만 년 1.69억 년

이런 이유로 많은 사이트들은 숫자, 소문자, 대문자, 특수문자를 섞어서 비밀번호를 만들 것을 권장하고 있습니다.

문제가 있다면, 숫자, 소문자, 대문자, 특수문자를 전부 섞어서 비밀번호를 정말 복잡하게 만들었는데, 이걸 기억하기가 어렵다는 것입니다.

기억하기 쉬운 비밀번호

그러면 ‘기억하기 쉬운’ 건 무엇일까요?

사람마다 기억하기 어렵고 쉬운 것은 다르겠지만, 일반적으로는 비밀번호에 어떤 의미를 부여하면 기억하기 쉬워지는 것 같습니다. 아무 의미도 없는 이상한 문자열 말고, 예를 들어.. 제가 지금 배고프니까 음식 이름으로 비밀번호를 만들어 봅시다. 비밀번호를 뚫는 데 얼마나 걸릴지는 여기에서 테스트해 볼 수 있습니다.

최근 가격인상으로 말 많은 BBQ 치킨입니다. #Golden_Olive_Chicken이라는 비밀번호를 생각해낼 수 있겠습니다. 위 사이트에 넣어 본 결과 이 비밀번호를 뚫는 데는 1해 7,600경($=1.76\times10^{20}$)년이 필요하다고 합니다. 숫자는 없지만 대소문자와 특수문자가 적절하게 섞였고, 기억하기 쉬우면서 무려 21글자나 됩니다. 배고플 때는 로그인하기 조금 그렇겠지만, 충분히 강력한 비밀번호 같네요!

혹은 노래 가사에서도 비밀번호를 생각해낼 수 있을 것 같습니다.

벌써 발표된 지 4년이 넘어간 곡입니다. 시간 참 빨리 가는 것 같습니다.. I'm_a_mother_father_gentleman_130412 정도를 생각할 수 있을 것 같습니다. 가사만으로는 예측하기 쉬울 수도 있으니 뒤에 발매일을 붙여줬습니다. 특수문자, 대소문자, 숫자 모두가 포함된 36글자의 강력하고 기억하기 쉬운 비밀번호입니다. $1.82\times10^{53}$년이 걸려야 뚫을 수 있습니다.

혹은, 한글 문장을 키보드로 그냥 쳐서 비밀번호를 만들 수 있습니다. 예를 들어.. ‘웃으면서 미래의 이야기를 합시다’는 dntdmaustj_alfodml_dldirlfmf_gkqtlek 정도가 되겠네요, 소문자와 특수문자밖에 없지만 충분히 길기 때문에 $9.0\times10^{39}$년이 걸립니다.

쌍자음이 있으면 대문자를 만들 수 있으니까(영어 키보드는 Shift를 누르면서 글자를 누르면 대문자가 됩니다) ‘대한민국의 주권은 국민에게 있다’는 eogksalsrnrdml_wnrnjsdms_rnralsdprp_dlTek가 됩니다. 무려 41글자, $5.86\times10^{56}$년이 걸리는군요!

이런 식으로 기억하기 쉽고 강력한 비밀번호를 만들 수 있습니다. 취약하거나 기억하기 어려운 비밀번호들은 지금 다시 만들어보는 게 어떨까요?

컴퓨터는 삼각함수를 어떻게 계산하는가

주의: 이 포스트는 약간의 미적분학 지식이 있어야 이해하기 쉽습니다. 그래도 설명을 위해 약간의 증명은 들어가 있으니, 아는 부분은 스킵하셔도 됩니다.

우리는 언제나 직각과 직사각형이 편합니다. 인류는 직교좌표계를 발명했습니다. 그리고 컴퓨터 모니터의 픽셀 배열은 대부분 가로세로 수백~수천 개 픽셀로 이루어진 격자로 이루어져 있고, 이는 직교좌표계로 접근할 수 있습니다. 직교좌표계로 화면을 그리면 픽셀 하나하나를 관리하기가 제일 쉽고 자유로워서가 아닐까 싶습니다.

만약에 누군가가 사칙연산만 제공되는 엔진으로 게임을 개발한다고 생각합시다. 직교좌표계 위에 그려진 어떤 도형이 있는데 이 도형을 회전시켜야 한다고 합니다. 어떻게 하면 될까요?

사실 수학은 이미 답을 알고 있습니다. 어떤 픽셀의 좌표 \(\left ( x, y\right )\)에 대해 회전된 좌표 \(\left ( x′, y′\right )\)는
\[\begin{bmatrix}\cos \theta & -\sin \theta \\ \sin \theta & \cos \theta\end{bmatrix}\begin{bmatrix}x\\y\end{bmatrix}=\begin{bmatrix}x′\\ y′\end{bmatrix}\]
다른 말로 \[\begin{cases}x′=x \cos \theta-y\sin \theta\\ y′=x \sin \theta+y \cos \theta \end{cases}\] 임이 자명합니다. 이걸 회전하기 전의 이미지의 모든 픽셀의 \(\left ( x, y\right )\)에 대해 한 번씩 해 주면 회전한 이미지가 나옵니다. 참 쉽죠?

사칙연산만 갖고 삼각함수를 계산하라고요?

컴퓨터가 어떻게 삼각함수를 계산하는지를 논하기로 했으니까, 컴퓨터가 할 수 있는 연산만을 이용해야겠습니다. 아주 기본적인 연산만 사용 가능한 프로세서에서 말입니다.

그럼 대체 삼각함수는 어떻게 근사할 수 있을까요? \(\sin\)과 \(\cos\)를 구하면 \(\tan\) 등은 나눗셈으로도 구할 수 있으니까 \(\sin\)과 \(\cos\)를 구하는 데 집중해 봅시다.

삼각함수를 다항함수로 근사하면 되지 않을까요?

다항함수는 사칙연산만으로 계산할 수 있으니 삼각함수의 그래프와 비슷한 다항함수를 만들어서 거기다 집어넣으면 되겠네요!

근데 그 다항함수는 대체 어떻게 구할까요? 여기서 테일러 급수가 등장합니다.

테일러 급수

테일러 급수를 이용하면 어떤 미분 가능한 함수라도 다항함수로 근사해 버릴 수 있습니다. 세상에 그런 흑마법이 존재하냐고요? 네, 놀랍게도 존재합니다!

증명

우선 어떤 함수 \(f^\prime\left(x\right )\)를 \(a\)부터 \(x\)까지 정적분해 봅시다. 미적분의 정의에 의해 아래 식과 같이 표현할 수 있습니다.
\[\int_{a}^{x}f^\prime\left(t\right )\mathrm{d}t=f\left(x\right )-f\left(a\right )\]
그리고 위 식을 변형해 봅시다.
\[\int_{a}^{x}f^\prime\left(t\right )\mathrm{d}t=\int_{a}^{x}\left(-1\right )\left(-f^\prime\left(t\right )\right )\mathrm{d}t\]
이제 \(-1\)을 적분하고 \(-f^\prime\left(t\right )\)를 미분해 부분적분법을 씁시다. 이 때 \(f\left(x\right )\)가 무한히 미분 가능하다면, 부분적분법도 무한히 써 버릴 수 있습니다. 그러니까
\[\cdots = \left.\begin{matrix}\left (-\left ( x-t \right )f^\prime\left ( t \right )- \dfrac{\left( x-t \right )^2}{2}f^{\prime\prime}\left ( t \right )- \dfrac{\left( x-t \right )^3}{6}f^{\prime\prime\prime}\left ( t \right )- \cdots\right )\end{matrix}\right|_{a}^{x}\]
가 됩니다. 이 때 적분변수 \(t\)와 관계없는 \(x\)는 상수취급됩니다. 이 식을 전개해 보면
\[\cdots =\left ( x-a \right )f^\prime\left ( a \right )+ \dfrac{\left( x-a \right )^2}{2!}f^{\prime\prime}\left ( a \right )+ \dfrac{\left( x-a \right)^3}{3!}f^{\prime\prime\prime}\left ( a \right )+ \cdots\\ \]
\[= f\left ( x \right )-f\left ( a \right )\]
마지막으로 \(f\left ( a \right )\)를 이항하면
\[f\left ( x \right ) =f\left ( a \right )+ \left ( x-a \right )f^\prime\left ( a \right )+ \dfrac{\left( x-a \right )^2}{2!}f^{\prime\prime}\left ( a \right )+ \dfrac{\left( x-a \right )^3}{3!}f^{\prime\prime\prime}\left ( a \right )+ \cdots\]
즉 \(f^{\left( n \right)}\)이 \(f\)를 \(n\)번 미분한 함수라고 할 때
\[f\left ( x \right ) = \sum_{n=0}^{\infty}\dfrac{f^{\left ( n \right )}\left ( a \right )}{n!}\left( x-a \right )^n\]
가 유도됩니다. 이 때 \(a\)에 어떤 수를 넣어도 근사됩니다.

그래서 이게 삼각함수랑 무슨 상관이에요!

삼각함수는 무한히 미분 가능합니다. 그러니까, \(f\) 대신 삼각함수를 넣으면 삼각함수를 다항함수로 근사할 수 있습니다. 어떤 삼각함수 \(f\left ( x \right )\)에 대해 \(a\)에 \(0\)을 대입해 보면
\[f\left ( x \right ) =f\left ( 0 \right )+ \left ( x-0 \right )f^\prime\left ( 0 \right )+ \dfrac{\left( x-0 \right )^2}{2!}f^{\prime\prime}\left ( 0 \right )+ \dfrac{\left( x-0 \right )^3}{3!}f^{\prime\prime\prime}\left ( 0 \right )+ \cdots\]
\[=f\left ( 0 \right )+ x f^\prime\left ( 0 \right )+ \dfrac{x^2}{2!}f^{\prime\prime}\left ( 0 \right )+ \dfrac{x^3}{3!}f^{\prime\prime\prime}\left ( 0 \right )+ \cdots\]
인데요, \(f\left ( x \right ) = \sin x\)라고 하고 대입해 보면
\[\sin x =\sin\left ( 0 \right )+ x \sin^\prime\left ( 0 \right )+ \dfrac{x^2}{2!}\sin^{\prime\prime}\left ( 0 \right )+ \dfrac{x^3}{3!}\sin^{\prime\prime\prime}\left ( 0 \right )+ \cdots\]
\[=0+ \left ( x \cdot 1 \right )+ \left ( \dfrac{x^2}{2!}\cdot 0 \right )+ \left ( \dfrac{x^3}{3!}\cdot -1 \right )+ \left ( \dfrac{x^4}{4!}\cdot 0 \right )+ \left ( \dfrac{x^5}{5!}\cdot 1 \right )+ \cdots\]
정리하면
\[\therefore \sin x =x- \dfrac{x^3}{3!}+ \dfrac{x^5}{5!}- \dfrac{x^7}{7!}+ \dfrac{x^9}{9!}+ \cdots\]
마찬가지로
\[\cos x =1-\dfrac{x^2}{2!}+\dfrac{x^4}{4!}-\dfrac{x^6}{6!}+\dfrac{x^8}{8!}+ \cdots\]
이 됩니다. 중간 과정에 비해서 정말 간단한 식이 되었습니다. 더구나, 우리의 궁극적인 목표인 사칙연산만으로 삼각함수 표현하기에 성공했습니다! (팩토리얼은 곱셈의 연속일 뿐이니까요!)

근데, 식이 참… 무한합니다. 이건 어떻게 하면 좋을까요? 우리는 어차피 floating-point 변수들은 굉장히 정확하지 않다는 걸 잘 알고 있습니다. 그러니까 저 식을 어디까지만 계산하고 그 이후의 오차는 무시해 버려도 됩니다.

위에서 구한 다항식을 최고차항이 \(n\)인 항까지만 계산하고, 그 이후는 무시해버립시다. 그리고 이걸 \(n\)차 근사식이라고 합시다. 이제부터 차수를 올려나가면서 \(n\)차 근사식의 그래프를 그려보겠습니다.

그래프

▶ 1차 근사식: \(f\left ( x \right ) = x\)

… 하나도 비슷해보이진 않습니다. 다음!

▶ 3차 근사식: \(f\left ( x \right ) = x-\dfrac{x^3}{3!}\)

앞에서는 감을 좀 잠은 거 같기도 한데, 겨우 \(\dfrac{\pi}{2}\)도 가기 전에부터 조금씩 이상하더니 아래로 곤두박질쳐버리는군요. 다음!

▶ 5차 근사식: \(f\left ( x \right ) = x-\dfrac{x^3}{3!} + \dfrac{x^5}{5!}\)

이제 \(\dfrac{\pi}{2}\)에서도 비슷해졌네요! 다음!

▶ 7차 근사식: \(f\left ( x \right ) = x-\dfrac{x^3}{3!} + \dfrac{x^5}{5!}- \dfrac{x^7}{7!}\)

\(pi\) 근처까지도 꽤 비슷해졌습니다. 몇 개만 더 해 봅시다.

▶ 9차 근사식: \(f\left ( x \right ) = x-\dfrac{x^3}{3!} + \dfrac{x^5}{5!}-\dfrac{x^7}{7!} + \dfrac{x^9}{9!}\)

거의 원본 함수와 같아졌습니다. 사실 여기부터는 이제 \(0 < x < \pi\)일 때는 그냥 가져다 써도 오차는 크지 않을 것 같습니다. 어차피 \(sin\)은 주기함수이고 대칭함수이니까 \(0 < x < \dfrac{\pi}{2}\)에서만 정확해도 다른 범위에서는 함수의 특징을 이용해 계산해내면 됩니다.

▶ 11차 근사식: \(f\left ( x \right ) = x-\dfrac{x^3}{3!} + \dfrac{x^5}{5!}- \dfrac{x^7}{7!} + \dfrac{x^9}{9!}- \dfrac{x^{11}}{11!}\)

차이가 얼마나 나는지 점점 이렇게 봐서는 확인하기가 어렵습니다. 마지막으로 13차 근사식까지만 그려보겠습니다.

▶ 13차 근사식: \(f\left ( x \right ) = x- \dfrac{x^3}{3!} + \dfrac{x^5}{5!}- \dfrac{x^7}{7!} + \dfrac{x^9}{9!}- \dfrac{x^{11}}{11!} + \dfrac{x^{13}}{13!}\)

그래프 범위 내에서는 거의 똑같은 곡선이 그려집니다.

프로그래밍 언어에서의 구현 사례

OpenJDKStrictMath 네이티브 코드가 13차 근사식을 통해 삼각함수를 구현하고 있습니다. 정확성을 위해서 13차 근사식을 그대로 사용하진 않고, 이렇게 조금 변형해서 사용합니다.
\[\sin x \sim x- \dfrac{x^3}{3!} + \dfrac{x^5}{5!}- \dfrac{x^7}{7!} + \dfrac{x^9}{9!}- \dfrac{x^{11}}{11!} + \dfrac{x^{13}}{13!}\]
\[\frac{\sin x}{x} \sim 1- \dfrac{x^2}{3!} + \dfrac{x^4}{5!}- \dfrac{x^6}{7!} + \dfrac{x^8}{9!}- \dfrac{x^{10}}{11!} + \dfrac{x^{12}}{13!}\]
그러므로 \(r\)을 이렇게 정의할 때
\[r = x^3 \left(\dfrac{1}{5!} + x^2 \left(-\dfrac{1}{7!} + x^2 \left(\dfrac{1}{9!} + x^2 \left(-\dfrac{1}{11!} + {x^{2}} \cdot \dfrac{1}{13!}\right)\right)\right)\right)\]
\(\sin x\)는 이렇게 표현할 수 있습니다.
\[\sin x \sim x + x^3 \cdot \left(-\dfrac{1}{3!} + x^2 r \right)\]
예를 봅시다. sin 함수에서 __kernel_sin 함수를 호출할 때 코드에서 \(|x| \prec \pi/4\)라면 y, iy의 값은 모두 0입니다. 이외의 범위에서는 적절한 범위로 평행이동시켜 __kernel_sin 혹은 __kernel_cos 함수값을 구합니다.

#include "fdlibm.h"
#ifdef __STDC__
    static const double
#else
    static double
#endif
half = 5.00000000000000000000e-01, /* 0x3FE00000, 0x00000000 */
S1 = -1.66666666666666324348e-01, /* 0xBFC55555, 0x55555549 */
S2 = 8.33333333332248946124e-03, /* 0x3F811111, 0x1110F8A6 */
S3 = -1.98412698298579493134e-04, /* 0xBF2A01A0, 0x19C161D5 */
S4 = 2.75573137070700676789e-06, /* 0x3EC71DE3, 0x57B1FE7D */
S5 = -2.50507602534068634195e-08, /* 0xBE5AE5E6, 0x8A2B9CEB */
S6 = 1.58969099521155010221e-10; /* 0x3DE5D93A, 0x5ACFD57C */

#ifdef __STDC__
    double __kernel_sin(double x, double y, int iy)
#else
    double __kernel_sin(x, y, iy) double x,y; int iy; /* iy=0 if y is zero */
#endif
{
    double z,r,v; int ix;
    ix = __HI(x)&0x7fffffff; /* high word of x */
    if(ix < 0x3e400000) /* |x| < 2**-27 */ {
        if((int)x==0) return x;
    } /* generate inexact */
    z = x*x;
    v = z*x;
    r = S2+z*(S3+z*(S4+z*(S5+z*S6)));
    if(iy==0) return x+v*(S1+z*r);
    else return x-((z*(half*y-v*r)-y)-v*S1);
}

소스에서
\(S1 = -\dfrac{1}{3!} \approx -1.66666667 \times {10}^{-1}\)
\(S2 = \dfrac{1}{5!} \approx 8.33333333 \times {10}^{-2}\)
\(S3 = -\dfrac{1}{7!} \approx -1.98412698 \times {10}^{-4}\)
\(S4 = \dfrac{1}{9!} \approx 2.75573137 \times {10}^{-6}\)
\(S5 = -\dfrac{1}{11!} \approx -2.50521084 \times {10}^{-8}\)
\(S6 = \dfrac{1}{13!} \approx 1.58969099 \times {10}^{-10}\)
으로 근사식의 계수들이 근사되어 하드코딩되어 있는 것을 알 수 있습니다. 또한 \(z=x^2\), \(v=zx=x^3\)으로 계산하고 있습니다. 13차 근사식을 그대로 쓴다면 항마다 1번, 3번, 5번, …, 13번의 곱셈을 해야 하지만 \(x^2\)를 새 상수로 두면 곱셈을 줄일 수 있어서 이런 방법을 사용하지 않았을까 하는 생각입니다.

다른 방법으로도 계산할 수 있나요?

물론 다른 방법들도 있습니다. 예를 들어 볼더가 1956년에 고안한 CORDIC(COordinate Rotation DIgital Computer) 알고리즘을 이용해 삼각함수의 값을 근사하는 것도 가능합니다.

간단하게 설명하자면, 맨 위에서 회전을 하기 위해 곱하는 행렬을
\[\begin{bmatrix}\cos \theta & -\sin \theta \\ \sin \theta & \cos \theta\end{bmatrix}\]
으로 소개했습니다만, CORDIC 알고리즘은 이를 \(\tan\) 함수만으로 표현해
\[R_i = \dfrac{1}{\sqrt{1 + \tan^2 \left(\gamma_i\right)}}\begin{bmatrix}1 & -\tan \left(\gamma_i\right) \\\tan \left(\gamma_i\right) & 1\end{bmatrix}\]
로 변형하고, 컴퓨터가 빠르게 계산할 수 있도록 \(\tan \left(\gamma_i\right) = \pm2^{-i}\)가 되는 \(\gamma_i\), 즉 \(\arctan\left(2^{-i}\right)\)의 값들과 이 때의 \(\dfrac{1}{\sqrt{1 + \tan^2 \left(\gamma_i\right)}}\)의 값들을 하드코딩해 두고 원하는 각도에 가까워질 때까지 \(i\)를 하나씩 증가시키면서
\(\arctan\left(2^{-i}\right)\)를 더하거나 빼면서 행렬 계산을 해나가는 알고리즘입니다.

이 알고리즘은 계산기에 주로 쓰이고 있고, 인텔의 8087 ~ 80486 CPU에도 채용되어 왔습니다.

컴퓨터는 이렇게 삼각함수를 계산합니다.