Jekyll2021-10-14T11:59:32+00:00https://blog.solarmagic.dev/rss/SolarMagic’s Archives솔라매직의 기록 저장소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>solarmagicICPC와 한국2021-06-01T00:00:00+00:002021-06-01T00:00:00+00:00https://blog.solarmagic.dev/icpc/2021/06/01/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>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>solarmagic2021 Reply Challenge 간단한 후기2021-03-16T00:00:00+00:002021-03-16T00:00:00+00:00https://blog.solarmagic.dev/algorithm/2021/03/16/2021replychallenge<p><img src="https://i.imgur.com/DQG7n7L.png" alt="" /></p> <p>dtc03012님과 google hashcode와 비슷한 유형의 대회인 reply cahllenge를 2021년 03월 11일 참여하였다.</p> <h2 id="간단한-후기">간단한 후기</h2> <p><img src="https://i.imgur.com/XTJaSmU.png" alt="" /></p> <p>생각보다 문제가 너무 어려웠다. 처음에 간단한 그리디로 점수를 얻었는데 거기서 큰 발전이 없었다.</p> <p>대회 2시간 정도 지나가 갑자기 백준의 Washer 문제를 k-means clustering으로 빠르게풀었던 것이 생각이 났다. 그래서 이문제도 클러스터링으로 할 수 있을까 하고 했는데 데이터가 너무 커서 최적화가 필요 했고 가장 큰 F번은 대회 끝나고 2분뒤에 다 돌아갔다.</p> <p>두자리수 등수는 충분히 찍을수 있었는데 뭐 사실 초반부터 망해서 별 생각은 없다. 아쉬운건 빠르게 다른 알고리즘이나 휴리스틱을 떠오르지 못한 부분?</p> <p>코드포스 관련 스레드 보면 생각지도 못한 풀이가 많다.</p>solarmagic2021 Google Hashcode 예선 후기2021-03-04T00:00:00+00:002021-03-04T00:00:00+00:00https://blog.solarmagic.dev/algorithm/2021/03/04/2021hashcode<p><img src="https://i.imgur.com/kNkcoUk.png" alt="" /></p> <h2 id="google-hashcode">Google HashCode</h2> <p>구글 해시코드는 팀 프로그래밍 대회로 주로 휴리스틱 문제가 나온다. 매년 참가자수가 늘고 있고 올해는 9000개 이상의 팀이 1번 이상 제출을 하였고 전세계 170개 이상의 나라가 참여했다.</p> <p>약 30~50팀(150명 제한)이 월드 파이널에 진출하게 되고 원래는 더블린에서 치뤘지만 작년부터는 코로나로 인해 온라인으로 치룬다.</p> <h2 id="팀">팀</h2> <p>작년에는 hojoon0205, queued_q, chunghan과 같이 참여 했는데 올해는 Juno와 둘이서 참여했다.</p> <h2 id="타임라인">타임라인</h2> <h3 id="문제">문제</h3> <p>3시간 45분동안 대회가 진행되었다.</p> <p>문제는 <a href="https://hashcodejudge.withgoogle.com/">해시코드 사이트</a>에서 볼 수 있다. 문제를 요약하면 신호등의 초록불 스케줄을 잘 관리해서 자동차가 잘 지나다닐수 있게 하라는 것이다. 도로가 연결된 상황과 길이가 주어지고 차량들의 이동경로가 있다. 교차로에서는 여러 도로중 하나만 불을 켤 수 있다. 점수는 도착 보너스 점수와 도착했을때 시간 점수의 합이다.</p> <h3 id="기본">기본</h3> <p>가장 간단히 떠올릴 수 있는 방법은 실제 도로 교통망처럼 계속 번갈아가면서 신호등을 켜주는 것이다. 문제 설정상 1초에 1차량씩 지나갈수 있으므로 1초마다 켜주는 코드를 작성했다.</p> <p>이렇게 7,885,741점을 얻을 수 있다.</p> <p>여기서 A번을 손으로 풀어준다면 1001점을 더 얻어서 7,886,742점을 얻을 수 있는데 이 근방의 점수가 매우 많았다.</p> <h3 id="개선">개선</h3> <p>이후에 생각을 하면서 여러가지 개선을 했다.</p> <p>먼저 하나도 안쓰이는 도로는 켜주지 않는코드를 작성하면 1,039,874점의 개선이 이루어진다. (8,926,616)</p> <p>그 다음으론 많이 사용하는 도로에 시간을 좀 더 많이 할당하는 코드를 작성했다. 이 때 어느 정도 많이 줄지에 대해서는 여러번 제출하면서 최적의 값을 찾아 나갔다. 이 방법으로 9백 30만에서 40만점까지 올렸고 당시 한국 3위의 기록이었다.</p> <p>그러나 이 이후로 좋은 최적화 방법을 찾지 못하였다.</p> <p>신호등이 켜지는 순서를 최적화해야하는 것은 생각했지만 마땅히 떠오르는 방법이 없었다. 정렬하거나 거꾸로 켜기 혹은 랜덤등을 활용해서 대회가 끝날때까지 약 20만점을 올렸다.</p> <h2 id="결과-및-후기">결과 및 후기</h2> <p><img src="https://i.imgur.com/2hsskH9.png" alt="" /></p> <p>960만 447점을 얻었다.</p> <p><a href="https://hashcodejudge.withgoogle.com/scoreboard">퍼블릭 스코어보드</a>에서 자세한 결과를 볼 수 있다. 우리팀은 ‘asdf’ 팀으로 세계 121위를 달성하여 월드 파이널에 진출하지는 못했다. 작년에는 세계 300등대였는데 그래도 나름 발전했다. 한국 순위도 작년엔 11위 올해는 8위다.</p> <p>작년엔 한국에서 한 팀만 세계 대회에 나갔는데 올해는 세 팀이나 세계 대회에 나갈 것 같다. 작년에 세계 대회를 나간 팀의 멤버가 쪼개지고 추가하면서 더 강해진것 같다. 그리고 재작년에 세계 대회 나간 팀에 멤버 추가를 한 팀이 나간다.</p> <p>신호등이 켜지는 순서를 최적화하는 걸 좀 더 일찍 고민하고 거기서 점수를 더 올렸으면 하는 아쉬움이 있다.</p> <p>3/11에 <a href="https://challenges.reply.com/tamtamy/challenges/category/coding#home">Reply Challenge</a>라는 비슷한 유형의 대회를 dtc03012님과 같이 나갈것 같은데 여기서 좋은 결과를 보여주는것이 목표다.</p>solarmagic2021년 첫 팀 연습2021-02-23T00:00:00+00:002021-02-23T00:00:00+00:00https://blog.solarmagic.dev/algorithm/2021/02/23/2020-Ateneo-de-Manila-University-DISCS-PrO-HS-Division<p><img src="https://i.imgur.com/qt5j6ro.png" alt="" /></p> <h2 id="팀-결성">팀 결성</h2> <h3 id="팀원">팀원</h3> <p>2020년 02월 04일 작년에 같이 휴학생으로 연습한 dtc03012 한테 연락이 와서 올해 같이 PS팀을 하기로 했다. 작년 신입생으로 들어온 Lemonade255 과 셋이서 같이 UCPC, ICPC등을 나가기로 약속을 했다.</p> <h3 id="목표">목표</h3> <p>나름 한양대학교 안에서 나올 수 있는 최상의 스쿼드가 아닐까 생각해본다. ICPC WF같은 거창한 목표를 세우고 싶은데 솔직히 요즘에 잘하는 학교가 너무 많아서 학교 순위 Top5 드는것도 열심히 안하면 힘들것 같다.</p> <h3 id="팀명">팀명</h3> <p>아직 팀 명은 못정했다. 추천 받아요. ㅎㅅㅎ</p> <h2 id="첫-팀-연습">첫 팀 연습</h2> <ul> <li>시간: 2021-02-23 14:05 ~ 17:05</li> <li>장소: 한양대학교 법학도서관 스터디룸 4번</li> </ul> <p>5시에 문을 닫아서 ICPC 예선처럼 3시간짜리 셋을 돌기로 했다. 급하게 Codeforces Gym 2페이지에 3시간짜리로 별 3개 난이도가 있길래 그냥 그걸로 하기로 했다.</p> <p><a href="https://codeforces.com/gym/102556">2020 Ateneo de Manila University DISCS PrO HS Divisio</a></p> <p>사실 무슨 대회인지 잘 모르는데 미리 요약하면 그렇게 문제 퀄이 좋진 않았지만 우리에게 많은 교훈을 주긴했다.</p> <h2 id="연습-타임-라인">연습 타임 라인</h2> <p>“전체적으로 문제는 쉬웠지만 우리는 더 바보였다.” 로 요약할 수 있다.</p> <h3 id="1405--1416">14:05 ~ 14:16</h3> <p>내가 A번을 읽고 “엥 개 쉽잖아”하고 코딩을 했다. 그러나 WA 2번을 당했다. 이렇게 쉬운걸 틀리다니하고 약간 충격을 먹었다. 근데 알고보니 구하라는 것을 잘못 생각했다. 대충 위 읽고 예제보고서 원형으로 했을 때 연속된 구간의 수를 세라는 건줄 알았는데 연속된 구간의 수로 만들기 위해 필요한 사람의 수를 구하는 거였다.</p> <p>근데 우연히 예제는 잘 나와서 눈치를 전혀 못챘는데 Lemonade255 이 알려줬다.</p> <h3 id="-1427">~ 14:27</h3> <p>Lemondade255 제대로 된 문제 해석으로 A를 짜서 제출 했다. 그런데 2WA만 더 적립했다. 사실 풀이는 뭐 안 들어봐도 너무 쉬운거라 당연히 잘 짰을텐데 30분 동안 한 문제도 못풀고 -4 되어서 이게 뭐지 했다.</p> <h3 id="-1432">~ 14:32</h3> <p>난 A 손절하고 dtc03012님이 E번을 읽어보라해서 내가 E번을 읽어봤다. E번을 읽으니깐 엥 뭐지 개쉬운데 해서 하고 그냥 풀었다. 문제 풀이보다 장황한 지문 해석이 훨씬 어려운 문제다. 모든 경우 기하 평균을 구하라는데 대충 수학으로 다 상쇄되어서 그냥 입력 받은수 그대로 출력하면 된다.</p> <p>E Solve</p> <h3 id="-1506">~ 15:06</h3> <p>A를 다시 내가 처음부터 짜서 계속 제출 했다. 다른 사람은 B, C, D를 읽고 있었다. 그런데 내가 짜도 A가 또 틀리더라. 페널티 생각안하고 막 제출하기 시작했고 A는 5번을 더 틀려서 -9가 되었다. 정말 아무리봐도 틀린데가 없다고 생각했다.</p> <h3 id="-1520">~ 15:20</h3> <ul> <li>15:07 dtc03012님이 D번을 짜서 냈다. 틀렸다.</li> <li>15:08 Lemonade255님이 C번을 짜서 냈다. 틀렸다.</li> <li>15:09 dtc03012님이 D번을 수정했다. 틀렸다.</li> <li>15:14 Lemonade255님이 B번을 제출했다. 틀렸다.</li> <li>15:20 Lemonade255님이 B번을 제출했다. 틀렸다.</li> </ul> <p>대회 시작한지 1시간 15분 되었는데 그냥 그대로 출력하는 E번 빼고 하나도 못맞췄다. 엌ㅋㅋㅋ 역대 모든 코딩중에 가장 말렸다. 나만 말린게 아니라 모두가 다같이 말린건 처음봤다.</p> <h3 id="-1528">~ 15:28</h3> <p>근데 A번에 잘못된 점을 찾았다. 예외처리를 이상하게 한거였다. 해석이 바뀐걸 알았는데도 바보같이 모두 꽉차 있을때 원펀맨이 한번 쳐야 한다 생각해서 1을 출력하게 했다. 너무 당연해서 의심을 안했는데 dtc03012님과 얘기를 하면서 알게되었다. 수정해서 제출해서 맞추었다. 중간에 코드를 잘못 제출해서 -2가 더 깎였는데 뭐 크게 중요하진 않다.</p> <p>A Solve</p> <p>dtc03012님도 D번의 틀린점을 알거 같아서 3번 수정 제출 했지만 틀렸다. 그후에 Lemonade255님이 B번을 한번더 수정해 제출했지만 또 틀렸다.</p> <p>상황을 정리하면 다음과 같다.</p> <ul> <li>27분 E Solve</li> <li>81분 A Solve (10 WA 1RTE 1CE)</li> <li>C 2WA</li> <li>D 5WA</li> <li>B 3WA</li> </ul> <h3 id="-1541">~ 15:41</h3> <p>다같이 뇌절하지말고 하나하나 풀자해서 A를 끝내고 D를 봤다. D도 천천히 생각하니깐 풀이가 나왔다. 식도 천천히 했으면 금방 나오는데 오히려 급해져서 막 내다가 정리해서 맞추었다. 그 사이에 4번 더 틀리고 맞췄다.</p> <p>D Solve</p> <h3 id="-1547">~ 15:47</h3> <p>Lemonade255가 알아서 실수한 부분을 찾아서 고쳤다.</p> <p>C Solve</p> <h3 id="-1601">~ 16:01</h3> <p>Lemondade255가 B번을 수정시도하나 틀렸다. dtc03012가 H번을 2번 시도 했으나 틀렸다.</p> <h3 id="-1612">~ 16:12</h3> <p>G번을 dtc03012님과 같이 읽었는데 dtc03012님이 주변 8방향에서 시뮬레이션 하면 될것 같다고 했다. 나는 안될거같은 의구심이 들었는데 반례가 안나왔다. 노트에 대충 그리다 보니깐 8방향 말고 그냥 주변 4방향 사각형만 하면 무조건 된다라는게 나왔다. dtc03012님이 혹시모르니깐 BFS로 하라했지만 걍 수학으로 했는데 잘 되었다. 문제 끝부분에 절반 이상이면 이상한 문구 출력하는걸 빼먹어서 한 번 틀렸는데 어쨌든 내가 대충 짜서 맞추었다.</p> <p>G Solve</p> <h3 id="-1616">~ 16:16</h3> <p>Lemonade255랑 B번 코드를 보면서 이상한 데를 찾았다. 잘못된걸 같은 부분이 발견 되었고 Lemonade255가 고쳐서 내니 맞았다.</p> <h3 id="-1637">~ 16:37</h3> <p>나는 F번을 읽고 풀기 시작했고 다른 사람들은 H, I번을 풀고 있었다. F번 코드 짜는 사이에 옆에서 들어보니 대충 풀이는 다 나온거 같았다. 근데 좀 코딩이 빠르게는 되지 않았지만 정확히 짜려 했다. 정말 간단한 문제이다. 지문에 소녀시대 사진이 나오면서 한국 문화에 관한 문제여서 조금 신기했다. 어쨌든 맞췄다.</p> <p>F Solve</p> <h3 id="-1643">~ 16:43</h3> <p>삼각형 사이에 있는 점의 개수를 세는 문제라 한다. dtc03012님이 USACO에 나왔던 문제라고 해서 알고 있는 문제였다. 남은 시간이 부족해서 팀노트라 생각하고 과거코드를 이용해 풀었다.</p> <p>I Solve</p> <h3 id="-1705종료">~ 17:05(종료)</h3> <p>F를 풀고 나는 할게없었다. 남은 문제 풀이가 다나왔고 H번은 Lemonade255가 짜기로 했다. 대충 들어보니 풀이는 맞는것 같았다. 17:00에 나가야해서 짐을 정리하고 알아서 잘 풀길 기도했다. 근데 뭔가 코딩이 꼬였는지 막판에 예외케이스로 1과 int를 넘어가는 실수 수정해서 냈는데도 TC 15에서 셋다 틀렸다. 뭔가 올 솔브할수 있었는데 아쉽다.</p> <h2 id="스코어보드"><a href="https://codeforces.com/gym/102556/standings">스코어보드</a></h2> <p><img src="https://i.imgur.com/FDHvW1V.png" alt="scoreboard" /></p> <p>8솔브/9문제 1434페널티로 8솔 꼴지 했다.</p> <p>초반에 개망했는데 어떻게 그래도 거의 다 맞추기는 했다.</p> <h2 id="후기">후기</h2> <ul> <li>전체적으로 문제는 엄청 쉬웠다. 근데 지문이 좀 난잡해서 읽기가 어렵고 맞왜틀을 좀 유발했다.</li> <li>개인적인 문제점으로 터널시야가 있는지 잘 해석하다가 문제 감이 오면 중간에 해석 건너뛰고 코딩하는 안좋은 버릇이 있나보다. A번과 G번에서 그랬다.</li> <li>근데 위에랑 별개로 3명 다 실수가 너무너무 많았다. 쉬운 문제 정확하고 빠르게 푸는 연습을 해야 한다.</li> <li>막 셋이서 다같이 고민할만한 문제는 없었고 오늘은 디버깅 대축제였는데 다음에는 좀 어려운 셋으로 5시간 돌아봐야 겠다.</li> <li>H, I는 내일 아님 모레 풀어봐야겠다.</li> </ul>solarmagic