본문 바로가기

분류 전체보기

(26)
Generalized Sorting with Predictions 이 글에서는 Pinyan Lu 외 3인의 논문 "Generalized Sorting with Predictions"에 대해 소개합니다. 구사과님이 호스트 하는 스터디 #project_tcs 에서도 발표를 한 번 했는데, 발표 자료는 다음 링크에 있습니다. 오타가 많음에 유의하세요. 1. Generalized Sorting Problem 1.1. 문제의 정의 어떤 object들을 정렬하는 것은 컴퓨터 과학에 있어 매우 중요한 문제입니다. 일반적으로 우리가 (comparison-based) 정렬을 한다고 할 때, 우리는 임의의 원소 간의 "비교"가 가능한 상황을 상정합니다. Generalized sorting problem에서는 이 상황을 보다 일반화하여 일부 원소들 사이에는 비교 연산을 이용할 수 없는, ..
다니고 있는 회사가 유니콘이 되었다. 나는 현재 몰로코(MOLOCO)라는 회사에서 인턴으로 근무하고 있는데, 우리 회사가 유니콘이 되었다고 한다. 참고로, 몰로코는 머신러닝을 이용해 모바일 광고와 관련된 일을 하는 회사다. 회사에 뛰어난 사람들도 많고, 빠르게 돌아가고, 사람들이 일 하는게 프로덕션에도 빠르게 반영되어서 좋은 것 같다. 나도 열심히 노력해서 다른 사람들 처럼 잘 하고 싶다. 아래는 관련 기사 링크 MK NEWS 몰로코, 유니콘 대열 합류…"한국인 실리콘밸리 AI 기업 최초 몰로코, 유니콘 대열 합류…"한국인 실리콘밸리 AI 기업 최초", 요약-애드테크 스타트업 몰로코는 신한GIB 등으로부터 2천만 달러(224억원)의 투자를 유치해 총 10억 달러(1조1천185억원)의 기업가치를 인정받으며 유니콘 대열에 합류했다고 4일 밝혔다..
Marp: Markdown Presentation Ecosystem Marp 라는 굉장히 편한 툴을 찾아서 기록해둔다. 예전에 시아닌이라는 닉네임을 쓰는 분의 소개로 알게 되었던 걸로 기억하는데, 그 때 당시에는 TikZ를 쓸 일이 많아서 beamer를 더 선호했지만, Tikz를 쓸 일이 줄어드고 난 지금은 상당히 매력적으로 다가오는 것 같다. 거두절미하고 소개하자면, 마크다운 기반으로 프레젠테이션 슬라이드를 만드는 툴인데, Visual Studio Code Extension도 존재한다. marketplace.visualstudio.com/items?itemName=marp-team.marp-vscode Marp for VS Code - Visual Studio Marketplace Extension for Visual Studio Code - Create slide d..
제2회 UNIST 알고리즘 프로그래밍 경진대회 Uni-CODE 2020 이번에 UNIST 알고리즘 프로그래밍 경진대회에 3문제를 출제했다. 출제와 검수의 전 과정을 도울 수 있어서 기뻤고, 좋은 경험이었던 것 같다. 간단한 풀이는 아래와 같고, 문제 채점은 다음 링크에서 할 수 있다. https://acmicpc.net/category/detail/2353 A. 트리플 소트 출제: queued_q 문제에서 주어진 swap 연산으로는 기우성이 같은 인덱스 끼리만 바꿀 수 있음을 알 수 있다. 고로, 홀수 번째 인덱스와 짝수 번째 인덱스를 별개로 생각해볼 수 있다. 버블 소트를 생각해보면, 인접한 인덱스의 스왑 연산으로는 모든 배열을 정렬할 수 있음을 알 수 있다. 따라서, 홀수 번째 인덱스에는 홀수만, 짝수 번째 인덱스에는 짝수만 있는 것이 정렬 가능할 필요충분조건임을 알 수..
SCPC 2020 짧은 후기 1차 예선 SCPC 1차 예선은 무난하게 통과했던 것 같아서 별 기억이 없습니다. 100 / 150 / 150 / 39 / 0을 받았습니다. 2차 예선 SCPC 2차 예선은 건강검진 예약일과 겹쳐서 많은 시간을 투자하지는 못했습니다. C번 문제가 풀이 자체는 쉬우나, 상수가 큰 풀이는 통과하지 못하는 빡빡한 제한이라 해결하지 못했던 점이 아쉬웠습니다. 100 / 150 / 61 / 41 / 47을 받았습니다. 본선 본선에 갈 것이라고 생각하지 못했지만, 본선에 참가하게 되었습니다. 본선 문제를 보니 생각보다 어려워 보여서, 점수만 열심히 긁어도 상은 받을 수 있다고 생각했습니다. 1번 문제는 쉬워서 간단히 100점을 받았습니다. 2번 문제는 지문이 더러워서 뭐 하라는건지 한참을 고민했는데, 결국 SCC를..
ICPC 2020 Seoul Regional 후기 이채준, 신민철 님과 함께 참가한 대학생 프로그래밍 경시대회에서 8솔브 / 1303분으로 전체 10등을 했고, 학내에서는 2등을 했다. 좋았던 점과 아쉬운 점 모두 있지만, 팀원들에게 수고했다는 말을 해주고 싶고, 우리 팀에 미래가 있다는 사실을 확인했다는 점이 너무나 좋았다. 사실 우리 팀은 인터넷 예선을 앞두고 팀 연습 1번, 인터넷 예선 이후에 팀 연습을 아예 안 할 정도로 별 준비 없이 봤음에도 불구하고, 전체 팀들 가운데 10등을 차지한 것은 사실 꽤나 잘한 성과라고 생각한다. 하지만, 인터넷 예선에서 운 좋게 8등을 한 덕택에 (객관적 실력상 진출이 힘듬이 명백한) 세계 대회에 갈 수 있다는 행복 회로를 돌리던 것은 썩 좋게 작용하지만은 않은 것 같다. 아무튼, 별 준비 없이 전체 10등은 나..
2020 천하제일 코딩대회 예선 또 인연이 닿아 선린인터넷고등학교의 천하제일 코딩대회 예선 및 본선을 출제하게 되었다. 출제는 junie님, wookje님과 함께 했으며, 서버 관리는 감사하게도 suckzo_o 님께서 맡아주셨다. (감사합니다) 예선은 junie 님이 2문제, 내가 2문제를 만들었다. 본선 팀을 선발하기 위한 대회인 만큼, 비교적 쉬운 문제들 위주로 구성하였다. 백준 온라인 저지에는 추후에업로드 할 예정이다. 간단한 풀이는 다음과 같다. A. 세금 출제: leejseo 정수 연산만을 이용해서 해결할 수 있도록 입력이 주어진다. $N / 1000 \times 780$ 와 $N / 1000 \times 956$을 사이에 공백을 두고 출력하면 된다. 오버플로우가 날 수 있는 입력 데이터를 준비해서 넣었다. 이 문제를 만든 ..
Minimums on the Edges 풀이 최근에 푼 문제 중 가장 재미있는 것 같아서 풀이를 기록해둔다. Link: www.acmicpc.net/problem/18664 18664번: Minimums on the Edges Print n numbers a1, a2, . . . , an (0 ≤ ai ≤ s), where ai is the number of tokens you put on the i-th vertex. The sum of printed integers must be equal to s. The sum of capacities of all edges must be the maximum possible. If there are multiple optimal www.acmicpc.net $N$개의 정점이 있고, $M$개의 간선 $(u_..
ICPC 2020 Seoul Regional 예선 후기 8솔브 / 563분 으로 전체 8등을 했고, 학내에서는 1등을 했다! (5등 팀은 휴학생 팀이기 때문이다.) 대회를 치기 전 사실 대회를 치기 전에 걱정이 많았다. 대충 아래와 같다. 다른 팀들은 모든 팀원이 최소 오렌지인데, 우리 팀은 내가 퍼플이다. 같은 학교 팀들 중 절반 이내에 들어야 리저널에 가는데, 이번에 대회가 온라인으로 개최되면서 웬만큼 PS에 관심 있는 팀이 아니면 참가 신청을 하지 않았다. 팀원 모두가 각자 할 일이 있어서 팀연습을 한 번 밖에 못했다. (교내대회 포함하면 두 번) 내가 최근에 수면에 있어 큰 어려움을 겪어서 컨디션이 굉장히 안좋았다. 그럼에도 불구하고 우리 팀이 잘 칠 수 있다는 근거 있는 자신감도 있었다. 전날 친 KAIST 교내 대회에서 8솔브 / 6등을 했고, 위..
2020 선린 정보 알고리즘경시대회 올해 선린인터넷고등학교의 교내 정보경시대회를 출제하게 되었다. 출제는 김준원님, 권욱제님과 함께 했으며, 정종인님이 서버 관리를 맡아주셨다. 일정이 워낙 촉박해서 대회 진행에 있어 다소 아쉬운 점이 있었으나, 문제 자체의 질은 괜찮다고 생각한다. 간단한 문제 해설과 함께 본인이 출제한 문제에 대해서는 출제 의도, 본인이 출제하지 않은 문제에 대해서는 출제 의도가 아닌 예상 난이도를 적어둔다. 문제는 BOJ에서 해결할 수 있다. 문제 풀이 A. 헛간 청약 출제: wookje 예상 난이도: Bronze IV - Bronze III 정답이 최대 $N$임에 유의하여 해결하면 된다. $\lfloor W/L \rfloor \times \lfloor H/L \rfloor$가 가장 많이 등장한 오답 중 하나였다. B...