알고리즘 39

Topcoder SRM 794, 795 후기

Topcoder는 알고리즘 대회인 Single Round Match (일명 SRM)을 비롯해 다양한 프로그래밍 분야의 온라인 대회를 여는 사이트이다. 온라인으로 알고리즘 문제 해결 대회를 정기적으로 여는 대표적인 사이트는 Topcoder 외에도 Codeforces, Codechef, AtCoder 등이 있는데, Topcoder SRM은 그 중에서도 가장 오랜 역사를 자랑하는 근본 넘치는 대회이다. Topcoder SRM은 Div1 / Div2로 나뉘어 열리며, 각각 Easy / Medium / Hard의 3문제가 나온다. SRM 하나의 시간표는 보통 아래와 같이 진행된다. 코딩 (75분) -> 휴식(5분) -> Challenge(15분) -> System Test 코딩 시간에는 문제를 읽고 풀어서 코드를..

ICPC Seoul Regional 2020 후기

19년도에는 18년도랑 똑같은 팀(789)으로 나갔었는데, 올해 초만 해도 3학년 2학기에 휴학을 하고 산업기능요원 복무를 하러 갈 계획을 세우고 있었어서 팀원들한테 미리 "나 팀 나간다" 하고 나가고, 내 빈 자리는 어떻게 잘 해서 병특 끝나고 복학하신 gs12117님이 들어가게 되었다. 그런데... 코로나 때문에 방학 중에 끝나기로 돼 있었던 일정이 미뤄짐 + 산업기능요원 안 하기로 결정함 등등의 요인으로 3학년 2학기도 그냥 등록을 하게 되었고, 또 어쩌다 보니 tonyjjw님이 팀원을 찾고 계셔서 결국 팀을 새로 꾸리게 되었다. 팀원은 tonyjjw님과 rhrnald님. 두 분 다 상당한 실력자이셔서 WF 진출 가능성이 아주 없지는 않은 팀이었다. 아무튼 팀 연습도 몇 번 하고 하면서 대회를 준비..

SCPC 2020 본선 후기

예선 후기는 쓰는 걸 까먹어서 없다. ^^;; 역대 예선 문제 풀이는 github.com/kdh9949/snups-scpc2020 여기에 다 올라와 있다. (6회 2차예선은 코드만 있다) 동아리 스터디 진행한다고 예선 문제 다 풀고 풀이 슬라이드도 만들었는데, 참여율이 저조하기도 하고 마지막에는 내가 힘들어서 그냥 자연스럽게 쫑났던 것 같다. 아무튼 1차 / 2차 예선 모두 만점으로 본선에 진출하였고, 올해는 2회 수상 제한에 걸린 채로 (3등상 2번 탔음) 나가는 첫 대회라서 별로 기대감 없이 치기로 했다. 대회 직전에는 뭘 공부할까 하다가 문자열 알고리즘이나 좀 공부하자 해서 Suffix Array, LCP, KMP 이런 걸 좀 외웠다. 그놈의 코로나 때문에 대회를 온라인으로 진행해야 해서 준비 과정..

ICPC World Finals 2019 후기

좀 많이 늦은 것 같기는 하지만... 그래도 이건 어딘가에 남겨 놓은 기록이 있어서 안 써두면 아까울 것 같다. 2019년 3월 30일부터 4월 5일까지 개최된 ACM-ICPC World Final에 신승원, 김현수와 함께 서울대학교 대표로 출전하였다. 우리 팀은 11문제 중 7문제(페널티 783분)를 풀어 최종 순위 7위로 은메달을 받았다. 다양한 이유들로 인해 부담감을 많이 안고 출전한 대회인 만큼, 적어도 메달은 꼭 땄으면 좋겠다는 생각으로 출전했는데 정말 운 좋게도 은메달을 받게 되어 다행이다. 포르투갈에 도착해서 팀 연습을 두 번인가 했던 것 같은데, 하나를 완전히 망쳤었다. 심지어 드레스 리허설 때에도 쓸데없이 열심히 한 거 치고 결과가 별로 안 좋았다. 대회 날 아침에는 천둥번개까지 치고 그..

SCPC 2018 1차예선

SCPC는 삼성에서 주최하는 대학생 대회로, 상금이 빵빵하기로 유명하다. (스택메모리 1MB밖에 안 주기로도 유명하다 UPD(20.12): 이젠 스택메모리제한 따로 없다)1차 예선, 2차 예선을 온라인으로 치른 뒤 본선을 오프라인 대회로 치른다. 올해 1차 예선은 배점이 100 / 100 / 150 / 200 / 250점으로, 4번째 문제를 제외한 나머지 문제는 평범한 알고리즘 문제, 4번째 문제가 Optimization Problem (??)이 나왔다. 요즘 유행인가...나는 모든 문제에서 만점을 받았다! 예선 특별상 같은 거 안주나... 1. 버스 타기n(

제 2회 NYPC 후기

대회 Timeline4분 : 1번 AC (왠지 모르게 한 번 틀림...)~1시간 : 2번을 짜다가 말림. 계속 틀리더라 ㅜㅜ~2시간 : 3번을 짜다가 말림. ㅋㅋㅋㅋㅋㅋㅋ 이쯤부터 약간 느낌이 안 좋았다.~3시간 : 5번 풀이를 생각한 줄 알았는데 아니더라. 70점을 긁음.이 때 점수가 80 / 17 / 23 / 0 / 70 이었어서 나는 내가 스코어보드에도 안 보일 줄 알았다. (10등까지만 보여줌) 그런데 있더라? ㅋㅋㅋ 사람들도 나와 같은 길을 걷고 있다는 것을 깨달으니 약간 안심이 되었다(??)테트리스 문제가 처음에는 너무 어려워 보여서 넘겼는데 이제는 침착하게 마주해야 할 것 같아서 짰다. 생각보다 코딩 시간이 짧게 걸려서 1시간도 안 돼서 다 짜고 제출을 했는데, 처음에는 두 개 빼고 다 죽더..

IOI 2017 후기

처음 나가는 IOI라서 되게 설레기도 하고 긴장도 조금 됐는데 완벽하지는 않지만 그래도 내 당시 상태에서 할 만큼은 하고 온 것 같다. 새롭고 다시는 해 보지 못할 경험을 많이 했다는 점은 되게 좋은 것 같다.IOI라고 해서 대회 환경이 좋음이 보장되는 것은 아닌 것 같았다. Practice session 초반에 채점이 안 되는 것부터 뭔가 낌새가 이상했는데, Day 1때는 대회 시작 시점에 문제 pdf가 올라와 있지도 않았으며(프린트된 문제가 있어서 상관은 없었지만) 중간에 채점 큐가 조금씩 밀리기도 하고 Day2 때는 채점이 아예 안 되던 시점도 있었다. 이런 상황에서 굳이 연습할 필요까지는 없지만 제출을 좀 더 신중하게 쓰는 연습은 분명 필요한 것 같다.내 최대한의 실력을 발휘 못 한 것 같아 아쉬..

대회실습 7 (6.11) + 멘토교육 마무리

paint, messy, ailen 문제를 풀었다. 일단 messy가 interactive고 뭔가 별로 안 어려워 보여서 먼저 시작했다.제한을 보면 N=128인데 입력, 조사 쿼리가 각각 896=7*128=NlogN이라 딱 봐도 뭔가 반씩 나눠서 잘 하면 되겠다는 생각이 들었고, 일단 처음에 "1000...00", "01000...00" 같이 1개만 1인 문자열을 처음 반 개만 만들어서 넣어 보면 처음 반이 어디로 mapping되는지 알 수 있다는 것에서 시작하여, 그 다음에 분할을 어떻게 할 지 생각하다가 일단 보고자 하는 구간 [s, e]의 모든 수가 어디로 가는지 안다면 나머지 부분에 다 1을 채워 넣으면 된다는 것을 생각하고, 이를 이용해 간단한 분할 정복 풀이를 짜서 맞았다. 풀이가 빠르게 생각..

대회실습 7 (6.10)

molecules, railroad, shortcut 문제를 풀었다. 사실 세 문제 다 예전에 본 적이 있는 문제였긴 하다.가장 먼저 molecules를 풀었다. 탐지 범위가 분자들간의 무게 차이의 최댓값 이상이라는 조건 때문에 주어진 수들을 정렬한 뒤 임의의 [s, e] 구간의 합만 고려해도 충분하다는 사실을 알 수 있다. 각 구간의 길이에 대해 이분탐색으로 간단히 조건을 만족하는 구간이 있는지 판별할 수 있다.그 다음에는 railroad와 shortcut을 각각 봤는데, 둘 다 일단은 아무 생각이 들지 않았다. railroad는 34점 풀이까지는 간단히 생각할 수 있었어서 일단 보류한 뒤 shortcut에 대해 고민을 좀 한 결과, 케이스를 적절히 나누고 전처리를 몇 가지 하여 모든 지름길을 놓는 경..

대회실습 5 (6.4)

역대 POI 문제 중 ploughing, subway, railway 문제를 한 셋으로 풀었다.처음 문제 세 개를 훑어 본 후 ploughing과 subway는 일단 제쳐 둔 뒤 railway 문제에 대해 뭔가 쉬운 그리디가 떠올랐고, 1시간 좀 안 되게 열심히 노력한 결과 그게 틀렸다는 것을 알 수 있었다... 습관이 참 무섭다.그냥 18점 naive 풀이를 긁은 후 ploughing으로 넘어와서 다시 생각을 해 봤는데 O((HW)^2) 말고는 아직 잘 모르겠었다. subway도 마찬가지로 "리프 쌍들을 적절히 잘 고르면 된다"라는 것에서 더 넘어가지를 못 했다.railway 문제에 대해 다시 고민해 본 결과 풀이에 접근할 수 있었다. 기차가 들어오는 순서가 정해지면 각 기차가 몇 번째 기차까지 들어온..