Jekyll2022-03-07T09:29:05+00:00https://blog.solarmagic.dev/rss/SolarMagic’s Archives솔라매직의 기록 저장소solarmagic신기한 상태 메시지 만들기2021-11-29T00:00:00+00:002021-11-29T00:00:00+00:00https://blog.solarmagic.dev/c/2021/11/29/statusmessage<p><img src="https://i.imgur.com/WAxKAFN.png" alt="" /></p> <h2 id="상태메시지">상태메시지</h2> <p><code class="language-plaintext highlighter-rouge">double ans[]={.33066404772027283E3,1&lt;&lt;0xA};main(){--1[ans]?*ans/=2,main():puts(ans);}</code></p> <h2 id="실행결과">실행결과</h2> <p><code class="language-plaintext highlighter-rouge">☀🪄</code></p> <p>C로 컴파일해서 실행하면 솔라매직을 상징하는 해(solar)와 마법봉(magic)을 출력한다.</p> <p><a href="https://ideone.com/9YkiOm">온라인 IDE 결과</a></p> <h2 id="계기">계기</h2> <p><code class="language-plaintext highlighter-rouge">double k[]={12.596070810382761,495};main(){k[1]--?k[0]/=2,main():puts(k);}</code></p> <p>Steam 친구 자기소개에 이런게 있는 것을 발견했다. 실행해보니 결과는 <code class="language-plaintext highlighter-rouge">kcy1019!</code> 신기해서 어떻게 만드는지를 물어봤다.</p> <h2 id="만들기">만들기</h2> <pre><code class="language-C">#include &lt;cstdio&gt; #include &lt;cassert&gt; #include &lt;cstring&gt; int main(int argc, char *argv[]) { assert(argc &gt; 1); int n = strlen(argv[1]); assert(n &lt; 9); char buf[8] = {}; memcpy(buf, argv[1], n); double v = *(double*)buf; int shl = 0; for (; v &lt; 10; v *= 2) ++shl; printf("double k[]={ %.15f,%d};main(){k[1]--?k[0]/=2,main():puts(k);}", v, shl); return 0; } </code></pre> <p>친절하게 만드는 코드까지 제공해주셨다.</p> <p>기본적인 원리는 간단하다. 8바이트 ASCII문자를 하나의 double(8바이트)로 담은다음에 변형하고 다시 출력하는 것이다. long long같은 8바이트 정수로 하면 좀 더 직관적이다.</p> <h3 id="변형">변형</h3> <p>하지만 내 이름은 10글자(solarmagic) 이기 때문에 그대로 쓰기에는 조금 무리였다. 16바이트 자료형인 <code class="language-plaintext highlighter-rouge">long double</code>이나 <code class="language-plaintext highlighter-rouge">__int128</code> 같은 걸 사용하면 될 수도 있지만 그냥 그대로 써먹기로 했다. 대신 ASCII문자가 아니라 유니코드 문자를 이용해서 출력하면 좀 더 비직관적인 결과가 나오지 않을까 생각해서 솔라매직을 이모지로 출력하기로 마음 먹었다.</p> <p><code class="language-plaintext highlighter-rouge">☀🪄</code> 가 가장 적절한 이모지로 보였다. <code class="language-plaintext highlighter-rouge">☀</code>☀ 이모지는 환경에 따라서 좀 많이 다르게 보이는게 조금 아쉬웠지만 그래도 가장 적절한 이모지라 생각했다.</p> <p>원본 코드는 적절히 한 10.x 되는 수로 만들어 주는데 나는 뭔가 1024($2^{10}$)번 반복하는게 컴공 답다고 생각해서 코드를 조금 변형 시켰다.</p> <p><code class="language-plaintext highlighter-rouge">double ans[]={.33066404772027283E3,1&lt;&lt;0xA};main(){--1[ans]?*ans/=2,main():puts(ans);}</code></p> <p>배열이름은 ans로 바꾸었고(PS 사이트에 올릴것이기 때문에 적절한 이름이다.) 배열 원소를 직접 지정할때 [] 안에 수를 안써도 되는 것은 모두 알 것이다.</p> <p>그밖에 코드를 보면 실수를 그냥 <code class="language-plaintext highlighter-rouge">330.xxx</code> 담는 것보다는 <code class="language-plaintext highlighter-rouge">.330...E3</code> 형태로 표기하면 난독화가 조금더 올라갈거라 생각했다. 참고로 <code class="language-plaintext highlighter-rouge">0.x</code> 의 수에서 <code class="language-plaintext highlighter-rouge">0</code>을 생략하는건 C/C++에서 가능하다.</p> <p>$1024$도 $1024$라고 쓰는것보다 <code class="language-plaintext highlighter-rouge">1&lt;&lt;10</code>이라 쓰는게 좋아보였고 한 술 더떠서 <code class="language-plaintext highlighter-rouge">1&lt;&lt;0xA</code>로 $10$을 $16$진수로 표기했다.</p> <p>코드의 기본 동작은 <code class="language-plaintext highlighter-rouge">main</code> 함수의 재귀이다. 사람들이 잘 모르는 사실이지만 <code class="language-plaintext highlighter-rouge">main</code>도 재귀가 가능하다. 그래서 <code class="language-plaintext highlighter-rouge">main</code>을 <code class="language-plaintext highlighter-rouge">ans[1]</code> 만큼 반복하면서 절반으로 나누고 그값을 출력하면 원본 글자가 나온다. 재귀의 판정은 삼항연산자를 사용했다.</p> <p>난독화를 조금도 하기 위해서 <code class="language-plaintext highlighter-rouge">--ans[1]</code>을 <code class="language-plaintext highlighter-rouge">--1[ans]</code>로 썼다. (C 수업을 되새겨보면 이게 왜 가능한지 생각날 것이다.) 또한 <code class="language-plaintext highlighter-rouge">ans[0]</code> 은 자연스럽게 <code class="language-plaintext highlighter-rouge">*ans</code> 바꿔써도 상관이 없다.</p> <h2 id="마무리">마무리</h2> <p>나의 상태메시지를 설명하는 글이었다. 프로그래머라면 위 코드 및 다른 코드들을 활용해서 나만의 코드 상태메시지를 하나씩 가져보면 좋을 것 같다.</p>solarmagic백준[BOJ] 1557번 제곱 ㄴㄴ2021-11-23T00:00:00+00:002021-11-23T00:00:00+00:00https://blog.solarmagic.dev/boj/2021/11/23/squarefree<p><img src="https://i.imgur.com/Vyayxqp.png" alt="SQUAREFREE" /></p> <h1 id="square-free-integers">Square-free integers</h1> <h2 id="서론">서론</h2> <p>오늘 기준(2021/11/23) 가장 많이 풀린 다이아몬드 이상의 문제가 <a href="https://www.acmicpc.net/problem/1557">1557번: 제곱 ㄴㄴ</a>이다. 그만큼 어려우면서 쉬운(?) 문제가 바로 이 문제인데 이 문제의 풀이는 정말 짧지만 그것을 제대로 이해하는 건 매우 어렵다고 생각한다. 실제로 나도 완벽히 이해하지 못했었고 다른 블로그의 글 설명 또한 부족한 부분이 있다고 생각하여 이 글을 작성하게 된다. 이 글이 1557번 풀이의 레퍼런스가 되었으면 한다.</p> <p>글의 양이 상당히 긴데 차근 차근 따라오면 문제가 풀리도록 설명하도록 노력했다.</p> <p>사실 jh05013님이 설명한 걸 다시 한 번 정리하는 것이긴 하다.</p> <h2 id="1557번-문제">1557번 문제</h2> <p>어떤수 $N$이 $1$이 아닌 제곱수로 나누어지지 않을 때, 이 수를 제곱ㄴㄴ수라고 한다. 제곱수는 $4, 9, 16, 25$와 같은 것이고, 제곱ㄴㄴ수는 $1, 2, 3, 5, 6, 7, 10, 11, 13, …$과 같은 수이다.</p> <p>이 때 $1 \leq K \leq 10^9$ 의 $K$가 주어졌을 때 $K$ 번째 제곱 ㄴㄴ수(Square-free integers)를 구하는 문제이다.</p> <ul> <li>시간 제한: 2초</li> <li>메모리 제한: 128MB</li> </ul> <h2 id="풀이">풀이</h2> <h3 id="브루트-포스">브루트 포스</h3> <div class="language-python highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="k">def</span> <span class="nf">is_square_free</span><span class="p">(</span><span class="n">n</span><span class="p">):</span> <span class="s">''' function to check if n is square free '''</span> <span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">2</span><span class="p">,</span> <span class="nb">int</span><span class="p">(</span><span class="n">n</span><span class="o">**</span><span class="mf">0.5</span><span class="p">)</span><span class="o">+</span><span class="mi">1</span><span class="p">):</span> <span class="k">if</span> <span class="n">n</span> <span class="o">%</span> <span class="p">(</span><span class="n">i</span> <span class="o">*</span> <span class="n">i</span><span class="p">)</span> <span class="o">==</span> <span class="mi">0</span><span class="p">:</span> <span class="k">return</span> <span class="bp">False</span> <span class="k">return</span> <span class="bp">True</span> <span class="k">def</span> <span class="nf">kth_square_free</span><span class="p">(</span><span class="n">k</span><span class="p">):</span> <span class="s">''' function to find kth square free numnber '''</span> <span class="n">cnt</span><span class="p">,</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">1</span> <span class="k">while</span> <span class="bp">True</span><span class="p">:</span> <span class="k">if</span> <span class="n">is_square_free</span><span class="p">(</span><span class="n">i</span><span class="p">):</span> <span class="n">cnt</span> <span class="o">+=</span> <span class="mi">1</span> <span class="k">if</span> <span class="n">cnt</span> <span class="o">==</span> <span class="n">k</span><span class="p">:</span> <span class="k">return</span> <span class="n">i</span> <span class="n">i</span> <span class="o">+=</span> <span class="mi">1</span> <span class="k">print</span><span class="p">(</span><span class="n">kth_square_free</span><span class="p">(</span><span class="mi">100</span><span class="p">))</span> </code></pre></div></div> <p>하나씩 세면서 제곱 ㄴㄴ수인지 확인 하는 방법이다. 코드는 쉽지만 매우 느리다.</p> <h3 id="포함-배제의-원리17436번-풀기">포함 배제의 원리(17436번 풀기)</h3> <p>이 문제 풀이의 가장 핵심은 바로 포함 배제의 원리이다.</p> <p><a href="https://www.acmicpc.net/problem/17436">17436번: 소수의 배수</a>는 포함 배제의 가장 기초적인 문제이다. (<del>푼 사람 수는 <a href="https://www.acmicpc.net/problem/155">1557번</a>이 포함 배제 태그 중에 가장 많다.</del>)</p> <p>$N(1 \leq N \leq 10)$개의 소수가 주어지고 $M(1 \leq M \leq 10^{12})$ 이하의 자연수 중 $N$개의 소수 중 적어도 하나라도 나누어 떨어지는 개수를 세는 문제이다.</p> <p>이 문제의 풀이는 다음과 같다. 하나 하나 해보면서 규칙을 파악해보자.</p> <p>1) 소수($p$)가 한 개 주어 졌을 경우</p> <p>$[M/p]$를 출력하면 된다. 예를 들어 $p = 3$이고 $M = 100$이면 100보다 작은 수에 3으로 나누어 떨어지는 수는 33개다. 여기서 $[x]$는 $x$ 이하의 최대 정수를 구하는 함수이다.</p> <p>2) 소수가 두 개 주어졌을 경우</p> <p>$[M/p_1] + [M/p_2] - [M/(p_1p_2)]$를 계산하면 된다. 예를 들어 $p1 = 2, p2 = 3, M = 100$인 경우 $[100/2] + [100/3] - [100/6] = 50 + 33 - 16 = 67$이다.</p> <p>$2$로 나누어 떨어지는 개수를 세고 $3$으로 나누어 떨어지는 개수를 세는데 이 때 중복으로 센 개수는 다시 빼주는 데 이는 $[100/(2*3)]$으로 쉽게 구할 수가 있다.</p> <p>3) 소수가 세 개 주어졌을 경우</p> <p><img src="https://i.imgur.com/Af6ZdNL.png" alt="" /></p> <blockquote> <p>Wikipedia(포함 배제의 원리)</p> </blockquote> <p>$[M/p_1] + [M/p_2] + [M/p_3] - [M/(p_1p_2)] - [M/(p_1p_3)] - [M/(p_2p_3)] + [M/(p_1p_2p_3)]$을 더하면 된다.</p> <p>소수가 두 개일 경우와 비슷하게 하는데 이 때는 다시 3개가 겹쳐진 영역은 너무 많이 빼져서 다시 더해 줘야한다.</p> <p>일반화하면 모든 소수들의 부분집합의 곱을 보는데 하면 홀수 개의 소수가 곱해졌을 때는 더하고 짝수 개의 소수를 곱한 것은 빼주면 된다.</p> <p><img src="https://i.imgur.com/xT26JD0.png" alt="" /></p> <p>매우 자주 쓰이는 테크닉이니 알아두면 좋다. <a href="https://www.acmicpc.net/problem/17436">17436</a>번 풀이 소스</p> <div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#include &lt;bits/stdc++.h&gt; </span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> <span class="k">using</span> <span class="n">ll</span> <span class="o">=</span> <span class="kt">long</span> <span class="kt">long</span><span class="p">;</span> <span class="kt">int</span> <span class="nf">main</span><span class="p">()</span> <span class="p">{</span> <span class="n">ios_base</span><span class="o">::</span><span class="n">sync_with_stdio</span><span class="p">(</span><span class="nb">false</span><span class="p">);</span> <span class="n">cin</span><span class="p">.</span><span class="n">tie</span><span class="p">(</span><span class="nb">nullptr</span><span class="p">);</span> <span class="kt">int</span> <span class="n">N</span><span class="p">;</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">N</span><span class="p">;</span> <span class="n">ll</span> <span class="n">M</span><span class="p">,</span> <span class="n">ans</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">M</span><span class="p">;</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">primes</span><span class="p">(</span><span class="n">N</span><span class="p">);</span> <span class="k">for</span><span class="p">(</span><span class="k">auto</span><span class="o">&amp;</span> <span class="n">x</span><span class="o">:</span> <span class="n">primes</span><span class="p">)</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">x</span><span class="p">;</span> <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="p">(</span><span class="mi">1</span><span class="o">&lt;&lt;</span><span class="n">N</span><span class="p">);</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span> <span class="c1">// 2^N - 1번 반복하면서 </span> <span class="kt">int</span> <span class="n">popcnt</span> <span class="o">=</span> <span class="n">__builtin_popcount</span><span class="p">(</span><span class="n">i</span><span class="p">);</span> <span class="c1">// 켜진(1) 비트의 개수를 센다</span> <span class="n">ll</span> <span class="n">x</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">j</span> <span class="o">&lt;</span> <span class="n">N</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span> <span class="k">if</span> <span class="p">(</span><span class="n">i</span> <span class="o">&amp;</span> <span class="p">(</span><span class="mi">1</span><span class="o">&lt;&lt;</span><span class="n">j</span><span class="p">))</span> <span class="n">x</span> <span class="o">*=</span> <span class="n">primes</span><span class="p">[</span><span class="n">j</span><span class="p">];</span> <span class="c1">// 켜진 비트에 해당하는 소수 곱하기</span> <span class="p">}</span> <span class="k">if</span> <span class="p">(</span><span class="n">popcnt</span> <span class="o">%</span> <span class="mi">2</span> <span class="o">==</span> <span class="mi">1</span><span class="p">)</span> <span class="n">ans</span> <span class="o">+=</span> <span class="p">(</span><span class="n">M</span> <span class="o">/</span> <span class="n">x</span><span class="p">);</span> <span class="c1">// 켜진 비트가 홀수면 더하고</span> <span class="k">else</span> <span class="n">ans</span> <span class="o">-=</span> <span class="p">(</span><span class="n">M</span> <span class="o">/</span> <span class="n">x</span><span class="p">);</span> <span class="c1">// 켜진 비트가 짝수면 뺀다</span> <span class="p">}</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">ans</span><span class="p">;</span> <span class="p">}</span> </code></pre></div></div> <p>비트마스크를 이용하면 정말 간단한게 코딩할 수 있다.</p> <h3 id="1557번에-적용하고-시간복잡도-줄이기">1557번에 적용하고 시간복잡도 줄이기</h3> <p>이 문제도 위의 문제와 매우 비슷하다. 각 소수의 제곱수로 떨어지는 수의 개수를 구하는데 포함 배제를 사용해서 중복 처리를 잘 해주면 된다.</p> <p>좀 더 수학으로 정리하면 집합 $P = ${p $\mid$ p 는 소수 } 의 공집합이 아닌 모든 부분집합 $S$에 대해 $-1^{\mid S \mid}[N/q^2]$($q = \prod_{p\in S} p$)를 계산하면 $N$ 이하의 제곱 ㄴㄴ 수의 개수를 알 수 있다.</p> <p>$K$번째 제곱 ㄴㄴ 수를 구하는 것이므로 $N$을 이분 탐색해서 답을 찾을 수가 있다. 최댓값은 $2K$ 정도면 충분하다. 그러나 문제는 $2K = 2 \times 10^9$ 이하의 소수가 몇 천만개는 있다는 것이고(<a href="https://namu.wiki/w/%EC%86%8C%EC%88%98%20%EC%A0%95%EB%A6%AC">소수 정리</a>를 사용하면 개수를 추측할 수 있다.) 이러면 시간 복잡도가 2의 5천만제곱 이라는 무지막지한 시간 복잡도가 나온다.</p> <p>여기서 5분 정도 생각을 해보자.</p> <hr /> <p>이 때 필요한 관찰은 $-1^{\mid S \mid}[N/q^2]$에서 <strong>$q$가 $\sqrt N$보다 크다면 저 값은 항상 0이 된다는 것</strong>이다. 원래 포함 배제 문제를 풀 때에는 모든 부분 집합 $S$를 찾고 그것에 해당하는 $q$를 만들어서 저 식을 계산했다면 이 문제에서는 반대로 $q$에 대해서 반복하면서 그에 해당하는 $S$가 있는지를 판단하는 것이다!</p> <p>여기서 필요한 또 다른 관찰은 그에 해당하는 $S$의 개수는 항상 $\sqrt N$개 이하라는 것이다. 왜냐하면 서로 다른 집합 <strong>$S$의 원소의 곱은 항상 다르기</strong> 때문이다.</p> <p>이분 탐색을 하면서 모든 $q$에 대해 값을 계산하면 $O(\sqrt K \log K)$이 걸린다.</p> <p>여기서 이제 남은 것은 모든 $q$에 대해서 이것이 제곱ㅇㅇ(squareful number)인지 파악하고 제곱 ㄴㄴ수라면 소수가 짝수번 곱해졌는지 홀수번 곱해졌는지만 파악하면 된다. 이는 미리 전처리하기만 하면 된다. 각 수에 대해서 $O(\sqrt x)$의 시간이 걸리므로 전체 시간 복잡도는 $O(K^{3/4})$가 된다. 이정도만 되어도 이 문제를 통과하기 충분한 시간 복잡도이다.</p> <h3 id="1557-최종-풀이">1557 최종 풀이</h3> <p>최종적으로 정리하면 풀이는 다음과 같다.</p> <ol> <li>집합 $P = ${p $\mid$ p 는 소수 }의 공집합이 아닌 모든 부분집합 $S$에 대해 $-1^{\mid S \mid}[N/q^2]$($q = \prod_{p\in S} p$)를 계산하면 $N$ 이하의 제곱 ㄴㄴ 수의 개수를 알아낼 수 있다. 이를 $Q(N)$이라 하자.</li> <li>이 문제의 답이 될수 있는 최댓값을 $R = 2*10^{9}$ 라고 하자 최솟값은 $1$이다. $1$부터 $R$사이에서 $Q(x) = K$를 만족하는 최소의 $x$를 이분 탐색으로 알아낸다.</li> <li>$Q(x)$를 계산할 때 다 계산하면 양이 많으니 $q$의 후보가 최대 $\sqrt R$ 까지임을 이용해 $q$를 정했을때 $q$가 가능한 $q$인지 판단 및 $-1^{ \mid S \mid}$의 값을 $q$를 소인수 분해해서 알아 낸다. 이를 전처리해서 알아내자.</li> </ol> <p>소스 코드</p> <div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#include &lt;bits/stdc++.h&gt; </span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> <span class="k">const</span> <span class="kt">int</span> <span class="n">KMAX</span> <span class="o">=</span> <span class="mi">1'000'000'000</span><span class="p">;</span> <span class="k">const</span> <span class="kt">int</span> <span class="n">NMAX</span> <span class="o">=</span> <span class="mi">2</span><span class="o">*</span><span class="n">KMAX</span><span class="p">;</span> <span class="k">const</span> <span class="kt">int</span> <span class="n">MAX</span> <span class="o">=</span> <span class="mi">50000</span><span class="p">;</span> <span class="kt">int</span> <span class="n">is_composite</span><span class="p">[</span><span class="n">MAX</span><span class="p">];</span> <span class="kt">int</span> <span class="n">sign</span><span class="p">[</span><span class="n">MAX</span><span class="p">];</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">primes</span><span class="p">;</span> <span class="kt">void</span> <span class="nf">get_sieve</span><span class="p">(</span><span class="kt">int</span> <span class="n">n</span><span class="p">)</span> <span class="p">{</span> <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">2</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span> <span class="k">if</span> <span class="p">(</span><span class="o">!</span><span class="n">is_composite</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <span class="n">primes</span><span class="p">.</span><span class="n">push_back</span><span class="p">(</span><span class="n">i</span><span class="p">);</span> <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="n">i</span><span class="o">+</span><span class="n">i</span><span class="p">;</span> <span class="n">j</span> <span class="o">&lt;</span> <span class="n">n</span><span class="p">;</span> <span class="n">j</span><span class="o">+=</span><span class="n">i</span><span class="p">)</span> <span class="p">{</span> <span class="n">is_composite</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="p">}</span> <span class="p">}</span> <span class="p">}</span> <span class="kt">void</span> <span class="nf">sign_precompute</span><span class="p">(</span><span class="kt">int</span> <span class="n">n</span><span class="p">)</span> <span class="p">{</span> <span class="n">memset</span><span class="p">(</span><span class="n">sign</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="k">sizeof</span><span class="p">(</span><span class="n">sign</span><span class="p">));</span> <span class="n">sign</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">2</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span> <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">2</span><span class="p">;</span> <span class="n">j</span> <span class="o">*</span> <span class="n">j</span> <span class="o">&lt;=</span> <span class="n">i</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span> <span class="k">if</span> <span class="p">(</span><span class="n">i</span> <span class="o">%</span> <span class="p">(</span><span class="n">j</span> <span class="o">*</span> <span class="n">j</span><span class="p">)</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span> <span class="p">{</span> <span class="n">sign</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="k">break</span><span class="p">;</span> <span class="p">}</span> <span class="p">}</span> <span class="k">if</span> <span class="p">(</span><span class="n">sign</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span> <span class="k">continue</span><span class="p">;</span> <span class="kt">int</span> <span class="n">cnt</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="kt">int</span> <span class="n">x</span> <span class="o">=</span> <span class="n">i</span><span class="p">;</span> <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">j</span> <span class="o">&lt;</span> <span class="n">primes</span><span class="p">.</span><span class="n">size</span><span class="p">()</span> <span class="o">&amp;&amp;</span> <span class="n">primes</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">&lt;=</span> <span class="n">x</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span> <span class="k">if</span> <span class="p">(</span><span class="n">x</span> <span class="o">%</span> <span class="n">primes</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span> <span class="p">{</span> <span class="n">cnt</span><span class="o">++</span><span class="p">;</span> <span class="n">x</span> <span class="o">/=</span> <span class="n">primes</span><span class="p">[</span><span class="n">j</span><span class="p">];</span> <span class="p">}</span> <span class="p">}</span> <span class="k">if</span> <span class="p">(</span><span class="n">cnt</span> <span class="o">%</span> <span class="mi">2</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span> <span class="n">sign</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="p">}</span> <span class="p">}</span> <span class="kt">int</span> <span class="nf">Q</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">)</span> <span class="p">{</span> <span class="kt">int</span> <span class="n">ans</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o">*</span> <span class="n">i</span> <span class="o">&lt;=</span> <span class="n">x</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span> <span class="n">ans</span> <span class="o">+=</span> <span class="n">sign</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">*</span> <span class="p">(</span><span class="n">x</span> <span class="o">/</span> <span class="p">(</span><span class="n">i</span> <span class="o">*</span> <span class="n">i</span><span class="p">));</span> <span class="p">}</span> <span class="k">return</span> <span class="n">ans</span><span class="p">;</span> <span class="p">}</span> <span class="kt">int</span> <span class="nf">main</span><span class="p">()</span> <span class="p">{</span> <span class="n">ios_base</span><span class="o">::</span><span class="n">sync_with_stdio</span><span class="p">(</span><span class="nb">false</span><span class="p">);</span> <span class="n">cin</span><span class="p">.</span><span class="n">tie</span><span class="p">(</span><span class="nb">nullptr</span><span class="p">);</span> <span class="n">get_sieve</span><span class="p">(</span><span class="n">MAX</span><span class="p">);</span> <span class="n">sign_precompute</span><span class="p">(</span><span class="n">MAX</span><span class="p">);</span> <span class="kt">int</span> <span class="n">K</span><span class="p">;</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">K</span><span class="p">;</span> <span class="kt">int</span> <span class="n">s</span> <span class="o">=</span> <span class="mi">1</span><span class="p">,</span> <span class="n">e</span> <span class="o">=</span> <span class="n">K</span><span class="o">*</span><span class="mi">2</span><span class="p">,</span> <span class="n">ans</span> <span class="o">=</span> <span class="n">e</span><span class="p">;</span> <span class="k">while</span> <span class="p">(</span><span class="n">s</span> <span class="o">&lt;=</span> <span class="n">e</span><span class="p">)</span> <span class="p">{</span> <span class="kt">int</span> <span class="n">m</span> <span class="o">=</span> <span class="n">s</span> <span class="o">+</span> <span class="p">(</span><span class="n">e</span> <span class="o">-</span> <span class="n">s</span><span class="p">)</span> <span class="o">/</span> <span class="mi">2</span><span class="p">;</span> <span class="k">if</span> <span class="p">(</span><span class="n">Q</span><span class="p">(</span><span class="n">m</span><span class="p">)</span> <span class="o">&lt;</span> <span class="n">K</span><span class="p">)</span> <span class="n">s</span> <span class="o">=</span> <span class="n">m</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span> <span class="k">else</span> <span class="n">e</span> <span class="o">=</span> <span class="n">m</span> <span class="o">-</span> <span class="mi">1</span><span class="p">,</span> <span class="n">ans</span> <span class="o">=</span> <span class="n">m</span><span class="p">;</span> <span class="p">}</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">ans</span><span class="p">;</span> <span class="p">}</span> </code></pre></div></div> <p>백준 기준으로 100ms 가 나왔다. <img src="https://i.imgur.com/77Ogw7w.png" alt="" /></p> <p>정답 코드를 가지고 확인 해보면 $K$가 $10^9$일때 답은 $1644934081$이고 이를 $R$로 할때 MAX는 $40558$까지만 계산하면 된다. 이러면 72ms로 조금 더 시간 단축을 할 수 있다.</p> <h3 id="더-발전하기">더 발전하기</h3> <p>현재 시간 복잡도의 큰 축을 차지하는 것은 sign을 계산하는 것이다.</p> <p>이는 에라토스테네스의 체를 살짝 변형시켜서 발전할 수 있다. 에라토스트네스의 체에서 $i$가 소수면 소수 목록에서 $i$를 추가한다. 소수 목록에 있는 $j$에 대해서, $ij$는 합성수이고, $i$가 $j$의 배수면 멈춘다. 이를 Linear Sieve라 하여 기존의 에라토스테네스의 시간 복잡도인 $O(n \log \log n)$ 보다 빠른 $O(n)$에 돌아가는 소수 체를 구현 할 수 있다. 뿐만 아니라 가장 작은 소인수를 담고 있어 소인수 분해도 훨씬 빨리 할 수 있다.</p> <div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="kt">int</span> <span class="n">smallest_prime_factor</span><span class="p">[</span><span class="n">MAX</span><span class="p">];</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">primes</span><span class="p">;</span> <span class="kt">void</span> <span class="nf">get_linear_sieve</span><span class="p">(</span><span class="kt">int</span> <span class="n">n</span><span class="p">)</span> <span class="p">{</span> <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">2</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span> <span class="k">if</span> <span class="p">(</span><span class="n">smallest_prime_factor</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span> <span class="n">primes</span><span class="p">.</span><span class="n">push_back</span><span class="p">(</span><span class="n">i</span><span class="p">);</span> <span class="k">for</span> <span class="p">(</span><span class="k">auto</span> <span class="n">j</span> <span class="o">:</span> <span class="n">primes</span><span class="p">)</span> <span class="p">{</span> <span class="k">if</span> <span class="p">(</span><span class="n">i</span> <span class="o">*</span> <span class="n">j</span> <span class="o">&gt;=</span> <span class="n">n</span><span class="p">)</span> <span class="k">break</span><span class="p">;</span> <span class="n">smallest_prime_factor</span><span class="p">[</span><span class="n">i</span> <span class="o">*</span> <span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="n">j</span><span class="p">;</span> <span class="k">if</span> <span class="p">(</span><span class="n">i</span> <span class="o">%</span> <span class="n">j</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span> <span class="k">break</span><span class="p">;</span> <span class="p">}</span> <span class="p">}</span> <span class="p">}</span> <span class="c1">// return -1 when squareful number</span> <span class="c1">// return number of primes </span> <span class="kt">int</span> <span class="nf">prime_factorization</span><span class="p">(</span><span class="kt">int</span> <span class="n">n</span><span class="p">)</span> <span class="p">{</span> <span class="kt">int</span> <span class="n">pre</span> <span class="o">=</span> <span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="n">cnt</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="k">if</span> <span class="p">(</span><span class="n">n</span> <span class="o">==</span> <span class="mi">1</span><span class="p">)</span> <span class="k">return</span> <span class="mi">2</span><span class="p">;</span> <span class="c1">// exception</span> <span class="k">while</span> <span class="p">(</span><span class="n">smallest_prime_factor</span><span class="p">[</span><span class="n">n</span><span class="p">])</span> <span class="p">{</span> <span class="k">if</span> <span class="p">(</span><span class="n">smallest_prime_factor</span><span class="p">[</span><span class="n">n</span><span class="p">]</span> <span class="o">==</span> <span class="n">pre</span><span class="p">)</span> <span class="k">return</span> <span class="o">-</span><span class="mi">1</span><span class="p">;</span> <span class="n">pre</span> <span class="o">=</span> <span class="n">smallest_prime_factor</span><span class="p">[</span><span class="n">n</span><span class="p">];</span> <span class="n">n</span> <span class="o">/=</span> <span class="n">smallest_prime_factor</span><span class="p">[</span><span class="n">n</span><span class="p">];</span> <span class="o">++</span><span class="n">cnt</span><span class="p">;</span> <span class="p">}</span> <span class="k">if</span> <span class="p">(</span><span class="n">pre</span> <span class="o">==</span> <span class="n">n</span><span class="p">)</span> <span class="k">return</span> <span class="o">-</span><span class="mi">1</span><span class="p">;</span> <span class="k">return</span> <span class="n">cnt</span><span class="p">;</span> <span class="p">}</span> <span class="kt">void</span> <span class="nf">sign_precompute</span><span class="p">()</span> <span class="p">{</span> <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">MAX</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span> <span class="kt">int</span> <span class="n">num_of_primes</span> <span class="o">=</span> <span class="n">prime_factorization</span><span class="p">(</span><span class="n">i</span><span class="p">);</span> <span class="n">sign</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="p">(</span><span class="n">num_of_primes</span> <span class="o">==</span> <span class="o">-</span><span class="mi">1</span><span class="p">)</span> <span class="o">?</span> <span class="mi">0</span> <span class="o">:</span> <span class="p">(</span><span class="n">num_of_primes</span> <span class="o">%</span> <span class="mi">2</span> <span class="o">?</span> <span class="o">-</span><span class="mi">1</span> <span class="o">:</span> <span class="mi">1</span><span class="p">);</span> <span class="p">}</span> <span class="p">}</span> </code></pre></div></div> <p>이 때 <code class="language-plaintext highlighter-rouge">smallest_prime_factor[x]</code> 에는 $x$가 소수면 0, 합성수면 가장 작은 소인수가 들어가 있다. Linear Sieve에 대한 자세한 설명은 <a href="https://ahgus89.github.io/algorithm/Linear-sieve/">여기</a>에서 볼 수 있다.</p> <p>이를 활용한 코드는 4ms로 매우 빠른 속도를 보여주었다. <img src="https://i.imgur.com/LzIun9g.png" alt="" /></p> <h3 id="뫼비우스-함수">뫼비우스 함수</h3> <p>여태까지 위에서 구한 <code class="language-plaintext highlighter-rouge">sign[x]</code>는 사실 $\mu(x)$ 와 같이 쓰며 <a href="https://ko.wikipedia.org/wiki/%EB%AB%BC%EB%B9%84%EC%9A%B0%EC%8A%A4_%ED%95%A8%EC%88%98">뫼비우스 함수</a>라는 이름이 있다.</p> <div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="kt">void</span> <span class="nf">sign_precompute</span><span class="p">()</span> <span class="p">{</span> <span class="n">sign</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">MAX</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">2</span> <span class="o">*</span> <span class="n">i</span><span class="p">;</span> <span class="n">j</span> <span class="o">&lt;</span> <span class="n">MAX</span><span class="p">;</span> <span class="n">j</span> <span class="o">+=</span> <span class="n">i</span><span class="p">)</span> <span class="p">{</span> <span class="n">sign</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">-=</span> <span class="n">sign</span><span class="p">[</span><span class="n">i</span><span class="p">];</span> <span class="p">}</span> <span class="p">}</span> <span class="p">}</span> </code></pre></div></div> <p>위키를 통해 알 수 있듯이 정의는 우리가 구하려던것과 완전히 동일하고 이를 구하는 방법은 위와 같이 잘 알려져 있는데, 에라토스테네스의 체처럼 자신의 배수의 홀짝성이 바뀌는 것을 이용해 계산한다.</p> <p>위를 활용한 최종 코드는 다음과 같다.</p> <div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#include &lt;bits/stdc++.h&gt; </span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> <span class="k">const</span> <span class="kt">int</span> <span class="n">R</span> <span class="o">=</span> <span class="mi">1644934081</span><span class="p">;</span> <span class="k">const</span> <span class="kt">int</span> <span class="n">MAX</span> <span class="o">=</span> <span class="mi">40558</span><span class="p">;</span> <span class="kt">int</span> <span class="n">sign</span><span class="p">[</span><span class="n">MAX</span><span class="p">];</span> <span class="kt">void</span> <span class="nf">sign_precompute</span><span class="p">()</span> <span class="p">{</span> <span class="n">sign</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">MAX</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">2</span> <span class="o">*</span> <span class="n">i</span><span class="p">;</span> <span class="n">j</span> <span class="o">&lt;</span> <span class="n">MAX</span><span class="p">;</span> <span class="n">j</span> <span class="o">+=</span> <span class="n">i</span><span class="p">)</span> <span class="p">{</span> <span class="n">sign</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">-=</span> <span class="n">sign</span><span class="p">[</span><span class="n">i</span><span class="p">];</span> <span class="p">}</span> <span class="p">}</span> <span class="p">}</span> <span class="kt">int</span> <span class="nf">Q</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">)</span> <span class="p">{</span> <span class="kt">int</span> <span class="n">ans</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o">*</span> <span class="n">i</span> <span class="o">&lt;=</span> <span class="n">x</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span> <span class="n">ans</span> <span class="o">+=</span> <span class="n">sign</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">*</span> <span class="p">(</span><span class="n">x</span> <span class="o">/</span> <span class="p">(</span><span class="n">i</span> <span class="o">*</span> <span class="n">i</span><span class="p">));</span> <span class="p">}</span> <span class="k">return</span> <span class="n">ans</span><span class="p">;</span> <span class="p">}</span> <span class="kt">int</span> <span class="nf">main</span><span class="p">()</span> <span class="p">{</span> <span class="n">ios_base</span><span class="o">::</span><span class="n">sync_with_stdio</span><span class="p">(</span><span class="nb">false</span><span class="p">);</span> <span class="n">cin</span><span class="p">.</span><span class="n">tie</span><span class="p">(</span><span class="nb">nullptr</span><span class="p">);</span> <span class="n">sign_precompute</span><span class="p">();</span> <span class="kt">int</span> <span class="n">K</span><span class="p">;</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">K</span><span class="p">;</span> <span class="kt">int</span> <span class="n">s</span> <span class="o">=</span> <span class="mi">1</span><span class="p">,</span> <span class="n">e</span> <span class="o">=</span> <span class="n">R</span><span class="p">,</span> <span class="n">ans</span> <span class="o">=</span> <span class="n">e</span><span class="p">;</span> <span class="k">while</span> <span class="p">(</span><span class="n">s</span> <span class="o">&lt;=</span> <span class="n">e</span><span class="p">)</span> <span class="p">{</span> <span class="kt">int</span> <span class="n">m</span> <span class="o">=</span> <span class="n">s</span> <span class="o">+</span> <span class="p">(</span><span class="n">e</span> <span class="o">-</span> <span class="n">s</span><span class="p">)</span> <span class="o">/</span> <span class="mi">2</span><span class="p">;</span> <span class="k">if</span> <span class="p">(</span><span class="n">Q</span><span class="p">(</span><span class="n">m</span><span class="p">)</span> <span class="o">&lt;</span> <span class="n">K</span><span class="p">)</span> <span class="n">s</span> <span class="o">=</span> <span class="n">m</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span> <span class="k">else</span> <span class="n">e</span> <span class="o">=</span> <span class="n">m</span> <span class="o">-</span> <span class="mi">1</span><span class="p">,</span> <span class="n">ans</span> <span class="o">=</span> <span class="n">m</span><span class="p">;</span> <span class="p">}</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">ans</span><span class="p">;</span> <span class="p">}</span> </code></pre></div></div> <p>역시 4ms 에 배열을 조금 써서 메모리가 조금 줄었다.</p> <p><img src="https://i.imgur.com/c6Jrmzj.png" alt="" /></p> <p>혹시 다른 블로그 등에서 이 문제의 풀이를 보면 뫼비우스 함수 얘기를 먼저 꺼내곤 한다. 하지만 나도 그렇고 뫼비우스 함수를 갑자기 얘기하면 왜 이 함수가 나오는지 이해하기 힘들고 문제의 중요한 부분을 놓치게 된다. 이 문제의 핵심 풀이는 포함 배제에서 집합 $S$를 구하고 $q$를 구하는게 아니라 $q$를 구하고 집합을 구하는 발상이 가장 핵심 발상이라 할 수 있는데(개인적인 생각이다.) 그 부분의 주목도가 조금 떨어지는 것 같아서 아쉽다. 또한 뫼비우스를 모르고 있었어도 충분히 풀 수있다는 것을 이 블로그 글을 통해서 알리고 싶었다.</p> <h3 id="정답-예측하기">정답 예측하기</h3> <p>이 문제를 브루트 포스를 응용해서 풀 수 없을까 혹은 더 발전되어서 수학으로 한번에 푸는 방법이 없을까를 생각한다.</p> <table> <thead> <tr> <th>K</th> <th>K번째 제곱 ㄴㄴ수</th> </tr> </thead> <tbody> <tr> <td>1</td> <td>1</td> </tr> <tr> <td>10</td> <td>14</td> </tr> <tr> <td>100</td> <td>163</td> </tr> <tr> <td>1000</td> <td>1637</td> </tr> <tr> <td>10000</td> <td>16446</td> </tr> <tr> <td>100000</td> <td>164498</td> </tr> <tr> <td>1000000</td> <td>1644918</td> </tr> <tr> <td>10000000</td> <td>16449369</td> </tr> <tr> <td>100000000</td> <td>164493390</td> </tr> <tr> <td>1000000000</td> <td>1644934081</td> </tr> </tbody> </table> <p>무언가 규칙이 보이지 않는가? K번째 제곱 ㄴㄴ 수는 완벽하진 않더라도 약 1.64493…를 곱한 수에 매우 가깝다.</p> <p>정확히 이 수는 $\pi^2/6$ (역수로 보면 $6/\pi^2$)에 수렴한다. 갑자기 뜬금없이 $\pi$가 나왔다. 원과는 전혀 관련이 없어 보이는 문제임에도 말이다.</p> <p>왜냐하면 Q(x)를 위에서 정의한 함수라고 하고 x가 매우 큰수라고 하자. 그러면 3/4는 4로 나누어떨어지지 않을 것이고, 8/9는 9로 나누어 떨어지지 않을 것이다. 그런식으로 가다보면 multiplicative property를 만족하기 때문에</p> <p>$\begin{align}Q(x) &amp;\approx x\prod_{p\ \text{prime}} \left(1-\frac{1}{p^2}\right) = x\prod_{p\ \text{prime}} \frac{1}{(1-\frac{1}{p^2})^{-1}}<br /> &amp;\approx x\prod_{p\ \text{prime}} \frac{1}{1+\frac{1}{p^2}+\frac{1}{p^4}+\cdots} = \frac{x}{\sum_{k=1}^\infty \frac{1}{k^2}} = \frac{x}{\zeta(2)} = \frac{6x}{\pi^2}.\end{align}$</p> <p>임을 알 수 있다.</p> <p>리만 제타 함수 $\zeta(2)$ 는 Basel Problem 이라는 문제로도 유명하며 이 값에 <a href="https://youtu.be/d-o3eB9sfls">왜 $\pi$가 나오는지는 아주 잘 설명해주는 영상</a>이 있다.</p> <p>또한 $Q(x) = \frac{6x}{\pi^2} + O\left(\sqrt{x}\right)$ 라는것이 알려져 있으며 <a href="https://www.sciencedirect.com/science/article/pii/S0022314X15002462">2015년 논문</a>에서는 $O(x^{11/35+\epsilon})$ 이라고 오차항이 더 작음을 증명했다. 어쨋든 간에 $Q(x)$와 $x$ 사이의 관계가 $6/\pi^2$에서 크게 벗어나지 않음을 알 수 있다. 이를 이용하면 이분 탐색의 L~R범위의 후보를 줄일 수가 있다.</p> <p>심지어 이를 활용해 리니어 서치로 하는 코드도 통과가 된 것을 확인할 수 있다.</p> <h3 id="더더-발전하기">더더 발전하기</h3> <p>아직 끝이 아니라 더 시간 복잡도를 줄인 논문이 존재한다. 바이너리 서치를 빼고 현재 $O(\sqrt N)$ 인 알고리즘을 $O(N^{2/5})$로 더 최적화 시켰다. 이것까지 소개하는 건 안그래도 글이 너무 긴데 더 길어질것 같아서 이만 줄인다. 관심 있는 사람은 <a href="https://www.researchgate.net/publication/51918452_Counting_Square-Free_Numbers">링크</a> 확인</p> <h2 id="비슷한-문제">비슷한 문제</h2> <h3 id="프로젝트-오일러-193번-제곱청정-수"><a href="https://projecteuler.net/problem=193">프로젝트 오일러 193번: 제곱청정 수</a></h3> <p>$2^{50}$미만의 제곱청정 수는 몇 개입니까?</p> <h3 id="해커랭크-프로젝트-오일러-193번"><a href="https://www.hackerrank.com/contests/projecteuler/challenges/euler193/problem">해커랭크: 프로젝트 오일러 193번</a></h3> <p>$K$의 제한이 $10^{18}$로 증가한 BOJ 1557번</p> <h3 id="백준-8464번-non-squarefree-numbers"><a href="https://www.acmicpc.net/problem/8464">백준 8464번: Non-Squarefree Numbers</a></h3> <p>사실 이 문제가 많이 풀린 이유중 하나가 한 문제 풀면 다이아 2개를 풀 수 있기 때문이다.</p> <h3 id="백준-2814번-최소인수"><a href="https://www.acmicpc.net/problem/2814">백준 2814번: 최소인수</a></h3> <p>소수와 포함 배제 등에 재미를 느꼈으면 또 풀만한 문제</p> <h3 id="백준-1792번-공약수"><a href="https://www.acmicpc.net/problem/1792">백준 1792번: 공약수</a></h3> <p>뫼비우스 함수를 넘어, 뫼비우스 반전 공식의 튜토리얼(?) 급 문제</p>solarmagic2021 ICPC Regional 후기와 연습 기록2021-11-15T00:00:00+00:002021-11-15T00:00:00+00:00https://blog.solarmagic.dev/icpc/2021/11/15/icpc2021regional<p><img src="https://i.imgur.com/w76yOFw.png" alt="" /></p> <p>나(solarmagic)와 팀원(tlsdydaud1, dtc03012)과의 2021년 프로그래밍 대회 후기</p> <h2 id="팀-결성">팀 결성</h2> <p>2020년 2월 4일 tlsdydaud1과 dtc03012와 UCPC, ICPC팀을 하기로했다.</p> <p>팀명은</p> <ul> <li><strong>s</strong> olarmagic</li> <li><strong>t</strong> lsdydaud1</li> <li><strong>d</strong> tc03012</li> </ul> <p>에서 따와 <strong>std</strong>::accept으로 하였다.</p> <h2 id="전반기-팀-연습">전반기 팀 연습</h2> <p>디테일 후기는 팀원의 후기로 대체한다.</p> <ul> <li><a href="https://codeforces.com/gym/102556">2020 Ateneo de Manila University DISCS PrO HS Division</a> <ul> <li><a href="https://blog.naver.com/tlsdydaud1/222254736913">디테일 후기</a></li> <li>2021-02-23, 온라인, 3시간</li> <li>온라인으로 처음 풀었는데 쉬운 셋이었는데 페널티 보다시피 개말렸다</li> <li><img src="https://i.imgur.com/jpVHJ0r.png" alt="" /></li> </ul> </li> <li><a href="https://codeforces.com/gym/102900">2020 ICPC Shanghai Site</a> <ul> <li><a href="https://blog.naver.com/tlsdydaud1/222285807994">디테일 후기</a></li> <li>2021-03-17, 오프라인, 5시간</li> <li>너무 어려웠고 엄청 못했다</li> <li><img src="https://i.imgur.com/qbE4zoN.png" alt="" /></li> </ul> </li> <li><a href="https://www.acmicpc.net/category/detail/2360">Benelux Algorithm Programming Contest 2020</a> <ul> <li><a href="https://blog.naver.com/tlsdydaud1/222296066487">디테일 후기</a></li> <li>2021-03-31, 오프라인, 5시간</li> <li>처음으로 그래도 잘 푼 것 같다. BAPC는 항상 잘푸는 듯</li> <li><img src="https://i.imgur.com/OoYmGki.png" alt="" /></li> </ul> </li> <li><a href="https://www.acmicpc.net/category/detail/2396">The 2020 ICPC Asia Jakarta Regional Contest</a> <ul> <li><a href="https://blog.naver.com/tlsdydaud1/222339926794">디테일 후기</a></li> <li>2021-05-05, 오프라인, 5시간</li> <li><img src="https://i.imgur.com/XUY6Ylh.png" alt="" /></li> <li>20분만 더 있었으면 9솔인데…</li> <li><img src="https://i.imgur.com/15vsa4v.png" alt="" /></li> </ul> </li> <li><a href="https://codeforces.com/gym/103049">2020-2021 ICPC Northwestern European Regional Programming Contest (NWERC 2020)</a> <ul> <li><a href="https://blog.naver.com/tlsdydaud1/222357180307">디테일 후기</a></li> <li>2021-05-17, 오프라인, 5시간</li> <li>무난하게 한듯 J도 맞췄으면 좋았지만</li> <li><img src="https://i.imgur.com/NNemKIf.png" alt="" /></li> </ul> </li> <li><a href="https://codeforces.com/gym/102556">2020-2021 ICPC Southwestern European Regional Contest (SWERC 2020)</a> <ul> <li><a href="https://blog.naver.com/tlsdydaud1/222388402858">디테일 후기</a></li> <li>2021-05-31, 오프라인, 5시간</li> <li>저번이랑 비슷한 퍼포먼스 B를 잡으면 안되었음</li> <li><img src="https://i.imgur.com/XmSV259.png" alt="" /></li> </ul> </li> <li><a href="https://codeforces.com/gym/102785">ICPC Central Russia Regional Contest (CRRC 18)</a> <ul> <li><a href="https://blog.naver.com/tlsdydaud1/222420920375">디테일 후기</a></li> <li>2021-07-03, 오프라인, 5시간</li> <li>문제 읽기 어렵고 파싱 나왔는데 무난하게 품, 팀 실력이 안정화 되고 있다 느낌</li> <li><img src="https://i.imgur.com/3wdJq7r.png" alt="" /></li> </ul> </li> <li><a href="https://www.acmicpc.net/category/detail/1956">Latin America Regional Contests 2018</a> <ul> <li><a href="https://blog.naver.com/tlsdydaud1/222436054180">디테일 후기</a></li> <li>2021-07-17, 오프라인, 5시간</li> <li>J번 뭔가 쉽게 될것 같은데 알고보니 엄청 어려운 문제</li> <li><img src="https://i.imgur.com/u9ckRVa.png" alt="" /></li> </ul> </li> </ul> <h2 id="ucpc-2021">UCPC 2021</h2> <p><a href="(https://ucpc.me/)">링크</a></p> <p><img src="https://i.imgur.com/dNv2RrY.png" alt="" /></p> <p>2021 여름 대회 전국 대학생 프로그래밍 대회 동아리 연합 대학생이 참여할수 있는 대회중에선 참가 범위가 가장 넓은 대회이다.</p> <h3 id="ucpc-2021-예선">UCPC 2021 예선</h3> <p><a href="https://www.acmicpc.net/category/detail/2692">문제 링크</a></p> <ul> <li><a href="https://blog.naver.com/tlsdydaud1/222453131140">디테일 후기</a></li> <li>2021-07-31, 3시간, 오프라인(대회는 온라인)</li> <li><a href="https://ucpc.acmicpc.net/contest/spotboard/668">스코어보드</a> <ul> <li><img src="https://i.imgur.com/ldbQLzt.png" alt="" /></li> <li>E를 맞추지 못해서 좀 아쉬웠다. J는 센트로이드 분할 문제라서 좀 미리 공부할걸 생각을 했다.</li> <li>어쨌든 본선 진출은 했으나 바로 위에 같은 학교 팀이 있었다.</li> </ul> </li> </ul> <h3 id="ucpc-2021-본선httpswwwacmicpcnetcategorydetail2743">UCPC 2021 본선(https://www.acmicpc.net/category/detail/2743)</h3> <ul> <li><a href="https://blog.naver.com/tlsdydaud1/222472079305">디테일 후기</a></li> <li>2021-08-14</li> <li>5시간, 오프라인(대회는 온라인)</li> <li><a href="https://ucpc.acmicpc.net/contest/spotboard/670">스코어보드</a> <ul> <li><img src="https://i.imgur.com/UkzBNao.png" alt="" /></li> <li>실력은 늘었는데 등수는 떨어지는걸 보고 붉은 여왕효과를 크게 느끼기도 했다. (18년 27등, 19년 27등, 20년 23등, 21년 35등)</li> <li>한문제 더 풀었어야 평소 등수랑 비슷했을텐데 F번이 너무 수학수학하게 생겨서 감도 못잡은게 큰 것 같다. (6솔 팀은 1팀 빼고 F를 풀었다)</li> </ul> </li> </ul> <h3 id="후반기-팀-연습">후반기 팀 연습</h3> <ul> <li>개인 팀 연습 <ul> <li>2021-09-10, 온라인, 3시간</li> <li>백준에서 적당히 문제를 골라서 대회처럼 문제를 풀었다.</li> <li><img src="https://i.imgur.com/jfMhMnb.png" alt="" /></li> <li>방식이 별로여서 다시는 하지 않았다.</li> </ul> </li> <li><a href="https://codeforces.com/gym/103202">The 2020 ICPC Asia Shenyang Regional Programming Contest</a> <ul> <li><a href="https://blog.naver.com/tlsdydaud1/222525000962">디테일 후기</a></li> <li>2021-09-24, 오프라인, 5시간</li> <li>전체적으로 어려웠다. M번 문제를 통해서 FWT의 존재를 알게되었는데 상당히 재밌어서 백준에서 문제 좀 풀었다.</li> <li><img src="https://i.imgur.com/YMkYv34.png" alt="" /></li> </ul> </li> <li><a href="https://www.acmicpc.net/category/detail/2567">ICPC 2020 Asia Yokohama Regional</a> <ul> <li><a href="https://blog.naver.com/tlsdydaud1/222560095322">디테일 후기</a></li> <li>2021-10-15, 오프라인, 5시간</li> <li>역대 최악으로 말렸다. 악몽같은 셋</li> <li><img src="https://i.imgur.com/7bu6yux.png" alt="" /></li> </ul> </li> <li><a href="https://codeforces.com/gym/101572">2017-2018 ACM-ICPC Nordic Collegiate Programming Contest (NCPC 2017)</a></li> <li><a href="https://blog.naver.com/tlsdydaud1/222560143153">디테일 후기</a> <ul> <li>2021-10-31, 온라인, 5시간</li> <li>gs12117님이 이 셋을 돌았다고 해서 했는데 상당히 잘 풀렸다 A도 풀 수 있었는데 A번 풀이를 정확히 이해 못해서 디버깅을 못도와줬다</li> <li><img src="https://i.imgur.com/tflupl0.png" alt="" /></li> </ul> </li> <li><a href="https://codeforces.com/gym/101170">2016-2017 ACM-ICPC Northwestern European Regional Programming Contest (NWERC 2016)</a> <ul> <li><a href="https://blog.naver.com/tlsdydaud1/222560208459">디테일 후기</a></li> <li>2021-11-05, 오프라인, 5시간</li> <li>마지막 팀 연습, 초반에 말렸으나 어떻게 풀 문제들은 다 풀었다 ICPC본선을 위한 준비를 잘 했다 생각했다.</li> <li><img src="https://i.imgur.com/OssNqHb.png" alt="" /></li> </ul> </li> </ul> <h2 id="icpc-seoul-regional-2021"><a href="http://icpckorea.org/">ICPC Seoul Regional 2021</a></h2> <h3 id="icpc-seoul-regional-2021-예선"><a href="http://icpckorea.org/archives/2463">ICPC Seoul Regional 2021 예선</a></h3> <ul> <li><a href="https://blog.naver.com/tlsdydaud1/222532818066">디테일 후기</a></li> <li>2021-10-09, 3시간, 오프라인(대회는 온라인)</li> <li>I, L번을 퍼스트 솔브 했다.</li> <li>그 밖에도 문제들을 계속 빠르게 맞춰서 초반에 5등 안에 계속 있었고 프리즈 때 6등이었고 프리즈때 한문제도 풀지 못해 8등으로 끝났다.</li> <li><img src="https://i.imgur.com/6CCZ1ZO.png" alt="" /></li> <li>C번은 진짜 풀만 했는데 머리가 후반에 돌아가지 않았다.</li> <li>예선에서 한자릿수 등수를 받으면서 본선 성적에 대한 엄청난 기대를 하게 되었다.</li> </ul> <h3 id="icpc-seoul-regional-2021-1"><a href="http://icpckorea.org/archives/2562">ICPC Seoul Regional 2021</a></h3> <ul> <li>2021-11-13, 5시간, 오프라인(대회는 온라인)</li> <li>12시 부터 대회 시작이고 대회 세팅(팀노트 준비, 카메라 세팅 등)을 해야해서 10시에 모이기로 했다.</li> <li>개인적으로는 대회 시간이 아쉬웠다. 10시에 모이려면 다들 엄청 일찍어나서 와야하는데 평소에는 1~2시에 모이자마자 대회를 했고 나는 원래 늦게 자는 패턴이었다.</li> <li>처음에는 개운한줄 알았는데 잠을 별로 못자고 와서 정말 대회 시작 30분전부터 눈꺼풀이 엄청 감겼다 하지만 그래도 대회를 하니 집중력 떄문에 졸리진 않았지만 피곤한게 좀 컸다.</li> <li>대회 셋은 정말정말 헬셋이었다. 실버 2개를 제외하면 현재(11/15) 기준으로는 전부 플레 중위권 이상의 매우 어려운 문제로만 구성되었다. <ul> <li>골드, 플레 하위가 없는게 아쉬운게 본선 하위권 팀 얘기를 들어보면 실버 2문제 1시간 안에 풀고 4시간 동안 풀 수 있는 문제가 없었다고 한다. (2솔팀이 매우 많다.)</li> </ul> </li> <li>우여 곡절이 많이 있었다. 실버 2문제는 빠르게 풀었으나 그 다음부터 상당히 고전을 했다.</li> <li>D번 문제의 풀이는 금방 나와서 코딩도 완료 했으나, 맞왜틀 고민을 한시간 동안 했다. <ul> <li>여기서 사실 멘탈이 터졌다.</li> <li>최근 나는 디버깅 연습을 하려고 최고의 반례 만들기 게임인 백준 질문/답변을 하고 있었다.</li> <li>진짜 맞는것 같아 보이는 코드인데 최대한 부정적으로 보면서 반례 만드는걸 하니깐 도와줘서 뿌듯하기도 하고 코드 잘못된 부분 찾는 실력이 느는것 같았다.</li> <li>그런데 이 코드도 정말 거기에 나오는 전형적인 패턴인 배열 음수 인덱스 참조 문제였다.</li> <li>그러나 그 때 나의 컨디션이 안좋아서 그걸 캐치를 못했다.</li> <li>또한 사실 집에서 디버깅 연습할때는 -fsanizite 옵션을 켜놔서 컴파일러가 음수 인덱스 접근하면 바로 잡아줘서 편했다.</li> <li>스노우볼이 구른게 대회 컴퓨터에 미리 체크를 안해서 대회 당일날 그 옵션을 넣으려고 했다가 gcc가 아니라 minGW라서 안되었다. “그래서 뭐 별상관없지 했다”가 호되게 당했다.</li> <li>약간 이런 여러가지 사정이 겹쳐서 좀 자책감 들면서 다른 문제가 잘 안보였다</li> </ul> </li> <li>L번은 dtc03012님이 혼자서 고민하면서 알아서 푸셨다.</li> <li>E번은 해석이 조금 어려웠는데 어쩄든 a+b=c 개수 구하라는건 금방 파악할수 있었다. <ul> <li>디테일한 개수세기만 이제 잘 구현하면 되는데 적당히 식 나오는게 보였고 혼자서 하는거였으면 뭔가 계속하면서 공식 만들 수 있을것 같긴했는데 tlsdyadu1이 더 잘할것 같아서 그냥 뭔가 놓게 되었다.</li> <li>어떻게 풀긴 했지만 상당히 느리게 풀긴했다. 도와줬어야했는데 그걸 못했다. 그냥 내가 혼자 푼다고 얘기해도 풀 수 있을것같았는데 자신이 없었다</li> </ul> </li> <li>G번은 트리 dp 문제인데 이것도 구현에 좀 미스가 있었고(사실 풀이자체가 좀 잘못되었다) 결국 이 문제도 tlsdydaud1이 E를 끝낸다음에 빠르게 풀었다. 이 문제부터 먼저 잡았다면~ 스노우볼도 굴렀다.</li> <li>이렇게 5솔을 했고 F, K가 아쉬운 문제였다.</li> <li>K번은 내가 먼저 해석을 했는데 진짜 너무 어려워서 그냥 조용히 있었다. 근데 또 스노우볼이 구른게 사실 이 문제는 dtc03012님이 알고 있는 문제였다. <ul> <li><a href="https://www.acmicpc.net/problem/20298">파인애플 피자</a>라고 비슷한 문제를 풀었다고 풀줄 안다고 한다.</li> <li><img src="https://i.imgur.com/NtPET4r.png" alt="" /></li> <li>위 사진에서 보다시피 3달전에 이 문제를 풀었고 대회 이틀전(11/11)에 다시 한번 풀었는데 정말 우연히 똑같은 문제가 나온거였다!!</li> <li>dtc03012님이 G번을 열심히 고민하고 있었기 때문에 내가 K번 읽고 좀 고민해봤는데 매우 어려운걸로 결론나서 그냥 조용히 있었다. (괜히 집중 방해 될까봐)</li> <li>K번을 그러다 늦게 잡아서 코딩을 시작했고 kmp + 세그먼트 트리풀이를 짜는데 약간의 디테일 이슈로 뭔가 값이 제대로 나오지 않았다.</li> <li>대회 끝나고 5시 10분에서야 모든 예제가 제대로 나왔다.</li> <li>여기서 이제 많은 ‘라면’을 끓일수 있었다. <ul> <li>D번을 빨리 디버깅 했더라면</li> <li>컴퓨터 컴파일러 옵션을 빨리 설정했더라면</li> <li>G번을 tlsdydaud1이 잡았더라면</li> <li>K번 해석을 그냥 넌지시 던졌더라면</li> <li>K번 풀 시간을 좀 더 줬더라면</li> <li>K번 오래 걸리고 다이아 문제였는데 그냥 차라리 F번 잡었더라면</li> <li><del>다른 팀원은 딴거 풀고 내가 E번을 내가 잡았더라면</del></li> </ul> </li> </ul> </li> <li>F번은 초반에 별로 안 풀렸는데 생각보다 쉬운 문제였다 <ul> <li>그냥 적당히 하면 될것같은 풀이가 나오긴 했는데 다른 팀들이 푼 풀이랑 달라서 실제로 되었을지는 살짝 의문이다.</li> <li>확실한건 그렇게 어렵진 않았고 시간 관리같은걸 잘했으면 풀만한 문제였는데 D, E, G, K 코딩을 하느라 컴퓨터가 쉬질 않았고 F를 풀시간은 존재하지 않았다.</li> </ul> </li> </ul> <h3 id="icpc-seoul-regional-2021-결과-및-후기"><a href="http://static.icpckorea.net/2021/scoreboard_regional/">ICPC Seoul Regional 2021 결과 및 후기</a></h3> <ul> <li><img src="https://i.imgur.com/wWO1ZaM.png" alt="" /></li> <li>결론적으로는 6솔 22등을 하게되었다.</li> <li>예선때 8등을 하면서 WF도 노려볼만했다는 생각과는 다르게 본선에서는 정말 아쉬운 성적이 나왔다.</li> <li>결론적으로는 UCPC와 ICPC 모두 학교 1등을 하는 것도 수상을 하는 것도 실패했다.</li> <li>대회가 끝났을때는 기분이 많이 안좋았고 사실 지금도 좋지는 않지만 큰 그림으로는 나쁘지 않다 생각한다.</li> <li>ICPC만 보면 아쉽지만 20번 가까이 팀원들과 모이면서 연습을 하는 과정이나 문제를 풀면서 나의 실력 상승 같은건 많이 도움되었다고 생각한다.</li> <li>1등을 한 서울대 FSM, 2등을 카이스트 Do Solve, 8등을 한 숭실대 LongestPathToWF팀에게 박수를 보낸다. 정말 대한민국을 대표할만한 엄청난 사람들이고 WF가 어떻게 될지는 모르겠지만 WF deserve한 팀이다.</li> <li>입학하고 나서 PS를 시작하면서 찾아보니깐 서,카,연,고,서,성 그리고 이대까지 WF를 갔는데 한양대는 한번도 WF를 간적이 없다는걸 알게 되었다.</li> <li>학벌주의를 좋아하지는 않지만 일반적으로 많이 쓰이는 ‘서성한’에서 우리학교만 못간게 약간 자존심이 상하면서 기록을 찾아보니 서강대는 백준온라인저지의 최백준님을 필두로 한 번 나간적이 있었고, 성균관대는 We love kriii의 주인공 김경근님을 필두로해서 2번 나간적이 있었던거였다. (물론 다른 팀원분들도 열심히 하셨을 거지만 두분의 이야기가 비교적 많이 들렸다는 얘기다.)</li> <li>그래서 그렇다면 한양대학교는 나(solarmagic)를 필두로 나갔다는 기록을 세우겠다는 신입생의 패기가 있었고 이걸 위해서 4~5년동안 PS를 하기 시작했다. (열심히 한 기간은 적긴하다.)</li> <li>대학 다니기전 hyunguk님이 해외리저널도 나가면서 도전을 했었다. 그리고 내가 대학을 다닐때도 나보다 고학년인 ckw1140님과 djm03178님도 도전을 했지만 아쉽게 되지 않았다.</li> <li>올해 나(solarmagic)과 dtc03012님은 마지막 ICPC였는데 Last Dance를 이루겠다는 약간의 마음가짐이 있었으나 Last Dance는 없었다.</li> <li>solarmagic은 이제 없다. 이제는 후배들의 차례다. tlsdydaud1은 아직 ICPC를 더 나갈수 있으면서 우리 팀에서 대회떄 가장 퍼포먼스가 좋았다. 레드 찍을 수 있다고 본다. SushidoQueue(artichoke42, jame0313, kyaryunha)는 우리팀보다 UCPC, ICPC를 더 잘 치루었고 이에 정말 큰 박수를 보낸다. 이 팀의 인원도 모두 나보다 싱싱한 두뇌라서 내년에도 나갈 수 있고 내년엔 더 좋은 성적을 낼거라 믿는다. 그 밖에도 18학번 이후로 ydk1104, juchan1220, ploffer11 등 그리고 내가 모르는 후배들도 충분히 큰 일을 낼 수 있는 사람이라 생각한다. 또한 22학번 등의 앞으로의 후배들도 기대가 된다. 내가 못 이룬 꿈을 누군가 꼭 이뤄줬으면 한다. 정말로!</li> </ul> <h2 id="팀-후기">팀 후기</h2> <p><img src="https://i.imgur.com/nKlKLgQ.png" alt="" /></p> <ul> <li>코로나라서 밖에 나갈일 없는데 팀연습하느라 가끔식 햇빛 구경해서 좋았다.</li> <li>팀원들 너무 잘하고 성격도 좋았다. 17년부터 PS를 하면서 많은 팀을 맺었지만 이번 팀이 가장 여러가지가 좋았다고 얘기할 수 있다. (이 글을 보는 다른 내 과거 팀원들이 뻘쭘할것 같으니 그 팀은 근소한 차이로 2등이라고 얘기하겠다)</li> <li>마음속 할 말은 팀노트 분량보다 많은데 막상 쓰기에는 오그라드니 그냥 접어두고 나중에 만나서 노는거나 했으면 좋겠다. <ul> <li>방탈출 ㄱㄱ</li> </ul> </li> </ul> <hr /> <p>전체적으로 아무말 대잔치를 했는데 그냥 할말이 많은데 그냥 메모장 남기듯이 하나는 남겨놔야 할것 같아서 아무렇게나 써봤다.</p> <ul> <li>PS는 접지 않을 거지만 그전만큼 열심히 하지는 않을 것 같다.</li> <li>다음 블로그 글에는 아마 나의 PS 이력을 한 번 정리하는 시간을 가질것 같다.</li> <li>앞으로는 일주일에 하나씩 블로그 글 써야지</li> </ul>solarmagicICPC와 한국2021-10-05T00:00:00+00:002021-10-05T00:00:00+00:00https://blog.solarmagic.dev/icpc/2021/10/05/icpchistory<p><img src="https://i.imgur.com/nKlKLgQ.png" alt="" /></p> <h1 id="icpc-와-한국팀의-도전기">ICPC 와 한국팀의 도전기</h1> <p>한국팀이 2021년에 열린 ICPC World Finals Moscow에서 놀라운 성과를 보여주었다. 역대 최고 성적인 2등을 기록하면서 금메달을 목에 걸었다. ICPC 기록을 누군가 정리한 글이 따로 없어서 한번 인터넷에서 자료를 모아서 정리해보았다.</p> <h2 id="icpc는-무엇인가">ICPC는 무엇인가?</h2> <p>과거 ACM-ICPC 불렸던 ICPC(International Collegiate Programming Contest, 국제대학생프로그래밍대회)는 1970년 텍사스에서 UPE Computer Science Honor Society가 주최한 경진대회에서 그 아이디어를 얻어 1977년 ACM의 주최로 첫 대회를 개최하였다. 이후 2017년까지 ACM의 주최로 ACM-ICPC로 불리다 현재는 ICPC로 이름을 바꾸었다. 전 세계 각지의 우수한 대학들의 우수한 인재들의 두뇌 경진 대회라 할 수 있다.</p> <p>알고리즘을 공부하는 대학생들의 최종 목표중 하나가 이 대회에서 수상, 결선(World Finals) 진출, 지역 대회(Regional)에서 높은 순위를 기록하는 것이다. 이 대회 결선에서 상을 받는 것은 프로그래머로서의 최고의 영예중 하나이다.</p> <h2 id="icpc의-역사">ICPC의 역사</h2> <p><img src="https://i.imgur.com/QNY7Wn4.png" alt="" /></p> <blockquote> <p>1977~1996 ACM-ICPC 우승 대학</p> </blockquote> <p>1977년부터 시작한 이 대회는 처음에는 주로 미국과 캐나다 대학이 참여했고 팀원 수도 3명이 아닌 4명이었다. 우승 대학도 주로 미국에 몰려있는 것을 알 수 있다. 그러나 1997년부터 IBM의 후원을 받으면서 대회가 질적, 양적으로 크게 성장하게 된다.</p> <p><img src="https://i.imgur.com/SxRSBO5.png" alt="" /></p> <p>1997년부터 IBM의 후원을 받기 시작하는데 이 후로 20년동안 2000% 이상의 참여가 늘어났다. 한국 팀 또한 비슷한 시기인 2000년 부터 지역 대회를열기 시작했다. 그래프에 나오듯이 2019년 대회에는 58,963명의 학생이 참여를 했고, 3406개의 대학, 104개의 나라에서 참여를 했다.</p> <p><img src="https://i.imgur.com/WwxrTR2.png" alt="" /></p> <blockquote> <p>참가자 수가 크게 늘어난 2000년대 부터는 오직 러시아, 중국, 폴란드의 대학만이 우승을 차지했다.</p> </blockquote> <h2 id="icpc-world-finals에-진출하는-법">ICPC World Finals에 진출하는 법</h2> <p>ICPC 대회에서는 대학을 대표하는 3명의 학생이 여러 단계의 지역 대회(Regional, 리저널)를 통과해야 최종 대회인 World Finals(WF)에 진출할 수 있다. 한국의 대학생은 주로 서울 리저널에 참여하게 되며, 서울 리저널에서 우수한 성적을 거둔 2개 정도의 대학의 팀이 월드 파이널에 진출하게 된다. 1등과 2등이 같은 A 대학에 나왔어도 대학의 대표는 한 팀만이 될 수 있으므로 A 대학을 제외한 가장 높은 성적을 기록한 대학의 최고 팀에게 WF 티켓(진출권)이 돌아가게 된다. 리저널을 한 해에 다음 해에 일반적으로 WF를 치룬다.</p> <p><img src="https://i.imgur.com/hTgqsZH.png" alt="" /></p> <blockquote> <p>ICPC에서는 지역을 이렇게 나누어서 관리하고, 한국은 아시아퍼시픽(보라색)에 해당한다.</p> </blockquote> <p>각 리저널은 주로 개최한 나라의 대학들이 많이 참여하지만 다른 나라의 리저널에 한국 팀이 참여하거나 한국 리저널에 다른 나라 팀이 참여하기도 한다. 그런 것들을 고려해 각 리저널의 가중치를 매겨서 WF 티켓을 준다. 한국 대회는 매년 바뀌지만 2장 이상의 티켓이 배분된다. (2005년까지는 1장이었다고 한다.)</p> <p>자세한 WF 티켓 규정은 규정이 자주 바뀌어 <a href="https://icpcasia.wp.txstate.edu/">ICPC 아시아 지역을 관리하는 사람의 블로그</a>에서 확인하는 것이 가장 정확하다.</p> <h2 id="역대-한국-regional">역대 한국 Regional</h2> <p><a href="http://icpckorea.org/">ICPC Korea</a></p> <p>한국은 2000년도 부터 대회를 주최했고 자세한 기록은 위 사이트에서 확인할 수 있으나 예전 기록은 말소되었고 찾기 어려운 경우가 많다.</p> <table> <thead> <tr> <th>연도</th> <th>우승학교</th> </tr> </thead> <tbody> <tr> <td>2000</td> <td>KAIST</td> </tr> <tr> <td>2001</td> <td>서울대학교</td> </tr> <tr> <td>2002</td> <td>KAIST</td> </tr> <tr> <td>2003</td> <td>KAIST</td> </tr> <tr> <td>2004</td> <td>서울대학교</td> </tr> <tr> <td>2005</td> <td>상해교통대학교</td> </tr> <tr> <td>2006</td> <td>서울대학교</td> </tr> <tr> <td>2007</td> <td>서울대학교</td> </tr> <tr> <td>2008</td> <td>서울대학교</td> </tr> <tr> <td>2009</td> <td>KAIST</td> </tr> <tr> <td>2010</td> <td>KAIST</td> </tr> <tr> <td>2011</td> <td>서울대학교</td> </tr> <tr> <td>2012</td> <td>KAIST</td> </tr> <tr> <td>2013</td> <td>동경대학교</td> </tr> <tr> <td>2014</td> <td>서울대학교</td> </tr> <tr> <td>2015</td> <td>KAIST</td> </tr> <tr> <td>2016</td> <td>서울대학교</td> </tr> <tr> <td>2017</td> <td>서울대학교</td> </tr> <tr> <td>2018</td> <td>서울대학교</td> </tr> <tr> <td>2019</td> <td>서울대학교</td> </tr> <tr> <td>2020</td> <td>서울대학교</td> </tr> <tr> <td>2021</td> <td>???</td> </tr> </tbody> </table> <p>해외 대학이 우승한 2005년과 2013년을 제외하고 서울대학교와 KAIST가 번갈아가면서 우승을 차지하고 있는 양상이다. 최근에는 5년 연속으로 서울대학교가 우승하며 압도적인 모습을 보여주었고 지난 2020년 대회에서는 1등부터 5등을 서울대학교가 모두 차지하기도 했다.</p> <h2 id="역대-한국의-world-finals">역대 한국의 World Finals</h2> <p>대만이나 중국같은 해외 리저널에서 티켓을 따 한국 리저널이 생기기전 1996년 부터 월드 파이널에 한국 팀이 진출하였다.</p> <table> <thead> <tr> <th>연도</th> <th>우승학교</th> </tr> </thead> <tbody> <tr> <td>1996</td> <td>KAIST</td> </tr> <tr> <td>1997</td> <td>KAIST</td> </tr> <tr> <td>1999</td> <td>KAIST</td> </tr> <tr> <td>2001</td> <td>서울대학교(은), 연세대학교, KAIST</td> </tr> <tr> <td>2002</td> <td>서울대학교, 이화여자대학교</td> </tr> <tr> <td>2003</td> <td>연세대학교, KAIST</td> </tr> <tr> <td>2004</td> <td>서울대학교, 연세대학교, KAIST</td> </tr> <tr> <td>2005</td> <td>서울대학교, 연세대학교, ICU</td> </tr> <tr> <td>2006</td> <td>서울대학교, KAIST, ICU</td> </tr> <tr> <td>2007</td> <td>서울대학교, KAIST</td> </tr> <tr> <td>2008</td> <td>서울대학교, ICU</td> </tr> <tr> <td>2009</td> <td>서울대학교, KAIST</td> </tr> <tr> <td>2010</td> <td>서강대학교, 서울대학교, KAIST</td> </tr> <tr> <td>2011</td> <td>서울대학교, KAIST</td> </tr> <tr> <td>2012</td> <td>고려대학교, 서울대학교</td> </tr> <tr> <td>2013</td> <td>성균관대학교, KAIST</td> </tr> <tr> <td>2014</td> <td>고려대학교, 성균관대학교</td> </tr> <tr> <td>2015</td> <td>고려대학교(동, 11위), 서울대학교, KAIST</td> </tr> <tr> <td>2016</td> <td>고려대학교, KAIST</td> </tr> <tr> <td>2017</td> <td>서울대학교(금, 3위), KAIST(동, 9위)</td> </tr> <tr> <td>2018</td> <td>서울대학교(은, 5위), KAIST, UNIST</td> </tr> <tr> <td>2019</td> <td>서울대학교(은, 7위), KAIST</td> </tr> <tr> <td>2020</td> <td>경북대학교, 고려대학교, 서강대학교, 서울대학교(금, 2위), 연세대학교, UNIST</td> </tr> <tr> <td>2021</td> <td>???</td> </tr> </tbody> </table> <p>특정대학교만 많이 참여하는 것을 볼 수 있다. 그리고 한 사람당 ICPC WF는 최대 2번만 진출 가능하다.</p> <h3 id="2020-icpc-world-finals">2020 ICPC World Finals</h3> <p>2020 ICPC World Finals는 2020년에 열리지 못하였고 2021년에 열리게 되었다. 그러면서 참가 팀에도 변화가 생겼는데 연도가 바뀌면서 못참가하게 되는 팀도 생겼고, 코로나 백신 접종이 힘든 나라들이 참가가 어려워지면서 Wildcard slot이 생겨 서강대, UNIST, 경북대 등의 한국팀이 수혜를 보게되어서 역대 최대 참가가 이루어졌다! (반면 KAIST는 불참하게 되었다.)</p> <p>경기 진행 방식도 달라졌는데 원래는 3인이 오직 1대의 컴퓨터를 통해 문제 해결을 해야했던 방면 이번 WF에서는 칸막이로 구분된 공간에서 각자 컴퓨터로 코딩 하는 3인 3컴퓨터 WF가 되었고 문제 수도 평소보다 많이 늘었다.</p> <h3 id="여러가지-사실들">여러가지 사실들</h3> <ul> <li>서울대: ainta는 유일한 한국 ICPC WF 금메달 2회 수상이다. 그밖에 많은 기록을 서울대가 보유하고 있어 다 적기에는 여백이 부족하다.</li> <li>KAIST: 한국에서 역대 최다 WF 참여 학교는 KAIST다</li> <li>연세대: 01, 03, 04, 05년도 진출 이후 15년만에 2020년 WF에 진출하였다.</li> <li>고려대: 사이버국방학과 학생들의 신분때문에 WF 티켓이 있음에도 못 간적이 있다.</li> <li>최초의 메달: 2015년에 딴 고려대의 동메달이 <a href="https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&amp;blogId=ku_1905&amp;logNo=220373167279">최초의 메달</a>로 알려져 있다. 그러나 메달은 04년부터 생겼고 01년도의 서울대의 기록도 ICPC에서는 메달로 인정하는것 같다.</li> <li>서강대: 백준 온라인 저지를 만든 baekjoon님 이후로 10년만에 solved.ac를 만든 shiftpsh님이 진출하였다.</li> <li>성균관대: <a href="https://www.acmicpc.net/problem/10718">10718번</a></li> <li>UNIST: 카자흐스탄 유학생 팀이 18년에 진출하였다. 이번 진출도 확인은 안되었지만 유학생계열로 알고 있다.</li> <li>이화여대: 리저널 6등, Best Women Team 자격으로 WF에 진출했다. 이는 세계최초 여성 3인팀 WF진출이었다.</li> <li>상해교통대: 한국 2005년 리저널 우승은 아직까지 유일한 여성 3인팀의 우승이기도 하며 첫번째로 한국팀이 우승못한 한국 리저널이다.</li> <li>펀잡대: 파키스탄의 펀잡대학교는 2007년 대회에서 패킷 스니핑으로 채점 데이터를 빼와 1등을 달리다가 적발되어 실격되어 학생들은 ICPC에서 영구추방 당하고 해당 대학은 2년 출전 금지를 먹은 <a href="http://joshisland.egloos.com/1647317">흑역사</a>가 있다.</li> </ul> <h2 id="참고자료">참고자료</h2> <ul> <li> <p>https://soyoja.com/91</p> </li> <li> <p>https://www.koreascience.or.kr/article/JAKO200725522697398.pdf</p> </li> <li> <p>https://en.wikipedia.org/wiki/International_Collegiate_Programming_Contest</p> </li> </ul>solarmagicSWERC 2020 팀연습 후기2021-06-01T00:00:00+00:002021-06-01T00:00:00+00:00https://blog.solarmagic.dev/algorithm/2021/06/01/SWERC2020<p><img src="https://i.imgur.com/R619fbq.png" alt="" /></p> <p>기존에 두 번의 팀연습이 더 있었지만 블로그 후기를 쓰는 게 생각보다 시간을 많이 잡아먹어서 팀원이 대신 글을 작성했다.</p> <ul> <li><a href="https://blog.naver.com/tlsdydaud1/222339926794">5월 5일 팀연습 AJRC 2020</a></li> <li><a href="https://blog.naver.com/tlsdydaud1/222357180307">5월 17일 팀연습 NWERC 2020</a></li> </ul> <p>5월 31일 1학기 마지막 팀연습을 진행했고 남은 기간에는 ICPC 기출을 여러번 풀 것 같다.</p> <p>방학때는 주말에나 연습이 가능할 듯 싶다.</p> <h2 id="팀연습-타임라인">팀연습 타임라인</h2> <p>SWERC2020으로 정해졌고. 14:05분 부터 5시간짜리 문제를 풀었다. 나는 코딩은 저번 부터 그냥 안하고 해석과 풀이 내는데에만 집중을 했다.</p> <h3 id="1407-e-solve">14:07 E Solve</h3> <p>내가 A번을 읽기 시작했고, dtc03012님이 B번을 읽었고, Lemonade255는 실행시간이 짧은 문제가 쉬운 문제라면서 E를 읽었다. E는 브론즈 문제라면서 빠르게 코딩을 끝내고 바로 맞추었다.</p> <p>끝나고 읽어보니 $min(\frac y x)$ 를 출력하면 답이다.</p> <h3 id="1417-a-solve">14:17 A Solve</h3> <p>A도 읽어보니 쉬웠다. $3N$개의 문장을 많이 나온 순서(같으면 나중에 나온 순서)대로 정렬하면 되는 문제이다. Lemonade255한테 설명하고 풀게 시켰다. <code class="language-plaintext highlighter-rouge">std::map</code> 같은걸 사용하면 쉽게 풀릴거라 생각했는데 약간 코딩 헤매긴 했지만 한번에 풀었다.</p> <h3 id="1431-c-solve">14:31 C Solve</h3> <p>나랑 dtc03012님이 A번 코딩하는 동안 B번이 답이 없다는걸 읽어보고 깨닫고 C번을 읽었다. 근데 C번도 쉬웠다. 이분탐색 -&gt; 이어져서 가로 세로 막는지 판별 -&gt; disjoint set 사용하면 쉬움 이렇게 풀이가 나오는데 1~2분도 안 걸린 것 같다. A번 코딩 끝나고 바로 코딩해서 AC</p> <h3 id="1550-k-solve">15:50 K Solve</h3> <p>K번은 A코딩을 끝내고 Lemonade255가 바로 읽고 Rabin-Karp로 짜면 된다고 얘기를 했다. C를 코딩할때 쯤 아이디어가 나왔으나 코딩이 매우 오래 걸렸다. 라빈카프 Hash 하는 것 자체가 충돌날 확률이 너무 높아서 그걸 해결하는데 고민을 많이했다. Chinese Remainder Theorem 같은걸 쓰려 했으나 결국에는 <code class="language-plaintext highlighter-rouge">__int128</code>로 코딩을 해서 제출해서 맞추었다.</p> <p>그 사이에 F번을 고민하고 있었는데 F번이 되게 풀이가 나올듯 말듯 안나왔다. F번은 좌우 개념이 없는 이진 트리를 $1$~$N$번 노드를 이용해 만드는데 부모 노드는 항상 자식 노드보다 번호가 클 때 $R$을 리프 노드로 하는 트리 개수가 몇 개인지 묻는 문제였다.</p> <p>$N$부터 $R$까지는 그냥 배치하고 $R-1$부터 $1$번까지를 어떻게 배치할까 이런식으로 고민하고 그냥 배치하는건 카탈란수 인가? 이런 여러가지 생각을 하고 있었다. 일단 트리 dp긴한데 식을 정확히 어떻게 짜야할지 고민하는데 어려워서 계속 잘 안 나왔다.</p> <h3 id="1557-d-solve">15:57 D Solve</h3> <p>K 고민하고 있는사이에 D번 푼 사람이 더 많아졌길래 D번을 읽었는데 너무 쉬워서 문제를 잘못 읽은줄 알았다. 그냥 다익스트라 돌려서 갈수 있는 간선의 개수를 세는 문제이다. dtc03012님한테 풀이 확인 받고 코딩해서 바로 맞추었다.</p> <h3 id="1638-f-solve">16:38 F Solve</h3> <p>다같이 F를 고민했는데 dp식을 알 것 같다면서 Lemonade255가 알아서 뚝딱 풀어버렸다. 아직 이 문제는 나는 풀이를 정확히 모른다.</p> <p>이때까지 한 번도 WA 없이 모든 문제를 원샷 원킬로 맞춰서 페널티가 상당히 잘 관리되었다.</p> <h3 id="1649-i-wa">16:49 I WA</h3> <p>I번은 재미있는 문제였다. 무향 그래프에서 최단 거리가 2인 곳에 간선이 생기는 작업을 반복할 때 몇번만에 완전 그래프가 되는지 묻는 문제다. 처음에는 몇번 해보니깐 그래프의 지름(모든 정점 쌍의 최단 거리 중 max 값)을 $D$라고 할 때 $ceil(\log D)$만에 된다는 것은 증명을 했다.</p> <p>그러나 $D$를 시간내에 구하는 방법을 알 수가 없어서 고민이었는데 트리의 지름 구하듯이 DFS를 한번 돌리고 다시 DFS로 가장 먼 거리를 측정하는 방식을 하는데, 그래프의 경우 어떤 정점을 선택하냐에 따라 제대로 못 구할 수 있기 때문에 random 하게 돌려가면서 하는 방식을 했다. 결과는 WA여서 다른 결정론적이 풀이 방법이 있을지 계속 고민했다.</p> <h3 id="1812-h-solve2-i-wa3-b-tle">18:12 H Solve(+2) I WA(+3) B TLE</h3> <p>H번은 처음에 이걸 어떻게 세그먼트트리로 풀지 했는데 dtc03012님이 보고서는 PST문제라고 했다. 그러고 보니 완벽히 PST 기초 문제라는 것을 알 수 있었다. 그러나 우리의 문제는 PST를 짜는 것을 할 수 없었고 팀 노트가 있다 가정해서 과거의 PST 코드를 가져왔다. 그 과정에서 다른 컴퓨터(코딩 자체는 1개로 했으나 문제 보는용)로 전달하려고 B번 문제를 이용해 전달했다.</p> <p>I번은 반복 횟수를 바꿔가면서 했지만 계속 WA가 나왔다.</p> <p>H번은 2번 틀렸지만 PST 템플릿을 바꿔서 새로 짜니깐 바로 맞았다.</p> <h3 id="1842-i-solve7">18:42 I Solve(+7)</h3> <p>I 번을 반복 횟수를 바꿔가면서 어떻게 잘 비비니깐 놀랍게도 통과를 했다. 랜덤 풀이가 맞긴 해던 것이다. 이 문제는 끝나고 랜덤이 정해인지 확인하려고 풀이를 봤는데 DFS를 한번만 돌리고 풀이를 할 수 있는 방법이 있었다. 보고 좀 소름이 돋았는데 확인하려면 <a href="https://youtu.be/YKY1SB-XE3s">영상</a> 참조. 재밌는 문제였다.</p> <h3 id="1905-종료">19:05 종료</h3> <p>마지막으로 L번과 G번을 보고 있었다. 문제 해석 같은걸 끝내니깐 10분정도 밖에 남지 않았다. 그래도 L번의 풀이는 꽤 정답에 가깝게 간거 같은데 시간이 부족했다. G번은 정해에 가깝지 않게 가고 있었는데 G번도 1시간 정도면 우리 팀의 실력이라면 충분히 풀만한 문제인 것으로 파악 됐다.</p> <h3 id="결과-및-후기">결과 및 후기</h3> <p>8 Solve 1114 페널티</p> <p><img src="https://i.imgur.com/ztVZTEI.png" alt="" /></p> <p>B, J, M은 풀기 힘들것 같고 L G는 풀만한 문제였는데 시간이 부족했다. F, I, K에서 시간을 좀 줄일 수 있었는데 그쪽에서 시간을 많이 쓴것 같다. 특히 I번이 아쉬운데 I번도 너무 결정론적 풀이를 내려고 시간을 오래 고민했는데 일단 코딩 해보면서 하는게 나았을것 같다.</p> <p>항상 그래도 초반 뇌절이 한 두문제는 있었는데 이번에는 없었던게 고무적인 것 같다. 코딩도 안정적이게 되었고 팀 합도 잘 맞는 것 같다. 꽤 괜찮은 실력이 나올 것 같지만 시간 배분이 가장 어려운 것 같다.</p> <p>WF 나가려면 10솔브는 기본이고 11솔브할 느낌상 대학교 3학교는 있었을것 같아서 좀 더 실력 많이 올려야할 듯 싶다.</p>solarmagic두 사람의 동작 유사도를 계산하기2021-04-16T00:00:00+00:002021-04-16T00:00:00+00:00https://blog.solarmagic.dev/ml/2021/04/16/pose-similarity<blockquote> <p>이글은 2020년 8월 4일에 작성한 글 을 옮긴 글입니다.</p> </blockquote> <h2 id="배경">배경</h2> <h3 id="pose-estimaton-설명">Pose Estimaton 설명</h3> <p><img src="https://img1.daumcdn.net/thumb/R1280x0/?scode=mtistory2&amp;fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fbpt20m%2FbtquaPjneyA%2FwbNlbM9jVIHqfb3TgEtdfK%2Fimg.gif" alt="AlphaPose" /> <img src="https://github.com/MVIG-SJTU/AlphaPose/raw/master/docs/posetrack2.gif" alt="alt" /></p> <p>머신 러닝, 딥 러닝을 이용하여 이미지나 영상의 사람의 포즈를 분석하는 기술을 Pose Estimation(포즈 추정)이라고 한다. 이미 많이 연구가 된 분야이고 통제된 데이터에서 잘 추출해내고 있다. 사람의 포즈를 추정하는 방식은 주요 관절 위치를 추정하는 것이다. 코, 어꺠 팔꿈치, 손목, 발목, 엉덩이, 무릎 등의 위치를 종합적으로 추정한다. 이런 주요 관절들을 <strong>Key Points</strong>라고 한다.</p> <h3 id="쉽게-사용가능한-pose-estimation">쉽게 사용가능한 Pose Estimation</h3> <p>현재 다양한 상용 Pose Estimation <a href="https://en.wikipedia.org/wiki/Application_programming_interface">API</a>가 나와 있다. 이를 통해서 응용 프로그램 개발자는 큰 ML 지식 없이도 ML을 활용한 프로그램을 만들 수 있게 되었다.</p> <ul> <li><a href="https://cloud.google.com/vision?hl=ko">구글 Vision AI</a></li> <li><a href="https://developers.kakao.com/docs/latest/ko/pose/common#intro">Kakao Developers</a></li> <li><a href="https://www.ncloud.com/product/aiService/poseEstimation">네이버 클라우드 플랫폼</a></li> <li><a href="https://maum.ai/?lang=kr">마음 AI</a></li> </ul> <p>주로 Pose Estimation을 하면 17개 정도의 키포인트와 함께 그 키포인트가 정말로 그 위치에 있을지 확신하는 정도인 Confidence Score를 같이 주곤 한다.</p> <h3 id="다양한-pose-estimation-응용-분야">다양한 Pose Estimation 응용 분야</h3> <p><img src="https://developers.kakao.com/docs/latest/ko/assets/style/images/pose/pose_use_case.png" alt="alt" /></p> <ul> <li>요가, 필라테스 자세 분석 &amp; 교정</li> <li>스포츠 자세 분석 &amp; 교정</li> <li>자신의 포즈를 그대로 따라하는 캐릭터</li> <li>이상 행동 탐지</li> </ul> <p>특히 이를 활용해서 스포츠에 활용하려는 앱, 회사들이 많이 생기고 있고 나도 이에 관한 프로젝트를 진행중이다.</p> <h2 id="문제-정의">문제 정의</h2> <p>어떤 사람의 포즈를 교정하려면 어떻게 해야할까? 먼저 잘 했는지 판단을 해야한다. 기준이 되는 포즈가 있고 어떤 사람의 포즈가 있어서 그 사람이 기준이 되는 포즈를 얼마나 잘 따라 했는지 수치화해서 보여줄 수 있을 것이다. 어떤 두 사람의 순간 포즈를 비교할 수 있다면 이를 활용해서 두 영상이 얼마나 비슷한지도 계산 할 수 있을 것이다.</p> <p>현재 나는 TensorFlow.js(PoseNet)를 활용해서 브라우저에서 홈 트레이닝을 할 수 있는 웹앱을 만드는 중이다. 모델(가이드) 포즈는 프레임마다 포즈를 추출 할 수 있다. 그러나 유저의 포즈는 하드웨어 자원을 활용하기 힘들고, Javascript라는 언어의 한계 때문에 초당 포즈 추정프레임이 그리 높지 않다.</p> <p>이런 불균형한 데이터가 있을때 어떻게 보정해서 점수를 매길지 생각해 본다. 이 문제에 대해 정리를 잘 정리하면 나중에도 쓰일 날이 있을 것으로 판단 된다.</p> <h2 id="문제-해결">문제 해결</h2> <p>이 문제를 해결하기 위해서 먼저 문제를 분해해서 각각의 문제를 푸는 방식을 생각해봤다.</p> <ol> <li>단일 이미지에서 포즈 비교를 어떻게 할 것인가?</li> <li>측정될때의 노이즈를 어떻게 제거할 것인가?</li> <li>속도 문제로 인해 부족한 프레임을 어떻게 채울 것인가?</li> <li>네트워크 지연, 유저의 반응속도 등으로 인한 가격차이를 어떻게 해소 할 것인가?</li> <li>유저는 다양한 각도로 촬영, 좌우 반전 촬영될 수 있는데 이를 처리하는 방법은 무엇인가?</li> </ol> <h3 id="1-단일-이미지에서-비교하는-법">1. 단일 이미지에서 비교하는 법</h3> <p>단일 이미지에서 두 사람이 얼마나 비슷한지 찾는 것은 구글의 <a href="https://experiments.withgoogle.com/collection/ai/move-mirror/view">Move Mirror</a>에서 그 방법을 찾아볼 수 있다.</p> <p><img src="https://lh3.googleusercontent.com/8lXXHoS-ibHI8hXPnU8mbqnckhXY2Gj8aHv4mE9HOxQWZzKQsGETiSao2BGsgvEBgVAFWfzYcalKA2ZHE8WS14Sw1JjwJw=s850" alt="alt" /></p> <p><a href="https://medium.com/tensorflow/move-mirror-an-ai-experiment-with-pose-estimation-in-the-browser-using-tensorflow-js-2f7b769f9b23">Move Mirror를 설명한 글</a>을 참조해보면 2가지의 거리 함수를 정의하여 빠르게 유사한 이미지를 매칭 시킨다. 그 두 가지 방법을 소개해보곘다.</p> <h4 id="cosine-distance">Cosine Distance</h4> <p>17개의 키포인트(일반적으로 키포인트는 이정도 개수이다.)를 벡터로 변환하면 34차원 벡터가 나올 것이다. (x, y 좌표) <del><a href="https://www.acmicpc.net/problem/13727">5차원 구사과 초콜릿</a>이나 11차원 <a href="https://www.acmicpc.net/problem/17114">하이퍼 토마토</a> 보다 고차원이다.</del> 이런 고차원 벡터 간의 가장 가까운 벡터를 찾아주는게 바로 코사인 거리이다.</p> <p><img src="https://miro.medium.com/max/700/0*n0USCt5M-yN6wkvy" alt="alt" /> 코사인 유사도는 두 벡터의 유사도를 측정하는데 각도가 완벽히 반대면 -1, 완벽히 같으면 1이 된다. 여기서 중요한건 벡터의 방향만 고려하고, 크기는 고려하지 않는다는 것이다. 이런 코사인 유사도는 꼭 그래프에 그려진 선위에서만 쓰일수 있는 것이 아니라 어떠한 <a href="https://engineering.continuity.net/cosine-similarity/">문장의 유사도를 구하는데</a>에도 유용하게 쓸 수 있다.</p> <p><img src="https://i.imgur.com/C6VnrI4.png" alt="alt" /></p> <p>그런데 바로 코사인 유사도를 적용하기 전에 해야할 일이 2가지 있다. 어떤 사진에서 사람이 나올때 그 사람의 크기는 다 다르다. 이를 다 맞춰 줄 것이다.</p> <ol> <li>Resize and Scale: 각 사람을 둘러싸는 박스(bbox, bounding box) 좌표를 기준으로 이미지를 자르고 scale을 다 상수로 맞춰준다.</li> <li>L2 Normalization: 키포인트의 좌표를 L2 Normaalize를 한다.</li> </ol> <p>여기서 <a href="https://mathworld.wolfram.com/L2-Norm.html">L2 Normalization</a>을 한다는 것은 모든 벡터가 단위 norm을 갖게 하겠다는 얘기이다. 좀 더 쉽게 말해서 L2 Norm된 벡터의 원소를 제곱해서 다 더하면 1이 되도록 하겠다는 거다. 아래 그림을 통해서 L2 Normzalize를 한 것과 안 한 것의 차이를 볼 수 있다.</p> <p><img src="https://i.imgur.com/DmNxtKb.png" alt="alt" /></p> <p><img src="https://i.imgur.com/OWQKAys.png" alt="alt" /></p> <p>정규화된 키포인트 좌표를 통해 위 공식대로 코사인 유사도를 계산한다.</p> <p><img src="https://i.imgur.com/9ifWsXa.png" alt="alt" /></p> <p>그리고 이런 공식에 대입하면 코사인 거리를 얻을 수 있다.</p> <p>이 떄 주목할건 F와 G의 17개의 x,y 좌표만 썼을 뿐 각 좌표의 Confidence Score는 사용하지 않았다는 것이다.</p> <h4 id="weighted-distance">Weighted Distance</h4> <p>코사인 거리는 매우 훌륭하고 좋은 결과 값을 주긴 하지만 아직 큰 결함이 있다. Confidence Score는 Pose를 추정할 때 이 좌표에는 어떤 키포인트가 있을지 얼마나 확신하는지 알려주는 정도이다. 이 정보를 무시한다면 우리는 매우 중요한 정보를 버리는 것이다.</p> <p>구글 연구진들은 이 공식을 통해 더 정확하게 거리를 추정했다.</p> <p><img src="https://i.imgur.com/SzAtmQD.png" alt="alt" /></p> <p>여기서 F_c가 Confidence Score이고 모두 L2 Norm이후이다. 아쉽게도 원 글에서 정확히 이 공식이 어떤 의미를 가지는지 설명을 하지는 않았지만 식을 대충 해석해봤을떄 17개 좌표중에서 Confidence Score가 높은 것은 거리를 계산할떄 영향을 많이 준다고 해석 된다.</p> <h4 id="구현">구현</h4> <p><a href="https://github.com/freshsomebody/posenet-similarity">유사도 구현 깃헙</a> 내가 처음부터 짤 필요 없이 이 설명대로 이미 구현이 되어 있는 라이브러리가 이미 존재하고 npm으로도 쉽게 설치할 수 있다. 이를 통해서 두 사진의 pose가 얼마나 비슷한지 측정하는건 할 수 있다.</p> <h4 id="뱀발">뱀발</h4> <p>이 글에서는 이 이후에 VP Tree라는 자료구조를 이용하여 어떻게 80,000개의 사진에서 빠르게 가장 비슷한 포즈 사진을 찾는지를 설명했다. 다음 기회에는 아마 이 VP Tree라는 자료구조에 대한 포스팅을 올릴 생각이다.</p> <h3 id="2-노이즈를-제거하는-방법">2. 노이즈를 제거하는 방법</h3> <p>사실 노이즈가 이 데이터에 있는지는 아직 잘 모르겠는데 멘토님께서 이걸 써보는게 어떻냐 해서 도입하게 되었다.</p> <p>칼만 필터는 데이터에 포함된 노이즈를 필터링 하는 알고리즘이다.</p> <p><img src="http://image.yes24.com/goods/73621194/800x0" alt="alt" /></p> <p>칼만 필터는 어렵지 않다고 한다.</p> <p>칼만 필터는 컴퓨터비전, 로켓, 로봇, 위성, 미사일, 제어 분야에 많이 이용되는 알고리즘이다. 원래는 신호 처리 쪽에서 많이 쓰이는데 OpenPose의 Object Tracking을 위해서도 쓰였다고 알려진다. 그러므로 우리의 데이터를 다룰 때도 사용해도 괜찮을 것으로 판단 된다.</p> <p><img src="https://i.imgur.com/n3vBCWi.png" alt="alt" /></p> <p>칼만 필터는 선형 시스템을 기반으로 설계된 필터로써 정상 상태 기준의 모델을 수행하였으므로 선형 시스템이라고 가정할 수 있다. 칼만 필터의 알고리즘은 예측과 업데이트를 반복적으로 계산하여 시스템 출력 값의 잡음 영향을 최소화하고 출력 값을 예측한다. 예측은 현재 상태의 예측을 말하고, 업데이트는 현재 상태에서 관측된 추정까지 포함한 값을 통해서 더 정확한 예측을 할 수 있는 것을 말한다.</p> <p><img src="https://i.imgur.com/u8CStNQ.png" alt="alt" /></p> <ol> <li>초기값</li> <li>추정과 오차 공분산 예측</li> <li>칼만 이득 계산</li> <li>추정값 계산</li> <li>오차 공분산 계산</li> </ol> <p>과정 2의 칼만 이득 계산 시에서 행렬 H와 치환 행렬 H^T는 계산을 위한 변환 행렬이므로 단순화 시키면 다음과 같다.</p> <p><img src="https://i.imgur.com/eBOvQyl.png" alt="alt" /></p> <p>전개한 수식을 통해 칼만 이득은 측정 값 오류 R 대비 추정값 오류 P_bar(k)의 비율임을 알 수 있다. 따라서 측정값 오류가 추정값 오류와 비교하면 상대적으로 크면 칼만 이득은 작아지고, 측정값 오류가 추정값 오류보다 상대적으로 작으면 칼만 이득은 커지게 된다.</p> <p>과정 3의 추정갑 계산 식을 전개하면 다음과 같다.</p> <p><img src="https://i.imgur.com/YFhddz1.png" alt="alt" /></p> <p>칼만 이득 K_k 은 0에서 1값을 가지며, 예측값 hat(x)_bar(k) 과 측정값 Z_k에 곱해지는 가중치를 의미한다. 즉, 예측값과 추정값 중 상대적으로 신뢰할 수 있는 값에 큰 가중치를 두고 계산하여 단위시간의 추정 값을 계산한다. 칼만 필터는 순환적으로 반복되어 수행되므로, 필터가 잘 작동되어 예측값 계산의 신뢰성이 높아질수록 칼만 이득은 점점 작아지며, 측정값 대비 상대적으로 높은 가중치가 예측값에 부여되게 된다.</p> <p>과정 1에서 예측 값 계산을 위해 예측시스템 오류 분산 값이 사용되며, 또한 과정 2 칼만 이득 계산 식에서 예측 시스템 오류 분산 값과 측정값 오류 분산 값이 이용된다. 과정 4에서 계산된 칼만 이득으로 예측시스템 오류 분산 값을 최적화한다.</p> <h3 id="구현체">구현체</h3> <p><a href="https://github.com/wouterbulten/kalmanjs">kalmanjs</a> 현재 프로젝트에 사용중이다. 아직 성능은 측정해보지 못하였다.</p> <p><a href="https://github.com/windsor718/poseTrack">poseTrack</a></p> <h3 id="더-읽어보기">더 읽어보기</h3> <ul> <li><a href="https://openaccess.thecvf.com/content_WACV_2020/papers/Buizza_Real-Time_Multi-Person_Pose_Tracking_using_Data_Assimilation_WACV_2020_paper.pdf">Real-Time Multi-Person Pose Tracking using Data Assimilation </a></li> <li><a href="https://arxiv.org/pdf/1906.10324v2.pdf">EKFPnP: Extended Kalman Filter for Camera Pose Estimation in a Sequence of Images</a></li> </ul> <p>아무래도 선형으로 안 맞다보니 실제로는 EKF를 많이 쓴다고 한다.</p> <h3 id="3-프레임-부족함을-해결하는-방법">3. 프레임 부족함을 해결하는 방법</h3> <p>이 분야는 motion interpolation 혹은 pose interpolation 이라고 할 수 있다.</p> <p>가이드가 될 영상은 preprocessing으로 프레임별 pose data를 미리 구해놓을 수 있지만 유저의 영상은 실시간으로 처리하기 때문에 프레임이 가이드 보다 부족하다. 예를 들어 현재 데모에서는 초당 10프레임 정도의 계산이 가능하다. 30fps 기준으로 사라진 20fps를 복구시켜서 같은 사이즈에서 비교하는 것이 좋아보인다.</p> <p>기존의 motion interpolation 은 대표적으로 다음과 같은 기술이 있다.</p> <ul> <li>Time remapping 은 단순히 똑같은 프레임을 한장 한장 더 늘려서 프레임만 증가시키는 기술.</li> <li>Frame blending 은 프레임들 사이에 앞 뒤 프레임을 겹친 프레임을 추가로 만든 기술.</li> <li>Frame interpolation 은 플래시의 Motion Shape 처럼 프레임들 사이에 움직임을 감지하고 바뀐 모양을 표현해주는 기술이다.</li> </ul> <p>가장 간단하게 현재도 쓸수 있는 방법 Time remapping이고 사실 이걸로 계산을 해도 크게 차이는 안 나긴한다. (사람이 0.x초만에 그렇게 빨리 움직이기 않기 떄문이다.) 그래도 정확한 frame interpolation을 해주는 것이 좋아보인다</p> <p><img src="https://i.imgur.com/s7loIc8.png" alt="alt" /></p> <p>간단하면서도 효과적일것으로 예상이 되는 것은 linear interpolcation을 통해서 이전 프레임과 다음 프레임 사이를 구하는 것이다. 사람의 어떤 키포인트가 x1에서 x2로 이동했다면 아마 그 사이를 지나갔을것이라고 추측하는 것이 합리적이다. 혹은 cubic 을 쓰는 것도 좋아보이는데 이는 테스를 통해서 알아 봐야 할 것 같다.</p> <p><img src="https://i.imgur.com/mQ7ALxu.png" alt="alt" /></p> <p>pose interpolation 동영상</p> <iframe width="560" height="315" src="https://www.youtube.com/embed/32m8rQ-lbuo" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen=""></iframe> <h3 id="4-싱크딜레이에-관한-문제-해결법">4. 싱크/딜레이에 관한 문제 해결법</h3> <p>유저들이 모든 프레임에 정확히 그 동작을 따라하는 것은 매우 힘들것이다. 그래서 실제 동작을 조금씩 느리게 하거나 조금씩 빠르게 하는 것에 대한 보정이 들어가야 할 것으로 보인다.</p> <p>이 문제는 <a href="https://en.wikipedia.org/wiki/Sequence_alignment">Sequence alignment</a> 문제와 비슷하다.</p> <p><img src="https://i.imgur.com/JXQYJ2s.png" alt="alt" /></p> <p>이중에서도 <a href="https://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algorithm">Needleman–Wunsch algorithm</a>을 변형해서 사용한다면 포즈 데이터를 잘 끼워 맞출 수 있을 것으로 예상 된다. 어차피 시간족잡도가 O(nm) 이라서 사실 다른 아무거나 써도 괜찮을 것으로 예상 된다. (Method of Four Russians 을 사용한다면 좀 더 단축할 수 있는 것으로 알려져 있다.)</p> <p>간단하면서도 효과적인 알고리즘으로 대각선 비교 알고리즘(가제)이 있다. n*m matrix를 다 채운다음 대각선 similarity / distance의 mean 값의 maximum을 통해서 점수를 계산하는 것이다. 단 프레임 수가 너무 작을 경우 극단 적이 값이 나오기 쉬우므로 일정 비율 이상일 때만 점수를 계산하는 것이다. 현재 그냥 생각나는대로 이런식으로 짜져있는데 좀더 생각해서 바꿔야 겠다.</p> <h3 id="5-다양한-각도--반전-문제-해결법">5. 다양한 각도 / 반전 문제 해결법</h3> <p>유저들은 가이드 화면과 똑같은 방향으로 서서만 운동을 해야한다면 너무 불편할 것이다. 어디에서 어떤 각도로 촬영을 해도 비슷한 동작을 하고 있는지 아닌지 잘 판단을 해야한다.</p> <p>먼저 3D Pose Estimation을 이용해서 키포인트에 대한 (x,y,z) 값을 알고 있다면 이 문제를 좀더 쉽게 해결 할수 있을 것이다. 그러나 아직은 3D pose estimation을 활용할 생각은 없다.</p> <p><img src="https://i.imgur.com/I2IUQ6s.png" alt="alt" /></p> <p>이러한 문제를 Procrustes는 그리스 신화에 나오는 도적인데 피해자들을 자신의 침대에 눕히고 잡아 늘이거나 침대 밖으로 나온 신체 부위를 잘라버려서 침대에 딱 맞추는 무서운 짓을 했다고 한다. Procrustes Analysis는 이와 같이 여러 geometrical shape들이 있을 때 크기와 회전에 대해서 모두 같게 만들기 때문에 신화의 인물의 이름을 차용해 왔다.</p> <table> <tbody> <tr> <td>[Procrustes analysis</td> <td>위키 피디아](https://en.wikipedia.org/wiki/Procrustes_analysis)</td> </tr> </tbody> </table> <p><img src="https://i.imgur.com/WmDIbfs.png" alt="alt" /></p> <ol> <li>각각의 Geometrical shape에서 평균 shape을 구해 빼주어 (0,0) 에 중심이 위치하도록 한다.</li> <li>모든 geometrical shape 들의 평균을 구한다.</li> <li>각각의 shape i 마다 size, rotation 그리고 translation 에 대한 parameter를 구해서 평균 geometric shape 과 차이가 최소가 되도록 한다. 자세한 과정은 다음 수식과 같으며 에러가 수렴할 때 까지 2~3번 과정을 반복한다.</li> </ol> <h2 id="결론">결론</h2> <ul> <li>어렵다 <ul> <li>두 영상의 포즈를 스코어링하는 것은 어려운 일이다.</li> <li>그러나 위에서 제시한 몇가지에 대한 해답을 정교하게 만들면 불가능한 일만은 아닌 것으로 보인다.</li> </ul> </li> <li>여러분들의 도움이 필요하다 <ul> <li>이 글을 쓰는 사람은 아직 학부 졸업도 안한 사람이다 보니, insight가 부족하고 guru에 비하면 배경지식도 떨어진다.</li> <li>좋은 솔루션이 있다면 댓글이나 연락처로 의견 주시면 정말 감사하게 더 생각해 볼 수 있을 것 같다.</li> </ul> </li> <li>비전이 좋다 <ul> <li>만약 이걸 정말 잘 만든다면 슈퍼스타 축구 선수, 야구 선수, 농구 선수와 나의 포즈를 비교해서 코치를 받을 수도 있다.</li> <li>요가나 필라테스, 홈 트레이닝</li> <li><a href="https://youtu.be/LKcbQHVB3xM">작렬 정신통일</a> 과 같은 게임 분야</li> </ul> </li> </ul> <p>이 글은 계속해서 업데이트 해 갈 예정이고 나중에 데모 GIF 등을 추가하고 더 낳은 알고리즘을 적용해서 더 나아지는 것을 보일 예정이다.</p> <h2 id="references">References</h2> <ul> <li><a href="https://developers.kakao.com/docs/latest/ko/pose/common">Kakao Developers Pose</a></li> <li> <table> <tbody> <tr> <td>[Pose Estimation</td> <td>TensorFlow](https://www.tensorflow.org/lite/models/pose_estimation/overview)</td> </tr> </tbody> </table> </li> <li><a href="https://medium.com/tensorflow/move-mirror-an-ai-experiment-with-pose-estimation-in-the-browser-using-tensorflow-js-2f7b769f9b23">Move Mirror: An AI Experiment with Pose Estimation in the Browser using TensorFlow.js</a></li> <li><a href="https://medium.com/tensorflow/real-time-human-pose-estimation-in-the-browser-with-tensorflow-js-7dd0bc881cd5">Real-time Human Pose Estimation in the Browser with TensorFlow.js</a></li> <li><a href="https://medium.com/@cavaldovinos/human-pose-estimation-pose-similarity-dc8bf9f78556">Human Pose Estimation: Pose Similarity</a></li> <li><a href="http://blog.naver.com/msnayana/80106682874">칼만필터 kalmanfilter</a></li> <li><a href="http://www.kibme.org/resources/journal/20190613143212078.pdf">딥 러닝 및 칼만 필터를 이용한 객체 추적 방법</a></li> <li><a href="https://trip2ee.tistory.com/105#:~:text=Procrustes%EB%8A%94%20%EA%B7%B8%EB%A6%AC%EC%8A%A4%20%EC%8B%A0%ED%99%94%EC%97%90,%EB%AC%B4%EC%84%9C%EC%9A%B4%20%EC%A7%93%EC%9D%84%20%ED%96%88%EB%8B%A4%EA%B3%A0%20%ED%95%9C%EB%8B%A4.">Procrustes Analysis</a></li> <li><a href="https://xiyo.tistory.com/6">motion interpolation란 뭘까?</a></li> <li><a href="https://github.com/MVIG-SJTU/AlphaPose">Alphapose</a></li> <li><a href="https://admission.postech.ac.kr/bbsLink.do?f=sub6-1_read&amp;boardId=GSKO_POS_YEAR&amp;BOARDSEQ=566&amp;iNowPage=2">2019 가을호 / 기획특집 / 미디어 콘텐츠 시대</a></li> <li><a href="http://www.yes24.com/Product/Goods/73621194">칼만 필터는 어렵지 않아</a></li> </ul>solarmagic이글은 2020년 8월 4일에 작성한 글 을 옮긴 글입니다.[TIL] std::vector 보다 std::stack 이 더 메모리를 많이 먹는다?2021-04-16T00:00:00+00:002021-04-16T00:00:00+00:00https://blog.solarmagic.dev/til/2021/04/16/stack-vs-vector<p><img src="https://i.imgur.com/9QqgcO8.jpg" alt="" /></p> <p>직관적으로 생각했을 때 <code class="language-plaintext highlighter-rouge">std::vector</code>는 <code class="language-plaintext highlighter-rouge">std::stack</code>의 <code class="language-plaintext highlighter-rouge">pop()</code> <code class="language-plaintext highlighter-rouge">push()</code> <code class="language-plaintext highlighter-rouge">top()</code> 연산 등을 동일하게 $O(1)$에 계산하면서 random-access(인덱스로 접근)도 가능하니깐 <code class="language-plaintext highlighter-rouge">std::stack</code>이 구현이 더 간단하거나 해서 메모리를 더 적게 먹을것 같지만 <a href="https://www.acmicpc.net/problem/17163">어떤 문제</a>를 풀어보니깐 아니었다.</p> <p><img src="https://i.imgur.com/9KHBkQk.png" alt="" /></p> <p><a href="https://en.cppreference.com/w/cpp/container/stack">cppreference</a>를 통해서 그 이유를 찾아 볼 수 있었다.</p> <p><code class="language-plaintext highlighter-rouge">std::stack</code>의 기본 Container(스택의 원소를 저장하는 역할)가 <code class="language-plaintext highlighter-rouge">std::deque</code>이기 때문이다. 설명을 보면 back(), push_back(), pop_back() 연산만 지원하면 어떠한 다른 컨테이너를 사용해도 상관 없다. 그리고 이를 만족하는 것은 <code class="language-plaintext highlighter-rouge">std::vector</code>, <code class="language-plaintext highlighter-rouge">std::deque</code>, <code class="language-plaintext highlighter-rouge">std::list</code>가 있다.</p> <h2 id="백준-17163번-결과">백준 17163번 결과</h2> <ul> <li><a href="http://boj.kr/4ab6459501e9452a941a76cd802ad2f7"><code class="language-plaintext highlighter-rouge">stack&lt;int&gt;</code></a></li> </ul> <p><img src="https://i.imgur.com/VGib4te.png" alt="" /></p> <ul> <li><a href="http://boj.kr/0e9c2af330f4479492db90eba67b6906"><code class="language-plaintext highlighter-rouge">stack&lt;int, vector&lt;int&gt;&gt;</code></a></li> </ul> <p><img src="https://i.imgur.com/DBwIeVR.png" alt="" /></p> <ul> <li><a href="http://boj.kr/a5463e83ac934019912095b339b96776"><code class="language-plaintext highlighter-rouge">stack&lt;int, list&lt;int&gt;&gt;</code></a></li> </ul> <p><img src="https://i.imgur.com/O2BlDgg.png" alt="" /></p> <p>Competitive Programming 을 할 때 <strong><code class="language-plaintext highlighter-rouge">stack&lt;int, vector&lt;int&gt;&gt;</code></strong>를 쓰는 것을 고려하는 게 메모리 관점에서 좋다는 것을 확인할 수 있다.</p> <hr /> <ul> <li>Q1. 다른 C++ Adaptor는 어떻게 구현되어 있나요. <ul> <li>A1. <code class="language-plaintext highlighter-rouge">std::queue</code>는 <code class="language-plaintext highlighter-rouge">std::deque</code>가 default고 <code class="language-plaintext highlighter-rouge">std::list</code>도 사용 가능하다. <code class="language-plaintext highlighter-rouge">std_priority_queue</code>는 <code class="language-plaintext highlighter-rouge">std::vector</code>가 default고 <code class="language-plaintext highlighter-rouge">std::deque</code>도 사용 가능하다.</li> </ul> </li> <li>Q2. 무슨 기준으로 default container가 그렇게 정해진걸까요. <ul> <li>A2. 아마도 작동 시간이 더 빠르기 때문일것으로 추측한다. <a href="https://www.codeproject.com/Articles/5425/An-In-Depth-Study-of-the-STL-Deque-Container">참고 자료</a>, vector는 resize를 자주하지 않고 빠르게 push_back() 지원하기 위해서 등비로 size를 바꾸는데 (amortized analysis 참고) 이게 performance가 생각보다 느린것 같다.</li> </ul> </li> </ul>solarmagicBAPC 2020 팀 연습2021-03-31T00:00:00+00:002021-03-31T00:00:00+00:00https://blog.solarmagic.dev/algorithm/2021/03/31/bapc2020<p><img src="https://i.imgur.com/0wtdNoW.png" alt="" /></p> <h2 id="bapc-2020-팀-연습">BAPC 2020 팀 연습</h2> <ul> <li>시간: 2021-03-31 13:15 ~ 18:15</li> <li>장소: 셀스스터디 부평</li> </ul> <p>이번에는 <a href="https://2020.bapc.eu/">BAPC 2020</a>를 풀기로 했다. 코드포스에 없는 관계로 <a href="https://www.acmicpc.net/group/6339">내 백준 그룹</a>을 통해 연습을 했다.</p> <p>여담으로 BAPC를 고른건 작년에 BAPC 연습 했을때 퍼포먼스가 좋았어서 이번에도 BAPC를 해봤다.</p> <h2 id="연습-타임-라인">연습 타임 라인</h2> <h3 id="1315--1412">13:15 ~ 14:12</h3> <p>Lemonade255가 H번 쉽다고 했다. 읽어보니 정말 쉬웠다. 풀어서 Solve.</p> <p>13:32 H Solve</p> <p>B번을 읽고 팀원들한테 얘기했는데 세명 다 똑같은 그리디 풀이를 생각해냈다. 근데 B번 코딩이 살짝 어려워서 C번을 읽었는데 C번도 쉬웠다. 단순 구현 문제 굳이 따지자면 그리디 문제였다.</p> <p>그래서 C번을 짰는데 틀렸다. 생각해보니 조금 더 생각할 부분이 있었다. 예외케이스 처리를 좀 추가했는데도 틀려서 혼자서 생각하고 있었다.</p> <p>B번은 dtc03012님이 짜는데 틀렸어가지고 Lemonade255가 반례를 찾아서 수정해서 풀었다.</p> <p>14:03 B Solve +1</p> <p>C번의 반례도 생각못하겠어서 Lemonade255가 디버깅을 했는데 $n = 1$일때가 반례였다. 역시 수정해서 AC</p> <p>14:12 C Solve +3</p> <h3 id="-1429">~ 14:29</h3> <p>J번 읽는데 너무 쉬웠다. $w &gt;= 2, h &gt;= 2$ 조건도 있다는걸 읽고서 아 무조건 길이가 있으니 예외처리도 편하게 해줬네라고 잘못 생각하고 한번 틀리고, 수정 해서 맞췄다.</p> <p>14:29 J Solve +1</p> <h3 id="-1456">~ 14:56</h3> <p>E번과 G번 문제는 어떤 문제인지 읽지도 못했는데 내가 J번 푸는 사이에 둘이서 쉽다고 하고 풀이 내서 코딩해서 풀었다.</p> <p>14:39 E Solve 14:56 G Solve +1</p> <h3 id="-1531">~ 15:31</h3> <p>되게 여기까지 스무스하게 진행되었다. E,G를 Lemonade255가 짜고 있을때 F번 I번 문제를 dtc03012님이랑 풀이를 생각하고 있었고 좋은 풀이가 생각나서 말했다.</p> <p>코딩은 dtc03012님이 한다고 해서 두문제를 코딩 했고 맞췄다.</p> <p>15:16 I Solve +1 15:31 F Solve</p> <p>연습 시작한지 절반이 안되었는데 8문제 풀고 3(A, D, K)문제만 남아서 되게 기분이 좋았다.</p> <p>그러나 그 이후로 문제를 못 풀었다. ㅠㅠ</p> <h3 id="-연습-종료">~ 연습 종료</h3> <p>D번 A번 K번을 다 읽어봤는데 다른문제랑은 다르게 풀이가 바로 나오지 않았다. 그나마 A번은 아예 모르겠고 D번과 K번이 좀 할만하다 생각했다. A번은 건드리지도 않았다.</p> <p>D번을 푸는데 이분탐색이 필요한건 간단하게 생각할 수 있다. 높이 찾는건 쉬운데 이제 가로로 이분탐색이 안된다는 것이다. dtc03012님이 기울기 이분 탐색을 얘기했고, 그래서 내가 제시한건 양쪽 모서리 sky / sea 경계를 찾으면 기울기가 (낮은쪽 sky와 높은쪽 sea를 연결하는 기울기)와 (높은쪽 sky와 낮은쪽 sea를 연결하는 기울기) 사이에 있다는 것이 보장되니깐 거기서 이제 정수 좌표를 찾는다? 이걸 했는데 뭔가 잘 정리가 되지 않았다.</p> <p>좀 더 고민을 하는데 갑자기 convex hull 이 생각이 나서 각도 순으로 넣고 정렬하면 찾을 수 있을것 같다 얘기했고 다른 사람들이 맞는거 같다 해서 내가 코딩을 하기로 하고, 나머지 둘은 K번을 열심히 토론 했다.</p> <p>근데 구현을 너무 내가 못했고(풀이가 틀리니깐 잘짜기 쉽지 않다) ad-hoc식으로 정답이 잘 나오게 코드를 수정했지만 역부족이었다. K번도 별 발전이 없어서 이후에 세명 다 D번에 몰두 했지만 풀리지 않았다. 그리고 끝나기 직전에 이게 왜 안되는지를 깨달았다.</p> <h2 id="결과">결과</h2> <p><img src="https://i.imgur.com/yFddo0O.png" alt="" /></p> <p><a href="https://2020.bapc.eu/scoreboard">BAPC 스코어보드</a>를 보니 11등 정도 퍼포먼스다.</p> <p>오피셜 솔루션 pdf도 존재해서 공부하기는 좋은것 같다.(대충 봤는데 아직 이해는 잘 안 된다.)</p> <h2 id="후기">후기</h2> <p>맞은 문제는 크게 얘기할건 없고 이제 D번이 중요한 것 같다. 사실 D번은 기하(?) + 이분탐색 + 인터랙티브라서 짤때부터 좀 많이 틀릴걸 각오 했다. 과거에 <a href="https://www.acmicpc.net/problem/14750">Jerry and Tom</a>라는 문제도 정말 고생해서 풀었어서 말이다.</p> <p>양쪽 끝점을 이분탐색하고 그걸 잇는 선분에 후보가 위아래로 2000개라고 생각을 했고 linear search는 당연히 안되니깐 이분탐색처럼 해야한다는건 생각했는데 그 때 생각을 할 때는 가로로 그렇게 이분탐색이 안된다고 생각 했다.(한쪽 날리면 정답이 날라갈수 있는것 같았다.) 근데 풀이를 보니깐, 해도 되던데 아직은 정확하게 이해가 되지 않는다.</p> <p>K번은 well-known 일거같은 냄새가 솔솔 났고 dtc03012님도 비슷한 문제 봤다고는 했는데 풀지는 못했다. 이런 xor은 항상 상위비트부터 잘 관리하거나 계산하면 되는데 풀이까지 연결되지는 못했다. 나는 offline query도 의심해봤지만 그런건 아니었다.</p> <p>A번은 그냥 제일 어려운거같아서 손도 못댔다.</p> <p>아마 다음 연습은 중간고사 전에 한번 더할수 있으면 하고 아니면 중간고사 끝나고 5월까지 되어야할것 같다.</p> <hr /> <p>구데기컵 오늘이였는지 몰랐는데 참여해야겠다.</p>solarmagicSW 마에스트로 11기 면접 질문2021-03-19T00:00:00+00:002021-03-19T00:00:00+00:00https://blog.solarmagic.dev/daily/2021/03/19/swmaestro12<p><img src="https://i.imgur.com/dkFllDy.png" alt="" /></p> <h2 id="sw-마에스트로-면접-길라잡이">SW 마에스트로 면접 길라잡이</h2> <p>2021-03-19 오늘 SW 마에스트로 12기 2차 코딩테스트 결과가 나왔다. 합격한 사람한테 축하들 보냅니다.</p> <p>이제 남은 관문은 면접이다. 면접에서 어떤 질문이 나오는지 궁금해하고 어떻게 대비해야할지 궁금해하는 사람이 많은데 그들을 위해서 글을 써본다.</p> <blockquote> <p>필자는 작년 SW 마에스트로 11기 활동을 했다.</p> </blockquote> <h2 id="작년-면접">작년 면접</h2> <h3 id="면접-참여-인원">면접 참여 인원</h3> <p>2배수이다. 150명을 뽑았으니 300명이 면접에 참여한 것이다.</p> <h3 id="면접-장소">면접 장소</h3> <p>코엑스 컨퍼런스 룸</p> <p>파이콘이랑 코드게이트 때문에 몇번 가봤는데도 너무 커서 길이 좀 헷갈린다. 일찍 가는게 좋다.</p> <h3 id="면접-진행">면접 진행</h3> <p><img src="https://i.imgur.com/fE1yekl.png" alt="" /></p> <p>대충 이렇게 5대 5로 진행이 되었다.</p> <p>면접관들은 컴퓨터로 우리의 코딩테스트 제출한 코드랑 자기소개서를 보는거 같았다.</p> <h4 id="면접관">면접관</h4> <p>면접관은 이후 SW마에스트로에 합격하게 된다면 우리의 멘토로 활약할 사람도 있고 이후 평가위원으로 활동할 사람도 있는 것으로 보였다.</p> <p>면접관들은 주로 경력이 오래되고 좋으신 현직 개발자분들이 많은 것으로 알고 있다.</p> <h4 id="면접-질문">면접 질문</h4> <p>면접은 1시간으로 기억하고 시간은 정말 철저하게 지킨다.</p> <p>기본적으로 SW마에스트로에서 얘기하기로는 아래와 같은 질문이 나온다고 한다.</p> <blockquote> <p>심층면접은 기술적 이론적 지식수준, 연수기간 중 활동계획 및 학습역량, 인성 및 발전가능성, 프로그래밍 등 기타 질의응답으로 진행됨</p> </blockquote> <p>작년 나의 경우에는 저 5명중 3번째 자리에 앉아 있었다. 1번이 가장 오른쪽 5번이 가장 왼쪽에 앉는 구조. 근데 우리 면접관만 그럴수도 있는데 주로 같은 질문을 1번 부터 5번한테 똑같이 물어봐서 솔직히 1번이 제일 불리한것 같다.</p> <ol> <li>자기소개 <ul> <li>1번 부터 5번까지 순서대로 자기소개</li> <li>사실 나는 준비를 안해갔다. ㅋㅋ 근데 뭐 자기소개서에 썼으니깐 그냥 몇가지 생각나는대로 얘기했다.</li> </ul> </li> <li>자기소개에서 발전된 질문 <ul> <li>방금 ‘자기소개’를 한 질문을 근거로 추가적인 질문을 물어본다.</li> <li>예를 들어 나같은 경우에는 작년에 belfast 에서 ml 관련 프로젝트를 했다고 했는데 추가 질문으로 그 ml 의 파이프라인을 물어봤다.</li> <li>이것도 그냥 내가 실제로 한 걸 얘기하면 되기 때문에 큰 부담이 없을것이다.</li> </ul> </li> <li>코딩 테스트 <ul> <li>코딩 테스트 관련 질문이 들어온다.</li> <li>나는 알고리즘 원툴이었기 때문에 이 질문이 들어온게 매우 반가웠다.</li> <li>Web, SQL 문제는 물어보지 않았다. (내가 아는 다른 면접 본 사람 중에서는)</li> <li>코딩테스트 1차는 물어보지 않았다. (내가 아는 다른 면접 본 사람 중에서는)</li> <li>우리 면접조에서는 1번한테 2차 1번 문제 배열 이름이 dp인데 왜 dp냐고 물어봤다. (문제는 연속합, 쉬운 dp)</li> <li>2번한테는 2차 2번 문제 함수이름이 dfs인데 dfs가 뭐냐고 물어봤다. (dfs로도 풀리고 union-find 기초 문제)</li> <li>그래서 나한테는 3번 문제(오프라인 쿼리, 세그먼트 트리)를 물어볼줄 알고 매우 기대했으나 뜬금없이 bits/stdc++.h 라고 썼는데 이게 뭔지 물어봤다.</li> <li>다른 면접조 얘기를 들어보면 그냥 자기가 푼 문제중에 하나 설명해보라고 5명한테 시켰다고 한다.</li> <li>그래서 추측하기로는 정말 자기가 이 문제 대리나 도움 없이 자기 힘으로 풀었는지 검증하는 그런 시간이 아닐까한다.</li> <li>자기가 지난 코테에서 어떻게 코드 짰는지 정리하면 도움이 될것이다.</li> <li>어려운 질문 보단 정말 확인용이니 걱정 안해도 된다</li> </ul> </li> <li>개발 상식 질문 <ul> <li>개발 상식 관련 질문인데 자신의 분야에 맞는 질문을 했다.</li> <li>백엔드 쪽 하는 사람한테는 OpenAPI 에 관한 질문을 했다. (이건 다른 면접조에도 무조건 물어보던데 이유는 알 수 없다. OpenAPI 공부 추천)</li> <li>공통 질문으로 C++ struct와 class 차이를 물어봤다. <ul> <li>캡슐화에 대해서 얘기하면 정답이다. 다른 조도 객체지향에서 캡슐화 관련 질문 하나씩 한걸로 들었다.</li> </ul> </li> <li>각 분야마다 사용한 라이브러리 물어봤고 그와 비슷한 라이브러리의 장단점을 물어봤다.</li> </ul> </li> <li>인성 질문 <ul> <li>인성 관련 질문도 하나씩 했었던것 같다.</li> <li>아마 채점표에 관련 배점이 있는것 같은데 그렇게 임팩트 있는질문이 없었는지 잘 기억이 나지 않는다.</li> <li>다른조에서도 다 비슷한걸 물어봤던걸로 기억하는데 별 문제 없었다.</li> <li>질문도 무난하고 답변도 교과서적인 답변 하면 된다.</li> </ul> </li> <li>하고 싶은 프로젝트 설명 <ul> <li>하고 싶은 프로젝트틑 설명하라 했다.</li> <li>특이한 점은 1번 2번 물어보고 5번 4번 물어보고 나는 안물어봤다.</li> </ul> </li> <li>마지막 어필 <ul> <li>위에서 나한테만 하고싶은 프로젝트 안물어보길래 이와 관련된 내용을 얘기 했다. <ul> <li>자기소개서에서 쓴걸 좀더 구체적으로 얘기했다.</li> </ul> </li> <li>이 질문은 다 하긴 했는데 사실 시간이 남아서 한거였다.</li> </ul> </li> </ol> <h2 id="tmi">TMI</h2> <ul> <li>교통비 3만원씩 준다. (Very Important)</li> <li>소마 면접장에서 줄 섰을때 바로 앞에 있는 사람이 나한테 코테 문제를 물어봤다. 그러고 면접 끝나고 카톡하면서 같이 붙으면 같이 팀하기로 했고 실제로 같이 팀했다.</li> </ul>solarmagic2021 ICPC Shanghai Site 연습2021-03-18T00:00:00+00:002021-03-18T00:00:00+00:00https://blog.solarmagic.dev/algorithm/2021/03/18/2020-icpc-shanghai-site<p><img src="https://i.imgur.com/8tBp3l0.png" alt="" /></p> <h2 id="두번째-팀-연습">두번째 팀 연습</h2> <ul> <li>시간: 2021-03-17 13:15 ~ 18:15</li> <li>장소: 안산 랭스터디 카페</li> </ul> <p>오늘은 날을 잡아서 5시간짜리 셋을 돌기로 하였다.</p> <p><img src="https://i.imgur.com/cjxdqHh.png" alt="" /></p> <p>대회는 <a href="https://codeforces.com/gym/102900">2020 ICPC Shanghai Site</a>로 정했다.</p> <p>확실히 저번보다는 어려웠다. 퍼포먼스도 사실 남들한테 보여주기 부끄러울정도다.</p> <h2 id="연습-타임-라인">연습 타임 라인</h2> <h3 id="1315--1324">13:15 ~ 13:24</h3> <p>G번이 제일 먼저 많이 풀려있는걸 보고 Lemonade255가 G를 읽고 바로 짰다. 끝나고 보니깐 그렇게 어려운 문제는 아닌것 같고 한번에 잘 풀었다.</p> <p>13:24 G solve</p> <h2 id="-1335">~ 13:35</h2> <p>나는 시작하자마자 B를 읽었는데 문제는 읽고 constructive 하다고 생각이 들었다. 일단 직관적으로 -1을 출력하는 경우는 없을거라 판단했다.</p> <p>dtc03012님이 이제 절반만 바꾸는 거니깐 홀수줄/짝수줄은 그대로 두고 한쪽 줄만 바꾸는걸로 만들어보자고 했다. 뭔가 될것 같기도한데 잘 안되었다.</p> <p>Lemonade255가 “그냥 A로 만들던가 A의 반전으로 만드는걸 시도 해보면 된다.” 얘기했고 들어보니 맞는말이어서 바로 짜서 맞추었다.</p> <p>B solve</p> <h2 id="-1417">~ 14:17</h2> <p>dtc03012님이 M번을 읽고, 나는 D번, Lemonade는 C번을 읽었다. dtc03012님이 해석을 도와달라 해서 gitignore 를 원래 써본 나는 실제 동작이랑 얘기하면서 설명해주고 그냥 dfs 돌리면 된다고 얘기했다.</p> <p>근데 RTE를 계속 내었다. 간단한문제라고 생각했는데 뭔가 고생을 하고 계셨다. RTE면 막 사이클을 돌아야하는데 A폴더가 B폴더를 참조하고 B폴더가 A폴더를 참조하는 경우는 있을수 없으니 의문이었다.</p> <h2 id="-1439">~ 14:39</h2> <p>D번은 삼분 탐색으로 쉽게 될 것 같아서 내가 짜서 제출을 해봤는데 틀렸다.</p> <h2 id="-1503">~ 15:03</h2> <p>M번도 수정하고 D번도 수정을 하는 작업을 했다. 나는 D번을 보고 있었는데 처음엔 삼분탐색을 잘못짰거나 정확도 문제인가 의심을 했는데 코드를 열심히봐도 딱히 그런부분이 없었다.</p> <p>D번은 dtc03012님이 p1, p2가 서로의 방향으로 쭉가는게 최선이 될수도 있다 해서 그걸 넣었더니 맞았다.</p> <p>D 4번 틀리고 Solve</p> <h2 id="-1613">~ 16:13</h2> <p>M이 왜틀렸는지도 알아냈다. 경로가 unique 하지 파일 이름 자체는 unique하지 않을 수 있다는 거다. 내가 해석해서 설명을 할때 파일 이름이 다 unique하다고 얘기했는데 나의 의도는 실제 OS처럼 path가 unique(같은 경로내에 같은 파일이 없다)한걸 얘기한거였고(그냥 원래 폴더/파일 구조가 그러니깐) dtc03012님은 어떤곳에서도 디렉토리나 파일 이름이 unique하다고 생각하고 코딩을 한거였다.</p> <p>M번도 그냥 이제 너무 많이 틀리다보니깐 새로 짜는게 낫다 판단해서 내가 새로 짜기로 했다. 근데 확실히 생각보다 이게 정확하고 빠르게 짜기가 쉽지 않았다. 알고리즘 자체는 딱히 뭐 없는데 구현이 나도 힘들었다.</p> <p>그래도 어떻게 느리긴하지만 짜긴해서 M을 풀었다.</p> <p>M 8번 틀리고 Solve</p> <h2 id="-1703">~ 17:03</h2> <p>내가 M을 짜고 있는 사이 E,H,C,I의 풀이를 준비했다고 했다.</p> <p>E는 dtc03012님이 DP식을 만들었는데 시간이 조금 애매할것 같다 얘기했다. H는 그냥 이분탐색 + 이분매칭하면 된다 했고.</p> <p>C,I는 수학적인 문제라서 Lemonade255가 짤 수 있다고 했다. 중간 중간 코딩을 하는데 뭔가 잘 안되어서 다시 노트를 들고 정리했다.</p> <p>dtc03012님이 E를 짰는데 시간 초과가 났다.</p> <h2 id="-1755">~ 17:55</h2> <p>나는 이미 풀이를 다 준비했다고 해서 코딩이라도 해야지 하고 H번을 이제 옛날에 풀었던 범죄 파티라는 문제가 생각나서 그것처럼 코딩을 했다.</p> <p>근데 틀렸다고 나왔다.</p> <h2 id="-1815">~ 18:15</h2> <p>다시 디버깅 + 코딩의 시간이 되었다. 얘도 이분탐색이나 이분매칭(호프크로프트-카프)에서 잘못된 부분이 있나 찾아봤는데 없어서 그래프를 만드는 부분이 조금 이상한것 같아서 그부분을 수정했고, dtc03012님은 E번을 좀 더 빠르게 돌릴 생각을 하고 있었다. Lemonade255는 C번 식을 다시 정리하고 있었다.</p> <p>H번 의심 가는 부분을 다 수정하고 dtc03012님이 짜보기도 했는데도 안되길래 이제는 알고리즘이 틀렸나 의심이 갔다. 그리고 의심하자 마자 반례가 떠올랐다. 그걸 얘기했고 풀이도 완전 이쪽 방향이 아니고 그냥 $O(K^2)$으로 풀수 있는 풀이 스케치가 떠올랐지만 너무 늦은 시간이었다.</p> <p>그렇게 대회가 종료되었다.</p> <h2 id="이후">이후</h2> <p>18:31분에 dtc03012님이 E번을 시간 줄여서 맞췄다.</p> <h2 id="결과">결과</h2> <p><img src="https://i.imgur.com/9FiQrSw.png" alt="" /></p> <p>555페널티 4솔브로 275등이다. C,I의 진행상황은 잘 모르지만 E, H는 맞추고 6솔은 했어야 했다.</p> <p>H번은 나도 바로 의심없이 코딩하지말고 풀이가 맞는지 검증을 거쳤어야 했다.</p> <p>M번이 시간을 많이 먹었는데 그걸 생각하더라도 후반 퍼포먼스가 너무 안좋았다.</p> <p>그래서 다음 연습에서는 그냥 따로따로 문제 읽고 풀지 말고 무조건 3명이서 같이 한문제씩만 보고 코딩하는 걸로 정했다. 아마 이러면 좀 더 잘 풀 수 있지 않을까 생각한다.</p> <h2 id="미래의-팀연습">미래의 팀연습</h2> <p>아마 앞으로도 5시간 셋을 돌 것 같다. 장소는 팀원이 살고 있는 왕십리-안산-인천을 한번씩 번갈아가면서 모일것 같다. 2주에 한번 정도 모여서 다음번 모임은 3/31 예정</p>solarmagic