The Way

간만에 미세먼지가 없고 날씨가 적당히 흐린 것 같아서 한강에 가서 자전거를 타기로 했다. 여름에 햇살이 쨍쨍할 때 밖에 나가면 말 그대로 진짜로 쪄 죽는 수가 있어서, 흐린 날이 야외활동하기 더 좋다. 작년에 대구에서 서울까지 자전거를 타고 올라올 때 잠실 쪽에 있는 광나루 자전거공원 도장까지 찍고 그냥 지하철을 타고 집으로 와서, 인천쪽 도장을 못 찍은 상태였다. 그래서 이번에 그때 찍지 못한 3개의 도장을 더 찍어버리기로 했다. 사실 이 계획은 그 때 같이 자전거를 타고 온 친구 두 명이랑 7월 말에 같이 하려던 계획인데, 하필이면 그 날 폭우가 쏟아져서 가지 못했었다. 그래서 그냥 오늘 혼자 갔다. 서울에는 따릉이라는 아주 좋은 제도가 있다. 2000원을 내면 2시간마다 반납 후 재대여를 한다는 가..

메이플의 계절이 돌아왔다~! (=방학) 메이플의 부흥기를 잘 알려주는 지표는 뉴비들의 유입이 활발하다는 것이다. 가령 우르스를 해도 이렇게 혼자서 캐리하게 된다. 사실 나는 그렇게 세지 않다. 카벨은 혼자 격파하고 노말 스우는 혼자 격파를 못하니 대충 비율은 상위 1.21%~3.62% 사이쯤 된다. 그런데도 이렇다. 아무튼 그간 업적을 많이 클리어했다. 사냥을 하다보니 자주색 구슬도 꽤 많이 먹었다 벼르고 있던 9999콤보 업적도 결국은 해버렸다.. 저번 도전에서는 중간에 택배가 와서 실패했지만, 이번에는 2시간 30분 정도 사냥을 하니 정신은 혼미해졌지만 어쨌든 클리어하게 되었다. 그동안 스펙업이 조금 되었는지 드림브레이커 70층도 슬슬 돌파할 수 있게 되었다. 코어강화 마저 하고 포인트 다 갈아넣으면..

2019 UCPC 본선에 참가했다.본선에는 총 48팀이 참가하였는데, 상을 6팀밖에 안 줘서 즐겜모드로 풀기로 했다. 우리가 풀 수 있는 문제를 다 풀고 나오면 좋겠다는 생각을 했다. 결과적으로 우리가 풀 수 있는 문제는 다 풀었다. 등수도 17등이라는 만족스러운 결과를 얻었다. 문제 풀이는 여기에 상세하게 나와있으므로 굳이 내가 안 써도 될 듯 하다. 사실 푼 문제도 별로 없다.. ㅋㅋ우리 팀 진행상황은 여기에 잘 적혀있다. 약간 첨언을 하자면 F번은 convex hull trick을 써야 하는 부분을 캐치를 못 했으니 아마 시간이 더 있었어도 대회 중에 쉽게 풀어내지는 못했을 것으로 보인다. 1)순간 최고등수 4등 달성해서 캡쳐해놨다. 이대로 대회가 종료되기를 바랐지만 그런 일은 일어나지 않았다.와중..

7월 30일에 열린 2019 SCPC 본선작년에도 SCPC 본선을 참가했지만 수상은 못 했었다. 이제 대학원을 입학해야 하는데 대학원이 얼마나 바쁠지, PS 공부를 계속 해나갈 수 있을지 확신이 없기 때문에 사실상 마지막 대회라는 생각으로 임했다. 사진을 거의 못찍어서 인증샷은 유튜브 동영상 캡쳐로 대체한다. (제일 왼쪽이 나)https://youtu.be/NG8CbnECy5w SCPC는 기념품이 아주 많고 좋은데, 저기에 있는 노트북만 빼고 다 가져가면 된다. 키보드, 마우스, 장패드, 가방, 노트, 펜을 준다. 11시부터 1시까지는 사전 등록 시간이었다. 나는 늦잠을 잔 탓에 12시 정도에 도착했다.작년과 마찬가지로 아는 사람이 없어서 멀뚱멀뚱 있었다. 극한의 아싸체험.. ^^그나마 작년 SCPC에서..

그간 2번의 팀연습을 더 거쳤으나... absolving을 제대로 하지 못했다. 1주일 12문제도 생각보다 많이 빡세다는 것을 느끼게 되었다. 아무튼 그동안 많은 일이 있었는데, 7월 27일의 예선을 가볍게 진출한 후, 이제 본선을 앞두고 마지막 팀연습을 하게 되었다. 약간 늦게 만나고 노트북 세팅도 상당히 오래 걸린지라, 5시간짜리 문제셋을 골라 2시간 정도 하다가 그냥 가기로 했다.문제셋은 뭐를 할까 고민하다가, 우리 실력이 어느 정도 되는지도 볼 겸 2018 ACM-ICPC Daejeon Regional을 하기로 했다.codeforces에 GYM 탭에서 virtual round를 진행할 수 있었는데, 놀랍게도 그 때 대회를 진행했던 사람들의 데이터도 그대로 들어있다. 작년 VISSLLE 팀도 잘 보..

조세퍼스 문제 시리즈를 풀어보았다. 조세퍼스 문제는 꽤 유명한 문제인데, 사람 n명이 원탁에 순서대로 둥글게 둘러앉은 뒤, 처음에 k번째 사람이 집에 가고, 그 다음에 집에 간 사람의 위치를 기준으로 하여 k번째 사람을 제거하고.. 를 반복하는 문제이다. 7명일 때 k가 3이면 다음과 같다. 1 2 3 4 5 6 7 => 3 1 2 4 5 6 7 => 6 1 2 4 5 7 => 2 1 4 5 7 => 7 1 4 5=> 5 1 4 => 1 4 => 4 백준 1158번: 조세퍼스 문제 정직한 구현 문제. 보통 큐를 이용하는데, 처음에 숫자를 순서대로 넣고 k - 1번 큐에서 빼고 집어넣은 뒤, 마지막 k번째 사람은 집어넣지 않고 출력한다. 대략 큐를 처음 써보는 사람들을 위한 문제 정도다. 백준 1168번:..

세그먼트 트리는 그냥 일반 알고리즘 수업만 들은 사람이랑 PS를 한다는 사람을 구분짓는 가장 대표적인 알고리즘이 아닐까 싶다. (CLRS 책에 안나와서 그러려나) 인터넷에 쳐보면 그야말로 넘쳐날 정도의 세그먼트 트리 글이 있지만, 아주 쉬운 구현을 발견해서 이를 포함해서 정리 겸 써본다.세그먼트 트리는 기본적으로 i) 구간에 대한 정보 쿼리, ii) 구간을 한번에 업데이트 시키기 두 가지에 아주 적합한 자료구조이다. 세부적으로 약간 차이가 있지만, 크게 3가지 타입이 있을 것 같다. i) 단일 업데이트, 구간 쿼리업데이트가 일어날 때는 하나의 원소만 변경되고, 쿼리는 구간에 대해서 묻는 질의이다.대표적으로 https://www.acmicpc.net/problem/2042과 같은 문제가 있다. 대표적인 세..

중간에 뜬금없이 끼어있는 어려운 문제. 고민을 꽤 많이 했다. 물론 답을 때려맞추기는 꽤 쉽지만, 답의 정당성까지 보이기는 쉽지 않다. 문제는 다음과 같다. 오각수(pentagon number)는 $P_n = n(3n-1)/2$의 형태로 주어진다. 앞에서부터 1, 5, 12, 22, 35, 51...이 된다. 이제 오각수 한 쌍 $P_i$와 $P_j$를 찾아야 하는데, 두 오각수의 합과 차가 모두 오각수가 되어야 한다. 이를 만족하는 오각수의 쌍 중 두 수의 차이의 최솟값을 구하는 문제이다. 보통은 이렇게 푼다. 적당히 오각수를 생성해놓고(만 개 정도) pair별로 확인하며 합과 차가 둘다 오각수인지 확인한다. 이렇게 코드를 작성하면, 적당히 빠른 시간 안에 5482660이라는 답을 얻을 수 있다. 조금..

어제는 AtCoder Beginner Contest를 했는데, E번까지 23분만에 순삭했음에도 불구하고 F를 못 풀어서 약간 존심이 상했다. 사실 ABC 마지막 문제는 Beginner Contest라는 이름에 맞지 않게 항상 난이도가 꽤나 높다.F를 푼 사람이 53명이고, 나는 85등이니 상당히 선방한 셈이다. 문제는 아주 간단하다. n과 k가 주어지는데, 1~n까지의 숫자로 이루어진 순열 중, 순열의 oddness를 $\sum^{n}_{i=1}{|i-p[i]|}$로 정의했을 때, oddness가 k인 순열의 수를 구하는 문제이다. oddness의 예시를 하나 들자면n = 4일 때, 순열 4312의 oddness는 |1-4| + |2-3| + |3-1| + |4-2| = 8이다. 먼저 oddness는 항..

라면의 연속 29회차 오늘의 라면: I'm e 민생라면 구성: 네모면 + 분말스프 용량: 115g 조리법: 물 500ml, 3분 30초 영양 성분: 열량480kcal- 나트륨1,800mg90% 탄수화물76g23% 당류7g7% 지방15g28% 트랜스지방0g- 포화지방7g47% 콜레스테롤0mg0% 단백질10g18% 한줄평:편의점에서 민생라면을 발견하고는 화들짝 놀랄 수밖에 없었다. 라면을 낱개로 파는데도 400원이 채 안됐던 것.민생이라는 이름을 갖다 붙인 것처럼, 그야말로 가격 면에서는 경쟁력이 확실하다. 맛은 그냥저냥 무난한 맛이다. 라면이라는 그 본업에 딱 충실한 맛. 약간 특별한 맛이 없어 밍밍하게 느껴질 수 있는데, 그런 사람들은 다른 라면과 함께 두 개를 섞어먹으면 좋을 것 같다. 저렴함과 무난함..