The Way

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원이 채 안됐던 것.민생이라는 이름을 갖다 붙인 것처럼, 그야말로 가격 면에서는 경쟁력이 확실하다. 맛은 그냥저냥 무난한 맛이다. 라면이라는 그 본업에 딱 충실한 맛. 약간 특별한 맛이 없어 밍밍하게 느껴질 수 있는데, 그런 사람들은 다른 라면과 함께 두 개를 섞어먹으면 좋을 것 같다. 저렴함과 무난함..

오늘 등산할 산은 청계산이다. 청계산은 과천과 서초구 사이에 있는 산으로, 서초구나 강남 시민들이 많이 찾는 산이라고 한다. 덤으로 모 회장덕에 약간 더 유명해진 산이다. 청계산 정상인 망경대는 군기지가 있어서 못가고, 대신 매봉을 정상 대용으로 방문한다고 한다. 서초구 쪽에서 올라가는 방법이 있고 과천에서 올라가는 방법이 있는데 서초구 쪽이 길은 훨씬 좋은 듯 하다. 나는 과천이 가까워서 과천쪽에서 올라갔다. 과천쪽에서 올라가려면, 대공원역에서 내린 후 서울대공원의 코끼리열차 다니는 길을 따라 등산로입구까지 가야하는데, 대공원역 기준 왼쪽에도 길이 있고 오른쪽에도 길이 있다. 오른쪽으로 가면 이수봉 등을 거쳐 매봉까지 가게 되고, 왼쪽으로 가면 더 빨라보여서 나는 왼쪽으로 갔다. 지도에 표시된 길을 따..

요즘은 오일러 도장깨기에 맛들렸다. 간혹가다 흥미로운 문제가 있다. 26번의 경우, 1/n을 소수로 나타냈을 때 반복되는 마디의 수를 구하는 것이 핵심이다. 나눗셈 과정을 역추적하면 이를 구할 수 있는데, 가령 1/14의 마디 수를 구하려면 1 % 14 = 1 10 % 14 = 10 100 % 14 = 2 20 % 14 = 6 60 % 14 = 4 40 % 14 = 12 120 % 14 = 8 80 % 14 = 10 반복되는 마디가 6개이므로, 마디의 길이는 6임을 알 수 있다. 하지만 이 방법을 사용하려면 각 나머지별로 출현했는지 여부를 저장해야 하므로, O(n)의 메모리 공간이 필요하다. 조금 더 좋은 방법이 있을까? 흥미로운 방법이 있는데, n자리가 반복되는 수는 모두 $\frac{x}{99...9..

3만원짜리 책을 한 권 사야한다. 내가 좋아하는 교보문고에서 사려다가, 결제 버튼을 누르기 직전에 CPT 스토어 생각이 났다. CPT(콘텐츠프로토콜토큰)은 내 기억에 올해 초쯤에 업비트에 상장된 코인인데, 왓챠에서 리뷰를 하는 사람과, 그 리뷰를 이용한 사람들이 공존하는 건전한 생태계를 만들겠다며 출시한 토큰이다. 왓챠에 리뷰를 남기면 지급되는데, 리뷰를 많이 남기고 그 리뷰가 많은 따봉을 받을수록 많이 지급되는 것으로 보인다. 최근에는 CPT 두 번째 보상이라고 해서, 설문조사를 하면 CPT가 지급되었다. 주목할 점은 6월쯤에 CPT 스토어라는 것이 개설되었는데, CPT를 이용해서 왓챠플레이 이용권, 메가박스 영화티켓, 알라딘 상품권, 심지어 전자기기까지 꽤 저렴한 가격에 구매할 수 있다. 코인을 비판..